Problem 1 { Scheme Programming
1. As we discussed in class, let and let* do not add anything to the ex-pressiveness of the language, i.e., they are only a convenient shorthand. For instance,
(let ((x v1) (y v2)) e) can be rewritten as ((lambda (x y) e) v1 v2).
How can you rewrite (let* ((x v1) (y v2) (z v3)) e) in terms of -abstractions and function applications?
2. Use the map and reduce functions we learned in class to implement function maxAbsoluteVal that determines the maximal absolute value of a list of integer numbers. Example
(define maxAbsoluteVal
(lambda (l)
... ))
...
(maxAbsoluteVal ’(-5 -3 -7 -10 12 8 7)) --> 12
Problem 2 { Lambda Calculus
Use / -reductions to compute the nal answer for the following -terms. Your computation ends with a nal result if no more reductions can be ap-plied. Does the order in which you apply the -reduction make a di erence whether you can compute a nal result? Justify your answer.
1. ((( x.x) ( x.28)) ( z.z))
1
2. (( x.(( z.(( x.(z x)) 2)) ( y.(* x y)))) 6)
3. (( z. (( y.z) (( x.(x x))( x.(x x))))) 11)
Problem 3 { Programming in Lambda Calcu-lus
In lecture 16 and 17, we discussed the encoding of logical constants true and false in lambda calculus, together with the implementation of logical operators.
1. Compute the value of ((and true) true) using -reductions.
2. De ne the or operator in lambda calculus. Prove that your de nition is correct, i.e., your lambda term for or implements the logical or oper-ation.
3. De ne the exor (exclusive or) operator in lambda calculus. Prove that your de nition is correct, i.e., your lambda term for exor \implements" the logical exor operation.
Problem 4 { Lambda Calculus and Combina-tors S & K
Let’s assume the S and K combinators:
Kxy.x
Sxyz.((xz)(yz))
Prove that the identify function I x.x is equivalent to ((S K) K), i.e.,
I SKK
2
