Following are examples using lambda from class. Note that I’ve done no
proofreading, so the notes reflect the state they were in when my
lecture ended.
(lambda x in x)
== (lambda x in x)
lambda is a value - what does that actually mean?((lambda x in x) 5)
== [x->5]x
== 5
app evaluates a lambda applied to an expression
((lambda z in z) (lambda x in x))
== [z->(lambda x in x)] z
== (lambda x in x)
What function is this?
(((lambda x in (lambda y in x+y)) 3) 2)
== [x->3](lambda y in x+y)
== ((lambda y in 3+y) 2)
== [y->2]3+y
== 3+2
== 5
(lambda x y z ...) == (lambda x in (lambda y in (lambda z in ...)))
(((lambda x in (lambda y in x+y)) 1)
== (lambda y in 1+y)
Signatures?
((lambda x in (x 3)) (lambda z in z))
== [x->(lambda z in z)](x 3)
== ((lambda z in z) 3)
== 3
Functions as parameters. What’s this?
bind inc=(lambda x in x+1) in (inc 3) [(inc,(lambda x in x+1))]
== (inc 3) [(inc,(lambda x in x+1))]
== ((lambda x in x+1) 3)
== 3+1
== 4
Named lambda values are just like any other value.
[]
bind inc=(lambda x in x+1) in [(inc,(lambda x in x+1))]
bind dec=(lambda x in x-1) in [(dec,(lambda x in x-1)),(inc,(lambda x in x+1))]
bind sqr=(lambda x in x*x) in [(sqr,(lambda x in x*x)),(dec,(lambda x in x-1)),(inc,(lambda x in x+1))]
(inc (sqr (sqr 3)))
== ((lambda x in x+1) (sqr (sqr 3)))
== ((lambda x in x+1) ((lambda x in x*x) (sqr 3)))
== ((lamdba x in x+1) ((lambda x in x*x) ((lambda x i x*x) 3)))
== ((lamdba x in x+1) ((lambda x in x*x) (3*3)
== ((lamdba x in x+1) 9*9
== 1+81
== 82
More using $\lambda$-calculus:
(lambda y in y)(lambda x in x)
== [y->(lambda x in x)]y
== (lambda x in x)
f==(lambda y in y)
s==y
i==y
va == a==(lambda x in x)
(lambda x in x x) 3
== [x->3](x x)
== (3 3)
(lambda x in x x)(lambda y in y)
== [x->(lambda y in y)](x x)
== ((lambda y in y)(lambda y in y))
== [y->(lambda y in y)]y
== (lambda y in y)
(lambda x in x x)(lambda y in y y)
== [x->(lambda y in y y)](x x)
== (lambda y in y y) (lambda y in y y)
== [y->(lambda y in y y)](y y)
== (lambda y in y y) (lambda y in y y)
More examples using abstract syntax. Note that a few are not worked - I will do them in class.
((Lambda i s) a) == bind i a s
bind f = (lambda x in x) in
(f 2)
== [f->(lambda x in x)](f 2)
== ((lambda x in x) 2)
== 2
bind n = 1 in
bind f = (lambda x in x + n) in
bind n = 2 in
f 1
== bind f = (lambda x in x + 1) in
bind n = 2 in
f 1
== bind n = 2 in
(lambda x in x + 1) 1
== (lambda x in x + 1) 1
== 1+1
== 2
(f a) -> (App f a)
f(x)=x+1 == bind f = (lambda x in x+1)
f(x,y)=x+y == bind f = (lambda x in (lambda y in x+y))
== f(x)=(lambda y in x+y)
Same problem as before - inefficient and kind of clumsy
Try again with environments:
Env = [(string,FBAE)]
eval e (Lambda i s) =
eval e (App f a) = do { }
eval e (Id i) =
Same technique as bind - save the value and substitute later.
bind f = (lambda x in x) in []
(f f)
==
Seems to work quite nicely.
bind n = 1 in []
bind f = (lambda x in x + n) in []
bind n = 2 in []
f 1
==
Oops… What happened here?