Strange Behavior: functions not work for a list/cons

Discussion of Common Lisp

Strange Behavior: functions not work for a list/cons

Postby 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.
:?
zgljosh
 
Posts: 3
Joined: Mon Feb 27, 2012 10:34 pm

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

Postby 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.
edgar-rft
 
Posts: 157
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby 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.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

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

Postby 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.
edgar-rft
 
Posts: 157
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby zgljosh » Tue Mar 13, 2012 8:48 pm

This issue is resolved by your replies. Thanks, Rarmarren and Edgar!
zgljosh
 
Posts: 3
Joined: Mon Feb 27, 2012 10:34 pm


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 8 guests