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

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

[Jean Abou Samra]

[-- Attachment #1: Type: text/plain, Size: 4142 bytes --]

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



[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

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

[Jean Abou Samra]

[-- Attachment #1: Type: text/plain, Size: 2478 bytes --]

Relatedly, R6RS is clear that an identifier matches a literal
in a syntax-case clause iff they're free-identifier=?, but as
far as I can see, it does not clarify how the literals themselves
in the syntax-case clause are recognized, namely what predicate
is used to match them against the literals list of the syntax-case
expression.

Test program:

(define-syntax build-syntax
  (syntax-rules ()
    ((_ expr expr* ...)
     (let-syntax ((temp-macro (lambda (ignored-syntax)
                                expr expr* ...)))
       (temp-macro)))))

(build-syntax
 (with-syntax ((foo1 (let ((foo 'foo)) #'foo))
               (foo2 (let ((foo 'foo)) #'foo)))
   (with-syntax ((foo1-foo2-free=? (free-identifier=? #'foo1 #'foo2))
                 (foo1-foo2-bound=? (bound-identifier=? #'foo1 #'foo2)))
     (syntax
      (begin
        (display "free-identifier=? ")
        (display foo1-foo2-free=?)
        (newline)
        (display "bound-identifier=? ")
        (display foo1-foo2-bound=?)
        (newline)
        (syntax-case #'not-foo (foo1)
          (foo2
           (display "Matched as literal\n"))
          (_
           (display "Not matched\n"))))))))


Guile 3.0:

free-identifier=? #f
bound-identifier=? #t
Matched as literal

Racket:

free-identifier=? #t
bound-identifier=? #t
Not matched

As you can see, foo1 and foo2 are *more* equal in Racket (also free-identifier=?
in addition to being bound-identifier=?), yet they don't match in Racket whereas
they do in Guile.


Chez Scheme gives the same identifier predicate results as Guile,
but it doesn't consider them matched:

free-identifier=? #f
bound-identifier=? #t
Not matched


Kawa somehow doesn't even handle the program:

free-identifier=? #t
bound-identifier=? #t
java.lang.NullPointerException: Cannot invoke
"kawa.lang.Translator.getCurrentSyntax()" because "tr" is null
	at kawa.lang.SyntaxPattern.match(SyntaxPattern.java:604)
	at kawa.lang.SyntaxPattern.match(SyntaxPattern.java:88)
	at tmp2.run(tmp2.scm:6)
	at gnu.expr.ModuleExp.evalModule2(ModuleExp.java:290)
	at gnu.expr.CompiledModule.evalModule(CompiledModule.java:42)
	at gnu.expr.CompiledModule.evalModule(CompiledModule.java:60)
	at kawa.Shell.runFile(Shell.java:571)
	at kawa.Shell.runFileOrClass(Shell.java:474)
	at kawa.repl.processArgs(repl.java:710)
	at kawa.repl.main(repl.java:830)


free-identifier=? #f
bound-identifier=? #t
Not matched


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

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

[Timothy Sample]

Hi Jean,

Jean Abou Samra <jean@abou-samra.fr> writes:

> 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)

FWIW, I tried this in my own pet expander, and got the following:

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

It’s a very simple expander that uses sets-of-scopes for hygiene.  As
such, they are not ‘bound-identifier=?’ since they can be distinguished
by the two different scopes introduced by the different invocations of
‘let’.  For ‘free-identifier=?’, they each resolve to different bindings
to the value ‘'bar’, so that’s a “no”.

Ultimately, I don’t think you can ask “who’s right?”  These predicates
answer questions about how a given expander distinguishes identifiers.
If two expanders distinguish identifiers differently, they should give
different answers!  However, I do agree that ‘bound-identifier=?’ should
imply ‘free-identifier=?’, so I don’t know what’s going on with Guile
and Chez.  (AIUI, their expanders are both based on psyntax, so I guess
it makes sense that they are similar.)  Also, Kawa is obviously wrong –
‘bound-identifier=?’ must imply “shadowed”.

May I ask why you are exploring this?  It’s quite arcane!

You could try and get in touch with Marc Nieper-Wißkirchen, the author
SRFI 211 (Scheme Macro Libraries) and Unsyntax
(https://gitlab.com/nieper/unsyntax).  Both of those projects suggest a
pretty thoroughgoing knowledge of Scheme macros.  I think Marc also
worked on getting ‘syntax-case’ into Chibi Scheme.

Lastly, you should read section 3.1 of “Binding as Sets of Scopes”:

    https://www-old.cs.utah.edu/plt/scope-sets/general-macros.html#%28part._.Identifier_.Comparisons_with_.Scope_.Sets%29

It shows that ‘bound-identifier=?’ gives false negatives in both
sets-of-scopes and marks-and-substitutions hygiene systems.  (I didn’t

test that example or anything, but I thought it fit the theme of
identifier predicate arcana pretty well.)


-- Tim

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

[Timothy Sample]

A quick follow-up.

Timothy Sample <samplet@ngyro.com> writes:

> Lastly, you should read section 3.1 of “Binding as Sets of Scopes”:
>
>     https://www-old.cs.utah.edu/plt/scope-sets/general-macros.html#%28part._.Identifier_.Comparisons_with_.Scope_.Sets%29
>
> It shows that ‘bound-identifier=?’ gives false negatives in both
> sets-of-scopes and marks-and-substitutions hygiene systems.  (I didn’t
>
> test that example or anything, but I thought it fit the theme of
> identifier predicate arcana pretty well.)

Actually, read section 3.2.  It covers your example exactly.  Discussing
the example

> (free-identifier=? (let ([x 1]) #'x)
>                    #'x)

it says,

> Note: Racket’s macro system matches Dybvig et al. (1993), where both
> free-identifier=? and bound-identifier=? produce #f for the above
> arguments, and bound-identifier=? always implies
> free-identifier=?. The current psyntax implementation, as used by Chez
> Scheme and other implementations and as consistent with Adams (2015),
> produces #f and #t for free-identifier=? and bound-identifier=?,
> respectively; as the example illustrates, bound-identifier=? does not
> imply free-identifier=?. The set-of-scopes system produces #t and #t
> for free-identifier=? and bound-identifier=?, respectively, and
> bound-identifier=? always implies free-identifier=?.

You can actually control what ‘free-identifier=?’ returns for the above
example using “scope pruning” when quoting syntax.  Those Racketeers
really have their act together....  :)


-- Tim

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

[Jean Abou Samra]

[-- Attachment #1: Type: text/plain, Size: 1852 bytes --]

Le jeudi 27 juillet 2023 à 16:10 -0600, Timothy Sample a écrit :
> A quick follow-up.
> 
> Timothy Sample <samplet@ngyro.com> writes:
> 
> > Lastly, you should read section 3.1 of “Binding as Sets of Scopes”:
> > 
> >    
> > https://www-old.cs.utah.edu/plt/scope-sets/general-macros.html#%28part._.Identifier_.Comparisons_with_.Scope_.Sets%29
> > 
> > It shows that ‘bound-identifier=?’ gives false negatives in both
> > sets-of-scopes and marks-and-substitutions hygiene systems.  (I didn’t
> > 
> > test that example or anything, but I thought it fit the theme of
> > identifier predicate arcana pretty well.)
> 
> Actually, read section 3.2.  It covers your example exactly.  Discussing
> the example
> 
> > (free-identifier=? (let ([x 1]) #'x)
> >                    #'x)
> 
> it says,
> 
> > Note: Racket’s macro system matches Dybvig et al. (1993), where both
> > free-identifier=? and bound-identifier=? produce #f for the above
> > arguments, and bound-identifier=? always implies
> > free-identifier=?. The current psyntax implementation, as used by Chez
> > Scheme and other implementations and as consistent with Adams (2015),
> > produces #f and #t for free-identifier=? and bound-identifier=?,
> > respectively; as the example illustrates, bound-identifier=? does not
> > imply free-identifier=?. The set-of-scopes system produces #t and #t
> > for free-identifier=? and bound-identifier=?, respectively, and
> > bound-identifier=? always implies free-identifier=?.
> 
> You can actually control what ‘free-identifier=?’ returns for the above
> example using “scope pruning” when quoting syntax.  Those Racketeers
> really have their act together....  :)


Oh, wow! I definitely need to read that paper. Thank you very much.

Cheers,
Jean




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

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

[Jean Abou Samra]

[-- Attachment #1: Type: text/plain, Size: 470 bytes --]

Le jeudi 27 juillet 2023 à 12:28 -0600, Timothy Sample a écrit :
> 
> May I ask why you are exploring this?  It’s quite arcane!

Because I am writing my own syntax expander :-)

(This is a school project, nothing serious. Still, formalizing the macro system
is kind of the whole point. I wanted to make sure I was getting it right, but
now I'm discovering that "right" is not a thing here :-).

Thanks for your links, I will read them.

Best,
Jean


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

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

[Timothy Sample]

Jean Abou Samra <jean@abou-samra.fr> writes:

> Le jeudi 27 juillet 2023 à 12:28 -0600, Timothy Sample a écrit :
>
>  May I ask why you are exploring this?  It’s quite arcane!
>
> Because I am writing my own syntax expander :-)

Nice!  Best of luck to you.  :)

> (This is a school project, nothing serious. Still, formalizing the
> macro system is kind of the whole point. I wanted to make sure I was
> getting it right, but now I'm discovering that "right" is not a thing
> here :-).
>
> Thanks for your links, I will read them.

One other one that I will point out is “Inferring scope through
syntactic sugar” by Justin Pombrio, Shriram Krishnamurthi, and Mitchell
Wand (https://dl.acm.org/doi/10.1145/3110288).  I didn’t get a ton out
of it (maybe I didn’t understand it!), but since you mentioned
formalizing, they give a more formal definition of variable scope
(section 3) that might interest you.


-- Tim