CPSC 521: Foundations of Functional Programming

Author: Robin Cockett
Date: 10 November 2014

Due:  24th November 2014

Assignment #3:  Evaluation with the CES Machine (aka. Modern SECD Machnine:

Implement an evaluator for the extended lambda calculus!

This involves the following steps:
  1. Turning (extended) lambda terms into De Bruijn notation
  2. Compiling De Bruijn terms into CES machine code (see attached document)
  3. Writing the CES machine: its  step function and running code on the machine.   (You may want a debugging mode!)
  4. Writing five example programs (including some recursive ones! e.g factorial) in the extended lambda calculus.
You are expected to work with the lambda calculus extended by:
This is described in more detail here: see section 3.1 on the modern SECD in particular.  These notes describe different reduction strategies, the modern SECD machine (including how to implement lists) and also the Krivine machine.