Fresh syntax and unintentional capture Andre van Tonder 23 Jun 2006 10:18 UTC

As I tried to argue in SRFI 72, unless fresh syntax is the default,
it is easy to reproduce in syntax-case all the unintentional capture
problems that hygienic macros were invented to solve in  the first
place.

If we have to remember to use generate-temporaries in these cases,
that is equivalent to the old problem of remembering to
use gensym, which is no progress at all.

I have run into these capture problems with syntax-case, and they
can be extremely difficult to debug - probably more so than defmacro
where at least one expects them.

The problems do not occur only in library helpers, but also in
quite ordinary syntax-case macros.  In fact, the Chez Scheme COND
and CASE macros are almost wrong, as I discuss
below, but here are some simpler examples first:

   (let-syntax ((main (lambda (_)
                        (define (help) (syntax (list 1 2)))
                        (with-syntax ((rest (help)))
                          (syntax (let ((list +)) rest))))))
     (main))
             ==> 3       with conventional model
             ==> (1 2)   with fresh syntax default

   (let-syntax ((main (lambda (form)

                        (define (make-swap x y)
                          (quasisyntax
                           (let ((t #,x))
                             (set! #,x #,y)
                             (set! #,y t))))

                        (quasisyntax
                         (let ((s 1)
                               (t 2))
                           #,(make-swap (syntax s) (syntax t))
                           (list s t))))))
     (main))
               ==> (1 2) with conventional hygiene algorithm

As mentioned, the full COND and CASE macros in the Chez Scheme user's
guide are "almost wrong".  By this I mean that the template they follow
will lead to incorrect macros in general:

(define-syntax cond
   (lambda (x)
     (syntax-case x ()
       [(_ c1 c2 ...)
        (let f ([c1 #'c1] [cmore #'(c2 ...)])
          (if (null? cmore)
              .......
              .......
              (with-syntax ([rest (f (car cmore) (cdr cmore))])
                (syntax-case c1 (=>)
                  [(e0) #'(let ([t e0]) (if t t rest))]
                  [(e0 => e1) #'(let ([t e0]) (if t (e1 t) rest))]
                  [(e0 e1 e2 ...)
                   #'(if e0 (begin e1 e2 ...) rest)]))))])))

Since it introduces the same identifier t recursively in nested LET
forms, this macro is only "accidentally correct", since no
references to t occur further down in REST.  If any had, they could
have been captured.

This example is written in the same style as COND,
but turns out to be wrong due to unintentional capture:

   (define-syntax let-in-order
     (lambda (form)
       (syntax-case form ()
         ((_ ((i e) ...) e0 e1 ...)
          (let f ((ies (syntax ((i e) ...)))
                  (its '()))
            (syntax-case ies ()
              (()            (quasisyntax (let #,its e0 e1 ...)))
              (((i e) . ies) (with-syntax ((rest (f (syntax ies)
                                                    (cons (syntax (i t)) its))))
                               (syntax (let ((t e)) rest))))))))))

   (let-in-order ((x 1)
                  (y 2))
     (+ x y))
                ==> 4 (wrong)                   [with conventional algorithm]
                ==> Error: unbound identifier t [with fresh syntax]

The conventional model silently gives the wrong result due to unintentional
capture of nested references to t, since the above expands to

(let ((t 1))
   (let ((t 2))
     (let ((x t) (y t))
       (+ x y))))

These examples, based on real bugs I have encountered, illustrate that exactly
the kind of problem hygiene was invented to solve reappear in syntax-case.
There are some more examples in various versions of SRFI-72.

These issues were not relevant for SYNTAX-RULES, but
they should be addressed in a procedural system in a way that does not rely on
generate-temporaries, which is as unreliable as the old gensym macros.

Regards
Andre