bug#20087: gensym

[Mark H Weaver <mhw@netris.org>]

ludo@gnu.org (Ludovic Courtès) writes:
> ‘gensym’ returns interned symbols, but the algorithm to determine the
> new symbol is simplistic and predictable.
> 
> Thus, one can arrange to produce a symbol before ‘gensym’ does, leading
> ‘gensym’ to return a symbol that’s not fresh (in terms of ‘eq?’), as is
> the case with the second call to ‘gensym’ here:

rain1@openmailbox.org writes:
> I agree, this goes against the main assumption people have about
> gensym. I was able to reproduce the bug.
>
> Here's a patch to libguile/symbol.c which fixes this behavior by
> incrementing the gensym counter in a loop until it creates a fresh
> symbol.

I've considered this idea in the past, but it only avoids collisions
with symbols that have been interned before the gensym.  It does not
avoid collisions with symbols interned *after* the gensym.  Obviously,
there's no way to avoid such collisions.

Therefore, we must unfortunately live with the possibility of
collisions.  Furthermore, if we add a requirement for deterministic
behavior (which I think we must), then we must live with the fact that
intentional collisions can be trivially achieved.

With this in mind, I'm not sure it makes sense to add code that
attempts, but fails, to eliminate the possibility of collisions.

If we cannot eliminate the possibility of collisions, and we cannot
avoid intentional collisions, what can we do?  I think the best we can
hope for is to significantly reduce the probability of _unintentional_
collisions, perhaps by starting the gensym counter at a large number.

The other thing we can do is to clearly document these inherent problems
with gensym, so that they will not be misused for jobs for which they
are not appropriate.

What do you think?

      Mark