Expanding macros

[jar@zug.AI.MIT.EDU (Jonathan Rees)]

Allow me sketch out a more robust way to write a macro expander.  Among
other problems, I note that your FULLY-EXPAND-MACRO won't work with
syntax tables, like the Scheme syntax table, in which the standard
special form names don't have their standard meanings.

(define expand
  (let ((quote-syntax  (syntax-table-entry standard-syntax-table 'quote))
	(lambda-syntax (syntax-table-entry standard-syntax-table 'lambda))
	(labels-syntax (syntax-table-entry standard-syntax-table 'labels))
	(if-syntax     (syntax-table-entry standard-syntax-table 'if))
	... Must handle all primitive special forms.  These are enumerated
	    in EVAL.T.  There aren't very many. ...
	)
    (lambda (exp syntax-table)
      (iterate recur ((exp exp))	;is there a RECUR macro?
	(if (not (pair? exp))
	    exp
	    (let ((descriptor
		   (cond ((symbol? (car exp))
			  (syntax-table-entry syntax-table (car exp)))
			 ((syntax-descriptor? (car exp))
			  (car exp))
			 (else nil))))
	      (cond ((not descriptor)	;Combination?
		     (let ((new-exp (map recur exp)))
		       (if (and (symbol? (car new-exp))
				(syntax-table-entry standard-syntax-table
						    (car new-exp)))
			   `((block ,(car new-exp)) ,@(cdr new-exp))
			   new-exp)))
		    ((eq? descriptor quote-syntax)
		     `(quote ,(cadr exp)))
		    ((eq? descriptor lambda-syntax)
		     `(lambda ,(cadr exp) ,@(map recur (cddr exp))))
		    ((eq? descriptor labels-syntax)
		     `(labels ...))
		    ((eq? descriptor if-syntax)
		     `(if ,@(map recur (cdr exp))))
		    ...
		    ((macro-expander? descriptor)
		     (recur (expand-macro-form descriptor exp syntax-table)))
		    (else
		     (error "Unknown special form -- ~S" exp)))))))))

Except for error checking, this is the way one should generally write
code walkers for T, for the time being.

This expander is idempotent in the sense that
  (expand E ST)
and
  (expand (expand E ST) standard-syntax-table)
should give the same result.  I think that's about as well as you can do.
It's impossible in general to make a full macro expander with the property
(expand E ST) is the same as (expand (expand E ST) ST).

The expansion code for combinations tries to deal with the case where
a program uses the name of a standard T special form or macro as a
variable.  E.g. the Scheme form (ITERATE X Y) should be treated as a
combination, but it would be a use of a macro according to T's
standard-syntax-table.  If T had a CALL special form (does it?) then
it would of course be cleaner to say (CALL ITERATE X Y) than
((BLOCK ITERATE) X Y).

For non-pairs, you probably ought to employ the syntax table's
atom-expander, but I think that feature might not be released.  Look
at EVAL.T or Orbit's front end to see what they do.

This code-walker is relying on the fact that in T the syntax and
variable namespaces are distinct.  That may change, especially if the
syntactic closures proposal is adopted.

I haven't run this code, so it is quite likely to have bugs.