Homework 02
Put all code for this homework in hw02.rkt.
Implement the Lambda calculus
In this section you will write functions in Scheme that evaluate lambda calculus expressions. Start by skimming the Wikipedia page on Lambda calculus.
1) In the Wikipedia page on Lambda calculus, read the section on Logic and Predicates.
Then translate the lambda terms for TRUE, FALSE and NOT into Scheme.
To get you started, here's TRUE written in the style I recommend:
(define TRUE
(lambda (x)
(lambda (y)
x)))
Notice two things
a) I am using the lambda form of function definition, not the fancy syntactic sugary form.
b) I am writing a function of two parameters as a function of one parameter that returns a function of one parameter. (See currying).
Now you write FALSE and NOT. If you get it right, then
(NOT TRUE) ;should yield FALSE, and
(NOT FALSE) ;should yield TRUE.
Chances are, you'll get procedures as return values, but Scheme might not recognize them as FALSE and TRUE.
The following function might help:
; boolean: take a boolean and return the
; canonical true or false value
(define boolean
(lambda (p) ((p TRUE) FALSE)))
But don't go on until you understand what it is doing. Really.
2) Now translate AND, and try
((AND TRUE) FALSE)
((AND TRUE) TRUE)
3) Ok, now translate OR and test it with
(boolean ((OR TRUE) FALSE))
(boolean ((OR FALSE) FALSE))
4) And then translate IFTHENELSE and test it with
(((IFTHENELSE TRUE) TRUE) FALSE)
(((IFTHENELSE FALSE) TRUE) FALSE)
But be forewarned that the natural Scheme implementation of IFTHENELSE is a "greedy" version that evaluates both branches.
This will turn out to be a problem later.
5) Translate the definitions for ZERO and SUCC, and then compute
(define ONE (SUCC ZERO))
6) Translate ISZERO and confirm that (ISZERO ZERO) is TRUE and (ISZERO ONE) is FALSE.
7) Now compute
(define TWO (SUCC ONE))
The result is a procedure, but we have the same problem we had with booleans: it is not easy to see which
number is represented by a given Church numeral.
Write a function called (integer) that takes a Church numeral and returns the corresponding Scheme number. You will use this procedure to convert from Church numerals to numbers, so you can use Scheme operators like (+).
Then run
(integer ZERO)
(integer ONE)
(integer TWO)
And see if you get the right thing.
8) Translate PLUS and compute
(define THREE ((PLUS ONE) TWO))
(integer THREE)
9) Translate MULT and compute
(define SIX ((MULT TWO) THREE))
(integer SIX)
9a) If you are having fun, translate the other form of MULT and EXP, but we won't need them.
10) Translate PRED and compute
(define FIVE (PRED SIX))
(integer FIVE)
10a) If you are having fun, translate the other form of PRED.
11) Translate PAIR, FIRST and SECOND, then test
(define X ((PAIR ONE) TWO))
(integer (FIRST X))
(integer (SECOND X))
Note: take some time to think about how these work. It might help to know that the parameters of CONS stand for first, second and boolean. Also, think about what the boolean values are; that is, what do they do?
Question: when you build a pair, where (ultimately) are the elements of the pair stored?
12) Translate NIL (which represents an empty pair) and NULL? (which is a boolean that returns TRUE for NIL and FALSE for any other PAIR).
(NULL? NIL) should return TRUE
(NULL? X) should return FALSE
Fun with higher-order functions
For these you can use as much of Scheme/Racket as you like, not just the lambda calculus subset. Credits: the following two exercises are from Lynn Stein's implementation of FOCS
1) Write a procedure called (repeatedly) that takes two arguments---(func), a procedure of one argument, and n, a number of times to apply (func)---and returns a function of one argument that applies (func) n times.
(define incr
(lambda (x) (+ 1 x)))
((repeatedly incr 3) 6)
9
For each of the following expressions, compute the value in your head, then run it and check:
((repeatedly (lambda (x) (* x x)) 3) 2)
((repeatedly (repeatedly incr 4) 5) 200)
2) Write a procedure called (repeatedly-until) that takes a procedure (f) of one argument and a procedure (test) of one argument, and returns a function of one argument that repeatedly applies (f) until (test x) evaluates to true (where x is the result of applying f). The function returned by (repeatedly-until) should return the value of x that make (test x) true.
> ((repeatedly-until incr (lambda (x) (= (remainder x 10) 0))) 346)
350