[racket] metacircular interpreter: hygiene, lexical variable, and substitution ==> Re: recursive macro expanding order

YC wrote:
> On Sat, Dec 11, 2010 at 2:49 PM, YC <yinso.chen at gmail.com> wrote:
> 
>> On Sat, Dec 11, 2010 at 8:56 AM, Ryan Culpepper <ryanc at ccs.neu.edu> wrote:
>>
>>> If you are only supporting syntax-rules, then I recommend implementing the
>>> algorithm from "Macros that Work" by Clinger and Rees. Hygienic macro
>>> expansion does typically involve alpha-conversion---renaming lexical
>>> variables to fresh names. The challenge, as you mention above, is in not
>>> renaming too eagerly.
>>
> Looking at the paper, it occurred to me that one way to ensure that macro
> expands to the correct binding is for the macro to carry the references to
> the environment itself.
> 
> So for the example in the paper:
> 
> (let-syntax ((push (syntax-rules
>                        ((push ?v ?x)
>                         =>
>                         (set! ?x (cons ?v ?x))))))
>   (let ((pros (list "cheap" "fast"))
>         (cons (list)))
>     (push "unreliable" cons)))
> 
> 
> The push macro already contains the bindings to set! and cons, so the later
> shadowing of cons does not overwrite push's own copy of cons.  In that sense
> a macro transformer's job is to merge its own environment along with the
> call-site's environment.
> 
> The key to correctly implement macros is then to ensure that every macro
> holds references to a environment at the point of its definition, so it can
> then be used for merging during the expansion.
> 
> Is this a fair way of thinking about macro expansions?

Not quite. There might not be a single environment for the macro. This 
can happen if the macro definition itself (in particular, the macro's 
template) is introduced by some other macro. It is possible to have a 
macro definition contain two occurrences of the same symbol that refer 
to different bindings.

Beyond that, they should also be treated differently if used as binding 
occurrences. It is a common trick when limited to syntax-rules to 
construct a list of fresh names by recursively adding the same symbol to 
an accumulator list. Since each occurrence of the symbol is introduced 
by a different macro step, they're all different for the purpose of binding.

(define-syntax with-fresh-names
   (syntax-rules ()
     [(with-fresh-names () names k k-arg)
      (k names k-arg)]
     [(with-fresh-names (thing . rest) names k k-arg)
      (with-fresh-names rest (tmp . names) k k-arg)]))

You might decide that instead of each macro closing over its 
environment, each subterm of the template must close over its 
environment. That gets you to the *syntactic closures* macro system 
(also in SLIB). Long story short, it's effectively impossible to use. 
IIRC, the critical mistake of syntactic closures is assuming that the 
common case is that a macro knows the complete environment of its input 
subexpressions. That's true of the 'or' macro (hygiene test case #1), 
but it makes writing new binding forms difficult.

If you take syntactic closures and relax the notion of "environment" to 
instead be "what seems to be the environment, given the expander's 
current state of knowledge" and adjusting the syntax representation and 
expander accordingly, you get the Dybvig-Hieb-Bruggeman algorithm ("the 
syntax-case algorithm").

Ryan