Honors Programming Languages
G22.3033.03 Fall 2005

Scheme programming Assignment
Due Monday, October 31

Your assignment is to implement a Scheme interpreter. The first thing you should do is understand the mini-scheme interpreter 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.

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.