EECS 662

Programming Languages

Index
Blog

Lambda Examples From Class

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