Homework 03

Put all code for this homework in hw03.rkt.

You will want to be able to access some of the procedures in hw02.rkt from hw03.rkt. To do that, add a line like this at the top of hw02.rkt

(provide TRUE FALSE ZERO ISZERO SUCC PRED MULT IFTHENELSE integer)

And a line like this at the top of hw03.rkt

(require "hw02.rkt")

The Y Combinator

No, not the startup incumbator, the original Y combinator!

Skim the Wikipedia page. Then skim this page by John Franco.

1) Follow the steps in Franco's article and write a nameless version of (fact) and (findmax) using the Y combinator.

2) Make your implementation of (fact) completely nameless by replacing the numbers with Church numerals and the operators with the appropriate operators for Church numerals.

Here are some steps you might want to follow:

a) If you try to write a recursive function using IFTHENELSE, you will discover that it recurses forever. The reason is that Racket evaluates expressions in applicative order, which implies that it evaluates the arguments before it evaluates the body.

So if you have a procedure named INFINITY that recurses forever, the following will not work:

(((IFTHENELSE TRUE) ONE) INFINITY)

However, we can simulate normal order evaluation using thunks. In Racket the simplest way to implement a thunk is like this:

(lambda (thunk) EXPRESSION)

There is nothing special about the identifier thunk; you could have put any identifier there. Now EXPRESSION is protected from evaluation until we "force" the thunk by applying it:

((lambda (thunk) EXPRESSION) ANYTHING)

The result is EXPRESSION. This is useful because we can evaluate

(lambda (thunk) INFINITY)

Without recursing forever.

Now, write a procedure called (LAZYIF) that takes a boolean expression and two thunks, selects one of the thunks, forces it, and yields the content of the thunk. So

(((LAZYIF TRUE) (lambda (thunk) ONE)) (lambda (thunk) (INFINITY ZERO)))

should return ONE (and never try to evaluate INFINITY).

b) Make a copy of F* called F! and replace all the numbers and operators with Church numerals and procedures. Invoke

((Y F!) FIVE)

and confirm that the resulting Church numeral is equivalent to 120.

c) Now write out the expanded version of (Y F!).

d) Replace all the remaining names with their definitions (one at a time, test after each one, and be prepared to revert).

To facilitate automated testing, please name the final, nameless version of factorial (nameless-factorial), and add this line somewhere in hw03.rkt

(provide nameless-factorial)

Scheme to lambda

Optional preview of parsing and code generation: Write a procedure (to-lambda) that takes a quoted Scheme expression and returns a string representing the expression in lambda calculus.