[r6rs-discuss] [Formal] Internal define-syntax lexical scoping violation

From: Abdulaziz Ghuloum <aghuloum>
Date: Tue Oct 24 09:21:02 2006

On Oct 23, 2006, at 3:54 PM, AndrevanTonder wrote:
>
> Suggestion:
> -----------
>
> Perhaps lexical scoping with internal define-syntax can be better
> handled by a multipass expansion algorithm instead of single-pass. On
> each pass, the expansion process would restart, using syntax
> definitions discovered on previous passes, until no more syntax
> definitions are discovered.
> It seems that such an algorithm would give the result 1 above. The
> implied reprocessing of forms, however, may cause problems with macros
> that update expand-time state (e.g. record definitions).

No. Multipass expansion, as you describe it, is ambiguous. Suppose
that I change your example slightly so that the outer bar is a macro
(defined externally), not a lexical variable:

      (let ()
        (bar x)
        (define-syntax bar
          (syntax-rules ()
            ((bar x) (define x 1))))
        x)

The expander, upon entering the body of the let, sees three forms:
   (bar x)
   (define-syntax bar ---)
   x

The current algorithm specifies that the forms are processed
*left-to-right*. You propose (let me repeat what I understand just to
double check my understanding) that the expander should expand and
evaluate the second form to discover that |bar| is actually this
locally defined macro, and then expand the call to (bar x). So,
discovering the (define-syntax bar ---) first makes the whole
expression equivalent to:
   (let ()
     (define x 1)
     x)
which evaluates to 1 as you said.

Now my expander has a different heuristic for picking which form to
process first, so I pick (bar x). Now (bar x) expands to something
"unnatural" that defines x to be 2 and redefines define-syntax to mean
something else. When I come to process the (define-syntax bar ---)
next, it expands to 17 instead of defining bar. So, discovering (bar
x) first makes the whole expression equivalent to:
   (let ()
     (define x 2)
     17
     x)

Therefore, the proposed expansion algorithm is ambiguous.

Aziz,,,

PS: Did you implement this algorithm?

PPS: implementation of bar follows.

(library F
   (export bar)
   (import r6rs syntax-case)
   (define-syntax bar
     (lambda (x)
       (syntax-case x ()
         [(_ t)
          (with-syntax ([kwd (datum->syntax #'_ 'define-syntax)])
            #'(begin
                (define-syntax kwd (lambda (stx) 17))
                (define t 2)))]))))
Received on Tue Oct 24 2006 - 09:20:54 UTC