Why is (type-of list) equal to CONS?

Question

I am playing around with Common Lisp and just realized that

(type-of (cons 1 2)) is CONS

and

(type-of (list 1 2)) is also CONS

However the two are clearly not the same because all "proper" lists, must be conses with second element being a list.

That said, when there are only two elements, the second element is 2, and first element is 1, neither is a list, but the construct is also still called a cons.

This gets even more confusing since

(print (list (cons 1 2)  3)) ; this is a ((1 . 2) 3), an improper list, but still cons
(print (cons 1 (list 2 3))) ; this is a (1 2 3), a proper list, but still cons

(cons 1 (cons 2 3)) ; is not a proper list, but is a (1 2 . 3), but still cons...

All are cons, but why isn't (list 1 2) a list? It can't be a cons because cons and list must be different types in order to be told apart in the algorithm for determining whether or not it is a proper list (and in turn, (equal (list 1 2) (cons 1 2)) should be true; without this discrimination, there should be no difference between a cons and a list, there would just be a cons.

Can somebody please help me understand why it says that (type-of (list 1 2)) is cons, even though it is clearly a list (otherwise it would be an improper list to my understanding).

Answer 1

@coredump's answer is the correct one, but it's perhaps useful to see pragmatic reasons why it's correct.

Firstly, it's quite desirable that typechecks are quick. So if I say (typep x 'list), I'd like it not to have to go away for a long time to do the check.

Well, consider what a proper list checker has to look like. Something like this, perhaps:

(defun proper-list-p (x)
  (typecase x
    (null t)
    (cons (proper-list-p (rest x)))
    (t nil)))

For any good CL compiler this is a loop (and it can obviously be rewritten as an explicit loop if you might need to deal with rudimentary compilers). But it's a loop which is as long as the list you are checking, and this fails the 'typechecks should be quick' test.

In fact it fails a more serious test: typechecks should terminate. Consider a call like (proper-list-p #1=(1 . #1#)). Oops. So we need something like this, perhaps:

(defun proper-list-p (x)
  (labels ((plp (thing seen)
             (typecase thing
               (null (values t nil))
               (cons
                (if (member thing seen)
                    (values nil t) ;or t t?
                  (plp (rest thing)
                       (cons thing seen))))
               (t (values nil nil)))))
    (plp x '())))

Well, this will terminate (and tell you whether the list is circular):

> (proper-list-p '#1=(1 . #1#))
nil
t

(This version considers circular lists not to be proper: I think the other decision is less useful but perhaps equally justified in some theoretical sense.)

But this is now quadratic in the length of the list. This can be made better by using a hashtable in the obvious way, but then the implementation is ludicrously consy for small lists (hashtables are big).

Another reason is to consider the difference between representational type and intentional type: the representational type of something tells you how it is implemented, while the intentional type tells you what it logically is. And it's easy to see that, in a lisp with mutable data structures, it is absurdly difficult for the representational type of a (non-null) list to be different than that of a cons. Here's an example of why:

(defun make-list/last (length init)
  ;; return a list of length LENGTH, with each element being INIT,
  ;; and its last cons.
  (labels ((mlt (n list last)
             (cond ((zerop n)
                    (values list last))
                   ((null last)
                    (let ((c (cons init nil)))
                      (mlt (- n 1) c c)))
                   (t (mlt (- n 1) (cons init list) last)))))
    (mlt length '() '())))

(multiple-value-bind (list last) (make-list/last 10 3)
  (values
   (proper-list-p list)
   (progn
     (setf (cdr last) t)
     (proper-list-p list))
   (progn
     (setf (cdr (cdr list)) '(2 3))
     (proper-list-p list))))

So the result of the last form is t nil t: list is initially a proper list, then it isn't because I fiddled with its final cons, then it is again because I fiddled with some intermediate cons (and now, whatever I do to the cons bound to last will make no difference to that bound to list).

It would be insanely difficult to keep track, in terms of representational type, of whether something is a proper list or not, if you want to use anything that is remotely like linked lists. And type-of, for instance, tells you the representational type of something, which can only be cons (or null for empty lists).

Answer 2

Proper and improper lists are not defined at the type level. This would require recursive type definitions which is only possible to do with Lisp with a satisfies type, and in that case type-of would still not return a type-specifier as complex:

b. the type returned does not involve and, eql, member, not, or, satisfies or values.

The list type could be defined as (or cons null):

The types cons and null form an exhaustive partition of the type list.

That means that nil is a list, and any cons cell is a list. See also the definition of listp.

In other words:

(typep '(a b c) 'cons)
=> T

But also:

(typep '(a b c) 'list)
=> T

And of course this is true for any supertype:

(typep '(a b c) 'sequence)
=> T

(typep '(a b c) 't)
=> T

The type-of function returns the most basic type, i.e. cons, which can be thought of as the type for which no other subtype satisfy typep (but read the specification which gives the actual definition).

Remarks

Just to clarify:

(cons 1 2)

... is a list, but it cannot be passed to functions that expect proper lists like map, etc. This is checked at runtime and generally, there is no confusion because the cases where one use improper lists are actually quite rare (when you treat cons cells as trees, for example). Likewise, circular lists require special treatment. In order to check if a list is proper or not, you only need to check whether the last cons has a nil or not as its cdr.

Also, I saw that you wrote:

((1 . 2) 3) ; [...] an improper list

What you have here is a proper-list of two elements where the first one is an improper list, a.k.a. a dotted-list.