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
