PLP: Lecture 26
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!