Hacker News Reader

Comment by pfdietz | Hacker News Reader

The type hierarchy in the standard has an amusing quirk.

Arrays can have an element type specified, and this type is "upgraded" to a type that is actually store in the array. This upgraded type is a supertype of the actual element type. Upgrading must also preserve subtypes: if T1 is a subtype of T2, then upgrade(T1) must be a subtype of upgrade(T2) (not necessarily a proper subtype, even if T1 != T2).

Now, the standard requires that the upgrade of BIT is BIT (that is, (INTEGER 0 1)), and the upgrade of CHARACTER is CHARACTER. So, what is the upgrade of NIL, the empty type? It must be a subtype of both BIT and CHARACTER, but the only type with that property is NIL itself.

So, the standard requires there must be a specialized array type with element type NIL. That is, it cannot store any values at all.

View on HN

Another quirk that bugs me is the strange and weak typing inside the numerical tower:

    * (typep #c(1 1) 'complex)
    T
    * (typep #c(1 0) 'complex)
    NIL
    * (typep #c(1.0 0) 'complex)
    T

Oh, it's worse than that. The rules behind complex type upgrading lead to even more bizarre results.

There's also a confusion between "subtype" and "recognizable subtype" (that is, something for which SUBTYPEP returns true as a second value). Subtype relations between SATISFIES types aren't even computable.

All this could have been worked through if the standardization process had continued, but commercial lisps ran out of steam to support the rather heavyweight standard making process.

And then, since the type NIL is a subtype of all types, it's a subtype of CHARACTER. So because the type STRING is the union of all array types whose element type is a subtype of CHARACTER, an array that can't store any values is also a string. Oops.

(Also, just for onlookers, in ANSI Common Lisp, but not its ancestors or its sorta-sibling Emacs Lisp, characters are disjoint from integers. That's why the intersection of BIT and CHARACTER is empty.)

That does look like it raises covariance versus contravariance issues.

Here is why: an array is actually a function which maps an integer index to a value.

The element type of an array therefore a return value type of this function.

A "function returning SUP" is not a supertype of "function returning SUB".

> That is, it cannot store any values at all.

NIL is a value in Lisp, no? So that means an array with element type NIL should be able to store exactly one value, whose index is NIL.

Yes, in Common Lisp, NIL is a value (it's a symbol, and by convention also the empty list).

But when used as a type specifier, NIL denotes the empty set. So no Lisp object is of that type, and an array with that element type cannot store any object.

The value NIL has type NULL.

No value has type NIL.

In Common Lisp, the type NULL is one which has only one value in its domain, which is NIL. The type of NIL is NULL.

The Common Lisp type NIL has no elements; no value exists which has type NIL.

NULL is Common Lisp's null type (and so is correctly named).

The type named NIL is Common Lisp's bottom type. The top type is T.

This is pretty clever; they found another punning of NIL and T. Everything is of type T, and nothing is of type NIL.

Only NIL is of type NULL.

The existing, ancient function NULL that predates this type system becomes a type predicate. That is to say, when we evaluate the expression (NULL NIL), yielding true, it has a semantic interpretation as a type test! By testing whether its argument is the NIL object, it's also perpetrating whether the argument is of the NULL type. And so that type name jibes with the name of the ancient NULL function.

Reply on news.ycombinator.com