430_notes

8/29

OCaml review:
      let add (x,y) = x+y;;
      	  int * int -> int
      let add x y = x+y;;
      	  int -> int -> int
	      (add 1) returns a funtion that adds 1 to a number
      let twice g x = g (g x);;
      	  ('a -> 'a) -> 'a -> 'a
      remember lists separated by semicolon [1,2,3] != [1;2;3]
      remember "rec" modifier to allow for recursion
      "_" replaces an unused part in a pattern match
      "function" like "fun" but automatically takes argument and pattern match
      Records:
	type course = {title:string; num:int}
	let x = {title="blah"; num=1234}
	x.num;; --> dot notation
	{x with num=431} --> can be used to set defaults
	by default, records are immutable
	   this can be changed as shown:
	   	type course = {title:"blah"; mutable int:1234}
	   then:
		x.num <- 430;;
      	Example:
	   	type course = {title:"blah"; mutable int:1234}
		let x = {title="blah"; num=1234}     
		Let w = {x with title="meh"}
		x.num <- 433
		What HAPPENS?

      References "ref":
      		 let x = ref 1;;
		     basically let x = {mutable contents=1}
      Shadowing:
	reusing a variable name causes a previous definition to be overwritten

      Type annotation (add a :TYPE after a variable to restrict its type)
      Nominal typing -> types distinguished by name, REGARDLESS of content
      
      Arrays:
	let x = [|4;2;3|]
	x.(0) <- 1
	MUTABLE!!
      Strings:
	Essentially arrays (which means theyre mutable)

      OCAML:
	Tuples
	Lists
	Records
	Arrays
	User-defined Data types (trees)

      Ruby:
        Array
	Hash (not built into OCaml -> interesting
	
      '_a -> this type implies that a mutable value of anuy type can be used, 
      	  but once it is it must remain of that type

8/31

   Syntax (language structure) vs. semantics (actual meaning)
   list.assoc will be helpful for project list of vars
   OCaml option type: Some vs. None (essentially NULL for OCaml)
   Project 1: for bvec, higher order bits to the right
   	      make sure to compile projects, not run them top level
   OCaml Review cont.:
      let f ~x ~y = x-y (named arguments to function)
         we can do:
	    f 4 3;;
	    f ~y:4 ~x:3
	 (in order to work, you must name all or no variables)
      
      Currying:
         create partial functions (partial application)
	 let add x y = x+y;;
	 let g = add 1;; (now we have an add 1 function)
	 More difficult to replace second argument:
	    achieved using named arguments
      
      Loops:
	 let rec foo() = foo();; --> never dies because of tail recursion
	 while true do () done;; --> internally turned into let rec w/ tail rec
	 there also exists a for loop implementation
      
      Modules:
         module type BLAH = 
	    sig
	      type blah
	      val hmm : blah -> int
	 end;;
	 
	 Note: the two semicolons and the next part are largely unnecessary for
	       compiled OCaml

	 module Blah : BLAH = 
	    struct
	       let hmm b = 0;;
	    end

	 consider the module Set (also consider module Hash_tbl)
	    functr is a function that takes modules and gives you new modules

	 Polymorphic Variants: 
	    [`On; `Off];;
	    [> `Off | `On] --> list of eith Off or On
	    `Number 1;;
	    let f x = match x with
	    [< `Number of int | `On | `Off]
	    `On -> 1
	    | `Off -> 0
	    | `Number n -> n;;

	    You could do something like:
	       `Number;; (You could do this with an explicitly defined type)
	    [> --> this means it has at LEAST the following types
	    [< --> this means it has at MOST the following types
	    Tradeoff: flexibility vs. compile-time check
	    Useful for stuff like:
	       f takes `A, `B, and `C
	       g takes `B, `C, and `D

9/7

   Project 1:
      lambda(x).y [replace y --> x]
         the x from lambda x is meaningless -> similar to:
	    int foo(int x) {
	       return x;
	    }
	 you can just rename x as z --> essentially alpha conversion
	 lambda(x).y --> lambda(z).y
	 therefore [replace y --> x] gives:
	    lambda(z).x which is essentially the same as lambda(x).x
	       just less confusing
      you won't lose any points for extra tests (make many)
      "open Module" --> don't have to write Module. notation
         List.assoc;;
	 open List;;
	 assoc;;
      testing sat? --> buggy in "natural ways"

   Parsing:
      Compiler -> two parts: front end vs. back end
	 source code-->lexer-->parser-->types-->AST--->...-->machine code
	 [-------------Front End------------------][------Back End ------]

	 More research into Front End --> not sure why

         lexer - creates tokens (terminals of language)
	    terminals:
	       identifier, integer
	       ex:
	          type expt = 
		     EFalse
		  |  False
	       type, =, | --> 
	       EFalse, False --> identifiers
	    uses regular expressions
	 parser - 
	    uses Context Free Grammars

	 Why this difference?
	    Regexp is really fast (so it's done first)
	       might be able to catch basic syntax mistakes/errors

	 Abstract Syntax Tree vs. Parse Tree:
	    Parse Tree is very similar but has more fluff (parentheses)
	    consider:
	       a ^ b v c vs. (a ^ b) v c vs. a ^ (b v c)
	    AST don't need this because it is clear from the structure of the
	       tree 

      Parsing Algorithms:
         General purpose algorithms: CYK and Earley (generally considered impractical)
	 they can deal with any CFG (yay) but slow
	 More practical algorithms:
	    LL(k): (ANTLR)
	       top-down parser
	          parses from top of parse tree to bottom
	       left-to-right
	       left-most-derivation
	          Always looks at left-most non-terminal to reduce first
	    Consider:
	       S -> AA
	       A -> a
	    Derivation - start from first symbol all the way to a string
	       S -> AA -> aA -> aa (left-most)
	       S -> AA -> Aa -> aa (right-most)
	    top-down-parser:
	       parses from S to aa (separates S -> AA -> aa
	    LR(k): (yacc)
	       bottum-up parsing
	          parses from bottom of parse tree
	       left-to-right
	       right-most-derivation
	    yacc: (lexer = lex)
	       different versions for different languages
	          bison (for c), ocamlyacc (for ocaml)
		  tied to lexers: flex and ocamllex respectively
		  
      Let's build a parser for arithmetic expressions:
         E -> E+E | n | (E)
	    where n is an arbitrary integer
	    what are tokens? "+", "(", ")", "n"
	    maybe we want whitespace? (lexer removes whitespace, comments, newlines, etc)
	 .mll extension for ocamllex
	 token lexbuf -> can remove unneeded things (whitespace, tabs, etc)
	 run ocamllex on .mll file creates (compiles) a .ml file
	    .ml is a table-driven finite automaton
	 rule token = parse
	    creates recursive function token that essentially does automata traversal
	 Lexing.engine -> ocaml module worth looking at
	 parser will take:
	    1+2+3
	    creates lexbuf (input string with pos in string)
	    calls token lexbuf which retrieves next token
	       Int(1), Plus, Int(2), Plus, Int(3), EOL
	 for parser, if any of the regexp overlap, ocaml will probably match the first
	 finite automata has limited number of states
	 parse string for:
	    1+2+3
	    Grammar is ambiguous: there are two possible parse trees
	 Let's consider instead:
	    E -> T | E + T
	    T -> n | (E)
	    no longer ambiguous
	    E
	    (E+T)
	    (E+T)(+)(3)
	    (T)(+)(T)(+)(3)
	 .mly file defines the parser
	    %token at beginning define tokens used by lexer
	    %start defines start symbol of grammar
	    generally terminals are uppercase, non-terminals are lowercase
	       opposite of how we generally write it
	 run .mly with ocamlyacc
	    we get .mli file and a .ml file
	 start symbol of grammar becomes name of function in .mli
	 .ml file:
	    there are many tables (table-driven file)
	    Parsing.yyparse -> ocaml standard library
	 Our goal is to produce AST
	 Every production has a given value (andtype)
	    {$1} in the .mli file

      Derivation
      Leftmost/rightmost
      sentential form
         E -> E+E -> n+E -> n+n (each thing separated by "->" is a sentential form)
      FIRST(alpha) - set of potential first characters
         S -> a | B | Bc |Df
	 B -> b
	 D -> d | empty
         First(S) = {a,b,d,f}

      if we have x,y where x,y are collections of terminals
         we want to go all the way backwards to S (starting symbol of grammar)
	 xy -> aby -> aBy -> ABy -> ... -> S
	 production goes from B->a, reduction goes from a->B
	 If there exists only one parse tree, there is only one left and right most derivation
	    maybe there's some hope for us
9/12

   Project 1:
      no errors in lambda add tested by secret tests (oUnit)

   Parsing:
      Ocaml yacc:
         .mly -> (.mli and .ml)

      Consider:
         1. S -> aABe
	 2. A -> Abc 
	 3.    | b
	 4. B -> d

	 input string = "abbcde"

	 should we start from S and work down (top down) or try to go
	 from string to S (bottom up)
	 
	 lets try bottom up:
	    
	    abbcde <--3-- aAbcde <--2-- aAde <--4-- aABe <--1-- S

	    the second "b" from "abbcde" isn't followed by a c, so it must
	    come from A
	    	    
            if the grammar is unambiguous, there is only one right and left
	    hand derivation!
	       the above example is a right-most derivation
	 
      handle - a pair (A->beta, k) where (A->beta) is a production and
      k is a position applied, where the handle is applied in a 
      (right-most) derivation
	 the handle is unique for a right-most derivation in an 
	 unambiguous grammar

      let's consider a parser that scans input from left-to-right
      	    shift-reduce parser
	       stack keeps track of what we've seen
	       let's pretend we have a lexer:
	          t = next-token() (Provided by lexer)
		  s = initially empty stack

	          until (s.top == S and token == EOF)
	             // should we reduce it?
	             if (s.top is handle A->beta)
		        pop |beta| symbols from S
		        push A
		     else
		        push t
		        t = next_token()

		   if --> "reduce" phase
		   else --> "shift" phase

      Consider:
         1. S -> aABe
	 2. A -> Abc 
	 3.    | b
	 4. B -> d

	 input string = "abbcde"

	 let's use a shift-reduce parser this time:
	    
	    initial top of stack = ^

	    stack:	   input:	   action:
	    ^		   abbcde	   shift
	    ^,a		   bbcde	   shift
	    ^,a,b	   bcde	   	   reduce 3
	    ^,a,A	   bcde	   	   shift
	    ^,a,A,b	   cde		   shift (convoluted reasoning)
	    ^,a,A,b,c	   de		   reduce 2
	    ^,a,A	   de		   shift
	    ^,a,A,d	   e		   reduce 4
	    ^,a,A,B	   e		   shift
	    ^,a,A,B,e	   EOF		   reduce 1
	    ^,S		   EOF		   ACCEPT
	    
	    Note: convoluted reasoning as to when shift vs. reduce

      When do you shift and when do you reduce?
         for this parser, we're going to use finite automata
	    we will have DFA states between every value on the stack
      	    each DFA state will have "memory" of what's been seen
	 Action vs. goto table
	    action table tells you whether you should shift or reduce
	    and which state you should go into
	    s3 -> shift and then go to state 3
	    r3 -> reduce by production 3
	 lets consider a parser table created by Ocamlyacc

	    s = stack     
	    t= next_token()
	    ^ = initial top of stack
	    #'s refer to corresponding states
	 
	    s.push(^)
	    s.push(1)
	    
	    not_found = true
	    while (not_found)
	       state = s.top
	       
	       if ACTION[state,t] == "reduce A->beta"
	          s.pop(2|beta| state/symbols)
		  state = s.top
		  s.push(A)
		  s.push(GOTO[state,A])
	       else ACTION[state,t] == "shift n"
	       	  s.push(t)
		  s.push(n)
		  t = next_token()
	       else
	          ERROR

	 Using Ocamlyacc example parser table from slide:
	    
	    stack:			input:		action:
	    ^,1				N+N+N		s3
	    ^,1,N,3			+N+N		r4
	    ^,1,term,7			+N+N		r2
	    ^,1,expr,6			+N+N		s10
	    ^,1,expr,6,+,10		N+N		s3
	    ^,1,expr,6,+,10,N,3 	+N		r4
	    ^,1,expr,6,+,10,term,12	+N		r3
	    ^,1,expr,6			+N		s10
	    ^,1,expr,6,+,10		N		s3
	    ^,1,expr,6,+,10,N,3		EOL		r4	
	    ^,1,expr,6,+,10,term,12	EOL		r3	
	    ^,1,expr,6,			EOL		s9
	    ^,1,expr,6,EOL,9				ACCEPT

	    *NOTE: the state you look at in the action table is whichever
	           state is at the top of the stack after reduction

      Let's consider the DFA:
         let's give our states helpful elements for our understanding:
	    an LR(0) item is a production with a dot (.)
	       (in writing the dot like multiply]
	       For example:
	          [A->.(beta)(gamma)] 
	          [A->(beta).(gamma)] 
	          [A->(beta)(gamma).]

	    
	    S -> E
	    E -> T+E
	       | T
	    T -> id

	    DFA:
		"State 1"	"State 2"	"State 3"	
	    	[S->.E]		[T->id.]	[E->T.+E]
	    	[E->.T+E]  			[E->T.]
	    	[E->T]
	    	[t->.id] 

		"State 1" --id--> "State 2"
		"State 1" -->T--> "State 3"

           *Note: It seems dot (.) refers to consumption of (Non)terminal

9/14

   Project 1: Final notes
      we can use the ocaml "top-level"
         run "ocaml"
	 you have acess to a bunch of things (i.e. #help)
	    also #use ONLY in top level
      we can also use ocamlc --> essentially make
         we can use Open instead of #use

   let's see how the DFA is actually built:
      
      S-> aSa | b

      let's add a start symbol (so we know if we reduce there, we are done)
      
      0. S' -> S
      1. S -> aSa 
      2.      | b	

      dot means we expect to see something spawned by S

      STATE 0 is the start state
      If we are in state 1, the DFA "remembers we've seen an "a""

      STATE 0:
      [S' -> .S] 
      [S -> .aSa]
      [S -> .b]

      STATE 1:
      [S -> a.Sa]
      [S -> .aSa]
      [S -> .b]

      STATE 2:
      [S -> b.]	

      STATE 3:
      [S -> aS.a]	

      STATE 4:
      [S -> aSa.]	
      
      STATE 5:
      [S' -> S.]

      STATE 0 --a--> STATE 1
      STATE 0 --b--> STATE 2
      STATE 1 --a--> STATE 1
      STATE 1 --b--> STATE 2
      STATE 1 --S--> STATE 3
      STATE 3 --a--> STATE 4
      STATE 0 --S--> STATE 5

      stack:		   input:		action:
      ^,0 		   aabaa		shift 1
      ^,0,a,1		   abaa			shift 1
      ^,0,a,1,a,1	   baa			shift 2
      ^,0,a,1,a,1,b2	   aa			reduce 2
      ^,0,a,1,a,1,S,3	   aa			s4
      ^,0,a,1,a,1,S,3,a,4  a			r1
      ^,0,a,1,S,3  	   a			s4
      ^,0,a,1,S,3,a,4  	   a			r1
      ^,0,S,5		   			accept

      whenever you have a state where the dot is all the way right it means you could
      reduce

            ACTION            GOTO
      State	a	b	S
      0	    	s1		5
      1		s1	s2	3			
      2		r2	r2
      3		s4	
      4		r1	r1	
      5		r0	r0

      Action table: 
         tells you when to transition on terminals

      GOTO table: 
         tells you when to transition on non-terminals

   New grammar:
      S' -> S
      S -> Ac|Bd
      A -> a
      B -> a

      let's build a parser DFA:

      STATE 0:
      [S' -> .S]
      [S -> .Ac]
      [S -> .Bd]
      [A -> .a]
      [B -> .b]

      STATE 1: --> reduce/reduce conflict (two reductions, unsure of which to do)
      [A -> a.]
      [B -> b.]      

      STATE 0 --a--> STATE 1

      reduce/reduce conflicts are generally caused by ambiguous grammars

      "ocamlyacc -v parser.mly" is super helpful
         look through the parser table!
	 it will tell you about shift/reduce conflicts

      S -> ac | ad (fixes reduce/reduce conflicts)

      algorithm for defining a parser DFA:
      
         closure(state) - 
	    for every item [A -> beta.B.delta] in state
	    for all productions B -> gamma
	    add [B -> .gamma] to state
	    (repeat this until there's nothing left to add to state)

	 goto(state,x) - 
	    x is either terminal or non-terminal
	    new state is initially empty
	    For every [A->beta.Xdelta] in state
	       new = new U [A -> betaX.delta]
	    add closure(new) to DFA

	    the "inital" part of the state (the first production) is called the kernel
	       the rest are called the closure
	       ocamlyacc only shows the kernel

9/19

   Exam: Possibly Monday, October 10th

   LR(0) parser (0 implies no lookahead)

   1. S -> E
   2. E -> T + E
   3.      | T
   4. T -> n
    
   Let's build a DFA:

   STATE 0:
   [S->.E]
   [E->.T+E]
   [E->.T]
   [T->.n]

   STATE 1:
   [T->n.]

   STATE 2:
   [E->T.+E]
   [E->T.]

   STATE 3:
   [E->T+.E]
   [E->.T+E]	
   [E->.T]
   [T->.n]

   STATE 4:
   [E->T+E.]	

   STATE 0 --n--> STATE 1
   STATE 0 --T--> STATE 2
   STATE 2 --+--> STATE 3
   STATE 3 --n--> STATE 1
   STATE 3 --T--> STATE 2
   STATE 3 --E--> STATE 4

   stack:	  	input:		action:
   ^,0		  	n+n$  		s1
   ^,0,n,1	  	+n$		r4
   ^,0,T,2	  	+n$		s3
   ^,0,T,2,+,3	  	n$		s1
   ^,0,T,2,+,3,n,1	$		r4
   ^,0,T,2,+,3,T,2	$		r3
   ^,0,T,2,+,3,E,4	$		r2
   ^,0,E,acc		$

   	 n:	 +: 	$:	E:	T:	S:
   0	 s1	 		acc	2
   1	 r4	r4	r4
   2	 r3	s3/r3	r3
   3	 s1			4	2
   4	 r2	r2	r2			

   closure(state s)
      until a fixpoint(terminal)
         for every [A->beta.Bdelta]
	    for every B-> gamma
	       add [B->.gamma] to s

   with lookahead:
   closure(state s)
      until a fixpoint(terminal)
         for every [A->beta.Bdelta,a]
	    for every B-> gamma
	       for every b in FIRST(deltaa)
	       	   add [B->.gamma,b] to s	
	   
   goto(s, X)
      new = empty
      for every [A->beta.Xdelta] in s
         add [A->betaX.delta]

   with lookahead"
   goto(s, X)
      new = empty
      for every [A->beta.Xdelta,a] in s
         add [A->betaX.delta,a]
      apply closure to new
 
   This grammar is not LR(0)
      the grammar is still unambiguous!
      shift/reduce conflict makes the parser not work
      How do we fix this?

   Let's try an LR(1) parser!
      an LR(1) item looks like:
         [A->.beta,a]
	 next character is beta, after that we expect to see "a"
	 what about:
	    [A->beta.,a]
	    only reduce if next character is actually a
	 We can have:
	    [A->.beta,a]
   	    [A->.beta,b]
	    in the same state
	    can be written as:
	    	[A->.beta,a/b]

   STATE 0:
   [S->.E,$]
   [E->.T+E,$]
   [E->.T,$]
   [T->.n,+/$]

   STATE 1:
   [T->n.,+/$]

   STATE 2:
   [E->t.+E,$]
   [E->T.,$]

   STATE 3:
   [E->T+.E,$]
   [E->.T+E,$]
   [E->.T,$]
   [T->.n,+/$] --> (+ is FIRST(+E$) and $ is FIRST($)

   STATE 4:
   [E->T+E.,$]

   STATE 0 --n--> STATE 1 
   STATE 1 --T--> STATE 2 
   STATE 2 --+--> STATE 3 
   STATE 3 --T--> STATE 2 
   STATE 3 --n--> STATE 1
   STATE 3 --E--> STATE 4  

   	 n 	 +	 $	E	T	S
   0	 s1	  	 	acc	2
   1	 	 r4	 r4		
   2		 s3   	 r3
   3     s1			4	2
   4	 		 r2

   stack:		 input:		action:
   ^,0			 n+n$		s1
   ^,0,n,1		 +n$		r4
   ^,0,T,2		 +n$		s3
   ^,0,T,2,+,3  	 n$		s1
   ^,0,T,2,+,3,n,1  	 $		r4
   ^,0,T,2,+,3,T,2  	 $		r3
   ^,0,T,2,+,3,E,4  	 $		r2
   ^,0,E,acc		

   ocamlyacc arbitrarily chooses shift over reduce in s/r conflicts
      be careful with this
      don't keep s/r conflicts in the project

   adding "left PLUS" at top of .mly file will make terminal 
   PLUS left-associative

   adding "left TIMES" above "left PLUS" gives TIMES lower precedence
      same line definition gives same precedence

   these declarations CAN help get rid of s/r conflicts
      you can use them, probably better to refactor grammar

   r/r convlict often but not always caused by an ambiguous grammar

   E->E+E
      | n

   Refactored: (Right Recursive)
   E->T+E
      | T
   T->n

   Again:(Left Recursive)
   E->E+T
      | T
   T->n

   Top-Down parser must be Right Recursive

   for shift/reduce parsers, either will work
       there is a slight memory benefit to left recursive
          if there's a long string of (n+n+n+...+n)
	     for left-recursion this might save space
	        reduces before all the ns are pushed on the stack

   despite what we've been told thusfar, ocamlyacc produces LALR(1)
      not LR(1)
      
   LALR(1):
      STATE 1:
      [E->a.,b]
      [E->ba.,c]
      
      STATE 2:
      [E->a.,d]
      [A->ba.,b]       

      core of a transition is just the thing without the lookahead
         if cores are equal, states are combined and lookaheads are
	 concatanated
	 
      makes slightly smaller parsing tables

      r/r conflicts can (but not likely) come from LALR(1) conflict
         even if it works with LR(1)
	 will never cause s/r conflicts

9/21

   Project 2:
      store in a hash table? up to you
      When writing the lexer:
         you can have an associated toekn for every keyword
	    will work, but you do end up with a larger DFA
	       more keywords make bigger DFAs (there is a max size, so careful)
	    ex:
	       b	{bool}
	 you can have a general rule: (assume hash table H)	 
	    [a+z]+ as lxm {if H.has_key? lxm H[lxm] else ID(lxm)}
	 what if an identifier is a keyword?
	    option 1: don't alow it to happen (probably best choice)
	    option 2: try to figure it out based on context (hard)

      Change to project description?
         "VEXPR = VEXPR" changed to "eq VEXPR VEXPR";