CSSE 403 Course Notes

Table of Contents

1 Introduction

1.1 Introduction

1.1.1 What's the deal with programming languages?

Students who are evaluating Rose often ask me what programming languages I know

  • This is not a very good question
  • only partly because I "know" a lot of languages

If every language is Turing complete, are they really different?

  • Are they important to learn (in class at Rose)?

1.1.2 What's the deal with programming languages? (my answer)

Each language represents a paradigm - a unique approach to problem solving.

Using the language gets you into the "head" of the creator

  • as long as you try to do it the "right way"

Even when you're not using the language, the ideas remain

1.1.3 Activity (you'll need a piece of paper)

You know Java, C, and Python. They're pretty different languages. They all have libraries that can do almost anything you can imagine.

Working in groups of 3-5, try to list the main strengths and weaknesses of these languages (i.e. when should you use them, when should you not?). BUT as you come up with these, try to think of what characteristic of the language MAKE these strengths and weaknesses and write those too.

Put your names on the paper - you'll turn it in.

1.1.4 Your answers

  1. Java

    Support for paralellism Garbage collection Platform independent Detailed documentation

  2. Python


  3. C

    Low Level Not a lot of restrictions on things like memory Not completely platform independent

1.1.5 We'll do some weird languages in this class

  • Prolog
  • Erlang
  • Elm

1.2 Some important details

1.2.1 Call me Buffalo

Or Dr. Buffalo in a pinch Or whatever you want

Check out my personal website http://hewner.com for every imaginable kind of contact info (yes we can be facebook friends if you want but I don't post about classes). You can call my cell phone if you're having a problem.

1.2.2 Design of this class

Always a dream of mine to teach a class like this

  1. To teach you about some weird languages
  2. Why weird?
  3. To gain you practice and confidence learning languages on your own
  4. The process will involve a lot of google and a lot of coding
  5. It won't (for the most part) involve a lot of lecturing
  6. I am not an "expert" in the languages we will learn

1.2.3 Course Policies

You are obligated to read and understand the complete Course Policies document.

It is on Moodle.

I will touch on the highlights only.

1.2.4 Two stages in our learning

  1. One week of (reasonably intense) practice with a new language
  2. One week of work on a larger project

1.3 What you need to do today

  1. Install a unix environment on your laptop (recommended — you're responsible for your own environment)
  2. Install swi-prolog (link in the online quiz)
  3. Read chapter 4.1 and try out some of the examples
  4. Fill out the online quiz
  5. If you have time, feel free to look at the coding project due Wednesday night (or some other prolog projects of interest)

2 Prolog 1

2.1 Facts and implications

In prolog, you have a knowledge base of things that are facts:

food_type(cheddar,cheese). % Cheddar is a type of cheese
food_type(swiss,cheese). % Swiss is a type of cheese
food_type(oreo,cookie). % oreo is a type of cookie

flavor(sweet,cookie). % cookies are sweet
flavor(savory,cheese). % cheese is savory

And then you have implications:

food_flavor(FoodName,Flavor) :- food_type(FoodName,Type) , flavor(Flavor,Type).
% if a food is of some type, and that type has a flavor, then the food has the flavor

2.1.1 Let's see it in action!

2.1.2 Representation Activity

2.1.3 How does it work? Unification

2.2 Let's do some examples with lists

  1. replace_in_list - replaces one value with another
    replace_in_list(FromItem,ToItem,[FromItem|Tail],[ToItem|ResultTail]) :- replace_in_list(FromItem,ToItem,Tail,ResultTail).
    replace_in_list(FromItem,ToItem,[Item|Tail],[Item|ResultTail]) :-
        FromItem \= Item,
  2. is_a_member - is a particular value in a list
    is_a_member(Item,[_|T]) :- is_a_member(Item,T).
  3. duplicate_members - take a list and duplicate all it's elements
    duplicate_members([Head|Tail],[Head,Head|OtherTail]) :- duplicate_members(Tail,OtherTail).
  4. only_repeats - true if a list just contains the same element over and over
    all_equal(Item,[Item|T]) :- all_equal(Item,T).
    only_repeats(List) :- all_equal(_,List).

3 Prolog 2

A few details:

3.1 Never Not an Unbound Variable

Be really careful with negations in prolog. They don't always do what you expect.

And never do a not when one of the variables might not be bound.

isNotSeven(X) :-
    \+(X = Y),
    Y = 7.

3.2 Use is for calculations

plus2(X,Y) :-
    Y is X + 2.

Note that this does not do the smart thing with unbound variables.

If you use equals with operators you will create compound objects.

?- Y = A ^ B, B = C / D.
Y = A^ (C/D),
B = C/D

They can be unified, but only in the simple way.

3.3 Strings

?- X="test",Y='test'.
X = [116, 101, 115, 116],
Y = test.

?- string_codes(X,[116, 101, 115, 116]).
X = "test".

3.4 Cuts

listBind([63|T]) :- listBind(T), !. % the "!" is known as a cut
listBind([_|T]) :- listBind(T).

4 Prolog 3 - a bit on user input

Languages of an AI bent tend to skimp a bit when it comes to input and output. Prolog is no exception. Your basic input function is called get_char(X).

?- get_char(X), get_char(Y).
|: hello

X = h,
Y = e.

Note that this returns in essence a one character 'string' not a char code

There is also get_code(X) which will give you the character code.

4.1 Prolog input challenge

4.1.1 Write a function that takes in a prolog string (terminated with '\n')

?- get_string(X).
|: hello world.
X = "hello world." .

Hint: my solution used string_concat but I'm not sure it's the best way

  1. Solution (my super ugly version)
    get_string(String) :- get_string('','',String).
    get_string(PrevChar,CurrentString,String) :-
        string_concat(CurrentString, PrevChar, NewCurrent),
  2. Variation for atoms
    get_string(String) :- get_string('','',String).
    get_string(PrevChar,CurrentString,String) :-
        atom_concat(CurrentString, PrevChar, NewCurrent),
  3. A nice variation by michaea1@ that uses ;
    get_string(X) :- get_string_helper(Y), string_codes(X,Y).
    get_string_helper(X) :- get_code(Y), (Y = 10, X = []; get_string_helper(Z), X = [Y|Z]), !.
  4. A version from hansondg@

    This one needs one more step before it does the right thing, but other it's very classy

    get_string('\n',[]) :- !.
    get_string(Head,[Head|Result]) :- get_char(Char), get_string(Char,Result).
    get_string(Result) :-

4.1.2 Write a function that takes in a string, and returns a list of strings separated by spaces

?- get_words(X).
|: hello how are you

X = ["hello", "how", "are", "you"] .

% Even better - a list of atoms

?- get_words(X).
|: hello how are you

X = [hello, how, are, you] .

No solution for this one - too similar for what you need to do for the final prolog project

5 Erlang 1 - Very basics

5.1 Erlang variables & matching

5.1.1 You can't redefine variables

28>X = hello.
29> X = goodbye.
exception error: no match of right hand side value goodbye

5.1.2 You can do prolog-like matching

39> {Abc,2} = {1,2}.
40> Abc.
  1. but it only works one direction
    41>{1,2} = Xyz. 
    41> Xyz.
    2: variable 'Xyz' is unbound
  2. and things can't be in a partially bound state
    42>PartlyBound = {1,2,_}. 
    42> PartlyBound.
    2: variable 'PartlyBound' is unbound

5.1.3 Atoms, lists, tuples

atom % these built in "symbols" are very handy for parsing

Also some pretty neat primitives for mapping bit level stuff Useful when you want to conserve bandwidth, yet keep stuff expressive

5.2 List functions

List Comprehensions Many languages have some syntactical sugar for iterating over a list

for(int x : integers) {
  System.out.print(x + ",");

//As opposed to (approx java from memory here, forgive my mistakes)

Iterator<Integer> i = integers.getIterator();
while(i.hasNext()) {
   int x = i.next();
   System.out.print(x + ",");

But in languages with more functional feel, you obviously can be a lot cleaner (elisp):

(mapc (lambda (x) (print x)) '(1 2 3))

5.2.1 In languages where iteration is not special syntax, you often get a profusion of cool "iterator" functions

RUBY VERSIONS (DO NOT attempt to use on your homework):

#do something generic to each item
itemsToPrint.each {|item| puts item } 

#do an operation and make a new list with the results
doubled = items.collect {|item| item*2 }

# get a subset of the list where something is true
positives = items.select {|item| item > 0}

# get a subset of the list where something is false
no_zeros = items.reject {|item| item == 0} 

#check to see if every item in the list has a property
is_all_evens = items.all? {|item| item % 2 == 0}

In these languages, using these special iterator functions are generally much preferred to standard loops

5.3 Erlang versions

% Make anonymous functions like this:
PlusThree = fun(X) -> X + 3 end

% Then pass it to iterator function (of course you can do it on one line)
lists:map(PlusThree, [1,2,3]).
% produces [4,5,6]

foreach - just runs the function and returns the result map - runs the function and collects the results into a new list filter - keeps only those that return true any - returns true if one element returns true …and more (see your textbook & language docs)

5.3.1 Write a call using filter removes all empty strings from a list

length("foo") gets the length

5.3.2 Solution

lists:filter(fun(X)->length(X) > 0 end,["","","a","","b"]).

5.4 Most complicated foldl (and foldr)

Iterate through the list, keeping a running value Eg, run through the list and compute the sum

AddToSum = fun(Item,CurrentSum) -> Item + CurrentSum end.

The new result will become CurrentSum for the next iteration.

The final result is the overall result.

Only other trick is you must pass in an initial value.

SumList(List) ->

5.4.1 Write a function that returns the length of the largest string in a list of strings

0 for an empty list hint: max(1,2) returns the max of 2 ints

5.4.2 Solution

lists:foldl(fun(Item,Max)->max(Max,length(Item)) end,0,["a","bc",""]).

5.5 List Comprehensions

A interesting mix of map,filter,and just a bit of prolog

% Turn a list of items into a list of {item,item} tuples
Data = [1,2,3].
Lists = [ {X,X} || X <- Data ].

% As above, but filter in anything two or higher

Lists = [ {X,X} || X <- Data, X > 1].

% Largest of a pair tuple
Data = [{1,2},{4,3},{5,6}].
Lists = [ max(First,Second) || {First,Second} <- Data3].

% Do all possible combinations of a couple values
% ++ is list/string concat

[ X ++ Y || X <- ["super ","tiny "], Y <- ["ninja","pirate"] ].

5.5.1 List all values of A B C that make (A or B) and C true

hint: and or and not are boolean operators in erlang hint: output should be [{true,true,true},{true,false,true},{false,true,true}]

5.5.2 Solution

Vals = [true,false].
[{A,B,C}|| A <- Vals, B <- Vals, C <- Vals, (A or B) and C].

6 Erlang 2 - Basic Process

Spawning processes and communicating in erlang is easy!

Update your svn and look at ErlangSimpleCommunication Take a look at the code in example.erl. Then try to solve the problem is solveme.erl

My solution is in solvemeSolution.erl but don't peek!

7 Erlang 3 - Connecting to a remote erlang server

  1. ssh to remote server
    ssh erlang.csse.rose-hulman.edu

    Note: you have to use your CSSE AFS password, not your EIT password

  2. start erlang with a long name
    erl -name buffalo

    Note: your name should be UNIQUE

  3. start erlang on your local computer using your ip address
    erl -name buffalo@

    (Note: type what's my IP into google to find out what it is)

  4. get the magic cookie from your home computer
    (buffalo@> erlang:get_cookie().
  5. on the remote computer, set its magic cookie to the same thing

    Note: don't use BLAHBLAHBLAH, use whatever your magic cookie actually is

  6. ping your remote computer from your local computer

    Note: pong is good - pang is bad

  7. nl loads your code on all connected servers
    nl(solveme). % using the solveme example from last class
  8. You can spawn a process on a remote server like this
    RemotePid = spawn('buffalo@erlang.csse.rose-hulman.edu', fun    solveme_sol:part2_loop/0).
  9. You can see your process running on the remote server with i() (note this is on the REMOTE server)
    (buffalo@erlang.csse.rose-hulman.edu)6> i().
    TONS 'O STUFF followed by
    <0.46.0>              inet_tcp_dist:do_accept/6              610     3983    0
                          dist_util:con_loop/9                    11              
    <0.51.0>              net_kernel:spawn_func/6                233       15    0
                          solveme_sol:part2_loop/0                 1              
    <0.54.0>              net_kernel:spawn_func/6                233       15    0
                          solveme_sol:part2_loop/0                 1              
    Total                                                      47741   399330    0
  10. Send a message to your remote process in the usual way:
    (buffalo@> Foo9 ! {test1,2,0.7}.
    Starting test1 Part 2.      
    Finished test1 Part 2. (output: 0.7)

    Note that the output of the process is on the local computer, even if it is running on the remote server.

    If you want to see output on the executing server, use erlang:display. For example:

    spawn('buffalo@erlang.csse.rose-hulman.edu', fun() -> erlang:display("hello") end).
  11. If you have time, try to write a new function in the SimpleCommunication project that starts up both the spawned part1 processes and the part 2 loop on two different servers. Something

8 Erang 4 - Final Assignment, Synod/Paxos algorithm

You'll want to concentrate on the Synod portion of the paxos algorithm

Two references I reccommend:

https://distributedthoughts.wordpress.com/2013/09/30/understanding-paxos-part-2/ http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf (Section 2, in particular section 2.2)

8.1 A Note on the purpose of the synod algorithm

The purpose of the synod algorithm is to ensure consistency. That is, once a ballot is considered "successful", its value can never change (all future ballots will inevitably have the same value). This is a good thing because we can have confidence in the state of the system - even in a highly volitile environment where servers are constantly unable to communicate or crashing. We can have confidence, even when any individual server might go down at any time so there is no "master" server who coordinates or knows the state of the system.

8.2 Limits

The above consistency is true iff: a. Things keep their state, so that even if they crash or go offline the state is not lost. This is usually easily accomplished with judicious use of hard drives. We won't actually be doing this feature though (very hard to unit test if state cannot be changed after 1st test). b. The protocol is implemented correctly (no bugs) and malicious users do not start server instances designed to act differently or cause problems. c. Messages may be lost or duplicated, but their contents are not modified (generally pretty reliably true with modern networking).

b & c can actually be improved upon with more advanced versions of the protocol, but that will not concern us in this course. a is maybe more tricky than it sounds because hard drives are not perfectly reliable (and indeed can even corrupt data) BUT in actual practice this is rare enough and the synod algorithm is redundant enough that you can work around those issues.

9 Erlang 5 - Let it crash

9.1 Linking processes

This discussion comes partly from the very good explaination here: http://learnyousomeerlang.com/errors-and-processes#links

Use link to make one process terminate when another dies abnormally.

exits_with_error() ->

spawn_exits_with_error() ->
    Pid = spawn(fun exits_with_error/0),
    io:format("function exited normally~n").

% elsewhere...
10> linkexample:spawn_exits_with_error().
 exception exit: baderror

9.2 Trapping exits

Converts the exception to a message that can be handled.

trap_exits() ->
    process_flag(trap_exit, true),
    Pid = spawn(fun exits_with_error/0),
        Anything ->
            io:format("Got message: ~w~n",[Anything])
    io:format("function exited normally~n").

12> linkexample:trap_exits().
Got message: {'EXIT',<0.77.0>,baderror}
function exited normally

9.3 Let it crash

A famous phrase in erlang's philisophy.

Crashing is preferred to attempted error recovery because

  • it simplifies the code
  • it localizes error handling to the place where the most is known
  • even if you had robust error handling, you'd need to handle crashes anyway

9.3.1 Notes to myself

Just some notes to myself - not ready for primetime yet!


10 Erlang 6 - Just some minor logistics

  • Problems with Prolog final project
    • Check your grade and make sure it makes sense
    • If I couldn't get something to work, but it worked for you feel free to show me in class
    • If you have a more serious disagreement issue, let's address it outside of class (but we should address it!)
  • New improvements to the course website!
  • Plus Delta

11 Elm 1

11.1 Elm is a functional reactive web programming language

import Graphics.Element (..)
import Text (..)

main : Element
main =
  plainText "Hello, World!"

11.2 Pure Functional

addTwo : Int -> Int
addTwo num = num + 2

It is a relative of Haskell and therefore is pretty strictly pure functional. That is, we want our code to be functions (in the mathematical sense). We don't want any "side effects". Erlang was functional but it often had side effects - message sends and receives.

11.3 Has Strong Typing

addTwo : Int -> Int
addTwo num = num + 2

-- this gives a type error
main : Element
main =
  plainText (toString (addTwo 4.0))

11.3.1 But also has type inference

import Graphics.Element (..)
import Text (..)

addTwo : Int -> Int
addTwo a = a + 2

mikesInt : Int
mikesInt = 7

addTwoImplicit a = a + 2

-- this figures out the right thing
main : Element
main =
  asText [addTwoImplicit 3.1, 5]

-- BUT YOU CAN'T DO THIS: asText [addTwoImplicit 3.1, addTwo 3]

11.3.2 An aside: Functions are designed for partial evaluation

import Graphics.Element (..)
import Text (..)

-- read this as "an int produces a function that takes one int and produces an int"
add : Int -> Int -> Int
add a b = a + b

-- read this carefully
addTwo : Int -> Int
addTwo = add 2

main : Element
main =
  asText (addTwo 2)

11.3.3 Activity

Take the code below and change it so it adds the phrase "Buffalo says" before each bit of wisdom:

import Graphics.Element (..)
import String (append)
import List (map)
import Text (asText)

wisdom:List String
wisdom = ["Ninjas are cool","Do the riskest part first"]

--use append (takes two strings and appends them)
--use map (list version, applys a 1 param function to a list of strings)
--use partial function evaluation

main : Element
main =
  asText wisdom

11.3.4 Solution

import Graphics.Element (..)
import String (append)
import List (map)
import Text (asText)

wisdom:List String
wisdom = ["Ninjas are cool","Do the riskest part first"]

main : Element
main =
  asText (map (append "Buffalo says ") wisdom)

11.4 But more importantly, how do you handle INPUT in a pure functional language?

  • All the answers tend to revolve around separating pure functional/non-functional
  • Usually the nonfunctional part is provided by a MAGIC FRAMEWORK so you only write functional code
  • Elm's answer is SIGNALS
  • Signals are an ongoing stream of data
  • Your program becomes a (pure functional) transformation from input signals to output signals

Details here: http://elm-lang.org/learn/Using-Signals.elm

11.4.1 Example of signals

Mouse.position : Signal (Int,Int)
Window.dimensions : Signal (Int,Int)

11.4.2 Let's say we want to get a signal that is the aspect ratio

We transform one signal to another!

toAspectRatio : (Int,Int) -> Float
toAspectRatio (w,h) =
    toFloat w / toFloat h

aspectRatio : Signal Float
aspectRatio =
    map toAspectRatio Window.dimensions

11.4.3 And then our whole program becomes a transformation!

import Graphics.Element (..)
import Signal (Signal, map)
import Mouse
import Text (Text,asText)

-- note that this is just an ordinary function - no signals
positionToText : (Int,Int) -> Element
positionToText (x,y) =
   asText ("X is " ++ toString(x) ++ " Y is " ++ toString(y))

main : Signal Element
main =
  map positionToText Mouse.position

11.4.4 Activity

Write a elm program that makes a circle grow wider with the mouse x value

Hint: circle expects a radius as a float. Use toFloat to convert.

11.4.5 Solution

import Color (..)
import Graphics.Collage (..)
import Graphics.Element (..)
import Mouse
import Signal (Signal, map)
import Text (asText)
import Window

main : Signal Element
main =
  map scene Mouse.position

scene : (Int,Int) -> Element
scene (x,y)  =
      collage 1000 1000
        [ filled green (circle (toFloat x)) ]

11.4.6 Map2, Map3 etc.

The examples we've seen thus far involve 1 signal but you can easily do more than one. Just use map2 or map3 or whatever to mave functions that depend on many signals.

You'll need to use this for your homework

import Graphics.Element (..)
import Signal (Signal, map2)
import Mouse
import Text (Text,asText)

positionToText : (Int,Int) -> Bool -> Element
positionToText (x,y) isdown =
   asText (if isdown 
     then "X is " ++ toString(x) ++ " Y is " ++ toString(y)
     else "hold left button to show position")

main : Signal Element
main =
  map2 positionToText Mouse.position Mouse.isDown

12 Elm 2 - Signals and state

Being pure functional makes your life interesting. How do you represent state?

12.1 foldp definition

Give this function definition a good hard look

foldp : (a -> state -> state) -> state -> Signal a -> Signal state

Takes 3 parameters: a function, a state, and a signal

12.1.1 Details

Let's look at the first function:

  • It is a function that takes two parameters
  • The first parameter is of type a - I'll call that the input type
  • The send parameter is of type state
  • The function returns a value of type state

This is a state transformation function. You give it a current state, and some input. It returns a new state - based on what has changed.

The second parameter is the initial state of the system The third parameter is a signal which provides that input

Note that these are all generic types - they can be anything as long as they are consistent.

12.2 foldp explaination

So the foldp function basically lets you make a "stateful signal"

You write the first parameter function, that indicates how the state should change on inputs

Then you can use that "state" signal as inputs to other parts of your program. Generally, the main other part of your program will be something that takes the state as a parameter, and renders it to some form your users will understand and like.

12.3 An unrealistically small example: click counter

import Graphics.Element (..)
import Signal (Signal, map, foldp)
import Mouse
import Text (asText)

-- state in this system is represented by an int
clickStateUpdater : ignoredEventType -> Int -> Int
clickStateUpdater event currentClickState =
  -- the only even possible is a click, so we just increment
  currentClickState + 1

countClick : Signal Int
countClick =
  foldp clickStateUpdater 0 Mouse.clicks

main : Signal Element
main =
  map asText countClick

12.4 An example: the click competition program

We want to write a program that challenges folks to click as many times as they can in 2 seconds. It will keep track of how many clicks happened in this 2 second interval, plus the running high score.

12.4.1 Issue 1: Representing events

Instead of only one kind of thing that can happen in the old system, now there are 2 kinds of things: a click and a timeout indicating the 10 second interval is up.

We need to somehow represent this. We will use elm's built in Union Types.

type Event = Click Timeout

Look here for details: http://elm-lang.org/learn/Union-Types.elm

12.4.2 Issue 2: The state transition function

Ok, now that we can represent events, our transition function is pretty simple:

competeStateUpdater : Event -> (Int,Int) -> (Int,Int)
competeStateUpdater event (currentCount,highScore) =
  case event of
     Click -> (currentCount + 1, highScore)
     Timeout -> if currentCount > highScore then (0,currentCount) else (0,highScore)

12.4.3 Issue 3: Building an event stream

This code is not hard to understand if you understand map and merge, but I won't discuss it in detail. This takes the two signals Mouse.clicks and (every (2*seconds)) which generates an event every two seconds – and combines them into one signal, with the appropriate event types.

mergedSignal : Signal Event
mergedSignal = 
  let clickSignal = map (\event -> Click) Mouse.clicks
      timeoutSignal = map (\event -> Timeout) (Time.every (2*Time.second))
  in merge clickSignal timeoutSignal

12.4.4 Issue 4: Making that persistent state signal

countClick : Signal (Int,Int)
countClick =
  foldp competeStateUpdater (0,0) mergedSignal

Check the definition of foldp above to see what those parameters mean

12.4.5 Issue 5: Displaying the state in a nice way

So now we have a persistent state signal. Often, display is a simple as converting it to something graphical.

render : (Int,Int) -> Element
render (current,highScore) =
  asText ("Your score: " ++ toString current ++ " HighScore: " ++ toString highScore)

12.4.6 Done!

import Graphics.Element (..)
import Signal (Signal, map, foldp, merge)
import Mouse
import Text (asText)
import Time

type Event = Click | Timeout

competeStateUpdater : Event -> (Int,Int) -> (Int,Int)
competeStateUpdater event (currentCount,highScore) =
  case event of
     Click -> (currentCount + 1, highScore)
     Timeout -> if currentCount > highScore then (0,currentCount) else (0,highScore)
mergedSignal : Signal Event
mergedSignal = 
  let clickSignal = map (\event -> Click) Mouse.clicks
      timeoutSignal = map (\event -> Timeout) (Time.every (2*Time.second))
  in merge clickSignal timeoutSignal

countClick : Signal (Int,Int)
countClick =
  foldp competeStateUpdater (0,0) mergedSignal

render : (Int,Int) -> Element
render (current,highScore) =
  asText ("Your score: " ++ toString current ++ " HighScore: " ++ toString highScore)

main : Signal Element
main =
  map render countClick

12.5 Activity - Mouse Odometer

Write a elm program that displays a total mouse distance in pixels as you move the mouse around the webpage.

12.6 Solution

import Graphics.Element (..)
import Signal (Signal, map, foldp, merge)
import Mouse
import Text (asText)
import Time

-- using the manhattan distance because I am lazy
mouseStateUpdater : (Int,Int) -> ((Int,Int),Int) -> ((Int,Int),Int) 
mouseStateUpdater (curX,curY) ((oldX,oldY),dist) =
  let moved = abs(oldX - curX) + abs(oldY - curY)
  in ((curX,curY),dist+moved)

state : Signal ((Int,Int), Int)
state =
  foldp mouseStateUpdater ((0,0),0) Mouse.position

render : ((Int,Int),Int) -> Element
render ((x,y),distance) =
  asText distance

main : Signal Element
main =
  map render state

13 Elm 3 - A Bit on Records

13.1 Elm has a record type!

13.1.1 Creating

point2D = { x=0, y=0 }

point3D = { x=3, y=4, z=12 }

bill  = { name="Gates", age=57 }
steve = { name="Jobs" , age=56 }
larry = { name="Page" , age=39 }

13.1.2 You can use it to make "generic" functions

dist {x,y} = sqrt (x^2 + y^2)

13.1.3 You can update just one field, which makes updating state easier

{ point2D | y <- 1 }
{ point3D | x <- 0, y <- 0 }
{ steve | name <- "Wozniak" }

Note that I've occasionally discovered problems with strict typing and this, but type inference always seems to work correctly.

13.1.4 You can also use them to store functions and homebrew your own polymorphic objects

manhattanPoint = { x=3, y=4, distance a b = abs(a.x - b.x) + abs(a.y - b.y) }

Storing functions can definitely be useful. I'm a lot less sure about the polymorphic objects.

13.2 Creating a game

  • Inputs
  • Model (probably a record type)
  • Update
  • View

This can be a little tricky to do incrementally

14 Elm 4 - Functional Design

14.1 An Initial Example

An excerpt from the elm mario example

jump {y} m = if y > 0 && m.y == 0 then { m | vy <- 5 } else m
gravity t m = if m.y > 0 then { m | vy <- m.vy - t/4 } else m
physics t m = { m | x <- m.x + t*m.vx , y <- max 0 (m.y + t*m.vy) }
walk {x} m = { m | vx <- toFloat x
                 , dir <- if x < 0 then "left" else
                          if x > 0 then "right" else m.dir }

step (dt, keys) mario =
  physics dt (walk keys (gravity dt (jump keys mario)))

14.1.1 Some variations

--could also be written as
stepV2 (dt, keys) mario =
 |> jump keys
 |> gravity dt
 |> walk keys
 |> physics dt

--could also be written as 
-- >> is function composition
step (dt, keys) =
  jump keys >> gravity dt >> walk keys >> physics dt

14.2 Functional folks love this!

They're not alone either. This is the same pattern as unix pipes.

tail -f logFile.txt grep ERROR sed s/ERROR//

14.2.1 What is good about it?

  • Lots of things can be abstracted this way
  • Can add new steps very incrementally - difficult change existing steps
  • Total separation of concerns - including state
  • Centralizes control - a large part of the magic is in the flow
    • Which is maybe really hard to understand
    • But its in one place

14.2.2 What is bad about it?

  • Sometimes things are interdependent and cannot be "layered" correctly
  • Critical dependence on intermediate data format
  • User input, output, network communication don't fit this model directly

14.3 Let's talk about (idealized) OO paradigm

Objects that each have ownership over some data. They communicate to get the job done.

14.3.1 What is good about it?

  • Lots of things can be abstracted this way
  • Can add new in-object state/features very incrementally - difficult to change existing communication patterns
  • Separation of concerns - but you do have state
  • Natural modeling of "things" often makes it possible to guess where to find code
  • Distributes control
    • Oftentimes you have to guess where to look for stuff
    • But maybe you don't always care

14.3.2 What is bad about it

  • State becomes very complex quickly - can be very hard to test
  • Critical dependence on object relationships
  • Object relationships often hidden throughout the code

15 Elm 5 - Being Tricky With Functions

15.1 Course Logistics: Midterm grades

  • Grades are submitted but not quite correct
  • Prolog final projects will be graded by demo
  • Elm into assignments should also be done this week

15.2 Course Logistics: ElmVideoGame Posted

15.3 BulletExample

Take a look at the BulletExample.


See if you can understand how the code works. How is the bullet state being stored?

15.4 Using Functions to Store State

In nonfunctional languages there's a tendency to want to store stuff like enums or type data that must then be reused.

if(bulletType == straightBullet) {
   // move the bullet in a straightWay
if(bulletType == sineBullet) {
   // update the bullet like a sine wave

Or maybe you make different types of objects:

bullet.doUpdate(); //polymorphically do the right thing

But in a functional language - why store something as an object when you can store it as a partially evaluated function? Read this code carefully!

type BUpdater = BUpdater (Float,Float) (Float -> BUpdater) 

straightBulletUpdate : Float -> Float -> Float -> BUpdater
straightBulletUpdate x y delta =
    let newX = x + delta*4
        newY = y
    in BUpdater (newX, newY) (straightBulletUpdate newX newY)

We can even use the function to encode arbitrary mutable state:

sineBulletCreate x y =
    sineBulletUpdate (x+10) y (x+10) y 0

sineBulletUpdate x y initialX initialY delta =
    let newX = x + delta*3
        deltaX = newX - initialX
        newY = initialY + 50*sin (deltaX/15)
    in BUpdater (newX, newY) (sineBulletUpdate newX newY initialX initialY)

15.5 Using functions to be a state machine

Oftentimes we want to model state machines with different states (and frequently a big complex case statement). But if our states are functions, doing the right thing is just the same as executing the functions. And changing state is just changing the function we're partially evaluating.

mineBulletUpdate x targetX y delta = 
    let newX = x - delta*4
        newY = y
    in if(x > targetX) then
           BUpdater (newX, newY) (mineBulletUpdate newX targetX newY)
           doNothingUpdate newX newY delta

doNothingUpdate x y delta = BUpdater (x,y) (doNothingUpdate x y)

You'll have to change the step function to see this code in action.

16 Elm 6 - By Popular Request: Randomness


  1. Create a generator object
  2. Create an initial seed
  3. Every call to random will generate a number and a new seed
  4. Store that new seed and pass it to later calls to generator

16.1 Example

import Graphics.Element (..)
import Signal (Signal, map, foldp)
import Mouse
import Text (asText)
import Random (..)

intRand : Generator Int
intRand = int 1 100

main : Signal Element
main =
  map displayRandom countClick

makeRandom: () -> (Int, Seed) -> (Int,Seed)
makeRandom event (ignored,seed) =
  generate intRand seed

displayRandom: (Int, Seed) -> Element
displayRandom (num, ignored) =
  asText ("Random number is " ++ (toString num))

countClick : Signal (Int, Seed)
countClick =
  foldp makeRandom (generate intRand (initialSeed 2)) Mouse.clicks

16.2 Problem: Initial seed is not random

Better make your seed initially depend on a clock or something

BUT this can make the initial state dicey.

import Graphics.Element (..)
import Signal (Signal, map, foldp, sampleOn)
import Mouse
import Text (asText)
import Random (..)
import Time

type State = State (Int, Seed) | NonInit

intRand : Generator Int
intRand = int 1 100

main : Signal Element
main =
  map displayRandom countClick

timeOnClick = sampleOn Mouse.clicks (Time.every Time.second)

makeRandom: Float -> State -> State
makeRandom time state =
  case state of
  NonInit -> State (generate intRand (initialSeed (floor time)))
  State (_,seed) -> State (generate intRand seed)

displayRandom: State -> Element
displayRandom state =
  case state of 
    NonInit -> asText "Not initalized"
    State (num,ignored) -> asText ("Random number is " ++ (toString num))

countClick : Signal State
countClick =
  foldp makeRandom NonInit timeOnClick

17 Instructor's Choice 1: Haskell and Monads

From the very good and detailed chapters on Monads here: http://learnyouahaskell.com/chapters

17.1 The idea

17.1.1 Oftentimes we have "almost" pure functions

coolAdd : Int -> Int -> Int                           
coolAdd a b = a + b                                   
{- I sure wish I could log that this was happening! -}

17.1.2 Of course, we can always add return values!

coolAddLog : Int -> Int -> (Int,String)                           
coolAddLog a b = (a + b,"added 2 numbers")

17.1.3 But the problem is nobody has time for that!

add3: Int -> Int -> Int -> Int
add3 a b c = coolAdd c (coolAdd a b)

add3Log: Int -> Int -> Int -> (Int,List String)
add3Log a b c = 
  let (sum1, log1) = coolAddLog a b
      (sum2, log2) = coolAddLog sum1 c
  in (sum2, [log1,log2])

17.1.4 Why does this seem annoying?

The issue is that coolAddLog actually conceptually does 2 things:

  1. Return a value like a function
  2. Edit a "context" - in this case the log

17.1.5 But the context is screwing us up!

  1. Dealing with a context shouldn't greatly uglify our code
  2. It should also be handled in a consistent way that callers can't screw up!

17.1.6 Here's what (we think) we want!

coolAddLog : Int -> Int -> (Int,String)
coolAddLog a b = 
    magicallyLog "added 2 numbers";
    a + b

Goodbye sweet pure functional correctness! :(

17.2 Monads

Note that I play somewhat fast and loose with the syntax here. The LoggedValue class I use is purely hypothetical and I switch to Haskell about 50% of the way down.

17.2.1 Monadic type = value with some context

coolAddLog : Int -> Int -> LoggedValue Int
coolSubtractLog : Int -> Int -> LoggedValue Int
coolNegateLog : Int -> LoggedValue Int

They'll all take ordinary functions but they'll return functions with some interesting context.

17.2.2 Let's combine the functions with some crazy operator!

coolAddLog 3 4 >>= coolSubtractLog 7 5 >>= coolNegate 8

The >>= could handle evaluating both sides and concating the results of the logs right?

17.2.3 Except what if we needed to use the value in a subsequent step?

So the second value actually needs to be a function taking a parameter of the regular result of the first function.

coolAddLog 3 4 >>= (\result1 -> coolSubtractLog 3 result1 >>= (\result2 -> coolNegate result2))

BTW, pause for a minute and reflect on those parenthesized functions. There's nothing strange going on here.

17.2.4 In Haskell, this can be improved with some syntactic sugar

foo :: LoggedValue Int
foo = do
    result1 <- coolAddLog 3 4
    result2 <- coolSubtractLog 3 result1
    coolNegate result2

Just keep in mind what is actually happening here.

  1. Eval coolAddLog 3 4
  2. Eval (result of that >>= a big anonymous function)
  3. As part of that eval, we pass 7 to said big anonymous function
  4. That causes Eval coolSubtract 3 7
  5. Eval (result of 2b >>= a smaller anonymous function)


  1. Eventually the result returns to the eval on line #2 - it's a LoggedValue
  2. The result of that eval #2 will be a LoggedValue with a value equal to the result of the anonymous function call and a log equal to the result of the anonymous function call PLUS the log from the result of #1
  3. That's what the function as a whole returns

17.3 An Example: The Maybe Monad

17.3.1 What is Maybe?

data Maybe a = Nothing | Just a

It's a type that can either contain a value or be Nothing. You use it when you want to have a value that might be "null".

17.3.2 Why do we want it to be a monad?

In short it is annoying in a long calculation

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =
  case mx of
    Nothing -> Nothing
    Just x  -> case my of
                 Nothing -> Nothing
                 Just y  -> Just (x + y)

Once something is Nothing, the overall result of the calculation is Nothing.

17.3.3 Surely we can fix it in a complicated way!

Our functions will be of the form (or similar):

normalFunction :: Int -> Maybe Int

So our concat should act something like this:

applyMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b  
applyMaybe Nothing f  = Nothing  
applyMaybe (Just x) f = f x

17.3.4 Using Haskell's fancy operator form

instance Monad Maybe where  
    return x = Just x  
    Nothing >>= f = Nothing  
    Just x >>= f  = f x  
    fail _ = Nothing

17.3.5 What's the deal with return

The return function is just a way of making a monadic value out of an ordinary value. So in Maybe it just is "Just". So calculation might look like:

sum a b = return (a + b) --equivalent to Just (a + b)

For our hypothetical logger, it would look like this

coolAdd a b = return (a + b) "adding two numbers"

17.3.6 Maybe Monad In Action

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my = do
  x <- mx
  y <- my
  return (x + y)

17.4 Doing IO with Monads

There is something called the IO Monad.

main = do  
    foo <- putStrLn "Hello, what's your name?"  
    name <- getLine  
    putStrLn ("Hey " ++ name ++ ", you rock!")

17.4.1 The IO Monad prevents your code from being "tainted"

All IO functions return types appropriate to the IO Monad.

getLine :: IO String putStrLn :: String -> IO ()

As a result, they are not compatible with normal values.

nameTag = "Hello, my name is " ++ getLine

(This is an attempt to concat a String and a IO String - not legal)

17.4.2 You can only extract the info within a IO operation

This means the IO monad "infects" all code that depends on IO.

nameTag :: IO String
nameTag = do
    name <- getLine
    return ("Hello my name is " ++ name)

This function can never return a type string. Because it must necessarily be the output of a IO typed do. Or it won't be able to actually read the value out of the IO String from getLine.

17.4.3 This encourages just one "main" function that depends on IO

And pure functions for the rest

nameTagForString :: String -> String
nameTagForString name = "Hello my name is " ++ name

main :: IO ()
main = do
    putStrLn "Welcome to Haskell!"
    name <- getLine
    putStrLn (nameTagForString name)

17.4.4 Can getLine really be a pure function?

Yes! remember what the do syntax actually means

main = do
    name <- getLine
    putStrLn name
main = getLine >>= (\name -> putStrLn name)

Now what's going on in >>=…that's a dark mystery.

17.5 Many other Monads

The cool thing about Monads is not that Haskell found a weird way to sneak IO into a pure functional language. It's that you can use this idea of (pure function + context) to do a lot of interesting stuff.

17.5.1 List

The standard list is Haskell uses monads to act like nondetermininstic computation.

listOfTuples :: [(Int,Char)]  
listOfTuples = do  
    n <- [1,2]  
    ch <- ['a','b']  
    return (n,ch)  

---outputs [(1,'a'),(1,'b'),(2,'a'),(2,'b')]

17.5.2 Writer

Works a lot like the log example I mentioned above.

import Control.Monad.Writer  

logNumber :: Int -> Writer [String] Int  
logNumber x = Writer (x, ["Got number: " ++ show x])  

multWithLog :: Writer [String] Int  
multWithLog = do  
    a <- logNumber 3  
    b <- logNumber 5  
    return (a*b)

You can also use it to sum interegers – basically anything that aggregates values of a certian sort.

17.5.3 State

Yep - have a modifiable state, using a type of your choice

import Control.Monad.State  

pop :: State Stack Int  
pop = State $ \(x:xs) -> (x,xs)  

push :: Int -> State Stack ()  
push a = State $ \xs -> ((),a:xs)  

stackManip :: State Stack Int  
stackManip = do  
    push 3  
    a <- pop  

18 Instructor's Choice 2: Writing our own monads

18.1 An example from me

Here's one a made up. Its an exception type. It works a lot like maybe except that when a problem is discovered you include a string. Then, if you want you can provide a default value and it will error and use the default value henceforth:

Note that this duplicates the functionality of various existing monads…but it's a good exercise.

data BuffaloException a = Normal a | Exception String

instance Monad BuffaloException where  
    return x = Normal x
    Exception s >>= f = Exception s
    Normal x >>= f = f x

attemptDivide :: Int -> Int -> BuffaloException Int
attemptDivide x 0 = Exception "divide by 0"
attemptDivide x y = Normal (div x y)

attemptAdd ::  Int -> Int -> BuffaloException Int
attemptAdd x y = Normal (x + y)

onErrorUseDefault :: a -> BuffaloException a  -> IO a
onErrorUseDefault defaultVal result =
    case result of
        Normal val -> return val
        Exception s -> do 
            putStrLn ("ERROR: " ++ s)
            return defaultVal

-- | The main entry point.
main :: IO ()
main = do
    valueToPrint <- onErrorUseDefault 0 (do
        result1 <- attemptAdd 3  (-3)
        attemptDivide 100 result1)
    putStrLn (show valueToPrint)

Try this by making a new project in this online haskell environment:


18.2 An example for you to do

Imagine you're participating in a programming golf competition. Generally, the idea of this kind of thing is to solve a problem using minimal code size (# of characters). But in this one, we have a limited set of functions each which has a given cost (e.g. calling map costs 2 points, calling + costs 1, etc). The game is to solve the problem with minimal cost.

Your goal is to write a monad that sums the cost of each called function. You'll only be calling your special monadic functions that return their individual costs.

Set up you main to have a do, then print both the result of your function plus the total cost.

If you'd like to see an additional example to help you, look here:


18.2.1 My solution (no peeking!)

-- | Main entry point to the application.
module Main where

newtype GolfScore a = GolfScore { getGolfScore :: (Int,a) } deriving Show

instance Monad GolfScore where  
    return x = GolfScore (0,x)  
    m >>= f = let GolfScore (score1, val) = m
                  GolfScore (score2, val2) = f val
              in GolfScore (score1 + score2, val2) 

doAdd a b = GolfScore (1, a + b)
doDivide a b = GolfScore (2, a / b)

testGolfScore =
        val1 <- doAdd 1 5
        doDivide 36 val1

-- | The main entry point.
main :: IO ()
main = do
    putStrLn (show testGolfScore)

19 Instructor's Choice 3: Self and Prototype Based OO

Getting self successfully running proved difficult so we're going to have to handle this in the abstract.

This is based on this paper:


19.1 Classes and Inheritance

  1. Classes and objects are not the same thing
  2. No single unifying principle behind object inheritance (e.g. you don't inherit constructors - why?)
  3. Things like interfaces and abstract classes further complicate matters

19.1.1 Multiple inheritance gets pretty weird

In particular with inheritance diamonds. Two problems:

  1. Which methods will be used when not overridden
  2. One or two copies of doubly inherited instance variables

19.2 Prototypes

  1. No type checking
  2. No classes
  3. Objects are sort of like untyped key-value stores
  4. Instead of being constructed from classes objects are manually created by adding and setting "slots", then cloned
  5. Slots can contain methods or data (and indeed you can replace data with no-parameter methods transparently)
  6. You can define a special kind of "parent slot" that makes unimplemented messages "forward" to that slot. This is called "object inheritance"

19.3 How to implement the basics

19.3.1 "Class" vs "Instance"

Two parts of a class - the traits and the prototype (you could get by with just one, but you probably want two)

Parent slot of the prototype is set to trait

You can think of this as the "static" vs "non-static" parts of a class.

As with classes - you can modify the traits to modify the object definition and all instances will inherit the effect.

See figure 1a

Sometimes you can get by with only 1 of these:

  1. Abstract classes with no variables
  2. Singleton objects (nil, true, etc.)
  3. Basically function repos (java.Math)

19.3.2 Inheritance is trait object parents

If you give a trait object a parent, that object becomes your "superclass". You don't inherit any instance variables though – but you can if you want to by making the prototype your "subclasses" parent as well. (BTW, you can have more than one parent slot)

See 2b and 3

This apparently also allows you to get around the difficulty of multiple inheritance duplicate variables - though it's unclear how disambiguation works.

19.3.3 What if you want multiple representations?

Abstract superclass in class orientations

In prototypes you can just not inherit the representation itself

19.3.4 What do you think?

Prototypes: are prototypes a better abstraction that classes? Discuss.

19.4 Dynamic Inheritance

Let's think about this:

We've got a object/class with some data. The object can be in one of 3 states. Depending on that state, many of the methods of the object ought to change behavior. In a classic OO language how do you handle this?

19.4.1 Prototype Solution

Change your class dynamically - it's a simple as modifying your parent.

Figure 5

19.5 Using Objects to Store and Categorize

Oftentimes you want to categorize things - like functions. Consider java Math for example. Wouldn't it be nice to maybe group things - put sine and cosine etc. into a separate part? But then it'd be annoying to remember what class they're in! You'd have to call AngularFunctions.sine or whatever.

Using object inheritance, we can divide as much as we wish for conceptual reasons, yet keep the namespaces as universal (or segregated) as we wish.

Figures 6 and 7

20 Instructor's Choice 4: Smalltalk 1

What to do:

  1. Download Pharo

    Their website (http://pharo.org/) was down as of this morning but you can get the windows version from Moodle. Also download the Pharo by Example pdf (on Moodle).

    Looks like the files on http://old.pharo-project.org/home work.

  2. Start up Pharo and run through the little programmatic tutorial included with it.
  3. Then do the tutorial in sections 2.1 - 2.9 of the PbE book. The book is just a bit outdated – here's a few hints:
    • What they call the Class Browser is the System Browser
    • Return in smalltalk is ^. It looks like a up arrow in their code examples but in my version it just looks like a ^. Still works though.
    • Alt shift click appears to meta click
    • Cut and pasting mostly works, though you have to edit out the line numbers. However, minus signs don't get translated correctly. You'll have to manually replace them.

21 Instructor's Choice 5: Smalltalk, The Image

21.1 What's going on with Smalltak

  • When you create a class?
  • When you save?

21.2 What is the image?

It's a binary file representing a system "memory state".

So in a language with an interactive interpreter (e.g. python, prolog, erlang) - imagine you could call a command that would output the state of the system. Then on a later run you could input that in and all your objects would be recreated, all your variables would be set to their old values, etc.

21.2.1 Sounds neat, but not really that important

In Smalltalk, 99% of the language is implemented in the image. Objects only has the methods they have because of the of the state of the Object Class object that lives in the image. There's no secret separate file that says what Object can do - literally the binary version in the image is the only version of Object there is.

Even the compiler for Smalltalk is implemented as classes in the image. So you can actually change the way all code compiles by editing objects in the image.

21.2.2 This seems crazy

This allows Smalltalk to be very "purely" object oriented. All operations are implemented in terms of objects. Creating an instance is just telling a Class object to make a new object and give it to you. Creating a new class is just telling some object to do the right thing. And you can inspect and modify the way any of this works.

21.2.3 How do you create an image?

You don't - unless you really want to get involved in heavy sorcery. Mostly you take an existing image and modify it with very fancy scripts to be what you want.

21.2.4 How do you share code if it's trapped in an image?

Smalltalk has a method of "fileing out" a particular class or set of classes - basically building a script that will add a class to an existing system or change things from one version to another. Sometimes you need to augment your fileout with some added code that will add globals you care about or whatever.

21.3 Why is an image good?

Basically it gives you an enhanced programming environment with richer things than files.

21.3.1 I like files! You wouldn't believe how good I am at vi. Plus all my tools like git operate on files.

I am giving this presentation from emacs so you know I sympathize. But text has some disadvantages:

  • It is not the "true" form of our code, and reconstructing that true form is extremely error prone for tools (e.g. autocomplete)
  • There is power in a textual representation (think latex) but sometimes other representations are more convenient (think Word)
  • A single file is part of larger code universe, but that universe is invisible except during the build process

21.3.2 An example

Say you wanted to - say - get an email everytime a particular method in a particular class is updated. How would you do that?

21.3.3 A programmatic programming environment gives you greater power

  1. You can utilize the same structures the compiler uses

    You know what methods classes have, you can access the abstract syntax trees that the parser makes directly. You can even augment classes with additional data.

    There is no danger that some critical part of the process (e.g. makefiles, preprocessing) might be doing something strange and this will make your tools work on bad input. (contrast C++ autocompletion)

    You could do this before, of course, but you could never be sure that you were doing it right.

  2. You can change the way editing happens!

    To pure text, or text + some visual form, or to whatever you want. And each form can edit something that's a lot more natural than a raw string.

    You could do this before, of course, but you always had to convert to text. And because text was the first class citizen - it always had to make sense in a textual world first. For example, you know how you can have a "string constant"? Why can't you have an "image constant"?

  3. Your tools can easily act on the entire codebase

    Or at least this entire particular product or project. This makes large scale changes a lot more possible.

21.4 Some examples

21.4.1 A demo

http://vimeo.com/97315968 start at 37:33

21.4.2 The refactoring browser

"We originally thought that the lack of static type-checking would make it hard to build a refactoring browser for Smalltalk. Lack of type information is a disadvantage, but the advantages of Smalltalk made it a lot easier to make a refactoring browser for Smalltalk than it would have have been for C++ or Java."

  • Ralph Johnson

A very approximate chronology: 1992 - First papers describing refactoring published 1997 - Refactoring Browser built, by two graduate students 2001 - First refactoring IDE for Java I can find IntelliJ IDEA 2002? - Eclipse (IBM spent about $40 million on this)

22 Instructor's Choice 6: Lua and C Integration

Lua is a language that has a lot going for it.

  • No strong typing
  • Very understandable & not too many special constructs
  • First class functions
  • Prototype based inheritance (similar to self) and some syntactic sugar

22.1 But probably its neatest feature is that is designed to be embedded

…in other languages (specifically C).

22.1.1 An Example

From the nice tutorial here: http://www.troubleshooters.com/codecorn/lua/lua_c_calls_lua.htm

lua_State *L;

L = luaL_newstate();                        /* Create Lua state variable */
luaL_openlibs(L);                           /* Load Lua libraries */

if (luaL_loadfile(L, "callfuncscript.lua")) /* Load but don't run the Lua script */
    bail(L, "luaL_loadfile() failed");      /* Error out if file can't be read */

if (lua_pcall(L, 0, 0, 0))                  /* Run lua like a script, defining 
                                               functions and variables */
    bail(L, "lua_pcall() failed");          /* Error out if Lua file has an error */

lua_getglobal(L, "tellme");                 /* Tell it to run callfuncscript.lua->tellme() */
if (lua_pcall(L, 0, 0, 0))                  /* Run the function */
    bail(L, "lua_pcall() failed");          /* Error out if Lua file has an error */

lua_close(L);                               /* Clean up, free the Lua state var */

22.1.2 Communication between lua and C is stack based

lua_getglobal(L, "square");                 /* Tell it to run callfuncscript.lua->square() */
lua_pushnumber(L, 6);                       /* Submit 6 as the argument to square() */
if (lua_pcall(L, 1, 1, 0))                  /* Run function, !!! NRETURN=1 !!! */
    bail(L, "lua_pcall() failed"); 

printf("Back in C again\n");
int mynumber = lua_tonumber(L, -1);
printf("Returned number=%d\n", mynumber);

22.2 Now you try

  1. If you've got lua and C installed on your local system, you can try to just use it directly. Otherwise you can ssh to erlang.csse.rose-hulman.edu and do your work there.
  2. checkout the code from your svn repo
    svn co http://svn.csse.rose-hulman.edu/repos/csse403-201520-YOURNETID/LuaCIntegration
  3. First compile luatry2.c

    This is the tricky one. On an ubuntu installation, this seemed to work:

    gcc luatry2.c -I/usr/include/lua5.2 -llua5.2 -o luatry2

    On my personal arch installation, this worked:

    gcc  -llua luatry2.c -o luatry2

    Moral of the story - getting building happening correctly is always the tricky part of language embedding.

  4. Run it like this
  5. Understand how that code works
  6. Move on to the pcr_competition activity

22.2.1 The Paper Scissors Rock Competition Activity

Imagine we want to have a AI programming competition. Everybody's going to write an AI that plays paper scissors rock, and then they will compete.

There's a couple ways to do this, but one of the easiest is with an embedded language. Contestants will write their code in Lua. Then we'll have a C contest runner that loads 2 lua solutions in 2 different lua "universes" and then has them compete.

The only function contestants will need to write is doRound which takes a parameter of what the opponent played in the last round. The contestants can use lua to have any amount of complicated variables, classes, etc. In terms of interacting with the external world though, they will only have the lua functions we specifically enable. I've got 2 example players included with your codebase (p1.lua, p2.lua).

Code is already written for actually running the competition in pcr_runner - you just have to add the integration with lua.

How my solution runs:

./pcr_runner p1.lua p2.lua 3

Welcome to the paper scissors rock competition runner

Always rock initalized
Mirror initalized
Number of rounds: 3
P1=rock P2=paper.  Player 2 wins.
P1=rock P2=rock.  Tie.
P1=rock P2=rock.  Tie.
Final Score: P1: 0 P2: 1 Ties: 2

22.2.2 My Solution (no peeking)

#include <lua.h>                                
#include <lauxlib.h>                            
#include <lualib.h>                             

#include <stdlib.h>                             
#include <stdio.h>                              

const int INITIAL_PLAY = 0;
const int PAPER = 1;
const int SCISSORS = 2;
const int ROCK = 3;

void bail(lua_State *L, char *msg){
        fprintf(stderr, "\nFATAL ERROR:\n  %s: %s\n\n",
                msg, lua_tostring(L, -1));

int whoWins(int p1Choice, int p2Choice) {
    if(p1Choice == p2Choice) return 0;
    if(p1Choice == PAPER && p2Choice == ROCK) return 1;
    if(p1Choice == SCISSORS && p2Choice == PAPER) return 1;
    if(p1Choice == ROCK && p2Choice == SCISSORS) return 1;
    return 2;

char* toString(int play) {
    switch (play) {
        case 1:
            return "paper";
        case 2:
            return "scissors";
        case 3:
            return "rock";
            return "illegal move";

lua_State* setupPlayer(char* file) {
    lua_State *L;

    L = luaL_newstate();                        

    if (luaL_loadfile(L, file)) 
        bail(L, "luaL_loadfile() failed");      

    if (lua_pcall(L, 0, 0, 0))                  
        bail(L, "lua_pcall() failed");
    return L;

int callFunction(lua_State* L, int previous) {
    lua_getglobal(L, "doRound");
    lua_pushnumber(L, previous);
    if (lua_pcall(L, 1, 1, 0))  
        bail(L, "lua_pcall() failed"); 
    return lua_tonumber(L, -1);
int main(int argc, char *argv[])

    printf("Welcome to the paper scissors rock competition runner\n\n");

    if(argc < 3) {
        printf("Usage: pcr_runner PLAYER1CODE PLAYER2CODE ROUNDS\n");

    lua_State *p1State, *p2State;
    p1State = setupPlayer(argv[1]);
    p2State = setupPlayer(argv[2]);

    int numRounds = atoi(argv[3]);
    printf("Number of rounds: %d\n",numRounds);

    int i;
    int lastP1 = INITIAL_PLAY;
    int lastP2 = INITIAL_PLAY;
    int wins[] = {0,0,0};
    for(i = 0; i < numRounds; i++) {
        int newP1 = callFunction(p1State,lastP2);
        lastP2 = callFunction(p2State,lastP1);
        lastP1 = newP1;
        int winner = whoWins(lastP1,lastP2);
        if(winner == 0)
            printf("P1=%s P2=%s.  Tie.\n",toString(lastP1), toString(lastP2));
            printf("P1=%s P2=%s.  Player %d wins.\n",toString(lastP1), toString(lastP2),winner);
    printf("Final Score: P1: %d P2: %d Ties: %d\n",wins[1],wins[2],wins[0]);
    return 0;

22.3 Why do we want an embedded programming language?

  • To always code extensions in a "safe" environment where we strictly control interaction with our systems
  • To write configuration files that might get really fancy
  • Works great! Just don't write the language yourself!

23 Instructor's Choice 7: A Fun Day, Inform7

Logistical note: No class Monday

23.1 Programming for Nonprogrammers

What is hard about programming?

  • Reading/writing the language
  • Don't get good feedback about what's going on
  • Structuring solutions in a systematic way
  • Too difficult to do something interesting

23.2 Many solutions have been developed

  • Smalltalk is one (programmers tend to think really "simple" languages will be easy to learn - not really so)
  • Others have argued that other languages might be better - e.g. Prolog, Scheme
  • Visual languages like Scratch (http://scratch.mit.edu/projects/editor/?tip_bar=getStarted)
  • Sometimes non-programmers will appropriate languages for their own devices (e.g. spreadsheets, Javascript in Photoshop)

23.3 Inform7

The iron-barred gate is a door. "An iron-barred gate leads [gate direction]." It is north of the Drawbridge and south of the Entrance Hall. It is closed and openable. Before entering the castle, try entering the gate instead. Before going inside in the Drawbridge, try going north instead. Understand "door" as the gate.

After opening the gate:

say "You shouldn't be able to open it, heavy as it is, but it swings aside lightly at your touch. The Beast said that it knows friend from enemy; and the castle, at least, still regards you as friend."

23.3.1 What do I like about Inform?

  • Really unique
  • Not trying to teach anything - just is what it is
  • A pleasure to play with

23.3.2 It is an extendable, fully powerful language

A thing has some text called scent. The scent of a thing is usually "nothing".

The block smelling rule is not listed in any rulebook.

Carry out smelling something:

say "From [the noun] you smell [scent of the noun]."

Instead of smelling a room:

if a scented thing can be touched by the player, say "You smell [the list of scented things which can be touched by the player].";

otherwise say "The place is blissfully odorless."

Definition: a thing is scented if the scent of it is not "nothing".

Before printing the name of something scented while smelling a room: say "[scent] from the "

But building your own extensions gets a little programmy

23.4 A fun day

So today (being the last day of instructor choice) is a fun day. Today if you wish you can work on:

  • Finishing your Monad in Haskell
  • Finishing the tutorial in Smalltalk (or heading deeper into the book if you wish)
  • Finishing your PSR competitor in C/Lua (or writing more sophisticated PSR players in Lua)
  • Making a text adventure game with Inform7
  • Working with your group on your presentation or project

I'm here to consult on educational approach for that last one if you wish.

Author: Buffalo

Created: 2015-02-05 Thu 16:42

Emacs 24.4.1 (Org mode 8.2.10)