On Types

Being dynamically typed doesn't mean that there are no types. And in fact, pretending that there are no types gives raise to a number of problems, like unclear semantics of a function and such.

Let's explore an example from the heart of Clojure.

Lazy sequences

The work horse in the very low-level code of the sequence library is the `lazy-seq` macro. It returns an instance of class `clojure.lang.LazySeq` which encapsulates the abstract instructions to realise the actual sequence according to the body of the `lazy-seq` macro.

Should this class implement the `clojure.lang.ISeq` interface?

To answer this question, we have to understand the types involved and what the semantics of the interface functions are.

Sequences

First we have sequences—let's call the type “`Seq`”. A `Seq` is either nothing – `nil` – or something with a first element and a `Seq` of next elements. In particular there is not an empty `Seq`! Clojure's interface to `Seq` is `c.l.ISeq` with the functions `first` and `next` on the Clojure side.

Let's use some mathematically inspired notation.

``````first : Seq → Object
next  : Seq → Seq
``````

A `Seq` represents a sequential view on some collection of things.

Seqables

That's nice, but how do we get a `Seq` in the first place?

Clojure's main factory for sequences is the – surprise! – `seq` function. It may be used to construct a sequential view on an instance of a given type. It works on `Strings`, `Vectors`, `Sets`,… In particular is `seq` the identity on `Seqs`!

Let's call elements in the domain of `seq` `Seqable`.

``````seq : Seqable → Seq
``````

Lazy sequences

This is not the end of the story, however. Why should only physical things like `Strings` or `Vectors` be a source for sequences?

Instead of providing the set of elements from which the view is constructed, one could just as well provide some computation rule to construct the sequence as it is needed. So one can eg. construct a sequence of all natural numbers. Since these are infinite in size they cannot be represented in a datastructure like a `Vector`.

Back in ye olden dayes this was done via `lazy-cons`.

``````lazy-cons : →Object x →Seq → Seq
``````

`lazy-cons` constructed from a thunk which evaluates to an `Object` (denoted as `→Object`) and a thunk which evaluates to a `Seq` (denoted as `→Seq`) a sequence consisting of the `Object` as first element and the result of the second thunk as next elements. The evaluation of the thunks is only done when necessary. That is when `first` or `next` are called on the result of `lazy-cons`.

So `lazy-cons` returns a true `Seq`. But there lies the rub. To actually create a sequence via `lazy-cons` you already have to know, that there is at least one element! The decision how it looks like might be delayed, but that there is something, you have to know.

This has implications. Consider the following example.

``````user=> (def x (drop-while odd? (iterate #(+ % 2) 1)))
``````

Back when `drop-while` was implemented by virtue of `lazy-cons`, this would send you in an infinite loop. Because you have to know whether to return a `lazy-cons` or `nil`, you have to check whether there is an even number in the input sequence or not.

Really lazy sequences?

To remedy this situation the interface of a sequence was modified. Another function was added: `rest`. *In fact: `rest` was renamed to `next` and `rest` got a new meaning.*

To be truely lazy, you have to also delay the decision of whether there are next elements.

The outcome might be that there are no more elements. However, you don't know, yet. So you can't return `nil`. So, the return value of `rest` cannot be a `Seq` anymore.

``````rest : Seq → Seqable
``````

In fact, `rest` returns a `Seqable`, ie. you can call `seq` on the return value to obtain again a `Seq`. This is also reflected in the new `lazy-seq` constructor which replaces the old `lazy-cons`.

``````lazy-seq : →Seq → Seqable
``````

So, although `lazy-seq` has “seq” in its name, it actually doesn't return a sequence. And as such, I think it is a mistake for `c.l.LazySeq` to implement `c.l.ISeq`.

Lists are sequences?

Another example is the empty list `()`. The empty list is not a sequence! If it were, `seq` would return `()` again, which it does not. It returns (correctly) `nil`. Non-empty lists on the other hand may serve as their own sequence. But this is merely an implementation detail.

Upshot

You are still awake? Wow! Congratulations.

This is a dry topic, but an important one. Even in a dynamically typed language like Clojure there are types. And it is important to understand their relationship. I think investing a bit of time in such considerations helps to get a deeper view into the problem domain.

Here the complete, consistent `Seq` interface in all its glory. Although Clojure does not fully adhere to it.

``````first     : Seq     → Object
next      : Seq     → Seq
rest      : Seq     → Seqable
seq       : Seqable → Seq
lazy-seq  : →Seq    → Seqable
; and formerly
lazy-cons : →Object x →Seq → Seq
``````