Strange Behavior: functions not work for a list/cons

Discussion of Common Lisp
Post Reply
zgljosh
Posts: 3
Joined: Mon Feb 27, 2012 10:34 pm

Strange Behavior: functions not work for a list/cons

Post by zgljosh » Mon Mar 12, 2012 8:00 pm

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.
:?

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Post by edgar-rft » Mon Mar 12, 2012 9:19 pm

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.
Last edited by edgar-rft on Tue Mar 13, 2012 3:59 am, edited 1 time in total.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

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

Post by ramarren » Tue Mar 13, 2012 3:32 am

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.

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Post by edgar-rft » Tue Mar 13, 2012 4:02 am

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.

zgljosh
Posts: 3
Joined: Mon Feb 27, 2012 10:34 pm

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

Post by zgljosh » Tue Mar 13, 2012 8:48 pm

This issue is resolved by your replies. Thanks, Rarmarren and Edgar!

Post Reply