Subject: RE: [External] : bug#62037: (proper-list-p '#1=(a #1#)) => 2. It should return nil.

From: Drew Adams <[email-masked]>
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.