Subject: bug#55395: What does (1 2 3 . #2) mean?

From: Mattias Engdegård <[email-masked]>
Date: Wed, 18 May 2022 16:29:51 +0200

14 maj 2022 kl. 15.45 skrev Stefan Monnier <[email-masked]>:

> I do have the impression that it used to be "correct", but I can't
> remember of a single time where I actually made use of that NNN.
> 
> And even if you know what it means and it works correctly, it's pretty
> hard for a normal human to correctly count the depth starting from
> the root.

It is. Counting upwards from a leaf seems slightly easier.

Perhaps these attempts to generate a meaningful circularity reference is a fool's errand and we should just go with #!circle! or something similar.

Anyway, I'm attaching a patch that tries to put some meaning back in the ` . #N` notation: it's an index into the same list, as it used to be, I think, prior to the switch from Floyd to Brent. This is done by keeping track of the index of the tortoise at all times, which isn't very expensive at all.

Without the patch: (rho 4 1) => (1 2 3 4 5 5 5 . #3)
With the patch:    (rho 4 1) => (1 2 3 4 5 5 5 . #6)

which should be a mild improvement.
It's still ambiguous:

 (1 1 . #1)

could mean either

 #1=(1 . #1#)

or

 #1=(1 1 . #1#)

and

 [(1 2 3 . #0)]

could mean either

 [#1=(1 2 3 . #1#)]

or
 #1=[(1 2 3 . #1#)]

but maybe it's less wrong, with room for future improvement?