Friday, March 25, 2005

Hygiene is weirder than referential transparency

Referential transparency (despite its damned awful, confusing, misleading name) is a simple concept: whatever existing bindings a macro definition makes reference to should never be violated, no matter how the macro is used. End of story.

But hygiene is weirder, for two reasons. First, new bindings introduced by a macro don't really exist until the macro is used, and then they should be totally new every time it's used. Because the macro template is really just that--a template, not actual code--it represents any number of instantiations of itself, and consequently any number of new bindings. And hygiene means that when these new--as of yet non-existent--bindings are created, they can't violate existing bindings in the call site.

Second, hygiene in Scheme is particularly weird because we don't even know which identifiers are binding occurrences until we fully expand a macro, so various macro expansion algorithms have to retroactively apply or revert renamings once expansion is complete! This is what Ryan refers to as the "decay" model, where hygienic renamings are invertible.