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.

Answer 1

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!

Answer 2

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.