[plt-scheme] a couple of questions

On Fri, 12 Jan 2007, Gregory Woodhouse wrote:

> I'm trying to write an evaluator in the style of SICP that I hope will be at 
> least somewhat idiomatic.

Hi Greg,


Did you get any responses about this yet?  Let's take a look.

... ok.  You may be able to avoid mutation here.  Let's look at a portion 
of the code:

      (let loop ()
        (with-handlers ...
          (printf "~a " main-prompt)
          (set! input-val (read))
          ...))


Here is a let loop here with no variables being bound.  Every time through 
the loop, though, we're rebinding input-val.  This idea can be captured by 
making the input-val a part of the loop's variables:

      (let loop ([input-val (begin (printf "~a " main-prompt)
                                   (read))])
        (with-handlers (...)
          ...))

Since we're going to be doing prompting quite a bit, we can then pull that 
prompting code up as a separate function.  I'll just call it READ-PROMPT 
for now:

   (define (read-prompt)
     (printf "~a " main-prompt)
     (read))


After this, the program looks a little bit more like:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (let loop ([input-val (read-prompt)])
     (with-handlers
         ((exn:fail:user?
           (lambda (exn) (printf "Error!~n") (loop (read-prompt)))))
       (if (not (eof-object? input-val))
           (begin
             (printf "~a~n~n" (eval-strict input-val env))
             (loop (read-prompt)))
           (printf "~a~n" exit-message))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



> 1. I don't want to break out of the loop when evaluating an expression 
> like (/ 1 0) but instead report the error and then give the user an 
> opportunity to enter another expression, leaving the environment intact. 
> But, of course, I do want to break out of the loop in case of a 
> programming error on my part, so my handler for exn:fail:user includes 
> (loop) (where loop is the label in named let). I've never encountered 
> code like this, and I wonder if it's even safe, much less idiomatic 
> scheme.

It looks ok to me.  I think it can be better, though.  You could probably 
push the exception handling closer to the expression that's likely to 
cause havoc, the eval-strict function.

Let's wrap eval-strict with a helper function SAFE-EVAL-STRICT, which 
we'll introduce within the LOOP definition.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (let loop ([input-val (read-prompt)])
       (define (safe-eval-strict input-val evn)
         (with-handlers
             ((exn:fail:user? (lambda (exn) (printf "Error!~n")
                                (loop (read-prompt)))))
           (eval-strict input-val env)))
       ...)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



And now the rest of RUN's body looks like:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       (if (not (eof-object? input-val))
           (begin
             (printf "~a~n~n" (safe-eval-strict input-val env))
             (loop (read-prompt)))
           (printf "~a~n" exit-message)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


In fact, we can do better: SAFE-EVAL-STRICT can be simplified: it can just 
return the string "Error!~n" as a value.

   ;; safe-eval-strict: expression environment -> value
   (define (safe-eval-strict input-val evn)
     (with-handlers
         ((exn:fail:user? (lambda (exn) "Error!")))
       (eval-strict input-val evn)))

The effect that the user sees should be the same.  We can even push the 
definition of SAFE-EVAL-STRICT up and out of our LOOP, since it no longer 
refers to the LOOP function.


Here's what this all looks like, with all those changes:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module evaluator mzscheme
   ;some global definitions (never modified)
   (define evaluator-name "Strict Evaluator")
   (define evaluator-version "0.0.1")
   (define main-prompt ">>")
   (define exit-message "Goodbye!")

   ;; eval-strict: expression environment -> value
   (define (eval-strict exp env)
     (raise-user-error 'oops))

   ;; safe-eval-strict: expression environment -> value
   (define (safe-eval-strict input-val evn)
     (with-handlers
         ((exn:fail:user? (lambda (exn) "Error!")))
       (eval-strict input-val evn)))

   ;; read-prompt: -> expression
   (define (read-prompt)
     (printf "~a " main-prompt)
     (read))

   ;; run: -> void
   (define (run)
     (printf "~a (version ~a)~n" evaluator-name evaluator-version)
     (let ([env '()])
       (let loop ([input-val (read-prompt)])
         (if (not (eof-object? input-val))
             (begin
               (printf "~a~n~n" (safe-eval-strict input-val env))
               (loop (read-prompt)))
             (printf "~a~n" exit-message))))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



> 2. The second question involves the environment, which I anticipate 
> storing as a list or perhaps a hash table.  To me, it makes more sense 
> for the evaluator to return an updated environment as a value than to 
> have it modify a global value.

Yes.  Also, just as in the case with INPUT-VAL, the environment is a value 
that's probably going to follow along in the looping: it might be 
appropriate to pass that around as well.  The structure of RUN can turn 
into:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (define (run)
     (printf "~a (version ~a)~n" evaluator-name evaluator-version)
     (let loop ([input-val (read-prompt)]
                [env '()])
       ...))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

And now LOOP is actually starting to look a little bit like, well...

http://download.plt-scheme.org/doc/360/html/r5rs/r5rs-Z-H-9.html#%_idx_600



> But it also seems that this style could involve a lot of unnecessary 
> copying.

It really depends on how you define environments and how you extend them. 
It's possible to define them so that you take advantage of shared 
structure.  That is, rather than a mutable hashtable, you can choose a 
representation that reuses the existing environment structure.

You can see some of this in SICP under "Operations on Environments":

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1.3

where "frames" can chain off of other frames.  In that case, the only 
stuff that's being allocated are new bindings.


Good luck!