Binary Tree parser

We can modify the parser to also construct the binary tree as it is parsed.

fun binTree2 ts = 
    case ts of 
        (numlit x)::tr => (leaf x, tr)
        | lparen::tr => 
            let val (tree1, ts1) = binTree2 tr
            let val ts2 = case ts1 of 
                          comma::tr2 => tr2
                          | _ => raise parseError
            let val (tree3, ts3) = binTree2 ts2
            val ts4 = case ts3 of 
                      rparen::tr4 => tr4
                      | _ => raise parseError
            in (node(tree1, tree3), ts4)
            end
        | _ => raise parseError

Then,

fun parse3 s = 
    let val(tree, rest) = binTree2(scan s)
    in if rest = [] then tree else raise parseError
    end;

Referential transparency

When a programming language updates memory (mutable structures), it isn’t referentially transparent. ML has features that violates referential transparency, mainly to avoid copying data structures to make small change to it.

Remember: pure functional programming languages do not have assignment!

$\lambda$ calculus

Scott, section 11.7 (supplement), Slonneger and Kurz, chapter 5

Developed by Church in the 1930’s. Can be used to define computable functions. Church showed that there is no algorithm to determine whether two lambda expressions are equivalent.

$\lambda$ calculus (LC) is the mathematical foundation for functional programming; fp is really just clever implementations with types and syntactic sugar.

What is a function?

LC is a calculus of anonymous functions. It’s a method of representing functions and a way to syntactically transform functions. LC has a constructive view of functions. For e.g., $\lambda$x. * 2 x is the function of x that returns times 2 x (prefix notation).

More complex example: $\lambda$ x. $\lambda$ y. * ( + x y) 2, which is the function of x that returns the function of y which returns * (+ x y) 2. In ML, this is implemented as a curried function!

Bound and free

In $\lambda$ y. * ( + x y) 2, x is free and y is bound.

Purity!

Everything is a function in pure LC. For e.g., natural numbers can be functions. Think peano axioms; a successor function S(n) applied to constant functions 0, 1, …

Syntax for $\lambda$ calculus (SK)

expr ::= var //lower case identifier
    | const //predefined objects
    | ( expr expr ) //application
    | ($\lambda$ var . expr) //abstraction

Application associates to the left. Application has higher precedence than abstraction. Need to use parantheses to make abstraction have higher precedence.

Naming $\lambda$ expressions

Example: define f = ($\lambda$ x . ((+ x) 1))

Use val in ML for equivalence: val f = fn x => x + 1.

Evaluation of $\lambda$ expressions

Apply a set of reduction rules to simplify expressions. 4 kinds:

  • $\delta$ - use for the built-in constants, e.g., numbers such as (+ 2 3) $\rightarrow$ $\delta$ 5
  • $\beta$ - (($\lambda$ x. E1) E2): take all instances of bound variable (x) in the body, E1, and replace with E2. e.g., (($\lambda$ x . * 2 x) 5) $\rightarrow$ $\beta$ * 2 5 $\rightarrow$ $\delta$ 10
  • $\alpha$ - rename bound variables. For e.g., ($\lambda$ x . ($\lambda$ x.x)(+ 1 x)) 3 $\rightarrow$ $\alpha$ ($\lambda$ x . ($\lambda$ y.y)(+ 1 x)) 3 $\rightarrow$ $\beta$ ($\lambda$ y.y)(+ 1 3) $\rightarrow$ $\delta$ ($\lambda$ y.y) 4
  • $\eta$ - eliminate unnecessary abstsractions; ($\lambda$ x. f) $\rightarrow$ $\eta$ f (where x is not free in f)

Problems with $\beta$ - name clashes can occur with complicated functions. So use $\alpha$ redux!