Study HW 5 Answers

1.    Evaluate the following lambda expressions.

 
• (((lambda-x.lambda-y.(y x)) lambda-p.lambda-q.p) lambda-i.i)
= ((lambda-y.(y lambda-p.lambda- q.p)) lambda-i.i)
= ((lambda-i.i) lambda-p.lambda-q.p)
= (lambda-p.lambda-q.p)
 
• (((lambda-h.((lambda-a.lambda-f.(f a)) h)) h) lambda-f.(f f))
= (((lambda-h.(lambda-f.(f h))) h) lambda-f.(f f))
= ((lambda-f.(f h)) lambda-f.(f f))
= ((lambda-f.(f f)) h)
= (h h)
 
• ((((lambda-f.lambda-g.lambda-x.(f (g z))) lambda-s.(s s)) lambda-a.lambda-b.b) lambda-x.lambda-y.x)
= (((lambda-g.lambda-x.((lambda-s.(s s)) (g z))) lambda-a.lambda-b.b) lambda-x.lambda-y.x)
= (((lambda-g.lambda-x.((g z) (g z))) lambda-a.lambda-b.b) lambda-x.lambda-y.x)
= ((lambda-x.(((lambda-a.lambda-b.b) z) ((lambda-a.lambda-b.b) z))) lambda-x.lambda-y.x)
= ((lambda-x.((lambda-b.b) (lambda-b.b))) lambda-x.lambda-y.x)
= ((lambda-x.(lambda-b.b)) lambda-x.lambda-y.x)
= (lambda-b.b)

2.    Analyze the following lambda-expressions and mark variables as free or bound.

• lambda-x.lambda-y.(lambda-x.y lambda-y.x)
         y: free in lambda-x.y
         x: free in lambda-y.x
         x,y bound in lambda-x.lambda-y.(…)        .
 
• lambda-x.(x (lambda-y.(lambda-x.x y) x))
         x: bound in (lambda-x.x y); y: free in (lambda-x.x y)
         x: free in (lambda-y.(…) x); y: bound in (lambda-y.(…) x)
         in lambda-x(…..) All variables are bound.
 
• lambda-a.(lambda-b.a lambda-b.(lambda-a.a b))
         a: bound, b:free in  (lambda-a.a b) 
         a,b bound in (lambda-b.(lambda-a.a b) 
         a: free, b: bound in(lambda-b.a lambda-b.(…))
         a,b bound in   lambda-a.(….)  
 
• lambda-p.lambda-q.(lambda-r.(p lambda-q.lambda-p.(r q)) (q p))
         r,q free in    lambda-p.(r q)
         r:free, q: bound in  (p lambda-q.lambda-p(r q)) (q p) 
         r,q bound in  (lambda-r. (p lambda-q.lambda-p(r q)) (q p))
         all variables bound in  lambda-p.lambda-q.(…) 


3. You are asked to find a lambda expression that evaluates
differently when we use by NAME and by VALUE, and not to just
reuse the example from our class lecture.
This is easiest to do by using our familiar 
(lambda-x.(x x)) (lambda-y.(y y))
function as an argument of a different function than the one we used
in class. That is, consider the following lambda expression:

(lambda-x.lambda-y.x) (lambda-x.x) ((lambda-s.(s s))(lambda-r.(r r)))

Remember that lambda expressions are left associative so we first
change variables in the the middle expression (lambda-a.a), and then
(by name) substitute it into the first expression yielding
(lambda-y.lambda-a.a). Then we substitute the third expression, our
favorite repeating lambda expression, for y in this, yielding
(lambda-a.a). BY NAME (the normal form for this expression)

Clearly if we use BY VALUE and evaluation the 3rd expression
((lambda-s.(s s)) (lambda-r.(r r))), we will just get itself back
again and will have a non-terminating lambda expression. BY VALUE

4. Examine the following Java program and for each call, tell which method 
is the actual target of the call.

class A {  public z(E e) {...} }
class B extends A 
{  public void z(E e){...};
   public void z(F f) {...}'
}
class C extends A
{  public void z(F f){..}
class E{...}
class F extends E{...}

E e = new E();
F f = new F();
A a = new A();
A ab = new B();
A ac = new C();
B b = new B();
C c = new C();

a.z(e);//A.z
ab.z(e);//B.z(E)
ac.z(e);//A.z
b.z(f);//B.z(F)
b.z(e);//B.z(E)
c.z(f);//C.z(F)
c.z(e);//A.z
ac.z(f);//A.z