Reference no: EM132580755
CSE 461 Programming Languages Concepts Assignment - Pennsylvania State University, USA
1. 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 multiplication of two natural numbers into the corresponding result.
(λf. λx. f(f x)) (λy. y *3)2
2. For the lambda-calculus term (λx. λy. y x) (λz. y).
(a) Calculate its free variables using the FV function. Show the steps. Note that "y x" stands for a function application applying y to x.
(b) Use lambda calculus reduction to reduce the expression to a normal form. Begin by renaming bound variables and show every step.
(c) Describe what would go wrong if you did not rename bound variables.
3. Answer this question based on the following Algol-like program fragment:
function f(x)
return x-3
end;
function g(y)
return 4+y
end;
f(g(10));
(a) We learned in class that function declarations like the ones in this program are just syntactic sugar. Convert the above program into an equivalent lambda-calculus term.
(b) Reduce the lambda-calculus term 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.