bug#16158: psyntax: bug in bound-identifier=?

bug#16158: psyntax: bug in bound-identifier=?

[Mark H Weaver]

While reading psyntax.scm, I noticed that the definition of 'bound-id=?'
does not match the definition in "Syntax Abstraction in Scheme" by
Dybvig, Hieb, and Bruggeman.

The paper states "Two identifiers that are bound-identifier=? are also
free-identifier=?".  The following expression shows that this is not the
case in Guile 2.0:

  (let* ((x 1) (s1 #'x)
         (x 2) (s2 #'x))
    (list (bound-identifier=? s1 s2)
          (free-identifier=? s1 s2)))
  => (#t #f)

Racket reports (#f #f) for the same expression.

According to the paper, two identifiers are 'bound-id=?' if and only if
they resolve to the same binding name (gensym) and have the same marks
(i.e. they were both introduced by the same macro instantiation, or
neither were introduced by a macro).  However, the implementation in
'psyntax.scm' does not compare the binding names (gensyms); it instead
compares only the symbolic names.

      Mark

bug#16158: psyntax: bug in bound-identifier=?

[Mark H Weaver]

Fixed in stable-2.0, commit 70c74b847680d3b239e591afa2e99c51a712980c

    Mark

bug#16158: psyntax: bug in bound-identifier=?

[Marco Maggi]

Mark H Weaver wrote:
> While reading psyntax.scm, I noticed that the definition of 'bound-id=?'
> does not match the definition in "Syntax Abstraction in Scheme" by
> Dybvig, Hieb, and Bruggeman.
>
> The paper states "Two identifiers that are bound-identifier=? are also
> free-identifier=?".

I think you are referring to this paragraph from the paper[1] (page 12):

    Two    identifiers   that    are   bound-identifier=?     are   also
    free-identifier=?,  but two  identifiers that  are free-identifier=?
    may not be bound-identifier=?.  An  identifier introduced by a macro
    transformer may refer to the same enclosing binding as an identifier
    not introduced by the transformer, but an introduced binding for one
    will not capture references to the other.

> The following expression shows that this is not the case in Guile 2.0:
>
>   (let* ((x 1) (s1 #'x)
>          (x 2) (s2 #'x))
>     (list (bound-identifier=? s1 s2)
>           (free-identifier=? s1 s2)))
>   => (#t #f)

  The expander in Ikarus/Vicare also returns this value.

> Racket reports (#f #f) for the same expression.

  Racket is different because its expander implements a variant of phase
separation; if the whole form is evaluated  at phase N, the "x" in "#'x"
should be searched  among the bindings at  phase N-1 (if any)  (I am not
authoritative  in  how Racket  works,  there  is always  something  that
escapes me).   Your code  works, but  when you actually  try to  use the
identifiers for something:

    #!r6rs
    (import (rnrs))
    (define-syntax doit
      (lambda (stx)
        (let* ((x 1) (s1 #'x)
               (x 2) (s2 #'x))
          #`(let ((#,s1 123))
              #,s2))))
    (doit)

$ plt-r6rs ~/var/tmp/proof.sps
/home/marco/var/tmp/proof.sps:7:23: x: identifier used out of context
  in: x
  context...:
   /opt/racket/5.3.5/lib/racket/collects/r6rs/run.rkt: [running body]

while the  same program  works fine in  Ikarus, Vicare,  Sagittarius and
Guile (Larceny's  opinion would  be interesting,  but I  do not  have it
installed).  IMHO this program should work for Racket, too, but maybe it
refuses to  run code that "looks  wrong" (indeed, usually, in  a correct
program we do not define identifiers this way).

  I dunno how  Guile's evolution of psyntax works, but  the two #'x must
be bound-identifier=? because the following result must stand:

    (define-syntax doit
      (lambda (stx)
        (let* ((x 1) (s1 #'x)
               (x 2) (s2 #'x))
          #`(let ((#,s1 123))
              #,s2))))

    (doit) => 123

  IMHO it  is an  error in  the paper.  Some  paragraphs from  the paper
preceding "the  one" have been recycled  in the R6RS document,  but this
one paragraph has not; maybe this means something.

HTH

[1] <http://www.cs.indiana.edu/~dyb/pubs/LaSC-5-4-pp295-326.pdf>
-- 
"Now feel the funk blast!"
Rage Against the Machine - "Calm like a bomb"

bug#16158: psyntax: bug in bound-identifier=?

[Mark H Weaver]

Hi,

Marco Maggi <marco.maggi-ipsu@poste.it> writes:
> Mark H Weaver wrote:
>> While reading psyntax.scm, I noticed that the definition of 'bound-id=?'
>> does not match the definition in "Syntax Abstraction in Scheme" by
>> Dybvig, Hieb, and Bruggeman.
>>
>> The paper states "Two identifiers that are bound-identifier=? are also
>> free-identifier=?".
>
> I think you are referring to this paragraph from the paper[1] (page 12):
>
>     Two    identifiers   that    are   bound-identifier=?     are   also
>     free-identifier=?,  but two  identifiers that  are free-identifier=?
>     may not be bound-identifier=?.  An  identifier introduced by a macro
>     transformer may refer to the same enclosing binding as an identifier
>     not introduced by the transformer, but an introduced binding for one
>     will not capture references to the other.

Yes.

>> The following expression shows that this is not the case in Guile 2.0:
>>
>>   (let* ((x 1) (s1 #'x)
>>          (x 2) (s2 #'x))
>>     (list (bound-identifier=? s1 s2)
>>           (free-identifier=? s1 s2)))
>>   => (#t #f)
>
>   The expander in Ikarus/Vicare also returns this value.

I think that indicates a bug in Ikarus/Vicare.

>> Racket reports (#f #f) for the same expression.
>
>   Racket is different because its expander implements a variant of phase
> separation; if the whole form is evaluated  at phase N, the "x" in "#'x"
> should be searched  among the bindings at  phase N-1 (if any)

I don't see how that's relevant to this example.

> Your code  works, but  when you actually  try to  use the
> identifiers for something:
>
>     #!r6rs
>     (import (rnrs))
>     (define-syntax doit
>       (lambda (stx)
>         (let* ((x 1) (s1 #'x)
>                (x 2) (s2 #'x))
>           #`(let ((#,s1 123))
>               #,s2))))
>     (doit)

Whether #`(let ((#,s1 123)) #,s2) works is equivalent to asking whether
s1 and s2 are 'bound-identifier=?', by definition.  That's precisely
what 'bound-identifier=?' is supposed to be used for: to determine
whether a binding for one should capture the other.

I don't see why you think #`(let ((#,s1 123)) #,s2) should work.  Why
would you use two identifiers with different binding names (s1 and s2)
to construct that code?  Can you construct a more realistic example?

     Thanks,
       Mark

bug#16158: psyntax: bug in bound-identifier=?

[Mark H Weaver]

Marco Maggi <marco.maggi-ipsu@poste.it> writes:

>   IMHO it  is an  error in  the paper.  Some  paragraphs from  the paper
> preceding "the  one" have been recycled  in the R6RS document,  but this
> one paragraph has not; maybe this means something.

Interesting.  I looked closer, and found this in the R6RS definition of
'bound-identifier=?':

   Operationally, two identifiers are considered equivalent by
   bound-identifier=? if and only if they have the same name and same
   marks (section 12.1).

I also found this in the R6RS errata:

   § 12.1

   The remark "An algebra that defines how marks and substitutions
   work more precisely is given in section~2.4 of Oscar Waddell's PhD
   thesis." is somewhat misleading and should be qualified as follows:

   "Note, however, that Waddell's thesis describes slightly different
   semantics for bound-identifier=? - it specifies that for two
   identifiers to be equal in the sense of bound-identifier=?, they
   must have the same marks and be equal in the sense of
   free-identifier=?, whereas this report requires instead that they
   must have the same marks and have the same name."

I guess that Kent Dybvig changed his mind about how 'bound-identifier=?'
should behave.  I don't fully understand the issues, so I'm inclined to
go along with the R6RS definition.

Therefore, I've reverted 70c74b847680d3b239e591afa2e99c51a712980c.

   Thanks,
     Mark