The power of Lists

[Keith Wright <kwright@xxxxxxxxxxxxxxxxxx>]

I was trying to think of a short example to show the
power of representing syntax as ordinary lists.  I wrote
the following simple recursive descent parser for arithmetic
expressions in infix form.  (No flames about the evil of infix
are needed, this is a short example not a proposed way of life.)

(define wall '#(wall))  ;; and end marker

(define (weight op)
   (if (eq? op wall)
       500
       (assoid op eq? table))

(define (assoid key == tab)
   (let look ((tab tab))
     (if (null? tab)
         (begin (display (list key " not found in " table)) (newline) #f)
         (if (== key (caar tab))
             (cdar tab)
             (look (cdr tab))))))

(define table '((:= . 8)(or . 7) (and . 6)
    (< . 5) (= . 4)(+ . 3)(* . 2)))  ;; sick of typing this, 
                                     ;; enough for an example

(define (parse tokens)

   (define (this) (if (null? tokens) wall (car tokens)))
   (define (next) (set! tokens (cdr tokens)))

   (define (get greed)
      (if (zero? greed)
          (let ((a (this)))
               (next)
               (if (list? (this))
                   (let ((arg (this)))
                       (next)
                       (list a (parse arg)))
                   (if (pair? a) (parse a) a)))
          (let ((a  (get (- greed 1))))
            (let more ((a a)
                       (op (this)))
                (if (< greed (weight op))
                    a
                    (begin
                       (next)
                       (let ((b (get (- greed 1))))
                          (list op a (more b (this))))))))))

   (get 10)) ; parse just primes the pump

This works with lists of symbols, and is easily tested since I can
read and write the output and input (respectively).
Then I changed it to work as a macro.  The change was very small,
just change |quote| to |syntax| in the table initialization:

(define table (syntax ((:= . 8)(or . 7) (and . 6)
                       (< . 5) (= . 4)(+ . 3)(* . 2))))

and use a different equality test when searching:

(define (weight op)
   (if (eq? op wall)
       500
      (assoid op free-identifier=? table)))

and add a macro to call it

(define-syntax arith
   (lambda (form)
      (parse (cdr form))))

a couple test cases

(arith 2 + 2 = 2 * (1 + 1))
  expands to: (= (+ 2 2) (* 2 (+ 1 1)))
  evaluates to: #t

(define (sqr x) (* x x))
(define three 3)

(arith three + sqr(5))
  expands to: (+ three (sqr 5))
  evaluates to: 28

So that all works, but it is the sort of thing that might
be assigned as an exercise to a student of Lisp 1.5.  I want to
show off the hygiene features.  As an old APL and Algol68 fan,
I pretend I like assignments that can be used as expressions.

(define-syntax (:= var x)
   (quasisyntax
     (let ((temp ,x))
       (begin (set! ,var temp) temp))))

(define x 0)
(arith (x := 8) + x * 2)
  expands to: (+ ((lambda (temp)
                    (set! x temp) temp) 8)
                 (* x 2)))
  evaluates to: 24

(Yes, I know it screws up if I have a Scheme that evaluates
 arguments to a procedure in a different order.  It screws up
 in Algol68 too, but stick with me.)

(display (list "x =" x ))
  displays: (x = 8)

So far so good, but unremarkable.  Now imagine I give my macro
to my friend the metorologist who uses it to calculate temperatures.
Ey writes:

(define temp 0)
(arith temp := 17)
  expands to: ((lambda (temp_local) (set! temp temp_local) temp_local)
               17))

(display (list "temp =" temp ))
  displays: (temp = 17)

Still no problem, but you all know the drill.  If I had used any previous
Lisp, the expansion would have been:

       ((lambda (temp) (set! temp temp) temp) 17))

which would have assigned 17 to the autogenerated local variable and had
no effect on the variable that the user sees.

Note that this is not a theoretical argument, it is a report on
what happens when I run these examples through the reference
implementation running under MzScheme (and presumable any other Scheme).
Only the expansions have been reformatted for deuglification.

I will not venture to assert that that such a thing is impossible
using syntax-rules, I am repeatedly amazed at what clever people
can do with twisted definitions, and I don't understand syntax-case
well enough to have any faith in my own opinions, but I will
say that it is not obvious to me how to do this with pattern matching,
because the arithmetic expression can be any length and nested
to any depth.

If it were done with some procedural macro system that represents
syntax as a special type, it could not have been tested on lists of
symbols, it would have been full of syntax->list and list->syntax
conversions in non-obvious places, and I just don't think it would
have been so much fun that I would have stayed up half the night
working on it, or finished it before morning.

-- 
     -- Keith Wright

Programmer in Chief, Free Computer Shop
 ---  Food, Shelter, Source code.  ---