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

YC wrote:
> Hi all -
> 
> continuing the metacircular interpreter topic, at this point I am looking at
> the hygiene issue.  Without trying to implement a full solution that include
> syntax and identifier objects, it seems that hygiene can be addressed via
> just substituting lexical identifiers introduced during the expansion
> process.
> 
> It seems doable to me because:
> 
>    - the non lexical identifiers all have to resolve to an existing binding
>    in the transform environment or throws compilation error - so they don't
>    need special handling
>    - since the interpreter will expand all parsed code, the substitution
>    process can be ensured to be unique so there are no name conflicts
>    (capturing or being captured)
>    - basically lambda is the only place that I am introducing lexical
>    binding (maybe case-lambda as well once I get to it), so substitution is
>    localized - what I need is to ensure that it's not too aggressive and ending
>    up substituting variables introduced by nested expressions
> 
> The above basically automates CL's gensym approach to hygiene AFAICT.
> 
> I am sure this has been tried before - does anyone see/know of issues with
> the substitution approach above?  Any ideas are appreciated, thanks,
> yc

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.

If you're looking for code, SLIB has implementations of several hygienic 
macro expanders, including the one from "Macros that Work". SLIB does 
not run in Racket (mostly because it does not respect Racket's 
separation of phases), but you might be able to extract and port the 
code you need, or use it as inspiration.

Ryan


> On Wed, Dec 8, 2010 at 12:19 PM, YC <yinso.chen at gmail.com> wrote:
> 
>> Thanks Robby!
>>
>>
>> On Wed, Dec 8, 2010 at 4:13 AM, Robby Findler <robby at eecs.northwestern.edu
>>> wrote:
>>> PS: check out this paper for an algorithm:
>>>
>>>  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8909
>>>
>>> Robby
>>>
>>> On Wed, Dec 8, 2010 at 6:11 AM, Robby Findler
>>> <robby at eecs.northwestern.edu> wrote:
>>>> Yes, outside in. Inside out doesn't work because the expander only
>>>> knows where the inside is when it sees a core (fully expanded) form.
>>>>
>>>> Robby
>>>>
> 
> 
> ------------------------------------------------------------------------
> 
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users