HOP WPO 8
Assistant: Bjarno Oeyen (email@example.com)
Section 1: More About Evaluators
Exercise 1: Quick Fire Questions
- What are the three ways for expanding the metacircular evaluator?
- What are special forms? How are they different from procedures? How do you add support for them?
- What special forms are available in Scheme?
- What is the advantage of an analysing evaluator?
- What are the semantics of
- What is a continuation? What happens when you evaluate a continuation is applied on an argument.
Exercise 2: Add support for
Add support for the
while special form in the CPS evaluator. The following program shows an example of its usage.
Section 2: Scheme Lambda Calculus
You can download a Scheme file containing implementations of Church booleans and numbers from this link. You will have to add extra code to this file.
Exercise 3: Church to Scheme, Scheme to Church
Implement two procedures
scheme->church that convert church numbers to scheme numbers.
Hint! How is a church number applied. How many arguments does it expect? What does it do with these arguments?
Exercise 4: Equal to zero?
Write a predicate in \(\lambda\) calculus to check whether a number is zero.
Extra question: Scheme helps you by adding the name of a procedure when it is printed to the REPL. If you would see
#<procedure> in both cases, how would you verify whether it returned the true procedure, or the false procedure?
Exercise 5: Fixpoint combinator
The following is a definition of a fixpoint combinator for Scheme.
Test the behaviour of this fixpoint combinator by implementing
almost-fib, which implements a fibonacci using the fixpoint combinator, without making use of church booleans and church numbers.
Exercise 6: Actual Factorial
Implement factorial, by using Church numbers and booleans.
Hint! Start by converting the
if condition to an expression in \(\lambda\) calculus. And then think how to pass the consequent and alternative branches to this boolean. Note the difference between applicative order, and normal order!
Hint! Make use of
zero? from exercise 4.
Bonus Exercise 1: The
repeat special form.
Recommended after exercise 2
repeat, which is inspired by the earlier implemented
while special form, but expects a tuple containing a variable name, and a total amount. Index starts from zero.
Bonus Exercise 2: Fibonacci
Recommended after exercise 6.
Implement fibonacci using church numbers and booleans.
Hint! You might need to implement a procedure to check whether a number is equal to 1, can you repurpose your solution from exercise 3?
It is different from the one seen in class, since it has issues with the evaluation rules of Scheme. Scheme is applicative order (first evaluate arguments, then body), Lambda Calculus is normal order (only evaluate arguments when needed). Thus the fixpoint combinator for Scheme is different. ↩︎