[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: The power of Lists

Hi Keith,

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.

I liked your example so much I decided to put in the conversions.

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

The first change is that the table isn't syntax, but a list.
You defined the table as

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

although it is only the identifiers are syntax-objects in
this context. (Btw - that's an example of "breaking the abstraction")
The assocations from identifiers to weights can be written directly as:

(define table `((,#':= . 8) (,#'or . 7) (,#'and . 6)
                (,#'< . 5)  (,#'= . 4)  (,#'+ . 3) (,#'* . 2)))

or if you prefer your way better, then the a syntax->list
must be added, since table needs to be a list.

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

These versions will work in both macro systems.

The definitions of assoid and weight requires no changes.

(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 (weight op)
  (if (eq? op wall)
      (assoid op free-identifier=? table)))

The routine parse is changed to be a function which
takes a list of syntax-objects representing sub-expressions
as input.

Since parse is recursive and calls it selv with a subexpression
(which now is syntax-object) we let parse convert a syntax-objects
representing lists into lists of syntax-objects automaticcally.
I.e. the body of parse is changed from (get 10) into
(if (syntax? tokens) (parse (syntax->list tokens)) (get 10)).

Since your version uses list? and pair? to check whether a
subexpression is a compound expression, we need stx-list?
and stx-pair? when checking for compund subexpressions.

(require (lib "stx.ss" "syntax"))  ; for stx-list? and stx-pair?

; parse : (list stx) -> stx
(define (parse tokens)
  ; this : -> stx
  (define (this) (if (null? tokens) wall (car tokens)))
  (define (next) (set! tokens (cdr tokens)))

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

  (if (syntax? tokens)
      (parse (syntax->list tokens))
      (get 10))) ; parse just primes the pump

(parse #'((1 + 2) * 3))

Jens Axel Søgaard