Inconsistencies with free-identifier=? and bound-identifier=?

[Jean Abou Samra]

Hi,

Consider the following test program.

(define-syntax foo-test
  (lambda (sintax)
    (let ((foo1 (let ((foo 'bar))
                  (syntax foo)))
          (foo2 (let ((foo 'bar))
                  (syntax foo))))
      (display "free-identifier=? ")
      (display (free-identifier=? foo1 foo2))
      (newline)
      (display "bound-identifier=? ")
      (display (bound-identifier=? foo1 foo2))
      (newline)
      (with-syntax ((foo1 foo1) (foo2 foo2))
        (syntax
          (let ((foo2 'not-shadowed))
            (let ((foo1 'shadowed))
              (display foo2) (newline))))))))
(foo-test)


Result on Guile 3.0:

free-identifier=? #f
bound-identifier=? #t
4.5/home/jean/tmp/tmp.scm.go
shadowed



Result on Chez Scheme:

free-identifier=? #f
bound-identifier=? #t
shadowed



Result on Kawa:

free-identifier=? #t
bound-identifier=? #t
not-shadowed



Result on Racket:

free-identifier=? #t
bound-identifier=? #t
shadowed


Who's right?

First, it makes little sense in Kawa that bound-identifier=?
returns #t, yet foo1 does not shadow foo2. That seems like
it's contradicting the whole purpose of bound-identifier=?.

In Racket, they're said to be bound-identifier=? and shadowing
happens, which is at least consistent.

I don't understand why Racket and Kawa say they're
free-identifier=? . They clearly don't refer to the same
binding.

But putting that apart, is shadowing supposed to happen in the
first place?


R6RS-lib 12.5 page 54 says:

(bound-identifier=? id1 id2)

Id1 and id2 must be identifiers. The procedure bound-
identifier=? returns #t if a binding for one would capture
a reference to the other in the output of the transformer,
assuming that the reference appears within the scope of
the binding, and #f otherwise. In general, two identi-
fiers are bound-identifier=? only if both are present in
the original program or both are introduced by the same
transformer application (perhaps implicitly—see datum->
syntax). Operationally, two identifiers are considered
equivalent by bound-identifier=? if and only if they have
the same name and same marks (section 12.1).



As far as I understand, the marks of these two identifiers
are indeed expected to be the same, because marks are applied
on inputting a syntax object to a macro transformer and
receiving its output. foo1 and foo2 are both created and
used within the same macro transformer application, so
they bear no marks, so Guile and Chez are right.

On the other hand, I thought that bound-identifier=? implied
free-identifier=?, but that is not the case according to
Guile, Chez Scheme and this interpretation of R6RS. Yet this
is written on

https://www.scheme.com/tspl2d/syntax.html

Is that page incorrect?

In Dybvig's paper "Syntactic Abstraction in Scheme", which I think
historically introduced the algorithm used by most Scheme implementations
today, it is written on page 12

Two identifiers that are bound-identifier=? are also free-identifier=?, but
two identifiers that are free-identifier=? may not be bound-identifier=?.

https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-5-4-pp295-326.pdf

And later on page 24:

Two identifiers i1 and i2 are free-identifier=? if and only if resolve(i1 ) =
resolve(i2 ). Two identifiers i1 and i2 are bound-identifier=? if and only if
resolve(subst(i1 , i2 , s)) = s for a fresh symbol s.

Dybvig is among the editors of R6RS and that paper is cited in the R6RS
(reference [9] in r6rs.pdf).

If you look at the definition of the resolve and subst functions, the
definition of bound-identifier=? says that i1 and i2 are bound-identifier=?
iff they have the same marks *and they resolve to the same binding*.
Modulo possible shenanigans around things like #:rename for modules,
that sounds like it's equivalent to being "strict R6RS" bound-identifier=?
*and free-identifier=?*.

To me, that behavior is more intuitive.

Then, should this be considered a bug in the R6RS spec? Or a bug in the
paper?

(And is there a better place to discuss these things than this mailing list?)

Jean

signature.asc
Description: This is a digitally signed message part