Cost of R5RS macros (was: Fyi.)

[jar@cs.cornell.edu (Jonathan Rees)]

- There is no requirement to expand COND, CASE, AND, OR, LET, LET*,
LETREC, DO, DELAY, or QUASIQUOTE into primitive expression types.  I
don't understand why you think this is necessary.  All that's needed
is for the interpreter to return the results of evaluation as
specified in the report.  Your interpreter can do with the derived
forms what it has been doing all along.  (I think I'm repeating
myself.)  The reason you don't see this in the existing
implementations is that it is more economical (less complicated) for
those implementations to interpret derived forms using rewrite rules,
not because there's some inherent reason to do so.  In particular,
note that Pseudoscheme handles LETREC directly while Scheme48 doesn't.

- DEFINE forms cannot "be inside several layers of LET and
LET-SYNTAXs" because LET and LET-SYNTAX forms are expressions, not
definitions.  This case is excluded by the grammar.

- You seem to think that macro expansion has to be done transitively
for all subexpressions before evaluation can precede.  This is false.
Scheme48 has (in addition to the byte-code compiler) a pure
interpreter that does R5RS macro expansion in the old-fashioned
interleaved manner.  It's so straightforward that I can't see how you
would learn anything from it - assuming you understand the basic idea
of R5RS macros, which I'm beginning to doubt.  Here's the main
dispatch:

    (define (run exp env)
      (cond ((name? exp)
	     (run-variable exp env))
	    ((pair? exp)
	     (cond ((name? (car exp))
		    (let ((den (lookup env (car exp))))
		      (cond ((operator? den)
			     ((interpreter-for-operator den) exp env))
			    ((transform? den)
			     (run (transform den exp (lambda (name)
						       (probe-env env name)))
				  env))
			    (else
			     (run-call exp env)))))
		   (else
		    (run-call exp env))))
	    ((literal? exp) exp)
	    (else (error "invalid expression" exp))))

Here "operator" means special operator (LAMBDA, QUOTE, etc.); the
third argument to TRANSFORM is only used by the comparison predicate
(for recognizing sub-keywords like ELSE).  This interpreter doesn't
handle LET-SYNTAX or LETREC-SYNTAX, but the modification to add these
would be simple - as in the POPL paper and Pseudoscheme, run the
output expression in an environment that specifies lookup of the
generated names in the environment of definition of the macro.

If results of expansions are cached, the expression tree will have to
be annotated at the point of the use of the macro to indicate that on
future evaluations the interpreter must set up the environment that
specifies how to get bindings of generated names.  Just off the top of
my head, I'd say the easiest way to represent these might be the way
that Pseudoscheme does, using unique id's.  Then note the lexical
distance (number of contours) from the current environment out to the
environment of the macro's definition.

  Expression tree at cached expansion has:
    . Unique id (generated at time of expansion and stored in every
      name generated by that expansion)
    . Lexical distance between macro use & macro definition
    . S-expression result of expansion

  "Diversion" environments have:
    . Expansion unique id
    . Parent lexical environment (environment of occurrence of macro
      form)
    . Lexical environment of point of definition of macro
      = (list-tail parent-env lexical-distance-to-macro-def)

  Generated names have:
    . Name (usually symbol) from which it was generated
    . Expansion unique id

Note that only macros defined with LET-SYNTAX or LETREC-SYNTAX really
need to set up diversion environment.  For DEFINE-SYNTAX-defined
macros, if you look up a generated name in an environment and don't
find any other binding of it, then just look up the original name in
the top-level environment.  This is how Scheme48 currently works.
It's not clear whether this would be faster or slower than creating a
diversion environment.

I'm sure there are many other ways to accomplish the same thing.  If
you like syntactic closures you will probably want to do something
very different.  If you only support SYNTAX-RULES then you may be able
to interpret macro templates more directly, as Will has hinted at.
You, as the software engineer, will have to figure out what will work
best in your system.

- You need an implementation of macros with certain properties.  You
will have to write it.  The fact that no one else has done your work
for you doesn't mean that the task is impossible.