Lectures‎ > ‎


Final Review

Final: Thursday, May 16th at 12:30pm-3:30pm

Language Implementation

Scanning - tokens
Parsing - structure
ASTs - in memory representation of parsed text
Interpretation - evaluate AST
Code Generation - translate AST to machine code or bytecode

Lambda Calculus


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

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.


Referential transparent - a function called with the same arguments always gives the same result.

Purely functional - the language doesn't allow side-effects to happen in a way that destroys referential transparency

Functions (pattern matching)
Data types
List comprehensions

  • Allow for computations to be combined and ordered
  • Allow "data" to be passed along through computations

IO Monad