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.1.4.1 Java
  • super object oriented & strict
  • garbage collected
1.1.4.2 Python
  • simplified syntax
  • can be fast in some applications
  • weakly typed - aids development speed in the short term
  • scripting
1.1.4.3 C
  • direct access to raw memory
  • similar to "the hardware"

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. Maybe 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.1.1 Buffalo's in class example notes
likes(buffalo, ninjas).
likes(buffalo, videogames).
% do an example with likes prolog filling in stuff

% get an example from the class
% find somebody who also likes video games
likes(steveo, running).
likes(alice, videogames).

% then make a implication
likes(buffalo,X) :- likes(X,videogames).
likes(alice,X) :- likes(X,videogames), likes(X,ninjas).
% how does this work?  Unification.

example(ninja,pirate,robot).
example(zombie,dino,alien).
example(X,Y,Z) :- example(Y,X,Z). % note that this causes an infinite loop

2.1.2 How does it work? Unification

2.1.3 Representation Activity

Adapted from Programming in Prolog, Clocksin & Mellish 5th ed.

% Suppose someone has already defined the following prolog relationships:

male(X) /* x is male */
female(X) /* x is female */
parent(X,Y) /* X is a parent of Y */
dif(X,Y) /* X and Y are different - this one is built in*/

% Write prolog code to define the following other relationships

is_mother(X) /* for people who are mothers */
grandpa_of(X,Y) /* X is a granfather of Y */
half_sister_of(X,Y) :- /* X is a half-sister of Y */

% Try it out in your prolog intepreter and make sure it works!

2.2 Let's do some examples with lists

2.2.0.1 replace_in_list - replaces one value with another
replace_in_list(_,_,[],[]).
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,
    replace_in_list(FromItem,ToItem,Tail,ResultTail).
2.2.0.2 is_a_member - is a particular value in a list
is_a_member(Item,[Item|_]).
is_a_member(Item,[_|T]) :- is_a_member(Item,T).
2.2.0.3 duplicate_members - take a list and duplicate all its elements
duplicate_members([],[]).
duplicate_members([Head|Tail],[Head,Head|OtherTail]) :- duplicate_members(Tail,OtherTail).
2.2.0.4 only_repeats - true if a list just contains the same element over and over
all_equal(_,[]).
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 if the operators match perfectly.

3.3 Strings

3.3.1 Not necessarily consistent! Last year's way

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


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

3.3.2 I reccommend: always single quotes and atom_chars

?- atom_chars('hello', [H|T]).
H = h,
T = [e, l, l, o].

Note that not all prolog functions can handle unbound variables. But really, what do you expect?

?- atom_chars(Y,[h,i]).
Y = hi.

?- atom_chars(Y,[h,_]).
ERROR: atom_chars/2: Arguments are not sufficiently instantiated

3.4 Cuts

3.4.1 Challenge:

Define a predicate

max(A,B,C) where C is the max of A and B.

3.4.2 Now lets read about cuts

I think a really good explaination of cuts can be found here:

http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse43

I especially like the details of the 2nd example with max.

3.4.3 Cuts in your homework

listBind(['?'|T]) :- listBind(T), !.
listBind([_|T]) :- listBind(T).
listBind([]).

3.5 Append

A useful function. Don't forget you can also use it like this:

append(A,B,[big bound list]).

To try various combinations of a & b. Can be useful for your homework.

3.6 Work on Word Find HW

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 atom not a char code

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

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.' .
4.1.1.1 Solution (my super ugly version)
get_string(String) :- get_string('','',String).
get_string('\n',String,String).
get_string(PrevChar,CurrentString,String) :-
    string_concat(CurrentString, PrevChar, NewCurrent),
    get_char(NextChar),
    get_string(NextChar,NewCurrent,String),
    !.
4.1.1.2 Another pretty ugly buffalo solution
get_string(String) :- get_char(C),
                      get_stringH([C|Rest]),
                      append(NoSlashN, ['\n'], [C|Rest]),
                      atom_chars(String, NoSlashN), !.
get_stringH(['\n']) :- !.
get_stringH([_,NextChar|Rest]) :-
    get_char(NextChar),
    get_stringH([NextChar|Rest]).
4.1.1.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.1.1.4 A version from hansondg@

This one is way better than mine.

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

get_string(Result) :-
    get_char(Char),
    get_string(Char,List),
    atom_chars(Result,List).

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

?- split('hello prolog world',' ', X)
X = [hello,prolog,world].

Turns out there is a built in predicate for this one - atomic_list_concat. But I would be curious to see your solutions.

4.1.2.1 solution from taylorj7@
isC(X,O) :- X=O,!.
split(X,R,On) :-
        atom_chars(X,Temp),
        split(Temp,[],[],T,On),rev(T,R).
split([],[],Work,Work,_).
split([],X,Work,R,On):-
        rev(X,T),
        string_chars(Temp3,T),
        split([],[],[Temp3|Work],R,On).
split([C|X],Cons,Working,R,On) :-
        (isC(C,On),
         rev(Cons,T),
         string_chars(Temp3,T),
         split(X,[],[Temp3|Working],R,On),
         !;
        split(X,[C|Cons],Working,R,On)
        ,!).

5 Prolog 4 - Parsing

5.1 Your Prolog Project

[HomeworkCode/PrologNLPTwo/readme.html]

The issues presented today in class are covered in detail here:

[HomeworkCode/PrologNLPTwo/PrologGrammarRules.pdf]

5.2 Issue: Parses with variable length

noun_phrase([the,Noun]) :- is_noun(Noun).
noun_phrase([Noun]) :- is_noun(Noun).
is_noun(ninja).
is_noun(ninjas).
is_noun(student).
is_noun(students).
verb_phrase([attack]).
verb_phrase([attacks]).

A bit of a problem.

5.2.1 Solution with some problems

sentence(X) :-
        append(N,V,X),
        noun_phrase(N),
        verb_phrase(V).

5.2.2 A more efficient but stranger solution

sentence(X) :-
        noun_phrase(X,NounRemainder),
        verb_phrase(NounRemainder,[]).

noun_phrase([the,Noun|Rest],Rest) :- is_noun(Noun).
noun_phrase([Noun|Rest],Rest) :- is_noun(Noun).
verb_phrase([attack|Rest],[Rest]).
verb_phrase([attacks|Rest],[Rest]).

5.2.3 A specialized syntax for the stranger solution

sentence --> noun_phrase, verb.
noun_phrase --> determiner, noun.
noun_phrase --> noun.
verb_phrase --> verb.
determiner --> [the].
noun --> [ninja].
noun --> [ninjas].
noun --> [student].
noun --> [students].
verb --> [attack].
verb --> [attacks].

5.2.4 I recommend you use the basic syntax, but it's up to you

5.3 Issue: Number Agreement

sentence(X) :-
        append(N,V,X),
        noun_phrase(N),
        verb_phrase(V).

noun_phrase([the,Noun]) :- is_noun(Noun).
noun_phrase([Noun]) :- is_noun(Noun).
is_noun(ninja).
is_noun(ninjas).
is_noun(student).
is_noun(students).
verb_phrase([attack]).
verb_phrase([attacks]).

The problem is that "the student attack" is a valid sentence.

5.3.1 Solution

A variable passed between the parsed steps

sentence(X) :-
        append(N,V,X),
        noun_phrase(Sop,N),
        verb_phrase(Sop,V).

noun_phrase(Sop,[Noun]) :- is_noun(Sop,Noun).
verb_phrase(Sop,[Verb]) :- is_verb(Sop,Verb).

is_noun(plural, ninjas).
is_noun(singular,ninja).
is_noun(plural, students).
is_noun(singular,student).

is_verb(singular,attacks).
is_verb(plural,attack).

5.4 Issue: We want to output something

We don't want to know if something parses, we want to output a parse tree.

5.4.1 Think about it before you peek!

We can use the same trick, we used with signular/plural only with the parse output.

#+BEGIN_SRC prolog sentence(X,sentence(NT,VT)) :- append(N,V,X), noun_phrase(Sop,NT,N), verb_phrase(Sop,VT,V).

noun_phrase(Sop,noun(Noun),[Noun]) :- is_noun(Sop,Noun). verb_phrase(Sop,verb(Verb),[Verb]) :- is_verb(Sop,Verb).

is_noun(plural, ninjas). is_noun(singular,ninja). is_noun(plural, students). is_noun(singular,student).

is_verb(singular,attacks). is_verb(plural,attack). #+END_SRC prolog

6 Debugging prolog

http://www.swi-prolog.org/pldoc/man?section=debugoverview

Some example code

parent(frank,tom).
parent(jane,tom).
parent(tom,gretchen).
parent(ben,abbey).
parent(gretchen,abbey).

is_ancestor(Ancestor,Decendent) :-
        parent(Ancestor,Decendent).
is_ancestor(Ancestor,Decendent) :-
        parent(Somebody,Decendent),
        is_ancestor(Ancestor,Somebody).

turn trace on to watch how prolog solves it

1 ?- trace().
true.
[trace] 3 ?- is_ancestor(frank,abbey).
   Call: (7) is_ancestor(frank, abbey) ? Options:
+:                  spy        -:              no spy
/c|e|r|f|u|a goal:  find       .:              repeat find
a:                  abort      A:              alternatives
b:                  break      c (ret, space): creep
[depth] d:          depth      e:              exit
f:                  fail       [ndepth] g:     goals (backtrace)
h (?):              help       i:              ignore
l:                  leap       L:              listing
n:                  no debug   p:              print
r:                  retry      s:              skip
u:                  up         w:              write
m:                  exception details
C:                  toggle show context
   Call: (7) is_ancestor(frank, abbey) ? creep
   Call: (8) parent(frank, abbey) ? creep
   Fail: (8) parent(frank, abbey) ? creep
   Redo: (7) is_ancestor(frank, abbey) ? creep
   Call: (8) parent(_G2050, abbey) ? creep
   Exit: (8) parent(ben, abbey) ? creep
   Call: (8) is_ancestor(frank, ben) ? creep
   Call: (9) parent(frank, ben) ? creep
   Fail: (9) parent(frank, ben) ? creep
   Redo: (8) is_ancestor(frank, ben) ? creep
   Call: (9) parent(_G2050, ben) ? creep
   Fail: (9) parent(_G2050, ben) ? creep
   Fail: (8) is_ancestor(frank, ben) ? creep
   Redo: (8) parent(_G2050, abbey) ? creep
   Exit: (8) parent(gretchen, abbey) ? creep
   Call: (8) is_ancestor(frank, gretchen) ? creep
   Call: (9) parent(frank, gretchen) ? creep
   Fail: (9) parent(frank, gretchen) ? creep
   Redo: (8) is_ancestor(frank, gretchen) ? creep
   Call: (9) parent(_G2050, gretchen) ? creep
   Exit: (9) parent(tom, gretchen) ? creep
   Call: (9) is_ancestor(frank, tom) ? creep
   Call: (10) parent(frank, tom) ? creep
   Exit: (10) parent(frank, tom) ? creep
   Exit: (9) is_ancestor(frank, tom) ? creep
   Exit: (8) is_ancestor(frank, gretchen) ? creep
   Exit: (7) is_ancestor(frank, abbey) ? creep
true ;
   Redo: (10) parent(frank, tom) ? abort
% Execution Aborted
[trace] 4 ?- notrace().
true.

[debug] 5 ?- nodebug().
true.

6 ?-

6.1 A Few other details

  1. trace(predicate) will print each time a predicate is evaled
  2. spy(predicate) will break into debug mode when a particular predicate is called
  3. leap (from debug menu) is "continue as normal"

7 Erlang 1 - Very basics

7.1 Erlang variables & matching

7.1.1 You can't redefine variables

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

7.1.2 You can do prolog-like matching

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

7.1.3 Atoms, lists, tuples

atom % these built in "symbols" are very handy for parsing
{tuple,is,a,specific,length,grouping}
[list,can,match,with,the,H,Tail,synatx,from,prolog]

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

7.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))

7.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

7.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]

% or completely anonymously
lists:map(fun(X) -> X + 3 end, [1,2,3]).

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)

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

length("foo") gets the length

7.3.2 Solution

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

7.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) ->
    lists:foldl(AddToSum,0,List).

7.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

7.4.2 Solution

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

7.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"] ].

7.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}]

7.5.2 Solution

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

8 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!

9 Erlang 3 - Connecting to a remote erlang server

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

    Use your EIT password. Don't add 'csse' - it may interfere with your connection.

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

    Note: your name should be UNIQUE - maybe your netid?

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

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

    BTW, you'll want to do this in the ErlangSimpleCommunication directory so you can load the code.

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

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

  6. ping your remote computer from your local computer
    net_adm:ping('buffalo@erlang.rose-hulman.edu').
    pong
    

    Note: pong is good - pang is bad

    In the past, sometimes only one direction will work. If that failed for you, you can try the connection in reverse (i.e. connecting from the sever to your local erlang).

    (buffalo@erlang.rose-hulman.edu)5> net_adm:ping('buffalo@137.112.40.173').
    pong
    

    Either way, you only have to do one of these. Once, you do both servers will be connected with each other. You can check by running nodes().

    (buffalo@137.112.40.173)1> nodes().
    ['buffalo@erlang.rose-hulman.edu']
    
  7. nl loads your code on all connected servers
    (buffalo@137.112.40.173)4> c(solvemeSolution).
    {ok,solvemeSolution}
    (buffalo@137.112.40.173)5> nl(solvemeSolution).
    abcast
    
  8. You can spawn a process on a remote server like this
    RemotePid = spawn('buffalo@erlang.rose-hulman.edu', fun    solvemeSolution:part2_loop/0).
    

    Or

    Pid2 = spawn('buffalo@erlang.rose-hulman.edu', fun() -> example:buffalo_counter(0) end).
    
  1. You can see your process running on the remote server with i() (note this is on the REMOTE server)
    (buffalo@erlang.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
                                                                 280              
    ok
    
  2. Send a message to your remote process in the usual way:
    (buffalo@137.112.40.226)25> Foo9 ! {test1,2,0.7}.
    {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.rose-hulman.edu', fun() -> erlang:display("hello") end).
    
  3. 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.

10 Erlang 4 - Let it crash

11 Erlang 5 - Final Assignment, Raft Algorithm

11.1 What is an consensus algorithm?

  1. Algorithm where state is distributed across multiple members.
  2. The problem is consistency - you want to be able to store data when not all members are available, BUT you don't want it to be possible to get into inconsistent state. This can be a problem when network partitions occur and cause members to leave/rejoin the pool. (let's do an example)
  3. We rely on the idea of a majority. If we require a majority of members to agree to something to consider it committed, this ensures that any subsequent majority must share at least one member in common with a previous majority.
  4. That said, the protocol tends to be complex, because no message can be trusted to arrive.

11.2 The Raft algorithm

http://thesecretlivesofdata.com/raft/

  1. Raft relies on the idea of a "leader" who serves for a term.
  2. The leader receives requests for updates, sends updates to all members, gets responses, then when a majority of members respond, considers the update "committed".
  3. Because of the way the raft algorithm elections work, something that is committed will definitely be in the log of any electable leader.
  4. A leader may encounter a follower that is not up to date. Such a follower will not accept new data. The leader transmits larger and larger logs, going further into the past, until it encounters a point of commonality with its follower. Once a point of commonality is found, the follower replaces any data they have not in common with the leader's version.

11.3 Your assignment

Only the data transmission part of the Raft algorithm. We won't do elections.

[HomeworkCode/ErlangRaft/raft.erl]

12 Erlang 6 - Debugging sends and receives

12.1 The basics

This command can let you debug a process you are starting…

7> dbg:c(mergesort,basic1_test,[],[s,r]).
(<0.193.0>) <0.194.0> ! {sort,[2,5,7],<0.193.0>}
(<0.193.0>) <0.195.0> ! {sort,[34,2,1],<0.193.0>}
(<0.193.0>) <0.196.0> ! {sort,[99,11,2],<0.193.0>}
(<0.193.0>) << {sorted,[2,5,7],<0.194.0>}
(<0.193.0>) << {sorted,[1,2,34],<0.195.0>}
(<0.193.0>) << {sorted,[2,11,99],<0.196.0>}
(<0.193.0>) <0.195.0> ! {merge,[1,2,34],[2,5,7],<0.193.0>}
(<0.193.0>) << {merged,[1,2,2,5,7,34],<0.195.0>}
(<0.193.0>) <0.195.0> ! {merge,[1,2,2,5,7,34],[2,11,99],<0.193.0>}

BUT it's not really what you want if your goal is to debug a Raft unit test.

12.2 Debugging a raft unit test

12.2.1 Install the trace in the test setup function

Since the raft processes are short lived in the unit tests, we need to add the instrumentation in the test setup.

setup() ->
    start_raft_member(raft1),
    start_raft_members([m1,m2,m3]),
    dbg:p(raft1,[s,r]).

12.2.2 Enable the trace

6> dbg:tracer().                     
{ok,<0.57.0>}

12.2.3 Run the test case

7> eunit:test(raft:ae_hist4_test_()).
(<0.97.0>) << {<0.102.0>,{append_entries,1,0,0,[{1,newdata}],0}}
(<0.97.0>) <0.102.0> ! {x,{1,true},[raft1,1]}
(<0.97.0>) << {<0.102.0>,{append_entries,1,1,1,[{1,bad1}],0}}
(<0.97.0>) <0.102.0> ! {x,{1,true},[raft1,2]}
(<0.97.0>) << {<0.102.0>,{append_entries,2,2,1,[{2,bad2}],0}}
(<0.97.0>) <0.102.0> ! {x,{2,true},[raft1,3]}
(<0.97.0>) << {<0.102.0>,{append_entries,3,3,3,[{3,newdata4}],0}}
(<0.97.0>) <0.102.0> ! {x,{3,false},[raft1]}
(<0.97.0>) << {<0.102.0>,{append_entries,3,2,3,[{3,newdata3},{3,newdata4}],0}}
(<0.97.0>) <0.102.0> ! {x,{3,false},[raft1]}
(<0.97.0>) << {<0.102.0>,
               {append_entries,3,1,1,
                               [{3,newdata2},{3,newdata3},{3,newdata4}],
                               0}}
(<0.97.0>) <0.102.0> ! {x,{3,true},[raft1,4]}
(<0.97.0>) << {<0.102.0>,{get_term}}
(<0.97.0>) <0.102.0> ! 3
(<0.97.0>) << {<0.102.0>,{get_commit_index}}
(<0.97.0>) <0.102.0> ! 0
(<0.97.0>) << {<0.102.0>,{get_log}}
(<0.97.0>) <0.102.0> ! [{1,newdata},{3,newdata2},{3,newdata3},{3,newdata4}]
  Test passed.
ok

13 Elm 1

13.1 Elm is a functional reactive web programming language

import Html exposing (text)

main =
  text "Hello, World!"

13.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.

13.3 Has Strong Typing

import Html exposing (text)

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

main =
  text (toString (addTwo 3.0))

13.3.1 But also has type inference

import Html exposing (text)

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

addTwoImplicit num = num + 2

-- This figures out the right thing
main =
  text (toString [addTwoImplicit 3.0, addTwoImplicit 4])

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

13.3.2 An aside: Functions are designed for partial evaluation

import Html exposing (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 =
  text (toString (addTwo 5))

-- also, note that in elm you often want to cause a series of transforms
-- not a bad thing BUT note that as in lisp things will look backwards
-- if you use parens.  But there is an alternative

otherMain =  addTwo 5
  |> toString
  |> text

13.3.3 Activity

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

import Html exposing (text)
import String exposing (append)
import List exposing (map)


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 =
  text (toString wisdom)

mainAlternate = wisdom
  |> toString
  |> text

13.3.4 Solution

import Html exposing (text)
import String exposing (append)
import List exposing (map)


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

main =
  text (toString (map (append "Buffalo says ") wisdom ))

mainAlternate = wisdom
  |> map (append "Buffalo says ")
  |> toString
  |> text

13.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

Some details here: http://elm-lang.org/guide/reactivity#signals

13.4.1 Example of signals

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

13.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 =
    Signal.map toAspectRatio Window.dimensions

13.4.3 And then our whole program becomes a transformation!

import Window
import Html exposing (text)

-- note that this is just an ordinary function - no signals
aspectRatio (x,y) = (text (toString ((toFloat x)/(toFloat y))))

main =
  Signal.map aspectRatio Window.dimensions

13.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.

13.4.5 To get you started

Here's some code that draws a circle

import Color exposing (..)
import Graphics.Collage exposing (..)
import Graphics.Element exposing (..)
import Mouse
import Signal
import Window

-- in your solution, this will become main : Signal Element
main : Element
main =
  collage 1000 1000 [ filled green (circle 100) ]

13.4.6 Solution

import Color exposing (..)
import Graphics.Collage exposing (..)
import Graphics.Element exposing (..)
import Mouse
import Signal
import Window

main : Signal Element
main =
  Signal.map scene Mouse.position


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

13.4.7 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 exposing (..)
import Signal exposing (Signal, map2)
import Mouse

-- show converts an object to an element
positionToText : (Int,Int) -> Bool -> Element
positionToText (x,y) isdown =
   show (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

14 Elm 2 - Signals and state

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

14.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

14.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.

14.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.

14.3 An unrealistically small example: click counter

import Graphics.Element exposing (..)
import Signal exposing (Signal, map, foldp)
import Mouse



-- 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 show countClick

14.4 Elm Architecture

https://github.com/evancz/elm-architecture-tutorial/

  • Model - the state, as stored with a foldp
  • Update - state update function, also used in foldp
  • View - convert state signal to renderable stuff

14.5 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.

* 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/guide/model-the-problem

14.5.1 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)

14.5.2 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

14.5.3 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

14.5.4 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)

14.5.5 Done!

import Graphics.Element exposing (..)
import Signal exposing (..)
import Mouse
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) =
  show ("Your score: " ++ toString current ++ " HighScore: " ++ toString highScore)


main : Signal Element
main =
  map render countClick

14.6 Activity - Mouse Odometer

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

14.7 Solution

import Graphics.Element exposing (..)
import Signal exposing (..)
import Mouse
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) =
  show distance


main : Signal Element
main =
  map render state

15 Elm 3 - A Bit on Records

15.1 Elm has a record type!

15.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 }

15.1.2 You can use it to make "generic" functions

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

Or give a particular collection of fields/types an alias:

type alias Point =
  { x : Float
  , y : Float
  }

hypotenuse : Point -> Float
hypotenuse {x,y} =
  sqrt (x^2 + y^2)

But these are not "true" types in that they can not be self referential.

15.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. This could well be fixed in the new version of elm though.

15.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.

15.2 Elm also has "Union Types"

type Visibility = All  | Active | Completed

Basically a global enum, but unlike Erlang you do get strong typing.

15.2.1 But these can contain data, and you can use case statements to map them

type Widget
    = ScatterPlot (List (Int, Int))
    | LogData (List String)
    | TimePlot (List (Time, Int))

view : Widget -> Element
view widget =
    case widget of
      ScatterPlot points ->
          viewScatterPlot points

      LogData logs ->
          flow down (map viewLog logs)

      TimePlot occurrences ->
          viewTimePlot occurrences

Note the use of tuples. That's not strictly necessary, but it is a good idea because it allows an approximate "encapsulation" of the data.

15.3 Maybe - cool or just a way to have null?

type Maybe a = Just a | Nothing

First note that this is a parameterized type.

It can be used like this

if n > 0 && n <= 12 then Just n else Nothing

15.4 Maybe makes pure functional programmers really happy!

"This may seem like a subtle improvement, but imagine all the code you have where you defensively added a null check just in case someone else behaves badly. Having contracts means you have a guarantee that a caller won't send you bad data! This is a world where you never again have to spend 4 hours debugging a null pointer exception!"

Maybe like the difference between checked an unchecked exceptions?

15.5 Union Types Can Be Recursive

type Tree a = Empty | Node a (Tree a) (Tree a)

15.6 Creating a game

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

This can be a little tricky to do incrementally

16 Elm 4 - Functional Design

16.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)))

16.1.1 Some variations

--could also be written as
stepV2 (dt, keys) mario =
 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

16.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//

16.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
  • Natural modeling of processes that consist of discrete steps
  • Each part can be separately unit tested

16.2.2 What is bad about it?

  • Sometimes things are interdependent and cannot be "layered" correctly
  • Best when data for communicating between steps is simple, worst when communication between steps is a massive blob
  • Critical dependence on intermediate data format
  • User input, output, network communication don't fit this model directly

16.3 Let's talk about (idealized) OO paradigm

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

16.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

16.3.2 What is bad about it

  • State becomes very complex quickly - can be very hard to test
  • Best when majority of stuff is happening within objects, worst when majority of stuff is in long chains of calls
  • Critical dependence on object's references to each other - this is usually setup at runtime
  • Object relationships often hidden throughout the code

17 Elm 5 - Being Tricky With Functions

17.1 Course Logistics: Midterm grades

  • Grades are submitted
  • If you did not get at least 50% on the Erlang project please talk to me

17.2 Course Logistics: ElmVideoGame Posted

17.3 BulletExample

Take a look at the BulletExample.

[HomeworkCode/ElmBulletExample/bulletExample.elm]

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

17.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)

17.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)
       else
           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.

18 Elm 6 - By Popular Request: Randomness

Steps:

  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

18.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

18.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 exposing (..)
import Signal exposing (Signal, map, foldp, sampleOn)
import Mouse
import Random exposing (..)
import Time

type State = State (Int, Seed) | NonInit

intRand : Generator Int
intRand = int 1 100

main : Signal Element
main =
  Signal.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 -> show "Not initalized"
    State (num,ignored) -> show ("Random number is " ++ (toString num))

countClick : Signal State
countClick =
  foldp makeRandom NonInit timeOnClick

19 The final project

Details are on Moodle. Proposals are due Wednesday!

20 Instructor's Choice 1: Haskell and Monads

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

20.1 The idea

20.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! -}

20.1.2 Of course, we can always add return values!

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

20.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])

20.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

20.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!

20.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! :(

20.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.

20.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 parameters but they'll return functions with some interesting context.

20.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?

20.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.

20.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)

etc…

  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

20.3 The elm maybe monad

import Graphics.Element exposing (..)
import List exposing (tail, head)

mylist1 = [1, 2, 3]
mylist2 = [1]

(>>=): Maybe a -> (a -> Maybe b) -> (Maybe b)
(>>=) maybeVal function =
  case maybeVal of
    Nothing -> Nothing
    Just val -> function val

thirdElement inputList = 
  tail inputList >>= (\result1 -> 
  tail result1 >>= (\result2 -> 
  head result2))

main = show (thirdElement mylist1)

20.4 Write your own monads!

21 Instructor's Choice 2: More on Monads

21.1 An Example: The Maybe Monad

21.1.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".

21.1.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.

21.1.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

21.1.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

21.1.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"

21.1.6 Maybe Monad In Action

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

21.2 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!")

21.2.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)

21.2.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.

21.2.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)

21.2.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.

21.3 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.

21.3.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')]

21.3.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.

21.3.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  
    pop

22 Instructor's Choice 3: 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
  • Can use prototype based inheritance - we'll talk about that in future classes

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 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!

22.3 Now you try

  1. If you've got lua and C installed on your local system, you can try to just use it directly.
  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
gcc luatry2.c -llua -o luatry2
  1. Run it like this

    ./luatry2

  2. Understand how that code works
  3. Move on to the pcr_competition activity

22.3.1 The Paper Scissors Rock Competition Activity

Imagine we want to have a AI programming competition. Everybody's going to write an AI that players 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.

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

23 Instructor's Choice 4: 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:

http://bibliography.selflanguage.org/_static/organizing-programs.pdf

23.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
  4. Rules are even more complex when multiple inheritance enters the picture

23.2 Prototypes in Self

  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"

23.3 How to implement the basics

23.3.1 Key insight: it needs to be possible the modify the class later

Can't just use copying straightforwardly because then modifications to the class after objects are created won't affect existing instances.

23.3.2 "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)

23.3.3 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

23.3.4 What if you want multiple representations?

Abstract superclass in class orientations

In prototypes you can just not inherit the representation itself

23.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?

23.4.1 Prototype Solution

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

Figure 5

23.4.2 What do you think?

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

23.5 Are prototypes a better abstraction than classes?

Your thoughts.

23.6 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

24 Instructor's Choice 5: Smalltalk 1

What to do:

  1. Download Pharo 4 from http://pharo.org
  2. Start up Pharo and run through the little programmatic tutorial included with it.
  3. Then do the tutorial in sections 1.1 - 1.9 of the PbE book.

    [HomeworkCode/SmalltalkPBELightsOut/PharoFirstApplication.pdf]

    A hint:

    • Alt shift click appears to meta click, which is how you bring up the Morphic "halo"

25 Instructor's Choice 6: Smalltalk, The Image

25.1 What's going on with Smalltak

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

25.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.

25.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.

25.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.

25.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.

25.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.

25.3 Why is an image good?

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

25.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

25.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?

25.3.3 A programmatic programming environment gives you greater power

25.3.3.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.

25.3.3.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"?

25.3.3.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.

25.4 Some examples

25.4.1 A demo

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

25.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)

Author: Buffalo

Created: 2017-01-05 Thu 15:25

Emacs 26.0.50.2 (Org mode 8.2.10)

Validate