Page 1 of 1

Strange Behavior: functions not work for a list/cons

Posted: Mon Mar 12, 2012 8:00 pm
by zgljosh
For this form
(cons 'a (cons 'chicken 'cat))

(consp (cons 'a (cons 'chicken 'cat))) returns T
(listp (cons 'a (cons 'chicken 'cat))) returns T

(list-length (cons 'a (cons 'chicken 'cat))) throws error CAT is not of type list
nth 0, nth 1 works but nth 2 gives the same error

It seems contradictory to me: if the form is a list as shown by listp function call, it should have a length or at least the length function should return meaningful value instead of throw a type condition.
:?

Re: Strange Behavior: functions not work for a list/cons

Posted: Mon Mar 12, 2012 9:19 pm
by edgar-rft
Preface: Here is what happens with LIST-LENGTH in Common Lisp:

Code: Select all

(list-length (cons 'a (cons 'chicken 'cat)))
=> error: undefined function LIST-LENGTH
Question: Is this Scheme (other Lisp dialect than Common Lisp) what your are talking about?

Sorry: The text above is wrong! - see Ramarren's comment below. The rest is still true:

But in Scheme as well as in Common Lisp, the problem is in principle the same.

The main underlying data structure in Lisp is not the list, but the cons cell. Lisp lists are build of cons cells. Lisp differs between two forms of lists, "proper" lists and "dotted" lists, where the main difference is that in a "proper" list the CDR of the LAST cons cell must be NIL.

With your CONS code from above you create a "dotted" list, because the last element is 'cat and not NIL:

Code: Select all

(cons 'a (cons 'chicken 'cat)) => (a chicken . cat)  ; with a dot

   +---+---+  +---+---+
-->| * | * -->| * | * --> cat
   +-|-+---+  +-|-+---+
     v          v
     a       chicken
Here the same example as a proper list, created by the LIST function:

Code: Select all

(list 'a 'chicken 'cat) => (a chicken cat)  ; with no dot

   +---+---+  +---+---+  +---+---+
-->| * | * -->| * | * -->| * | * -->nil
   +-|-+---+  +-|-+---+  +-|-+---+
     v          v          v
     a       chicken      cat
To create a "proper" list with CONS you must write:

Code: Select all

(cons 'a (cons 'chicken (cons 'cat nil))) => (a chicken cat)  ; with no dot
To test if a list is a "proper" list you must write:

Code: Select all

(null (cdr (last <list>)))
The reason why this is not a built-in function is that the test must follow all cons-cell pointers until it finds the LAST cell, to test if the CDR of the LAST cell is NIL. This test is very slow with long lists.

David Touretzky's book:
includes a program to print the CONS cells on the screen.

Re: Strange Behavior: functions not work for a list/cons

Posted: Tue Mar 13, 2012 3:32 am
by ramarren
edgar-rft wrote:Preface: Here is what happens with LIST-LENGTH in Common Lisp:
LIST-LENGTH is in fact a standard Common Lisp function and works on my SBCL.

It is specified to signal an error if the list is not a proper list or circular list, which are both subsets of lists. The specification for LISTP specifically notes that it returns true for any kind of list, including improper lists.

Re: Strange Behavior: functions not work for a list/cons

Posted: Tue Mar 13, 2012 4:02 am
by edgar-rft
Sorry: had tested this with a rather old XLISP version, that is known not to be 100% Common Lisp. :shock:

Nevertheless, thanks for the correction, I have added a comment to my wrong text above.

Re: Strange Behavior: functions not work for a list/cons

Posted: Tue Mar 13, 2012 8:48 pm
by zgljosh
This issue is resolved by your replies. Thanks, Rarmarren and Edgar!