Programming Languages Concepts

Homework 5:

We will allow late homework for up to only one day with 10% penalty

this time, as I want to release a solution soon after the due date to help

students prepare for the second midterm.

Submission: Please submit your homework via Canvas. It’s okay if you

submit a scanned version of your on-paper answers, but please make sure

your scanned version is legible.

1. (5 points) For the lambda-calculus term (λx. λy. x) (λz. y).

(a) (2 point) Calculate its free variables using the FV function. Show

the steps.

(b) (2 point) Use lambda calculus reduction to reduce the expression

to a normal form. Begin by renaming bound variables and show

every step.

(c) (1 point) Describe what would go wrong if you did not rename

bound variables.

2. (3 points) Reduce the following lambda-calculus term to the normal

form. Show all intermediate steps, with one beta reduction at a time.

In the reduction, assume that you are supplied with extra rules that

allow you to reduce the addition of two natural numbers into the corresponding results.

(λf. λx. f (f (f x))) (λy. y + 2) 2

3. (3 points) The Algol-like program fragment

function f(x)

return x+5

end;

function g(y)

return 2-y

end;

f(g(2));

1

can be written as the following lambda expression:

?

(λf. λg. f (g 2)) (λx. x + 5)?

(λy. 2 − y)

Reduce the expression to a normal form. In the reduction, assume

that you are supplied with extra rules that allow you to reduce the

addition or subtraction of two natural numbers into the corresponding

results.

2