"The starting list count" ?????

"The starting list count" ?????

[Alan Mackenzie]

Hello, Emacs.

I'm trying to make sense of the form whose printed syntax is

    (1 . #1)

which arises in the Emacs test suite file seq-tests.el.  I'm having
difficulty.

The Elisp manual page "Special Read Syntax" says about it:

   `#N'
       When printing circular structures, this construct is used to
       represent where the structure loops back onto itself, and `N' is
       the starting list count:

            (let ((a (list 1)))
              (setcdr a a))
            => (1 . #0)

..  What does this mean, please?  What does "is the starting list count"
mean?  There is only one "list", so what is the "list count"?

Clearly the N in #N is counting something, but what?  What is the
meaning of

    (1 . #1)

?  What is it about the description in the manual which is so perplexing
me?

Help!

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "The starting list count" ?????

[Robin Tarsiger]

Alan Mackenzie wrote:
>     `#N'
>         When printing circular structures, this construct is used to
>         represent where the structure loops back onto itself, and `N' is
>         the starting list count:
> 
>              (let ((a (list 1)))
>                (setcdr a a))
>              => (1 . #0)
> 
> ..  What does this mean, please?  What does "is the starting list count"
> mean?  There is only one "list", so what is the "list count"?

I agree that this is a bit too abbreviated, but basically it's the number
you'd pass to nthcdr along with the immediately enclosing list to get what's
spliced in as that last cdr.

    (a b c . #0) ~ (a b c a b c a b c ...)
    (a b c . #1) ~ (a b c b c b c ...)
    (a b c . #2) ~ (a b c c c ...)
    (a b c . #3) ~ <can't happen>

-RTT

Re: "The starting list count" ?????

[Andreas Schwab]

On Jan 03 2022, Robin Tarsiger wrote:

> Alan Mackenzie wrote:
>>     `#N'
>>         When printing circular structures, this construct is used to
>>         represent where the structure loops back onto itself, and `N' is
>>         the starting list count:
>>              (let ((a (list 1)))
>>                (setcdr a a))
>>              => (1 . #0)
>> ..  What does this mean, please?  What does "is the starting list count"
>> mean?  There is only one "list", so what is the "list count"?
>
> I agree that this is a bit too abbreviated, but basically it's the number
> you'd pass to nthcdr along with the immediately enclosing list to get what's
> spliced in as that last cdr.

It gets more complicated if the circle is embedded inside another
object.

ELISP> (list (let ((a (list 1))) (setcdr a a)))
((1 . #1))

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: "The starting list count" ?????

[Robin Tarsiger]

Andreas Schwab wrote:
> It gets more complicated if the circle is embedded inside another
> object.
> 
> ELISP> (list (let ((a (list 1))) (setcdr a a)))
> ((1 . #1))

Foo. You're right, I'd mixed it up with something else.

The number of descent operations necessary from the _outermost_
enclosing list expression to reach the referent, then? ... hmm.

   (setq abc (let ((x '(a b c))) (rplacd (cddr x) x))))

   abc
   ==> (a b c . #0)
   (cons 'x abc)
   ==> (x a b c . #1)
   (list abc)
   ==> ((a b c . #1))
   (list (list abc))
   ==> (((a b c . #2)))
   (list '(x y z) (list abc))
   ==> ((x y z) ((a b c . #3)))
   (vector '(x y z) (list abc))
   ==> [(x y z) ((a b c . #2))]
   (record 'foo (list abc))
   ==> #s(foo ((a b c a b . #2)))

Whoa, what happened with that last one?! Is that even intentional?

Alan's definitely right to imply that this needs a better definition.

-RTT

Re: "The starting list count" ?????

[Andreas Schwab]

On Jan 03 2022, Robin Tarsiger wrote:

> Whoa, what happened with that last one?! Is that even intentional?

It's basically the length of the shortest path in the tree from the root
to the referenced object.

> Alan's definitely right to imply that this needs a better definition.

I don't think it needs a precise definition, since it is only
best-effort.  For unambigous output, use print-circle.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: "The starting list count" ?????

[Eli Zaretskii]

> Date: Mon, 3 Jan 2022 12:59:56 -0600
> From: Robin Tarsiger <rtt@dasyatidae.com>
> Cc: emacs-devel@gnu.org
> 
> Alan's definitely right to imply that this needs a better definition.

"Better"? it sounds like we don't have a definition at all, just
examples (some of which we don't even understand).

Re: "The starting list count" ?????

[Alan Mackenzie]

Hello, Robin.

On Mon, Jan 03, 2022 at 12:00:29 -0600, Robin Tarsiger wrote:
> Alan Mackenzie wrote:
> >     `#N'
> >         When printing circular structures, this construct is used to
> >         represent where the structure loops back onto itself, and `N' is
> >         the starting list count:

> >              (let ((a (list 1)))
> >                (setcdr a a))
> >              => (1 . #0)

> > ..  What does this mean, please?  What does "is the starting list count"
> > mean?  There is only one "list", so what is the "list count"?

> I agree that this is a bit too abbreviated, but basically it's the number
> you'd pass to nthcdr along with the immediately enclosing list to get what's
> spliced in as that last cdr.

Thanks, that's helpful.

>     (a b c . #0) ~ (a b c a b c a b c ...)
>     (a b c . #1) ~ (a b c b c b c ...)
>     (a b c . #2) ~ (a b c c c ...)
>     (a b c . #3) ~ <can't happen>

But what about the (1 . #1) I'm seeing?  Isn't that the <can't happen>
case?  The #1 seems to be "pointing to itself".

I see this in the backtrace after C-g'ing out of the loop.

I get an infinite loop when (1 . #1) gets passed to copy-tree.

> -RTT

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "The starting list count" ?????

[Andreas Schwab]

On Jan 03 2022, Alan Mackenzie wrote:

> But what about the (1 . #1) I'm seeing?

It's probably embedded in another object.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: "The starting list count" ?????

[Stefan Monnier]

> ..  What does this mean, please?  What does "is the starting list count"
> mean?  There is only one "list", so what is the "list count"?

I'm not sure how to define it in general, but:

    (let ((x (list 1 2 3 4 5 6 7))) (setf (nthcdr 5 x) (nthcdr N x)) x)

returns a list with a #N inside of it (well, for N sufficiently small
to make sense here, obviously).

AFAIK this is only used to avoid inf-looping, but if/when you actually
care about that you should use `print-circle` which additionally
preserves sharing and gives an output that's more explicit about
what's going on, and hence easier to understand (tho not necessarily
easier to read).


        Stefan

Re: "The starting list count" ?????

[Alan Mackenzie]

Hello, Stefan.

On Mon, Jan 03, 2022 at 13:05:23 -0500, Stefan Monnier wrote:
> > ..  What does this mean, please?  What does "is the starting list count"
> > mean?  There is only one "list", so what is the "list count"?

> I'm not sure how to define it in general, but:

>     (let ((x (list 1 2 3 4 5 6 7))) (setf (nthcdr 5 x) (nthcdr N x)) x)

> returns a list with a #N inside of it (well, for N sufficiently small
> to make sense here, obviously).

> AFAIK this is only used to avoid inf-looping, but if/when you actually
> care about that you should use `print-circle` which additionally
> preserves sharing and gives an output that's more explicit about
> what's going on, and hence easier to understand (tho not necessarily
> easier to read).

I might have understood it now.  I think (1 . #1) refers to:

                       -----------------    ---
                       |               |    | |
                       |               v    v |
-----------------------+--------     ---------+-----------------------  
|               |      |       |     |        |       |              |      
|               |      |       |     |        |       |              |
|		|      |       |     |        |       |              |
|      1	|      |       |     |        |       |     nil      |
|		|              |     |                |              |
|		|              |     |                |              |
|		|              |     |                |              |
--------------------------------     ---------------------------------


Am I right?  This is an ugly thing, which surely only the most twisted of
imaginations could conceive.  ;-)

Obviously, a depth first operation on this "list" is going to take a long
time.

Just as a matter of interest, this object is being passed to
macroexp-strip-symbol-positions during the byte compilation of
seq-tests.el.

>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "The starting list count" ?????

[Andreas Schwab]

On Jan 03 2022, Alan Mackenzie wrote:

> I might have understood it now.  I think (1 . #1) refers to:

This is a single cons.

>                        -----------------    ---
>                        |               |    | |
>                        |               v    v |
> -----------------------+--------     ---------+-----------------------  
> |               |      |       |     |        |       |              |      
> |               |      |       |     |        |       |              |
> |		|      |       |     |        |       |              |
> |      1	|      |       |     |        |       |     nil      |
> |		|              |     |                |              |
> |		|              |     |                |              |
> |		|              |     |                |              |
> --------------------------------     ---------------------------------

This is a picture of two conses, which prints as (1 #1).

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: "The starting list count" ?????

[Alan Mackenzie]

Hello, Andreas.

On Mon, Jan 03, 2022 at 20:50:05 +0100, Andreas Schwab wrote:
> On Jan 03 2022, Alan Mackenzie wrote:

> > I might have understood it now.  I think (1 . #1) refers to:

> This is a single cons.

Yes.  It is surely nonsensical, since it is referring to #1 in a list
structure with only one element.

> >                        -----------------    ---
> >                        |               |    | |
> >                        |               v    v |
> > -----------------------+--------     ---------+-----------------------  
> > |               |      |       |     |        |       |              |      
> > |               |      |       |     |        |       |              |
> > |		|      |       |     |        |       |              |
> > |      1	|      |       |     |        |       |     nil      |
> > |		|              |     |                |              |
> > |		|              |     |                |              |
> > |		|              |     |                |              |
> > --------------------------------     ---------------------------------

> This is a picture of two conses, which prints as (1 #1).

> -- 
> Andreas Schwab, schwab@linux-m68k.org
> GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
> "And now for something completely different."

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "The starting list count" ?????

[Stefan Monnier]

> I might have understood it now.  I think (1 . #1) refers to:

No, if you see (1 . #1) then it's an error.  The #1 means "the second
heap object between the root and here" and in (1 . #1) there's only one
heap object.

You can have

    [a b c (1 . #1)]
and
    ((1 . #1))
and
    (a . (1 . #1))

and many more, but not just

    (1 . #1)


-- Stefan

Re: "The starting list count" ?????

[Stefan Monnier]

>> I might have understood it now.  I think (1 . #1) refers to:
>
> No, if you see (1 . #1) then it's an error.  The #1 means "the second
> heap object between the root and here" and in (1 . #1) there's only one
> heap object.

One way to think about it is that those #N are "de Bruijn levels" ;-)


        Stefan

Re: "The starting list count" ?????

[Alan Mackenzie]

Hello, Stefan.

On Mon, Jan 03, 2022 at 15:38:33 -0500, Stefan Monnier wrote:
> > I might have understood it now.  I think (1 . #1) refers to:

> No, if you see (1 . #1) then it's an error.

What I actually saw was in a backtrace, after C-g'ing out of the byte
compilation of set-tests.el, and was this:

Debugger entered--Lisp error: (quit)
  copy-tree((1 . #1) t)
  macroexp-strip-symbol-positions((1 . #1))
  byte-compile-constant((1 . #1))
  byte-compile-quote('(1 . #2))
  byte-compile-form('(1 . #2))

> The #1 means "the second heap object between the root and here" and in
> (1 . #1) there's only one heap object.

I can cope with "the second heap object", but what is "the root"?

> You can have

>     [a b c (1 . #1)]
> and
>     ((1 . #1))
> and
>     (a . (1 . #1))

> and many more, but not just

>     (1 . #1)

Yes.  Looking at seq-tests.el, it's clear the original source for it is

    (let ((l1 '#1=(1 . #1#))) ....)

, that being the only circular list or setc[ad]r in the entire file.

I'm actually feeling quite sad about the whole business.  There doesn't
appear to be a lot of support for circular lists in Emacs.  Does that
mean I have to write my own version of copy-tree (?etc.) that handles
circularity?  It's surely something that's already been done dozens of
times.

> -- Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "The starting list count" ?????

[Stefan Monnier]

> Debugger entered--Lisp error: (quit)
>   copy-tree((1 . #1) t)
>   macroexp-strip-symbol-positions((1 . #1))
>   byte-compile-constant((1 . #1))
>   byte-compile-quote('(1 . #2))
>   byte-compile-form('(1 . #2))
>
>> The #1 means "the second heap object between the root and here" and in
>> (1 . #1) there's only one heap object.
>
> I can cope with "the second heap object", but what is "the root"?

I suspect in the above backtrace, every arglist is passed to print as
is, so the "root" is the arglist.

>>     (1 . #1)
>
> Yes.  Looking at seq-tests.el, it's clear the original source for it is
>
>     (let ((l1 '#1=(1 . #1#))) ....)

Ah, one of those rare cases where the source code includes circular data.
Maybe we should apply the patch below.


        Stefan


diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index 9e5d59163f9..48ed72a1b06 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -474,7 +474,8 @@ test-sequences-oddp
   (should-error (seq-random-elt "")))
 
 (ert-deftest test-seq-mapn-circular-lists ()
-  (let ((l1 '#1=(1 . #1#)))
+  (let ((l1 (list 1)))
+    (setcdr l1 l1)
     (should (equal (seq-mapn #'+ '(3 4 5 7) l1)
                    '(4 5 6 8)))))
 

Re: "The starting list count" ?????

[Alan Mackenzie]

Hello again, Stefan.

On Mon, Jan 03, 2022 at 16:15:32 -0500, Stefan Monnier wrote:
> > Debugger entered--Lisp error: (quit)
> >   copy-tree((1 . #1) t)
> >   macroexp-strip-symbol-positions((1 . #1))
> >   byte-compile-constant((1 . #1))
> >   byte-compile-quote('(1 . #2))
> >   byte-compile-form('(1 . #2))

> >> The #1 means "the second heap object between the root and here" and in
> >> (1 . #1) there's only one heap object.

> > I can cope with "the second heap object", but what is "the root"?

> I suspect in the above backtrace, every arglist is passed to print as
> is, so the "root" is the arglist.

> >>     (1 . #1)

> > Yes.  Looking at seq-tests.el, it's clear the original source for it is

> >     (let ((l1 '#1=(1 . #1#))) ....)

> Ah, one of those rare cases where the source code includes circular data.

Yes.  But the current byte-compiler copes with it.  The version I have
in scratch/correct-warning-pos doesn't, because of that copy-tree call
(and possibly the further processing in macroexp-strip-symbol-positions,
too).

> Maybe we should apply the patch below.

Hmm.  That feels like papering over the problem rather than solving it.

>         Stefan


> diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
> index 9e5d59163f9..48ed72a1b06 100644
> --- a/test/lisp/emacs-lisp/seq-tests.el
> +++ b/test/lisp/emacs-lisp/seq-tests.el
> @@ -474,7 +474,8 @@ test-sequences-oddp
>    (should-error (seq-random-elt "")))
 
>  (ert-deftest test-seq-mapn-circular-lists ()
> -  (let ((l1 '#1=(1 . #1#)))
> +  (let ((l1 (list 1)))
> +    (setcdr l1 l1)
>      (should (equal (seq-mapn #'+ '(3 4 5 7) l1)
>                     '(4 5 6 8)))))
 
-- 
Alan Mackenzie (Nuremberg, Germany).

Re: "The starting list count" ?????

[Stefan Monnier]

> Yes.  But the current byte-compiler copes with it.  The version I have
> in scratch/correct-warning-pos doesn't, because of that copy-tree call
> (and possibly the further processing in macroexp-strip-symbol-positions,
> too).

FWIW, I consider the use of `copy-tree` as a code smell.
Can be handy in quick&dirty circumstances, but it's rarely exactly what
is needed, and if it is, it's probably only so by accident.

>> Maybe we should apply the patch below.
> Hmm.  That feels like papering over the problem rather than solving it.

You're probably right ;-)


        Stefan

Re: "The starting list count" ?????

[Andreas Schwab]

If you print with print-circle bound to t, you will see exactly which
object the circle refers to.  Otherwise, this is just a best effort to
avoid printing infinite output for circular structures.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."