GNU bug report logs - #62037
(proper-list-p '#1=(a #1#)) => 2. It should return nil.

Previous Next

To reply to this bug, email your comments to 62037 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Alan Mackenzie <acm <at> muc.de>
To: bug-gnu-emacs <at> gnu.org
Subject: (proper-list-p '#1=(a #1#)) => 2.  It should return nil.
Date: Tue, 7 Mar 2023 17:29:53 +0000

-- 
Alan Mackenzie (Nuremberg, Germany).

Message #8 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Ruijie Yu <ruijie <at> netyu.xyz>
To: Alan Mackenzie <acm <at> muc.de>
Cc: 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Wed, 08 Mar 2023 12:13:50 +0800

Notice the distinction between these two snippets:

    (let ((lst-1 '#1=(a #1#)))
      (list lst-1 (proper-list-p lst-1)))
    ;; => ((a #1) 2)

    (let ((lst-2 '#1=(a . #1#)))
      (list lst-2 (proper-list-p lst-2)))
    ;; => ((a . #0) nil)

Apparently, at least from the current behaviors, lst-1 is considered a
"proper list" because it is not a *circular list* [1], but still a
*circular object* [2].  This is because, in
essense, this is a list of two elements,
where the first one is 'a, and the second one is lst-1 itself.
Rewriting lst-1, we see that lst-1 is also not considered as dotted.

    (setq lst-1 '#1=(a #1# . nil))

That said, given that the docstring has some ambiguities on what
"circular" means -- as in, whether it means "circular list" or "circular
object", maybe at least the docstring and the Elisp manual about
`proper-list-p' should be updated to clarify which one it means?  Then
the implementation of `proper-list-p' can follow suite if necessary.

[1]:
(info "(elisp) Cons Cells")

> If the CDR of a list’s last cons cell is some value other than ‘nil’,
> we call the structure a “dotted list”, since its printed
> representation would use dotted pair notation (*note Dotted Pair
> Notation::).  There is one other possibility: some cons cell’s CDR
> could point to one of the previous cons cells in the list.  We call
> that structure a “circular list”.

[2]:
(info "(elisp) Circular Objects")

> To represent shared or circular structures within a complex of Lisp
> objects, you can use the reader constructs ‘#N=’ and ‘#N#’.

--
Best,


RY

Message #11 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Philip Kaludercic <philipk <at> posteo.net>
To: Ruijie Yu <ruijie <at> netyu.xyz>
Cc: Alan Mackenzie <acm <at> muc.de>, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Sat, 18 Mar 2023 07:41:14 +0000

Ruijie Yu <ruijie <at> netyu.xyz> writes:

> Notice the distinction between these two snippets:
>
>     (let ((lst-1 '#1=(a #1#)))
>       (list lst-1 (proper-list-p lst-1)))
>     ;; => ((a #1) 2)
>
>     (let ((lst-2 '#1=(a . #1#)))
>       (list lst-2 (proper-list-p lst-2)))
>     ;; => ((a . #0) nil)

Doesn't this point resolve the issue?  Shouldn't the bug report be
closed?

-- 
Philip Kaludercic

Message #14 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Alan Mackenzie <acm <at> muc.de>
To: Philip Kaludercic <philipk <at> posteo.net>
Cc: Ruijie Yu <ruijie <at> netyu.xyz>, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Sat, 18 Mar 2023 08:29:02 +0000

Hello, Philip.

On Sat, Mar 18, 2023 at 07:41:14 +0000, Philip Kaludercic wrote:
> Ruijie Yu <ruijie <at> netyu.xyz> writes:

> > Notice the distinction between these two snippets:

> >     (let ((lst-1 '#1=(a #1#)))
> >       (list lst-1 (proper-list-p lst-1)))
> >     ;; => ((a #1) 2)

> >     (let ((lst-2 '#1=(a . #1#)))
> >       (list lst-2 (proper-list-p lst-2)))
> >     ;; => ((a . #0) nil)

> Doesn't this point resolve the issue?

No, it doesn't.  A circular list is defined (Elisp manual page "Lists
and Cons Cells") as one where "some cons cell’s CDR could point to one
of the previous cons cells in the list".  A proper list (page
"List-related Predicates") is one which is neither dotted nor circular.

The list #1=(a . #1#) is clearly circular.  proper-list-p should return
nil for it.

The purpose of proper-list-p is surely to find out in advance whether an
algorithm one wishes to run on a list can proceed without taking special
precautions for dottedness or circularity.  proper-list-p fails here.

> Shouldn't the bug report be closed?

Only once it's been fixed.

> -- 
> Philip Kaludercic

-- 
Alan Mackenzie (Nuremberg, Germany).

Message #17 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Philip Kaludercic <philipk <at> posteo.net>
To: Alan Mackenzie <acm <at> muc.de>
Cc: Ruijie Yu <ruijie <at> netyu.xyz>, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Sat, 18 Mar 2023 13:48:40 +0000

Alan Mackenzie <acm <at> muc.de> writes:

> Hello, Philip.
>
> On Sat, Mar 18, 2023 at 07:41:14 +0000, Philip Kaludercic wrote:
>> Ruijie Yu <ruijie <at> netyu.xyz> writes:
>
>> > Notice the distinction between these two snippets:
>
>> >     (let ((lst-1 '#1=(a #1#)))
>> >       (list lst-1 (proper-list-p lst-1)))
>> >     ;; => ((a #1) 2)
>
>> >     (let ((lst-2 '#1=(a . #1#)))
>> >       (list lst-2 (proper-list-p lst-2)))
>> >     ;; => ((a . #0) nil)
>
>> Doesn't this point resolve the issue?
>
> No, it doesn't.  A circular list is defined (Elisp manual page "Lists
> and Cons Cells") as one where "some cons cell’s CDR could point to one
> of the previous cons cells in the list".  A proper list (page
> "List-related Predicates") is one which is neither dotted nor circular.
>
> The list #1=(a . #1#) is clearly circular.  proper-list-p should return
> nil for it.

But (proper-list-p '#1=(a . #1#)) does return nil?  And (proper-list-p
'#1=(a #1#)) does return 2, 

 +---+---+   +---+---+
 | a | ----->| | | ------> nil
 +---+---+   +-|-+---+
   ^           |
    \_________/

because #1=(a #1#)) is not a circular list, the cadr only has a
reference back to a the beginning of the list, but #1=(a . #1#)) is
cyclical because as you say a cdr points back to a previous cons cell:

 +---+---+
 | a | | |
 +---+-|-+
   ^   |  
    \__/

> The purpose of proper-list-p is surely to find out in advance whether an
> algorithm one wishes to run on a list can proceed without taking special
> precautions for dottedness or circularity.  proper-list-p fails here.
>
>> Shouldn't the bug report be closed?
>
> Only once it's been fixed.
>
>> --
>> Philip Kaludercic

Message #20 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Ruijie Yu <ruijie <at> netyu.xyz>
To: Philip Kaludercic <philipk <at> posteo.net>
Cc: Alan Mackenzie <acm <at> muc.de>, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Fri, 31 Mar 2023 12:35:49 +0800

>> [...]
>>> Doesn't this point resolve the issue?
>>
>> No, it doesn't.  A circular list is defined (Elisp manual page "Lists
>> and Cons Cells") as one where "some cons cell’s CDR could point to one
>> of the previous cons cells in the list".  A proper list (page
>> "List-related Predicates") is one which is neither dotted nor circular.
>>
>> The list #1=(a . #1#) is clearly circular.  proper-list-p should return
>> nil for it.
>
> But (proper-list-p '#1=(a . #1#)) does return nil? [...]
>
> because #1=(a #1#)) is not a circular list, the cadr only has a
> reference back to a the beginning of the list, but #1=(a . #1#)) is
> cyclical because as you say a cdr points back to a previous cons cell:
> [...]
>
>> The purpose of proper-list-p is surely to find out in advance whether an
>> algorithm one wishes to run on a list can proceed without taking special
>> precautions for dottedness or circularity.  proper-list-p fails here.
> [...]

So, it all boils down to the fact that the current documentation is
lacking and/or ambiguous, in terms of "the purpose of `proper-list-p'",
as well as the two definitions of the adjective "circular", which are
not interchangeable in different contexts.

If we all agree that only some pieces of documentation need updating,
then I will try to come up with a patch(set) in the upcoming few days --
or someone else can, should one volunteers to do so.  FTR, I am still
waiting for a counter signature from FSF.

-- 
Best,


RY

Message #23 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Philip Kaludercic <philipk <at> posteo.net>
To: Ruijie Yu <ruijie <at> netyu.xyz>
Cc: Alan Mackenzie <acm <at> muc.de>, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Fri, 31 Mar 2023 07:25:12 +0000

Ruijie Yu <ruijie <at> netyu.xyz> writes:

>>> [...]
>>>> Doesn't this point resolve the issue?
>>>
>>> No, it doesn't.  A circular list is defined (Elisp manual page "Lists
>>> and Cons Cells") as one where "some cons cell’s CDR could point to one
>>> of the previous cons cells in the list".  A proper list (page
>>> "List-related Predicates") is one which is neither dotted nor circular.
>>>
>>> The list #1=(a . #1#) is clearly circular.  proper-list-p should return
>>> nil for it.
>>
>> But (proper-list-p '#1=(a . #1#)) does return nil? [...]
>>
>> because #1=(a #1#)) is not a circular list, the cadr only has a
>> reference back to a the beginning of the list, but #1=(a . #1#)) is
>> cyclical because as you say a cdr points back to a previous cons cell:
>> [...]
>>
>>> The purpose of proper-list-p is surely to find out in advance whether an
>>> algorithm one wishes to run on a list can proceed without taking special
>>> precautions for dottedness or circularity.  proper-list-p fails here.
>> [...]
>
> So, it all boils down to the fact that the current documentation is
> lacking and/or ambiguous, in terms of "the purpose of `proper-list-p'",
> as well as the two definitions of the adjective "circular", which are
> not interchangeable in different contexts.

It might be lacking, but I don't think the explanation is ambiguous.
"its last cdr is nil" might not be awfully formal, but it does describe
the problem.

> If we all agree that only some pieces of documentation need updating,
> then I will try to come up with a patch(set) in the upcoming few days --
> or someone else can, should one volunteers to do so.  FTR, I am still
> waiting for a counter signature from FSF.

-- 
Philip Kaludercic

Message #26 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Ruijie Yu <ruijie <at> netyu.xyz>
To: Philip Kaludercic <philipk <at> posteo.net>
Cc: Alan Mackenzie <acm <at> muc.de>, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Fri, 31 Mar 2023 15:29:13 +0800

Philip Kaludercic <philipk <at> posteo.net> writes:
>> So, it all boils down to the fact that the current documentation is
>> lacking and/or ambiguous, in terms of "the purpose of `proper-list-p'",
>> as well as the two definitions of the adjective "circular", which are
>> not interchangeable in different contexts.
>
> It might be lacking, but I don't think the explanation is ambiguous.
> "its last cdr is nil" might not be awfully formal, but it does describe
> the problem.

I agree.  However, I would reorganize it slightly to make "cdr being
nil" stand out more.  See this snippet for `proper-list-p' docstring,
and note that I explicitly mentioned circular _list_ to avoid confusion.

--8<---------------cut here---------------start------------->8---
- A proper list is neither circular nor dotted (i.e., its last cdr is nil).
+ A proper list is a list whose last cdr is nil (i.e., neither a circular list nor dotted list).
--8<---------------cut here---------------end--------------->8---

Again, I find it problematic that there are two related definitions of
"circular", and the first search result for "circular" under Elisp info
manual is (info "(elisp) Circular Objects"), which is not what is
intended for `proper-list-p'.  This causes problems in understanding the
intended behavior of this function, manifested via this bug.

-- 
Best,


RY

Message #29 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Ruijie Yu <ruijie <at> netyu.xyz>
Cc: acm <at> muc.de, philipk <at> posteo.net, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2. It should return nil.
Date: Fri, 31 Mar 2023 10:50:15 +0300

> Cc: Alan Mackenzie <acm <at> muc.de>, 62037 <at> debbugs.gnu.org
> Date: Fri, 31 Mar 2023 15:29:13 +0800
> From:  Ruijie Yu via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
> 
> Again, I find it problematic that there are two related definitions of
> "circular", and the first search result for "circular" under Elisp info
> manual is (info "(elisp) Circular Objects"), which is not what is
> intended for `proper-list-p'.

How did you search?  If you type "i circular RET", the first hit lands
you in "Cons Cells", where both "circular list" and proper-list-p are
described.  So I don't think I understand what you mean by "the first
search result".

Message #32 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Ruijie Yu <ruijie <at> netyu.xyz>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: acm <at> muc.de, philipk <at> posteo.net, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Sat, 01 Apr 2023 22:16:33 +0800

Eli Zaretskii <eliz <at> gnu.org> writes:

> [...]
> How did you search?  If you type "i circular RET", the first hit lands
> you in "Cons Cells", where both "circular list" and proper-list-p are
> described.  So I don't think I understand what you mean by "the first
> search result".

I used `s circular RET', because in my mind I want to _search_ for the
word "circular".  But I guess I never knew about `Info-index', so TIL.

-- 
Best,


RY

Message #35 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: "Basil L. Contovounesios" <basil <at> contovou.net>
To: Alan Mackenzie <acm <at> muc.de>
Cc: Ruijie Yu <ruijie <at> netyu.xyz>, 62037 <at> debbugs.gnu.org,
 Philip Kaludercic <philipk <at> posteo.net>
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Sun, 26 Jan 2025 13:40:25 +0100

Alan Mackenzie [2023-03-18 08:29 +0000] wrote:

> The list #1=(a . #1#) is clearly circular.  proper-list-p should return
> nil for it.

It does.

But the subject of the bug report is about #1=(a #1#) not #1=(a . #1#).

> The purpose of proper-list-p is surely to find out in advance whether an
> algorithm one wishes to run on a list can proceed without taking special
> precautions for dottedness or circularity.  proper-list-p fails here.

proper-list-p checks along the list's cdrs.

Detecting the circularity in #1=(a #1#) requires checking along the cars
as well.  To me that implies a (more expensive) proper-tree-p (or
similar) rather than proper-list-p, for the same reason that 'length'
returns the same result as proper-list-p for #1=(a 1#).

Would it help if the documentation of proper-list-p just mentioned the
phrase 'along the cdrs', in the same way that copy-tree does?

Thanks,
-- 
Basil

Message #38 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: "Basil L. Contovounesios" <basil <at> contovou.net>
Cc: ruijie <at> netyu.xyz, acm <at> muc.de, philipk <at> posteo.net, 62037 <at> debbugs.gnu.org
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2. It should return nil.
Date: Sun, 26 Jan 2025 14:52:11 +0200

> Cc: Ruijie Yu <ruijie <at> netyu.xyz>, 62037 <at> debbugs.gnu.org,
>  Philip Kaludercic <philipk <at> posteo.net>
> From: "Basil L. Contovounesios" <basil <at> contovou.net>
> Date: Sun, 26 Jan 2025 13:40:25 +0100
> 
> Alan Mackenzie [2023-03-18 08:29 +0000] wrote:
> 
> > The list #1=(a . #1#) is clearly circular.  proper-list-p should return
> > nil for it.
> 
> It does.
> 
> But the subject of the bug report is about #1=(a #1#) not #1=(a . #1#).
> 
> > The purpose of proper-list-p is surely to find out in advance whether an
> > algorithm one wishes to run on a list can proceed without taking special
> > precautions for dottedness or circularity.  proper-list-p fails here.
> 
> proper-list-p checks along the list's cdrs.
> 
> Detecting the circularity in #1=(a #1#) requires checking along the cars
> as well.  To me that implies a (more expensive) proper-tree-p (or
> similar) rather than proper-list-p, for the same reason that 'length'
> returns the same result as proper-list-p for #1=(a 1#).
> 
> Would it help if the documentation of proper-list-p just mentioned the
> phrase 'along the cdrs', in the same way that copy-tree does?

It cannot harm, IMO.  But if you ask me, saying that doesn't make it
clear what proper-list-p can and cannot do.  So bonus points for
spelling that out explicitly.

And maybe we also want proper-tree-p.

Message #41 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Eli Zaretskii <eliz <at> gnu.org>, "Basil L. Contovounesios"
 <basil <at> contovou.net>
Cc: "ruijie <at> netyu.xyz" <ruijie <at> netyu.xyz>, "acm <at> muc.de" <acm <at> muc.de>,
 "philipk <at> posteo.net" <philipk <at> posteo.net>,
 "62037 <at> debbugs.gnu.org" <62037 <at> debbugs.gnu.org>
Subject: RE: [External] : bug#62037: (proper-list-p '#1=(a #1#)) => 2. It
 should return nil.
Date: Sun, 26 Jan 2025 20:48:51 +0000

> > the subject of the bug report is about #1=(a #1#) not #1=(a . #1#).
> >
> > > The purpose of proper-list-p is surely to find out in advance whether
> > > an algorithm one wishes to run on a list can proceed without taking
> > > special precautions for dottedness or circularity.

Maybe that's one purpose, OK.  But not any old
algorithm, which might concern checks of a lists
_elements_.  Only a check of whether list itself
is a proper list, i.e., has finite length.

> proper-list-p fails here.

Not in my opinion.

Whether a list is proper has _nothing_ whatsoever
to do with what any of its _elements_ might be like.

The list #1=(a #1#) has only two elements.  It' not
at all improper or circular.

It happens that one if its _elements_ (the second
one) is a circular list.

The list #1=(a #1#) can be informally written as
(a (a...)).  Its first element is `a', and its
second element is a circular list, each of whose
elements is `a'.  Nothing more is going on, here.

> > proper-list-p checks along the list's cdrs.

Which is exactly what it should do.  The properties
of an ordinary, proper list are satisfied.  That
list has a car that's an atom and a cdr that's a
circular list.  Two elements; length two.

> > Detecting the circularity in #1=(a #1#)

There's no circularity in that list.  There's only
circularity in the list that's the second element
(cadr) of that list.

> > requires checking along the cars as well.

No, checking circularity in a list, as a list,
i.e., checking whether it's proper/true, doesn't
require examining any list elements, because they
are irrelevant to whether the list has a finite
number of elements, i.e, whether it has a finite
number of cdrs, i.e., whether its length is
finite, i.e., whether the _list_ is finite.

> > To me that implies a (more expensive) proper-tree-p (or
> > similar) rather than proper-list-p, for the same reason that 'length'
> > returns the same result as proper-list-p for #1=(a 1#).

If you want to check whether each element of a list,
and each element of each list element of a list, ...
recursively, is an atom or a proper list, then sure,
that's more involved.  But it has nothing to do with
testing whether a list is itself finite.

_Users_ can define such checks if they really need
them.  I don't see any need to define such functions
as part of a Lisp implementation.  (And AFAIK other
Lisps don't bother doing that either.)

And if you go down that road of defining a "proper"
tree check, then maybe you want to also worry about
any list element that's a _string_ with a property
whose value is a circular list/tree, ... and so on.
Would you check each such string possibility, as
any list element?  Why not, if you really want to
check list elements for possible infinities?

[FWIW, I often use a list whose car is a string that
has a property whose value is the entire list (which
contains that string as its car).  I do that for
alists whose keys can be `equal' but different wrt
that property, because the cdrs are different.]

> > Would it help if the documentation of proper-list-p just mentioned the
> > phrase 'along the cdrs', in the same way that copy-tree does?

I don't think it's needed.  I suppose it wouldn't hurt,
but for listness there's nothing else than checking
"along the cdrs".  And that addition to the doc could
actually confuse some users into thinking that being a
proper list or not has something to do with the nature
of a list's _elements_, which it most certainly does not.
IMO it will likely only help mislead thinking about lists.

> It cannot harm, IMO.

See previous paragraph.  Not great harm, but more likely
to be harmful than helpful, IMO.

> But if you ask me, saying that doesn't make it
> clear what proper-list-p can and cannot do.  So bonus points for
> spelling that out explicitly.
> 
> And maybe we also want proper-tree-p.

A `proper-tree-p' function is certainly different from
a `proper-list-p' function.  That's the important point.

IMO there's no need for a `proper-tree-p' function, but
at least don't impose such checking on `proper-list-p',
please.

Has anyone actually pointed out a need for a general
function that does what `proper-tree-p' would do?  I
seriously doubt it.  Any code that needs to worry about
such a thing would likely do whatever specific checks
it needs, and wouldn't need any such general function.

Message #44 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Alan Mackenzie <acm <at> muc.de>
To: "Basil L. Contovounesios" <basil <at> contovou.net>
Cc: Ruijie Yu <ruijie <at> netyu.xyz>, 62037 <at> debbugs.gnu.org,
 Philip Kaludercic <philipk <at> posteo.net>
Subject: Re: bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It should return
 nil.
Date: Tue, 28 Jan 2025 13:11:38 +0000

Hello, Basil.

On Sun, Jan 26, 2025 at 13:40:25 +0100, Basil L. Contovounesios wrote:
> Alan Mackenzie [2023-03-18 08:29 +0000] wrote:

> > The list #1=(a . #1#) is clearly circular.  proper-list-p should return
> > nil for it.

> It does.

> But the subject of the bug report is about #1=(a #1#) not #1=(a . #1#).

> > The purpose of proper-list-p is surely to find out in advance whether an
> > algorithm one wishes to run on a list can proceed without taking special
> > precautions for dottedness or circularity.  proper-list-p fails here.

> proper-list-p checks along the list's cdrs.

Yes.

> Detecting the circularity in #1=(a #1#) requires checking along the cars
> as well.  To me that implies a (more expensive) proper-tree-p (or
> similar) rather than proper-list-p, for the same reason that 'length'
> returns the same result as proper-list-p for #1=(a 1#).

> Would it help if the documentation of proper-list-p just mentioned the
> phrase 'along the cdrs', in the same way that copy-tree does?

I'm not sure.  I bumped into the above scenario when I was writing or
amending some algorithm which worked on a generic list structure, and
got infinite loops when that list was as above, despite first checking
it with proper-list-p.

To my mind, #1=(a #1#) is not a "proper list", despite what Drew has
said about the matter.  proper-list-p doesn't seem very useful when
ones purpose is to filter out lists that will break list traversing
algorithms.

Perhaps there ought to be a proper-tree-p function too, like you
suggest.

> Thanks,
> -- 
> Basil

-- 
Alan Mackenzie (Nuremberg, Germany).

Message #47 received at 62037 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Alan Mackenzie <acm <at> muc.de>, "Basil L. Contovounesios" <basil <at> contovou.net>
Cc: Ruijie Yu <ruijie <at> netyu.xyz>,
 "62037 <at> debbugs.gnu.org" <62037 <at> debbugs.gnu.org>,
 Philip Kaludercic <philipk <at> posteo.net>
Subject: RE: [External] : bug#62037: (proper-list-p '#1=(a #1#)) => 2.  It
 should return nil.
Date: Tue, 28 Jan 2025 19:10:24 +0000

Hello Alan!

> I bumped into the above scenario when I was writing or
> amending some algorithm which worked on a generic list structure, and
> got infinite loops when that list was as above, despite first checking
> it with proper-list-p.

If your use case requires checking the elements
of a list ahead of time, to ensure that they
aren't infinite lists or don't involve infinite
lists, then yep, you need to do just that
(whatever "that" is, specifically, for your use
case).

And as I said, depending on what your actual
requirement is in that regard, that could mean
different kinds of checking, and it can be more
or less involved.

> To my mind, #1=(a #1#) is not a "proper list",
> despite what Drew has said about the matter.

We needn't agree on what "proper list" means.
What's important is what the predicate does.

IMO, the test needed - far and away the most
useful and most commonly needed - is a test
whether the list itself is circular/infinite.
And that means checking that its (extensional,
explicit) _length is finite_.

Whether to have other, more general (or more
specific, depending on your view point)
predicates, which check the list _elements_
for possible list values that are infinite,
or that test the elements for strings or
symbols that have properties whose values are
infinite lists, or ... -- that's a different
question (or a different basket of questions).

A priori, I don't see a need for Elisp to
predefine any such predicate(s).  My reasons:

1. Different use cases will call for different
   checks.
2. Such use cases aren't that common.
3. Providing such a general predicate, which
   can be costly to use, might encourage its
   use when it's not really needed or it's
   better to code a predicate specific to the
   given use.

   Let's not give the impression that such a
   check is parallel/equivalent to a check
   such as `proper-list-p'.  The latter has
   many, many, many more uses than any such
   check-cars-too predicate.
4. Users can anyway code up such a check if /
   when they really need it.

> proper-list-p doesn't seem very useful when
> ones purpose is to filter out lists that will
> break list traversing algorithms.

Be specific about your list traversal.  But
sure, if you need to traverse all branches
of a tree, and if one of those branches is
infinite, then ... Check each car that's a
list, to be sure it, in turn, has finite
length.  And hey - guess what! there's a
predicate for that...

(But sometimes you don't need to traverse
all branches all the way down or even know
whether you can do that.  Sometimes you can
traverse lazily, or at least breadth-first,
and not bother to find or act on nodes past
a given depth.)

> Perhaps there ought to be a proper-tree-p
> function too, like you suggest.

Just please don't get rid of or redefine the
useful predicate `proper-list-p'.  (I don't
care so much about its name; it's its behavior
that's useful.)

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.