Macros and internal definitions in Scheme

Question

A good question was asked on Freenode's #scheme channel. Consider the following code in Scheme:

(define alpha 1)

(define-syntax foo
  (syntax-rules (quote alpha)
    ((_ alpha msg) (define bar 2))
    ((_ other msg) (syntax-error msg)) ) )

(define (beta)
  (foo alpha "beta")
  (define alpha 3)
  'beta )

(define (gamma)
  (define alpha 4)
  (foo alpha "gamma")
  'gamma )

(define (delta alpha)
  (foo alpha "delta")
  'delta )

Which ones of beta, gamma, and delta should produce syntax errors? And which do? I have checked this with Chibi Scheme where beta is fine while gamma and delta fail. I wonder whether this is an intended behavior or just a bug in Chibi.

According to the standard, it seems that expanding the macros should happen before the internal definitions get rewritten into letrec*. So beta and gamma should both fail as foo will match with an internally defined alpha, not the global one.

However, it is not explicitly specified in the standard how internal definitions actually work, only that they can be thought of as a letrec shortcut. I get the same behavior with Racket's R5RS, so it seems that I am missing something in the standard that demands such behavior.

In R6RS (psyntax based impl), I get the same behavior when calling the procedures. — leppie, Sep 26 '14 at 07:40

John Clements · Answer 1 · 2014-09-24T16:08:30.120

Okay, I finally understand your question. Running your code was challenging, because you appear to have a 'syntax-error' function that signals a syntax error only if it winds up in fully-expanded code. Whatever.

I think the answer to your question is this:

These Scheme guys (Dybvig, Felleisen, Hieb, Clinger, Rees, Wand, Flatt, Culpepper, etc.) are pretty smart!

In particular, somehow Scheme/Racket manages to figure out how the binding structure works even when it doesn't know what's going to be a binding or not. You're right! That's crazy! But the algorithm outlined by Dybvig et al. does some very clever things to ensure that hygiene tracks whether identifiers are "free-identifier-equal" or "bound-identifier-equal" (Flatt's terminology) even when it doesn't yet know which one binds the other. I personally recommend reading "Macros That Work Together" (Flatt, Culpepper, Darais, Findler) for a better understanding of this.

Apologies if I've misunderstood your question, or if my tone is inappropriate!

Is there a good reference or tutorial, accessible by beginner students, that explains how define-syntax and syntax-rules work? The explanation given in the R5RS standard is not too understandable, for example. — Kim Mens, Mar 21 '23 at 15:02
I would point you to Matthew Butterick's "Beautiful Racket". It's a good piece of work. https://beautifulracket.com/ — John Clements, Mar 23 '23 at 04:25

score 1 · Answer 2 · answered Feb 09 '15 at 15:33

Might be a bit too much depending on implementation side but this behaviour is because of order of macro expansion. Theoretically, all definitions contains alpha so it shouldn't match with the one in literal keywords. However, macro expansion needs to be done before define forms are expanded to letrec*, otherwise compiler can't detect internal definition properly. So at that moment, compiler may or may not see the bindings. (The macro expansion timing is not specified on R7RS, so implementation may choose own timing as well.)

For the beta case, compiler didn't catch the binding so macro expander still can see that alpha is the same binding as global one. The other cases are other way around.

score 0 · Answer 3 · answered May 29 '15 at 14:50

First of all, delta is out (should not match alpha) because it clearly lexically binds alpha to another binding than the one under which your sytnax-rules appears. The interesting ones are beta and gamma.

As per section 5.2.2. of R4RS (p. 13) and R5RS (p. 16), section 5.3.2. of R7RS (p. 26), and section 11.3. of R6RS (p. 32), the "region" of a binding established through an internal definition is the entire <body> in which the definition appears. And your macro call to foo is clearly within the same <body> as those internal definitions.

R7RS also goes a little further and warns us:

Note that such a body [i.e. one which contains internal definitions] might not be apparent until after expansion of other syntax.

So the messed up order of events is admitted, but there is no ambiguity; your syntax-rules should not match the alpha branch if there's a binding for alpha by any internal definition in the same <body> as the call to the macro. Therefore, beta and gamma are out as well.

Appendix A

If we complicated the situation further, and your macro itself conditionally bound alpha, like

(syntax-rules (alpha)
  ((_ alpha x) (define alpha x)))

then it seems truly ambiguous at first thought, but I believe this is solved through the fact that the macro expander will rename the defined alpha identifier as per hygiene, meaning we would not be shadowing the alpha which we are matching as a literal, so matching it is fine, and the above will simply create a binding for a renamed alpha that's unreachable outside the macro body.

Appendix B

There is a constraint in the end of section 5.3. of R5RS (p. 17), the end of section 5.4. of R7RS (p. 26), and the middle of section 10. in R6RS (p. 30), which mention that a sequence of definitions shall not contain a definition which changes the meaning of any of them. (It's actually a little more complicated, all three standards using different wording, but that should be a reasonable summary.)

In your example, it is not clear to me whether the possibility of your syntax-rules expanding to a syntax error counts as an ambiguation of its "meaning." If one considers it an ambiguation, then your beta and gamma are "errors" (undefined behavior) as per R5RS and R7RS, and a "syntax violation" as per R6RS.

If your example contained another binding in the second branch of your syntax-rules (ideally a definition for the same variable even), then this nitpick would not apply, so your question stands.

Macros and internal definitions in Scheme

3 Answers3