Unsafe psyntax label generation

Unsafe psyntax label generation

[Mark H Weaver]

Hi Andy,

I'm worried about this change you recently committed:

> diff --git a/module/ice-9/psyntax.scm b/module/ice-9/psyntax.scm
> index 1bf3c32..fd33e98 100644
> --- a/module/ice-9/psyntax.scm
> +++ b/module/ice-9/psyntax.scm
> @@ -636,7 +636,12 @@
>      ;; labels must be comparable with "eq?", have read-write invariance,
>      ;; and distinct from symbols.
>      (define gen-label
> -      (lambda () (symbol->string (gensym "i"))))
> +      (let ((i 0))
> +        (lambda ()
> +          (let ((n i))
> +            ;; FIXME: Use atomic ops.
> +            (set! i (1+ n))
> +            (number->string n 36)))))
>  
>      (define gen-labels
>        (lambda (ls)

I guess you did this as an optimization, but as your comment above
confesses, this optimization is not quite correct.  Apart from the
obvious lack of mutex on the global counter, there's another problem
having to do with your implementation of `local-eval'.

If we use your implementation of `local-eval', I think we may need
universally-unique labels here.

You decided that we didn't, because labels are always compared using
`eq?' and labels from an earlier session will never be `eq?' to labels
generated in a newer session, even if they have the same name.  So far
so good, but there's a case you didn't consider:

`local-eval' combines syntax objects from two different sessions into a
single syntax object (in the wrapper procedure), and thus there may be
label name collisions.  Now, if this combined syntax object is
serialized as a compiled procedure, these labels with the same name will
be optimized together into the same string object!

I think this can actually happen, as follows:

* Session "A" compiles procedure (foo), which uses (the-environment), to
  a .go file.

* Session "B" loads the .go file and calls (foo) to create a
  <lexical-environment>.  Then it uses `local-compile' to compile a
  local-expression that uses (the-environment) again.

Maybe there's something I'm missing here, but if the change you made
above was safe, I think the burden of proof is on you to explain why.

   Thanks,
     Mark

Re: Unsafe psyntax label generation

[Andy Wingo]

On Tue 24 Jan 2012 15:01, Mark H Weaver <mhw@netris.org> writes:

> `local-eval' combines syntax objects from two different sessions into a
> single syntax object (in the wrapper procedure), and thus there may be
> label name collisions.  Now, if this combined syntax object is
> serialized as a compiled procedure, these labels with the same name will
> be optimized together into the same string object!

A very good point!

Cf. Aziz's psyntax/expander.ss from r6rs-libraries.dev:

  ;;; (two marks must be eq?-comparable, so we use a string
  ;;; of one char (this assumes that strings are mutable)).
  
  ;;; gen-mark generates a new unique mark
  (define (gen-mark) ;;; faster
    (string #\m))

  ;;; every identifier in the program would have a label associated
  ;;; with it in its substitution.  gen-label generates such labels.
  ;;; the labels have to have read/write eq? invariance to support 
  ;;; separate compilation.
  (define gen-label
    (lambda (_) (gensym)))

His gensyms are globally unique; he made the exact opposite choice that
I did in the fd5985271fee3bcb6a290b6ad10525980a97ef8d; interesting.  I
wonder who is right here.

> Maybe there's something I'm missing here, but if the change you made
> above was safe, I think the burden of proof is on you to explain why.

Indeed, and I think you found a good indication that it's not right.

Andy
-- 
http://wingolog.org/

Re: Unsafe psyntax label generation

[Mark H Weaver]

Andy Wingo <wingo@pobox.com> writes:

> On Tue 24 Jan 2012 15:01, Mark H Weaver <mhw@netris.org> writes:
>
>> `local-eval' combines syntax objects from two different sessions into a
>> single syntax object (in the wrapper procedure), and thus there may be
>> label name collisions.  Now, if this combined syntax object is
>> serialized as a compiled procedure, these labels with the same name will
>> be optimized together into the same string object!
>
> A very good point!
>
> Cf. Aziz's psyntax/expander.ss from r6rs-libraries.dev:
>
>   ;;; (two marks must be eq?-comparable, so we use a string
>   ;;; of one char (this assumes that strings are mutable)).
>   
>   ;;; gen-mark generates a new unique mark
>   (define (gen-mark) ;;; faster
>     (string #\m))
>
>   ;;; every identifier in the program would have a label associated
>   ;;; with it in its substitution.  gen-label generates such labels.
>   ;;; the labels have to have read/write eq? invariance to support 
>   ;;; separate compilation.
>   (define gen-label
>     (lambda (_) (gensym)))
>
> His gensyms are globally unique; he made the exact opposite choice that
> I did in the fd5985271fee3bcb6a290b6ad10525980a97ef8d; interesting.  I
> wonder who is right here.

John Cowan's recent message on scheme-reports "Re: fresh empty strings"
suggests that Ikarus does not merge equal string literals into a single
object, so I guess in that case his `gen-mark' would work properly.

>> Maybe there's something I'm missing here, but if the change you made
>> above was safe, I think the burden of proof is on you to explain why.
>
> Indeed, and I think you found a good indication that it's not right.

How would you like to fix this?  Would you like me to make a new
procedure that creates a universally-unique string?  Most of `gensym's
current code would be moved to that new procedure, and then `gensym'
would use it.

   Thanks,
     Mark

Re: Unsafe psyntax label generation

[Ludovic Courtès]

Hello,

Mark H Weaver <mhw@netris.org> skribis:

> How would you like to fix this?  Would you like me to make a new
> procedure that creates a universally-unique string?  Most of `gensym's
> current code would be moved to that new procedure, and then `gensym'
> would use it.

Would (symbol->string (gensym)) work?

Thanks,
Ludo’.

Re: Unsafe psyntax label generation

[Andy Wingo]

On Wed 25 Jan 2012 14:21, ludo@gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw@netris.org> skribis:
>
>> How would you like to fix this?  Would you like me to make a new
>> procedure that creates a universally-unique string?  Most of `gensym's
>> current code would be moved to that new procedure, and then `gensym'
>> would use it.
>
> Would (symbol->string (gensym)) work?

That would work, yes.  (Incidentally it's what we were doing before.)
The only disadvantage is that it goes through the symbol table, whereas
before this was unnecessary.  But that's Just An Optimization ;-)

Andy
-- 
http://wingolog.org/

Re: Unsafe psyntax label generation

[David Kastrup]

Mark H Weaver <mhw@netris.org> writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> On Tue 24 Jan 2012 15:01, Mark H Weaver <mhw@netris.org> writes:
>>
>>> `local-eval' combines syntax objects from two different sessions into a
>>> single syntax object (in the wrapper procedure), and thus there may be
>>> label name collisions.  Now, if this combined syntax object is
>>> serialized as a compiled procedure, these labels with the same name will
>>> be optimized together into the same string object!
>>
>> A very good point!
>>
>> Cf. Aziz's psyntax/expander.ss from r6rs-libraries.dev:
>>
>>   ;;; (two marks must be eq?-comparable, so we use a string
>>   ;;; of one char (this assumes that strings are mutable)).
>>   
>>   ;;; gen-mark generates a new unique mark
>>   (define (gen-mark) ;;; faster
>>     (string #\m))

Dingdingding.  That sounds to me like I am not the only person of the
opinion that (eq? (string) (string)) is a standard-compliant
implementation choice.  I know this was a different discussion
altogether but thought it might be worth pointing out.

-- 
David Kastrup

Re: Unsafe psyntax label generation

[Andy Wingo]

Heya Mark,

On Wed 25 Jan 2012 02:41, Mark H Weaver <mhw@netris.org> writes:

>> On Tue 24 Jan 2012 15:01, Mark H Weaver <mhw@netris.org> writes:
>>
>>> `local-eval' combines syntax objects from two different sessions into a
>>> single syntax object (in the wrapper procedure), and thus there may be
>>> label name collisions.  Now, if this combined syntax object is
>>> serialized as a compiled procedure, these labels with the same name will
>>> be optimized together into the same string object!
>>
> How would you like to fix this?  Would you like me to make a new
> procedure that creates a universally-unique string?  Most of `gensym's
> current code would be moved to that new procedure, and then `gensym'
> would use it.

I effectively did that: both marks and labels are now globally unique.

At some point though, I realized that not all gensyms need to be
globally unique.  For example, the gensyms used in Tree-IL only need to
be unique within a session.  So in the end I reverted your gensym patch,
and reworked some pieces of it to provide a "session identifier" to the
expander, which is included in generated symbols and strings that need
to be unique across sessions.  The procedure that provides this
identifier then gets shunted off into the (system syntax) toolshed after
boot.

Comments very much welcome, and thanks again for working on this
problem.

Andy
-- 
http://wingolog.org/