## CS 5314: Concepts of Programming Languages Spring 2016 Study Homework: Lambda Calculus and Virtual Method Problems

1. Evaluate the following lambda expressions. Note: we use "^" to denote lambda here.

• (((^x.^y.(y x)) (^p.^q.p)) ^i.i)

• (((^h.((^a.^f.(f a)) h)) h) ^f.(f f))

• ((((^f.^g.^x.(f (g z))) ^s.( s s)) ^a.^b.b) ^x.^y.x)

2. Analyze the following lambda-expressions and tell which variables are
free or bound in each expression.

• ^x.^y.(^x.y ^y.x)

• ^x.(x (^y.(^x.x y) x))

• ^a.(^b.a ^b.(^a.a b))

• ^p.^q.(^r.(p ^q.^p.(r q)) (q p))

3. Give an example of a lambda expression that would evaluate differently if we used call-by-value versus call-by-name. Do not use any examples from the class notes as your answer!

4. Examine the following Java program and for each call, tell what 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 ff = 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);
ab.z(e);
ac.z(e);
b.z(f);
b.z(e);
c.z(f);
c.z(e);
ac.z(f);
```

last changed at 12:08pm on April 25, 2016 BGR