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:
- Turning (extended) lambda terms into De Bruijn notation
- Compiling De Bruijn terms into CES machine code (see attached
document)
- Writing the CES machine: its step function and running
code on the machine. (You may want a debugging mode!)
- 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:
- Built in Booleans: True and False together with an conditional
construct (if ... then ... else ...)
- Built in basic arithmetic: addition, multiplication, and
comparison of integers.
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.