The history of hygiene for definition contexts

[Alexis King]

Hi all,

I recently posted two tricky hygiene puzzles on Twitter, reproduced below for completeness:

    (let ([x 'outer])
      (define-syntax-rule (m a)
        (let ([a 'inner]) x))
      (m x))

    (let ([x 'outer])
      (define-syntax-rule (m a)
        (begin
          (define a 'inner)
          x))
      (m x))

The puzzle is to guess what these expressions evaluate to. I have discovered that people find the “correct” answer remarkably unintuitive—at the time of this writing, it is the single least popular choice in the poll!

Despite this confusion, the Scheme implementations I’ve tried are unwaveringly consistent in their interpretation of these expressions: Racket, Chez, and Guile all agree on what the answers should be. This has led me to wonder where the original justification for these answers comes from, but I have been struggling to hunt down a source.

Matthew’s 2016 paper, “Bindings as Sets of Scopes”, discusses examples like these ones in gory detail, but it gives no justification for why these results are the right ones, it simply takes their meaning for granted. Earlier papers on macro technology I have found do not discuss internal definitions, and no Scheme standard specifies the macro system, not even R⁶RS. Obviously, something at some point must have set the precedent for the handling of such macros, but I cannot figure out what it is.

So, my question: when was hygiene for internal definitions first worked out, and did it make it into any papers, specifications, or documentation? Hopefully someone (probably Matthew) can provide some insight.

Thanks,
Alexis

[Matthew Flatt]

At Wed, 28 Jul 2021 02:31:12 -0500, Alexis King wrote:
> So, my question: when was hygiene for internal definitions first worked
> out, and did it make it into any papers, specifications, or documentation?
> Hopefully someone (probably Matthew) can provide some insight.

As far as I know, "Macros that Work Together" was the first attempt to
pin down internal-definition contexts, at least in a form other than a
full macro-system implementation. (The R6RS chapter 10 approach is
mostly "don't do that".)


Matthew

[Eric Eide]

Alexis King <lexi....@gmail.com> writes:

> So, my question: when was hygiene for internal definitions first worked out,
> and did it make it into any papers, specifications, or documentation?
> Hopefully someone (probably Matthew) can provide some insight.

I saw an interesting talk about the history of hygenic macro technology at
HOPL-IV. I haven't read the paper, but maybe you might ;-).

William D. Clinger and Mitchell Wand. 2020. Hygienic macro technology.
Proc. ACM Program. Lang. 4, HOPL, Article 80 (June 2020), 110 pages.
DOI:https://doi.org/10.1145/3386330

Eric.

--
-------------------------------------------------------------------------------
Eric Eide <ee...@cs.utah.edu> . University of Utah School of Computing
https://www.cs.utah.edu/~eeide/ . +1 801-585-5512 . Salt Lake City, Utah, USA

[Michael Ballantyne]

Section 4.5 of Abdulaziz Ghuloum's PhD thesis is the earliest description I've seen of an algorithm: https://www.proquest.com/openview/f6a12fd14db7fd3ea85cfebbf72e0bc5

It also does not provide much justification.

The second example you give becomes more natural if you've considered simpler cases of macros in definition contexts first:

1. Macro-generated references may refer to locally defined names

(let ([x 'outer])

  (define x 'inner)

  (define-syntax-rule (m)

    x)

  (m))

2. Macros may abstract over define

(let ([x 'outer])

  (define-syntax-rule (m a)

    (define a 'inner))

  (m x)

  x)

3. Definitions splice out of begin, in order to allow macros to generate multiple definitions

(let ([x 'outer] [y 'outer])

  (define-syntax-rule (define2 a b)

    (begin

      (define a 'inner)

      (define b 'inner))

  (m x y)

  (list x y))

From there, your second example is a macro simultaneously abstracting over a definition and referring to a locally defined name.

[Alexis King]

On Thu, Jul 29, 2021 at 12:53 PM Michael Ballantyne <michael.b...@gmail.com> wrote:

The second example you give becomes more natural if you've considered simpler cases of macros in definition contexts first

I agree that breaking the macro into two parts—one of which inserts a binder and one of which inserts a reference—is the most compelling way to intuitively explain the behavior of the second expression. (And Shu-Hung previously posted the same observation on Twitter.) Still, it is interesting how many people find the result deeply unintuitive.

To understand why, it seems helpful to start from Clinger and Rees’ strong hygiene condition, which provides a high-level definition of what hygiene is supposed to mean:

1. It is impossible to write a high-level macro that inserts a binding that can capture references other than those inserted by the macro.

2. It is impossible to write a high-level macro that inserts a reference that can be captured by bindings other than those inserted by the macro.

The precise meaning of these criteria is not completely obvious, because the intended interpretation of the phrase “inserted by the macro” is not perfectly clear. However, the intended interpretation seems to be that a “macro-inserted” reference or binding is one for which the reference or binding identifier itself does not come from the macro’s inputs.

This naturally justifies the interpretation of the first expression, since by the above definition, the reference to x is macro-inserted, but the binder for x is not. This lines up with the results of the survey: programmers generally agree that the result of the first example ought to be 'outer.

The second example is trickier, as at first blush it clearly violates the second criterion of the hygiene condition: the macro-inserted reference to x is captured by the non-macro-inserted binder. However, I don’t think the applying the condition is quite so straightforward when recursive definition contexts are involved.

My reasoning starts with contemplating the meaning of a macro like

    (define-syntax-rule (define-false x)
      (define x #f))

in isolation. What makes macros like this unusual is that they introduce what one might call free binders by analogy to the notion of a free reference. The first criterion of the strong hygiene condition clearly always applies to macro-inserted bound binders, but it doesn’t always seem apply to free ones. Why?

Intuitively, this is because the scope of a bound binder fundamentally never contains the macro definition, which is the lexical location of any macro-inserted reference. This invariant is broken by definition contexts, where a free binder can eventually become bound in a scope that does contain the macro definition. It is precisely this ability for a macro’s use site to “retroactively” affect its definition’s scope that allows the macro-inserted reference to be captured.

In other words, I don’t think this is actually a violation of the hygiene condition because the macro-inserted reference is not actually “captured.” Rather, the nature of recursive definition contexts necessarily allows future definitions to affect earlier ones, and in this case, the future definition of x is in scope at the macro’s definition site, which means it must be in scope in the context of the macro-inserted x.

I think what’s so intuitively surprising about this essentially stems from two things:

1. After expansion, the macro-inserted reference to x appears after the internal definition, which means the binding structure of the expanded expression does not need to be recursive. A completely sequential structure would suffice, a la let*.

2. If definition contexts were in fact sequential, not recursive, the result of the second expression would in fact be 'outer. This is because the internal definition of x would not be in scope at the macro’s definition, so the macro-inserted x should not be able to see it.

It is this bait-and-switch that seems to trip people up. The fact that the macro-inserted reference appears after the internal definition in the expansion makes it seem as though the macro-inserted reference is being captured, but in fact it is not the structure of the expansion that matters, but rather the structure of the original program. Indeed, there is nothing special, magical, or broken about define itself, which introducing a scope between macro definition and macro use site cleanly illustrates:

    > (let ([x 'outer])
        (define-syntax-rule (m a)
          (begin
            (define a 'inner)
            x))
        (let ()
          (m x)))
    'outer

Anyway, this email has ended up rather long, so perhaps it would be better moved to a small blog post. But an explicit statement of the above reasoning is precisely the sort of thing I have been looking for but have not been able to find, so perhaps it will be useful to future readers.

Alexis