content/blog/2018/08/types-and-classes-in-common-lisp.markdown @ b42cf43b7f35

+++
title = "Types and Classes in Common Lisp"
snip = "They're not the same thing!"
date = 2018-08-30:00:00Z
draft = true

+++

One thing that often confuses people new to Common Lisp is the differences
(and interactions) between types and classes in the language.  Type and classes
are two completely separate things in Common Lisp, but if you're coming from
modern languages it's easy to get the two blurred and confused.  Hopefully this
post will make the distinction more clear.

<div id="toc"></div>

## Objects

Before we dive into defining types and classes we should define what an "object"
is, because the term will come up immediately.  The following definition will be
good enough for our purposes here:

**An object is a hunk of bits somewhere in memory.**

Objects are the things the garbage collector manages.  They're the things you
pass to functions, and the things you return from them.  Objects have identity,
and that identity can be compared with `eq`.

I realize that this is a little handwavey, but I think it's good enough to work
with for now.

TODO values

(There are a few corner cases (e.g. fixnums), but you can safely ignore them
while trying to wrap your head around this post.)

## Types

Types in Common Lisp can be summed up in one single line:

**A type is a set of objects.**

We already saw what objects are.  "Set" in this definition is a set in the
mathematical sense: an unordered collection of elements (possibly *infinitely
many* elements) with no duplicates.

That's it.  That's all there is to it.  This probably seems like a weird
definition if you've never thought much about it before, but let's look at some
examples to see what falls out of it.

### Type Designators

First we need a way to specify types.  Common Lisp has a concept called [type
designators][TODO] for this purpose.  A type designator is something that
represents the given type.

Let's look at a common type: the set of all integers.  Obviously it would be
impractical to talk about this set by listing out all of its members.
A mathematician would denote this type as Z TODO.  A Common Lisp programmer
would use the type designator `integer`.

### Being Of a Type

What are some things we might want to do with a type?  One thing might be to ask
whether a particular object "is of that type", done with `typep` in Common Lisp
(and `instanceOf` in Java, TODO in Python, etc).  But what does this actually
*mean*?

When you're thinking of types as sets of objects, asking whether an object is of
a particular type essentially asking if the object is a member of that set!

Let's look at couple of examples:

    (typep 42 'integer)

Here we're asking "Is `42` a member of the set of all integers?"

    (typep x 'symbol)

Now we're asking "Is the object that `x` evaluates to a member of the set of all
symbols?".

    (typecase foo
      (symbol ...a...)
      (integer ...b...)
      (number ...c...))

And now we're saying "Evaluate `foo`.  If the result is a member of the set of
all symbols, do `a`.  Otherwise if it's a member of the set of all integers, do
`b`.  Otherwise if it's a member of the set of all numbers, do `c`.  Otherwise
return `nil`.".

### Subtypes and Supertypes

So checking if an object is of a particular type is simply the set membership
operation.  It turns out that other set operations also have useful definitions
when you think this way:

* If `foo` is a supertype of `bar`, that means `foo` is a superset of `bar`.
* If `bar` is a subtype of `foo`, that means `bar` is a subtype of `foo`.

For example:

* The set of all integers is a subset of the set of all real numbers, which
  makes `integer` a subtype of `real`.
* The set of all symbols is a superset of the set of all keyword symbols, so
  `symbol` is a supertype of `keyword`.
* The set of all floating point numbers is neither a subset nor a superset of
  the set of all symbols, so neither is a subtype of the other.

Common Lisp's numeric tower consists of nice sequences of types that get more
and more specific as you take further subsets:

`number` ⊆ `real` ⊆ `rational` ⊆ `integer` ⊆ `fixnum`

### Explicit Designation

There are other ways to designate sets too.  You can use the `member` type
designator to just list out the members of a set by hand if you want:

    (member 1 2 3) ; => designates the set {1, 2, 3}

### Everything and Nothing

The type `t` is the set of all objects.  The type `nil` is the empty set.

This last one can sometimes cause confusion.  The symbol `nil` is *not* of type
`nil` because the symbol `nil` is not a member of the empty set (because it's
empty!).  If you want to talk about the set containing the symbol `nil`, that's
called `null`:

```lisp
(typep nil nil)  ; => NIL, nil is NOT a member of the empty set
(typep nil null) ; => T,   nil IS a member of { nil }
```

### Type Combinations

Let's look at some more set operations.  Set complement is probably the
simplest, and Common Lisp supports this with the `not` compound type specifier
TODO:

```lisp
(typep 1/2     '(not integer)) ; => T
(typep "hello" '(not integer)) ; => T
(typep 42      '(not integer)) ; => NIL
```

Set union is covered with `and`:

```lisp
(typep 1     '(or integer string)) ; => T
(typep "hi"  '(or integer string)) ; => T
(typep :what '(or integer string)) ; => NIL
```

And of course set intersection is done with `and`:

```lisp
(typep 1 )
```


## Classes

## Blurring the Line