Description
Problem 1 { Scheme Programming
-
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?
-
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
-
(( x.(( z.(( x.(z x)) 2)) ( y.(* x y)))) 6)
-
(( 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.
-
Compute the value of ((and true) true) using -reductions.
-
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.
-
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
