From posting-system@google.com Thu Jan 29 04:34:30 2004
Date: Wed, 28 Jan 2004 20:30:54 -0800
From: oleg-at-pobox.com
Newsgroups: comp.lang.scheme
Subject: First-class macros: pattern-match at run-time
References: <buub2n$lda$1@la.iki.fi> <1xpoq5e4.fsf@comcast.net> <f95e8bea.0401271557.3ea2d052@posting.google.com> <401756A9.6297E664@sonic.net> <f95e8bea.0401281252.74284018@posting.google.com> <bv9dlu$9fo$2@camelot.ccs.neu.edu>
Message-ID: <7eb8ac3e.0401282030.289a1eab@posting.google.com>
Status: OR

Matthias Felleisen wrote in message news:<bv9dlu$9fo$2@camelot.ccs.neu.edu>...
> Since macros (thank you!) don't exist at run-time, what can it 
> mean to say "macros are first-order". I don't know, and I agree that an 
> explanation would really be appreciated.


In this article we shall show that macros do exist at run-time. Macros
-- that is, syntax transformers and syntax objects -- can be stored in
variables, passed to ordinary procedures and applied at run-time. We
show three examples. The last one uses exclusively syntax-rules and is
specifically written not to contradict R5RS in any way. The example
runs on Scheme48, Petite Chez Scheme, SCM, and Gauche. The last
example demonstrates using the pattern-matching machinery of
syntax-rules at run time.

The first hint that macros may exist at run time comes from Gambit, whose
source code contains the following definitions:

> (define-runtime-macro (define-macro pattern body . rest)
>   `(##define-macro ,pattern ,body ,@rest))
>
> (define-runtime-macro (namespace . rest)
>   `(##namespace ,@rest))


Our second example relies on a portable macro-expander by Dybvig, Hieb
at el. We use Petite Chez Scheme to run the following code.

Petite Chez Scheme Version 6.0a
Copyright (c) 1998 Cadence Research Systems

> (syntax-rules () ((_ x) 1))
#<procedure>

Quite interesting: it seems that syntax-rules is a regular
procedure...

However, this procedure needs syntax objects. We need at least one
syntax object (we can make others with datum->syntax-object). Here we
go:

(define a-syntax-object #f)
(let-syntax
  ((set-syntax-object
     (lambda (x)
      (syntax-case x ()
         ((_) 
	   (begin (set! a-syntax-object #'_) #'#f))))))
  (set-syntax-object))

> a-syntax-object
#3(syntax-object
   set-syntax-object
   ((#f top)
    shift
    #4(ribcage #1(set-syntax-object) #1((top)) #1("i"))
    #4(ribcage ((import-token . *top*)) ())))

It seems we have succeeded in capturing a syntax value and storing it
in a regular variable.

We can now make other syntax objects

(define (syntaxize x)
  (datum->syntax-object a-syntax-object x))

> (syntaxize (list 1 2 3))
#3(syntax-object
   (1 2 3)
   ((#f top)
    shift
    #4(ribcage #1(set-syntax-object) #1((top)) #1("i"))
    #4(ribcage ((import-token . *top*)) ())))

It seems to be working.

We define an ordinary procedure that applies a pattern to a target at
*run-time*.

(define (run-time-match pattern target)
  (syntax-object->datum (pattern (syntaxize target))))

Let us see how it works:

(define (test-match target)
  (let ((pattern 
        (syntax-rules ()
         ((_ x) one)
	 ((_ x y) (one one))
	 ((_ x ...) (more (token x) ...)))))
   (run-time-match pattern target)))

(display (test-match (list '_ 1))) (newline)
prints> one


(display (test-match (list '_ 1 2))) (newline)
prints> (one one)

(display (test-match (list '_ 'a 'b 'c))) (newline)
prints> (more (token a) (token b) (token c))


It seems everything is working as if syntax transformers and syntax
values were indeed first-class. We can pass them to procedures, store
in variables, bind to variables, return from procedures... By
extensionality (a.k.a. the duck test) syntax objects are first class.


Finally, we do not need to rely on syntax-case to do syntax operations
(in particular, pattern matching) at run-time. R5RS already gives us
all the needed tools.

(define (compile-pattern name pat)
  (eval
    `(define-syntax ,name
	(syntax-rules ()
	  ,pat))
     (interaction-environment)))

(define (apply-pattern name target)
   (eval `(,name ,@target) (interaction-environment)))

(compile-pattern 'foo (list '(_ (x ...) (y ...)) ''((x y) ...)))

(display (apply-pattern 'foo (list (list 10 20 30) (list 1 2 3))))

prints the desired result
	((10 1) (20 2) (30 3))

The example was tested on Scheme48, Petite Chez Scheme, SCM, and
Gauche -- each of which has an independently-written macro-expander.