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

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Thu Jul 17 11:08:50 EDT 2008

Gregory Woodhouse wrote:

> 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.

I've worked through PLAI using match. I abandoned Shriram's parse 
function and just used S-expressions directly, plus structures where 
necessary (for instance, in the representation of closures). Here's my 
interpreter for "basic arithmetic expressions", with some tests.

#lang scheme
;; grammar:
;; <bae> ::= <num>
;;           | (+ <bae> <bae>) | (- <bae> <bae>)
;;           | (* <bae> <bae>) | (/ <bae> <bae>)

(define (interp exp)
   (match exp
     [`(+ ,l ,r) (+ (interp l) (interp r))]
     [`(- ,l ,r) (- (interp l) (interp r))]
     [`(* ,l ,r) (* (interp l) (interp r))]
     [`(/ ,l ,r) (/ (interp l) (interp r))]
     [(? number? n) n]
     [x (error 'interp "no interpretation for ~a" x)]))

(= (interp 4) 4)
(= (interp '(+ 3 4)) 7)
(= (interp '(* 3 4)) 12)
(= (interp '(* (+ 1 2) (+ 3 4))) 21)

Now, this is heretical, but I discussed it with Shriram, and he didn't 
immediately excommunicate me. The benefits are clarity and brevity. The 
drawback, besides giving up all the nice safety features that John and 
Eli described, is a blurring of the distinction between textual code and 
abstract syntax trees. I thought it was a valuable exercise. I did my 
best to write the interpreters without looking at Shriram's code, only 
reading the text. I will try this approach with some students this fall 
(not covering all of PLAI, only the first few interpreters) and see how 
it goes. --PR

Posted on the users mailing list.