Quirks of Common Lisp Types | Hacker News Reader

Quirks of Common Lisp Types

fosskers.ca

121 pointstodsacerdoti29 comments

While the post references a link to the 'Type Hierarchy of Strings'[0], here is the full type tree[1] for Common Lisp.

[0]: https://lispcookbook.github.io/cl-cookbook/strings.html#stri...

[1]: https://sellout.github.io/2012/03/03/common-lisp-type-hierar...

The type tree is screaming for the Apple Pascal poster treatment

It's also easy to draw type graphs like these dynamically: DO-EXTERNAL-SYMBOLS + FIND-CLASS yields you list of types—and CLASS-DIRECT-SUPERCLASSES, from MOP, gives you the edge relations between them. In my personal SLIME setup I render graphs like this through graphviz and into an Emacs buffer.

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.

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

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".

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.

I think this article over-sells (to a point of being misleading) the amount of static type checking offered in Common Lisp even by a relatively good implementation like SBCL.

SBCL's static type checking provides in practice virtually zero guarantees about whether compiling your code actually implies the inexistence of type errors. In that regard, I like to consider SBCL's static type errors to be a mere courtesy [1].

Typically, the static type errors TFA demonstrates are nullified as soon as anything is abstracted away into a function. To show a trivial example:

    (+ 2 "2")

may error statically because the Common Lisp implementation has special rules and knowledge about the + function, but

    (defun id (x) x)

    (+ 2 (id "2"))

will not. Furthermore, Common Lisp has no way to label the type of the function ID to constrain its input type to be the same as its output type that works for all possible types. That is, there's nothing like the Haskell declaration

    id :: a -> a
    id x = x

or the C++

    template <typename A>
    A id(A x) {
        return x;
    }

In Common Lisp, the closest you can get is either to declare ID to be monomorphic (i.e., just select a single type it can work with), as in

    (declaim (ftype (function (string) string) id))

or to say that ID can take anything as input and produce anything (possibly different from the input) as output, as in

    (declaim (ftype (function (t) t) id))

Here, T is not a type variable, but instead the name of the "top" type, the supertype of all types.

[1] SBCL and CMUCL aren't totally random in what static type checking they perform, and the programmer can absolutely make profitable use of this checking, but you have to be quite knowledgeable of the implementation to know what exactly you can rely on.

(+ 2 (id "2")) may also produce a compile time warning. Nothing precludes from having a special rule for that. Like (+ 2 (print "2")) does warn.

This reminds me of my favorite special form in common-lisp: `the`. https://www.lispworks.com/documentation/HyperSpec/Body/s_the...

(the fixnum (compute-my-fixnum-value))

This specifies that the value in the form in the second argument is of the type specified by the first argument. One might assume that this is what other languages call `assert`, and it can be; your compiler / interpreter can be configured to assert if it detects a mismatch between the two.

... but the spec actually specifies that if they don't match, the behavior is undefined. `the` is also an opportunity for the compiler to throw away some dynamic typechecking logic; essentially, it's a chance to paint racing stripes on the implementation so it goes faster at the cost of risking undefined behavior.

Exactly. The primary purpose of type declarations in Common Lisp is to give the compiler a hint that you are taking responsibility for type management so the machine code doesn't need to check the type at runtime. But the spec does not require that the compiler obey that hint, and if the compiler does obey the hint the spec says it's not the compiler's fault if you screw up the type that you took responsibility for.

An additional purpose for type declarations is not mentioned in the spec: Static analysis. SBCL goes the extra mile and does do some static analysis with your type declarations, which means it catches many kinds of programmer errors at compile time. Not all CL implementations do this.

If you want a Common Lisp that performs thorough static analysis, use Coalton.

This is one of the things I appreciate about Common LISP's approach: it allows for undefined behavior, but UB is (mostly, as far as I know, I'm sure someone will jump in and correct me ;) ) off by default.

And I think that's the right place for the default to be. C and C++ support UB as well and there are definitely times where you want that for the speed benefits it affords the compiler's output, but getting to UB in those languages is as easy as creating a character array and then copying a string that is too long into that character array (gcc will warn you, but about the conversion of a string literal into a char pointer, not about the buffer overrun).

And with the C++ spec having a page count exceeding the entire Lord of the Rings trilogy, that's a lot of language definition for undefined behavior to live in.

> it allows for undefined behavior, but UB is (mostly, as far as I know, I'm sure someone will jump in and correct me ;) ) off by default.

It's actually much more sophisticated than that. See:

https://www.lispworks.com/documentation/HyperSpec/Body/01_db...

would you happen to know whether the spec requires a default value for the safety optimization quality, when no declartions are given in the program? Or is it implementation-defined; could conforming implementations be unsafe by default.

No idea, sorry.

[UPDATE] There is a clue in section 3.3.1 Minimal Declaration Processing Requirements:

"A safety declaration that increases the current safety level must always be recognized. An implementation that always processes code as if safety were high may safely ignore this declaration."

To me this seems to imply that the default value of SAFETY is implementation-dependent.

I also found that passage. It's either implementation-defined or else they went incredibly out of their way to hide the requirements.

Common Lisp has declared safety levels, so implementations can provide diagnostics about types at safety level 3, letting you roast in the flame of your undefined behavior only at lower safety levels.

I can't remember what the exact requirements are; I'd have to go back and re-read that.

Anyway, whether required by ANSI CL or not, implementations are good about protecting you from yourself unless you declare type AND request high speed and low safety.

Looking at the spec now, I don't see where it specifies that code is safe by default (safety 3) if no declarations are specified in the global or lexical environment. I see the requirement that implementations must not ignore safety deeclarations that raise the level of safety (unless they treat all code as safe and don't implement those declarations).

> Note also that this isn't a linear hierarchy: in the String example above, simple-array and string are unrelated.

Are you sure? If that's the case, it would have to be that the object is not a suitable argument to a method parameter of type string.

Don't guess about whether they're considered unrelated in that implementation, use subtypep and typep.

If (typep "X" 'string) yields true, then the type of "X", whatever it is, is related to string.

From article:

  (list (typep "漣" 'simple-array)
        (typep "漣" 'string)
        (typep "漣" 'vector)
        (typep "漣" 'array)
        (typep "漣" t))

  -> (T T T T T)

There you go. The type of "漣" is a subtype of string. Since we know that the type is (SIMPLE-ARRAY CHARACTER (1)), it means that this type is a subtype of string. They are therefore related by the supertype-subtype relationship.

The original intent was that `simple-array`, on its own, is not related to `string`. The referenced type hierarchy makes this clearer: https://lispcookbook.github.io/cl-cookbook/strings.html#stri...

Since the title includes the word "quirks," the observation I'll make here is entirely appropriate: the post oversimplifies this.

It says: "So as we can see, at both run-time and compile-time, Common Lisp does typechecking to prevent silly errors."

This is not entirely accurate, as the Common Lisp standard does not require such typechecking.

The Common Lisp standard specifies the types of the arguments that a function expects. It generally does not specify what happens if the function receives arguments of unexpected types. It explicitly does not specify this: the standard says that if you give a function unexpected types, the consequences are undefined:

https://www.lispworks.com/documentation/HyperSpec/Body/01_dd...

where "undefined" means that any behavior, from an error message to a harmless failure to a catastrophic failure, can occur:

https://www.lispworks.com/documentation/HyperSpec/Body/01_db...

Let's take + (the addition function) as an example. It "might signal" a type error if some argument is not a number:

https://www.lispworks.com/documentation/HyperSpec/Body/f_pl....

where "might signal" means that the result is unpredictable but if the function does signal an error, it will be of the given type:

https://www.lispworks.com/documentation/HyperSpec/Body/01_db...

I can understand why the standard is written this way. Checking the types of arguments takes time. Sometimes you might not want to check the types for performance reasons.

It seems the author is using SBCL. As a practical matter, SBCL on the default settings will check the types of arguments. SBCL's manual (along with the manual of its predecessor, CMUCL) discusses how to manipulate these settings - the author discusses this, with the DECLARE form. But Common Lisp does not require this checking, so if you need your types checked, consult your implementation's manual. Indeed, SBCL allows you to change the settings for SPEED and SAFETY to specify how much type-checking you want.

All these caveats are also true for structures. The author says structure types are checked - again, as a practical matter, SBCL will check these unless you tell it not to. But that's not what the standard requires. Indeed, the standard explicitly states that "It is implementation-dependent whether the type is checked when initializing a slot or when assigning to it."

https://www.lispworks.com/documentation/HyperSpec/Body/m_def...

[edit] Relevant part of SBCL manual is here:

https://www.sbcl.org/manual/#Declarations-as-Assertions

Thank you for this. There is occasionally disagreement about what "Common Lisp" even means, and the spec is often cited, but as far as all of my posts, library work, and application work are concerned, Common Lisp means "the current reality of the major compilers as implemented in 2025". This is a descriptive / bottom-up definition, and as an active author of software it is the one I'm more concerned with. For instance, `:local-nicknames` have been essentially universally implemented among the compilers, despite not being part of the spec. To me, this makes that feature "part of Common Lisp", especially since basically all CL software written today assumes its availability.

You're right to point out too that the post is somewhat SBCL-centric - this too reflects a descriptive reality that most new CL software is written with SBCL in mind first. Despite that I'd always encourage library authors to write as compatible code as possible, since it's really not that hard, and other compilers absolutely have value (I use several).

Every programming language has a practical definition: it is the intersection of the sets of features that are accepted by the various relevant production compilers and interpreted identically enough to be portable to all of them.

Formal language definitions, standards, and books are great, but you can't compile with them. Abstract language specs that don't have reference implementations or conformance test suites are not particularly useful to either implementors or users.

this piece is lovely.

it’s worth noting that the piece’s concern is with a somewhat passive experience of commonlisp, i think. for example the focus is on dealing with ansi=>sbcl types out-of-the-box; if i’m not mistaken there are no type definitions.

this is a useful lens through which to glean an accurate portrait of a partiality of what’s possible with types in and around modern lispcraft, maybe, i think.

it’s difficult to think about hackability in writing bottom-up programming code without thinking about typing at or near runtime and/or/either typing either/or/and retyping some clos mod or mop ( or any-&-everything else ) during some runtime.

this is to say nothing of the conditions system modulo defining types or incorporation of domain specific, embedded or foreign languages via same modulus.

it’s a lovely piece is my point.

Reply on news.ycombinator.com