John_K
John_K

Reputation: 114

Adding Macros in Scheme

For a college project we're working on learning scheme however we've been thrown into a difficult assignment with little knowledge. We're given certain functions like "'let", "'cond", "and'" etc. and asked to add macros.

(define eval
  (λ (e env)
    (cond ((symbol? e) (lookup-var e env))
          ((not (list? e)) e) ; non-list non-symbol is self evaluatory
          ;; special forms go here:
          ((equal? (car e) 'λ)      ; (λ VARS BODY)
           (let ((vars (cadr e)) (body (caddr e)))
             (list '%closure vars body env)))
          ((equal? (car e) 'if)
           (eval_ (if (eval_ (cadr e) env) (caddr e) (cadddr e)) env))
          ((equal? (car e) 'quote) (cadr e))
          ;; Add More Macros Here:
          ;; ((equal? (car e) 'let) xxx)
          ;;((equal? (car e) 'cond) xxx)
          ;;((equal? (car e) 'and) xxx)
          ;((equal? (car e) 'or) xxx)
          (else (let ((eeoe (map (λ (e0) (eval_ e0 env)) e)))
                  (apply_ (car eeoe) (cdr eeoe)))))))

So basically we're asked to fill in the blanks, where the ';;' comments are. I tried doing the 'cond part and got this

((equal? (car e) 'cond)
           (env (cdr e) env))

But I have no idea if it's correct (very little knowledge of scheme). Any help in figuring this out will be much appreciated. Thanks.

Upvotes: 0

Views: 94

Answers (1)

Sylwester
Sylwester

Reputation: 48745

It's not really macros but special forms you are adding. If you know that let is just syntax sugar for anonymous function call. eg.

(let ((a expr1) (b expr2)) body ...)

is supported in you evaluator already if you change and evaluate:

((lambda (a b) body ...) expr1 expr2)

To get you going let works like this:

(let ((bindings (cadr e))
      (body (cddr e)))
  (eval_ `((lambda ,(map car bindings) ,@body) ,@(map cadr bindings))))

Now real macros you would introduce a new type of %closure so that whenever you find it as operator you bind the symbols not their evaluation, run the evaluator on it as if it was a function, then do _eval on the result. Then instead of implementing cond and let you could just add a function on how to rewrite it down to something you already support. Thus you could make let like this:

((lambda (let)
   (let ((a expr1) (b expr2))
     (cons a b)))
  (~ (bindings . body) `((lambda ,(map car bindings) ,@body) ,@(map cadr bindings))))

It assumes you have quasiquote and map, but it could easily be implemented without these with more verbose code. ~ is just chosen randomly to be the macro version of λ. When evaluated it makes perhaps a %mclosure structure and you need to handle it specially to not evaluate its arguments, but evalaute the result. From that on you could support the special forms by having predefined %mclosure in the boot environment.

Upvotes: 1

Related Questions