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

Re: The power of Lists

This page is part of the web mail archives of SRFI 72 from before July 7th, 2015. The new archives for SRFI 72 contain all messages, not just those from before July 7th, 2015.

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