Honors Programming Languages
G22.3110 Spring 2009

Scheme programming Assignment
Due Wednesday, March 25

Your assignment is to implement a Scheme interpreter. The first thing you should do is understand the mini-scheme interpreter (click here) that is on the course web page. Then, rewrite a more complete interpreter from scratch (more or less). It should have all the features that I discussed in class, primarily define (including the special syntax for defining functions conveniently), lambda, if, cond, let, letrec, let*, and quote.

Important Note: The mini-interpreter will work fine in older versions of MzScheme, such as the one installed on the department machine. If you are downloading a new version of Scheme to your machine, I suggest using Petite Chez Scheme. See the link on the course web page.

In addition, you must also implement macros. These are functions that transform syntactic entities before they are evaluated. In particular, they take expressions (represented as atoms or lists) as arguments and return an expression as the result. The result expression is then evaluated.

Here is the syntax I want you to use:

(define-macro (<name > <param1> ... <paramn>)<body>)

When a macro is applied, the arguments are NOT evaluated. Rather the argument expressions are passed. The body then returns an atom or list, which is evaluated. For example,

(define-macro (strange-mult a b) (list '* a (list '- b 1)))

means that when you type

(strange-mult (+ 3 2) (+ x y))

a gets bound to the list (+ 3 2), b gets bound to the list (+ x y) , and the result of the macro is

(* (+ 3 2) (- (+ x y) 1))

This expression is then evaluated.

Notice that this syntax for macros is slightly different from that in mzscheme. In mzscheme, macros are generally defined by
(define-macro <name> (lambda (<param1> ... <paramn>) <body>))

Testing your interpreter

As a test of your interpreter, have your interpreter interpret itself. For example, here might be a session involving the interpreter interpreting itself interpreting the definition and use of the factorial function: 

> (load ``interpreter.scm'')     ;loading your interpreter into Scheme system

> (repl)                         ;invoking your interpreter

>> (load ``interpreter.scm'')      ;loading your intrepreter into your interpreter

>> (repl)                          ; invoking your 2nd interpreter

>> (define (fac x) (if (= x 0) 1 (* x (fac (- x 1)))))  ;defining factorial

>> (fac 4)                                              ;calling factorial

>> 24

>> (exit)                          ; exiting 2nd interpreter

>> (exit)                          ; exiting 1st interpreter

>                                ; back in scheme system


You should also demonstrate that your macro facility works.