Data-directed implementation of an evaluator [SICP]

user_12887145 0
Viewed 92

I'm solving SICP exercise 4.3 It's about writing a data-directed evaluator (eval procedure) instead of the one presented in section 4.1.1 of the book. The basic idea is to get the procedures used by eval from a table according to each type of expression instead of using conditions. The beginning of the eval procedure presented in the book is implemented as follows:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        [...]

And a data-directed version could be:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((get 'op (car exp)) exp env)
        [...]

Where all the cases besides self-evaluating? and variable? will be handled directly by get. This procedure is linked to a table with the required procedures (identified with 'op) and returns the procedure associated with the expression type (car exp).

The issue I was having is that some procedures have only one parameter ((text-of-quotation exp)) while others use two ((eval-assignment exp env)), so once (get 'op (car exp)) returns the appropriate procedure, I can't get the correct number of parameters (I'm already using two parameters with ((get 'op (car exp)) exp env).

One solution I found on the scheme wiki (here) does the following to handle getting the procedure and the parameters:

((get 'op (car expr)) (get 'op (car expr) expr env))

However, I don't understand at all how does the (get 'op (car expr) expr env) part will get the correct parameters to apply with (get 'op (car expr)).

I would really appreciate if someone could explain me how does this scheme wiki solution handles the parameters on that specific line of code, as it handles very elegantly the issue I'm having difficulties working around.

sicp mit-scheme scheme lisp
1 Answers

To my eyes some of the answers on the scheme wiki have potential issues. I think the solution that best answers your question is the one from Sphinxsky:

 (define (eval- exp- env) 
     (cond ((self-evaluating? exp-) exp-) 
         ((variable? exp-) (lookup-variable-value exp- env)) 
         (else 
             (let ((op (get 'eval (car exp-)))) 
                 (if op 
                     (op exp- env) 
                     (error "Unknown expression type -- EVAL" exp-))))))

First the 'operation' we're performing is evaluation so 'eval is used to indicate this (as the table could also contain arithmentic procedures).

(get 'eval (car exp-))

where (car exp-) will indicate the type of expression that needs to be evaluated (e.g., quote, define, begin, ...)

The code checks that an object (procedure) was returned and calls it with (op exp- env), as you say passing in two arguments exp- and env:

             ...
             (let ((op (get 'eval (car exp-)))) 
                 (if op 
                     (op exp- env) 
                     (error "Unknown expression type -- EVAL" exp-))))))

Nearly all the specialized evaluator take two arguments, and quotations might be the only exception. But that can be handled by having the quotation 'evaluator' take two arguments and simply ignoring the second, unused argument. Sphinxsky has done this here by installing a lambda that takes two arguments which then calls text-of-quotation with just one of them:

     (put 'eval 'quote 
         (lambda (exp- env) 
             (text-of-quotation exp-)))

As for BE's answer, I think it's missing a pair of paranthesis.

(cond
  ...
  ((get 'op (car expr)) (get 'op (car expr) expr env))
  ...

should be:

(cond
  ...                    v                  v          
  ((get 'op (car expr)) ((get 'op (car expr)) expr env))
  ...

If the first call of ((get 'op (car expr)) returns a value then we evaluate ((get 'op (car expr)) expr env) this results in repeating the lookukp, but we know it will return a value so:

((get 'op (car expr)) expr env)

becomes:

(<the-evalutor> expr env)

The double lookup is not ideal but Exercise 4.5 will show how this can avoided.

You may need to be a little cautious when reading answers for Chapters 4 and 5. For most of the previous chapters people will be posting code that they have run and so has been tested to some extent (the syntax is certainly correct). But, quite reasonably, not everybody will spend the time needed to write a full evaluator in order to run and and test their code, and so some of the answers are 'pencil and paper' code. Fwiw, My own solution is on github. I would probably do it differently now, but it does run.

user_532520
Related