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.

One step ahead

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

Published by Meikel Brandmeyer on .