Scheme programming Assignment

Due Monday, October 23

Implement a Scheme interpreter. The first thing you should do is understand the mini-scheme interpreter that I gave you in class. 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 > <param₁> ... <param_n>)<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.

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.