Final ReviewFinal: Thursday, May 16th at 12:30pm3:30pm
Language ImplementationScanning  tokens Parsing  structure ASTs  in memory representation of parsed text Interpretation  evaluate AST Code Generation  translate AST to machine code or bytecode
Lambda CalculusSyntax
expr ::= variable ::= (expr expr) ::= "\" variable "." expr
variable is an identifier (lowercase letters)
Consider how to write a parser for Lambda Calculus
Bound and free variables
\x.xy
x is bound y is free
Alpha Conversion
\x.M = \y.M [x < y]
Where y cannot be a free variable in M
Eta Conversion
Eta reduction
\x.Mx > M
Eta abstraction
M > \x.Mx
where x may not be a free variable in M.
Beta Reduction
Beta conversion
(\x.M) N <> M [x <> N]
Beta reduction
((\x.M) N) > M [x > N]
Beta abstraction
M > (\x.M)N)
(\x.xx) \y.y beta> (\y.y)(\y.y) beta> \y.y beta> (\y.y)(\y.y)
Normal order vs Applicative order
Church encoding
Numbers, operators Boolean, operators
The Y Combinator Y = \f.((\x.(f x x)))(\x.(f (x x))))Using the Y Combinator to implement recursion
Do some examples.
Haskell encoding of lambda calculus.
HaskellReferential transparent  a function called with the same arguments always gives the same result.
Purely functional  the language doesn't allow sideeffects to happen in a way that destroys referential transparency
Functions (pattern matching) Data types List comprehensions
Monads  Allow for computations to be combined and ordered
 Allow "data" to be passed along through computations
IO Monad
