« Return to index


Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

Section 1: More About Evaluators

Exercise 1: Quick Fire Questions

  1. What are the three ways for expanding the metacircular evaluator?
  2. What are special forms? How are they different from procedures? How do you add support for them?
  3. What special forms are available in Scheme?
  4. What is the advantage of an analysing evaluator?
  5. What are the semantics of call-with-current-continuation?
  6. What is a continuation? What happens when you evaluate a continuation is applied on an argument.

Exercise 2: Add support for while

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 church->scheme and 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[1].


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 Exercises

Bonus Exercise 1: The repeat special form.

Recommended after exercise 2

Implement 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?

  1. 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. ↩︎