[plt-scheme] And now for an actual Scheme question (PLAI)

From: Gregory Woodhouse (gregory.woodhouse at sbcglobal.net)
Date: Thu Jul 17 02:24:46 EDT 2008

I've been away from scheme for awhile, so I decided to go back to  
PLAI and start reading from the beginning

  I implemented the predicate AE? (for arithmetic expressions) like this

   ;;pattern based evaluator (language: AE)

   (define (AE? exp)
     (match exp
       ((? number? exp) #t)
       ((list '+ (? AE?) (? AE?)) #t)
       ((list '- (? AE?)) #t)
       ((list '- (? AE?) (? AE?)) #t)
       ((list '* (? AE?) (? AE?)) #t)
       ((list '/ (? AE?) (? AE?)) #t)
       (else #f)))

So far, so good, but if I follow the model in the book (minus the use  
of type-case, which doesn't seem to be part of PLT Scheme) I end up  
with something like this

(define (evaluate exp)
   (with-handlers
       ((exn:fail:user?
         (lambda (exn) (printf "~a~n" exn))))
   (match exp
     ((? number? exp) exp)
     ((list '+ (? AE? t1) (? AE? t2)) (+ (evaluate t1) (evaluate t2)))
     ((list '- (? AE? t1) (? AE? t2)) (- (evaluate t1) (evaluate t2)))
     ((list '* (? AE? t1) (? AE? t2)) (* (evaluate t1) (evaluate t2)))
     ((list '/ (? AE? t1) (? AE? t2))
      (let
          ([ n (evaluate t1)]
           [d (evaluate t2)])
        (if (equal? d 0)
            (raise-user-error "division by zero")
            (/ n d))))
     (else (raise-user-error "Unable to evaluate expression" exp)))))


Now, on the face of it, this seems awfully wasteful because I'm  
repeating all the pattern matching that I had to go through to  
identify an expression as an AE in the first place. My next step was  
going to be parsing the expression into a bunch of tagged elements  
(so I'd only need to read the tag).  For example (+ 2 3) would be  
parsed as (('builtin '+) ('num 2) ('num 3)).

Now, I kind of suspect that all this redundant pattern matching  
wouldn't really slow things down much (because the computations would  
be cached), but this hardly seems a very nice way to write the code.

So, I guess I'm asking whether this analysis is reasonable. Using  
match seems to be an elegant way of writing an evaluator. It is  
certainly more compact than a chain of conditionals, but it seems to  
introduce a lot of extraneous computation.

(Oh, if you're wondering about the use of with-handlers, I've wrapped  
this all in a REPL loop, and I don't want to be kicked out because of  
a typo or division by zero or some such thing.)

"The most incomprehensible thing about the world is that it is at all  
comprehensible."
  --Albert Einstein (1879-1955)

http://www.gwoodhouse.com
http://GregWoodhouse.ImageKind.com





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080716/48e3f914/attachment.html>

Posted on the users mailing list.