[Pika-dev] macro hygeine vs. Oleg

[Tom Lord]

Someone recently called my attention to:

        "How to write seeming unhygienic and referentially opaque
        macros with syntax-rules" Oleg Kiselyov; The Workshop on
        Scheme and Functional Programming (2002).


available via a link from:

        http://library.readscheme.org/page3.html


I think that this paper does not show what it claims to show:

        This paper details how folklore notions of hygiene and
        referential transparency of R5RS macros are defeated by a
        systematic attack.

On the contrary, I think that the paper:

  a) demonstrates a bug in some implementation of R5RS macros

  b) highlights how the specification of SYNTAX-RULES could
     be more clearly stated

Perhaps, though, I have badly misunderstood something so I thought I'd
briefly present my reasoning and see what people have to say.

The paper elaborates on a single conceptual trick:  using macros that
expand (in part) to macro definitions to thwart hygiene.   

For example, normally, if I define a macro MY-MACRO whose expansion
contains the literal identifier FOO used as a free variable reference,
then those uses of FOO in the expansion refer to the binding FOO had 
lexically at the point where MY-MACRO is defined.

Thus, for example, in:

        (let ((foo 42))
          (my-macro))

the binding of FOO enclosing the macro-use of MY-MACRO has no effect
on the meaning of MY-MACRO.

Through exhaustive macrology, Oleg would have us redefine binding
constructs in such a way that:

        (let ((foo 42))
          (my-macro))

expands to something like:

        (let ((foo 42))
          (let-syntax ((my-macro (syntax-rules () <rules>)))
            (my-macro)))

so that with each new scope, MY-MACRO is effectively redefined and
a free use of FOO in the definition of MY-MACRO will, indeed, be
captured by the enclosing LET.

I claim that no such macro-producing-macro redefinition of binding
constructs is possible.  It will (in a correct implementation) not
work as Oleg suggests.  Free uses of FOO in <rules> will not be
captured.

As support for that, here is what R5RS says in section 4.3.2:


      Identifiers that appear in the template but are not pattern
      variables or the identifier `...' are inserted into the output
      as literal identifiers. If a literal identifier is inserted as a
                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      free identifier then it refers to the binding of that identifier
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      within whose scope the instance of `syntax-rules' appears. 
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      [....]

      (emphasis added)


Let us suppose that <rules>, in the example above, is produced by an
expansion of another macro and that it contains a literal FOO.  It is
ambiguous at the time the LET-SYNTAX clauses is produced but is
disambiguated in the fully expanded code that the FOO in that "other
macro" is used as a free identifier.  Therefore,
_even_in_the_template_ <rules>, it carries its meaning as denoting the
binding of FOO _in_the_scope_of_the_original_macro_.  A free-use of
FOO in the macro-produced-macro-template <rules> is _not_ supposed to
be captured by the surrounding LET.  Implementations which allow to be
captured have a bug: they expanded a free variable reference
incorrectly.

I don't think it's even all that difficult for implementations to get
this case right.  For example, in the course of working on Pika
Scheme, I've introduced the concept of a "first class binding" -- a
reification of the mapping between an identifier and its denotation.
During expansion, these function similarly to the "aliases" or
"synthetic identifiers" of Reese and Kelsey's "lexical closures" macro
implementation, but without the need for first-class lexical closures.

Very briefly, in the "original macro", the very first one to introduce
FOO, occurences of FOO in the template are replaced by first-class
bindings.  As expansion proceeds: FOO references that expand into
denotations of symbols denote the symbol 'FOO; free references in
expansion (even recursive expansion of macros defined by macros) refer
to the original binding; bound references generate a new "synthetic
identifier" describing the same symbol but a new binding.  Oleg's
tricks simply wouldn't work with my expander.

(In the Pika source, see src/scm/notes/spec for details about my 
expansion rules, first class bindings, and related issues.)

-t