Writing an Eval Procedure in Scheme?

Question

My problem isn't with the built-in eval procedure but how to create a simplistic version of it. Just for starters I would like to be able to take this in '(+ 1 2) and have it evaluate the expression + where the quote usually takes off the evaluation.

I have been thinking about this and found a couple things that might be useful: Unquote: , (quasiquote) (apply)

My main problem is regaining the value of + as a procedure and not a symbol. Once I get that I think I should just be able to use it with the other contents of the list.

Any tips or guidance would be much appreciated.

Answer 1

Firstly, if you're doing what you're doing, you can't go wrong reading at least the first chapter of the Metalinguistic Abstraction section of Structure and Interpretation of Computer Programs.

---

Now for a few suggestions from myself.

The usual thing to do with a symbol for a Scheme (or, indeed, any Lisp) interpreter is to look it up in some sort of "environment". If you're going to write your own eval, you will likely want to provide your own environment structures to go with it. The one thing for which you could fall back to the Scheme system you're building your eval on top of is the initial environment containing bindings for things like +, cons etc.; this can't be achieved in a 100% portable way, as far as I know, due to various Scheme systems providing different means of getting at the initial environment (including the-environment special form in MIT Scheme and interaction-environment in (Petite) Chez Scheme... and don't ask me why this is so), but the basic idea stays the same:

(define (my-eval form env)
  (cond ((self-evaluating? form) form)
        ((symbol? form)
         ;; note the following calls PCS's built-in eval
         (if (my-kind-of-env? env)
             (my-lookup form env)
             ;; apparently we're dealing with an environment
             ;; from the underlying Scheme system, so fall back to that
             ;; (note we call the built-in eval here)
             (eval form env)))
        ;; "applicative forms" follow
        ;; -- special forms, macro / function calls
        ...))

Note that you will certainly want to check whether the symbol names a special form (lambda and if are necessary -- or you could use cond in place of if -- but you're likely to want more and possibly allow for extentions to the basic set, i.e. macros). With the above skeleton eval, this would have to take place in what I called the "applicative form" handlers, but you could also handle this where you deal with symbols, or maybe put special form handlers first, followed by regular symbol lookup and function application.