Lambda Island

Clojure is built on a well thought out set of abstractions. To implement these, it makes use of the ability to define abstractions in the host language, namely Java interfaces, and the high-performance polymorphism that they provides.

As a Clojure programmer you don’t have to resort to Java to achieve the same thing. All the facilities are there to create interfaces, and to create types that implement interfaces, getting you as close to the JVM as you need to be.

Transcript

If you came from an object oriented or statically typed programming language before coming to Clojure, you might have been disoriented at first. Where are the classes? Where are the types?

Clojure deliberately stepped away from the “kingdom of nouns” found in other languages. Instead of having many different types, each with their own custom interface, Clojure code tends to use a small number of general purpose data structures. This way the focus shifts from how the program is structured, to what the program does.

This works well because Clojure’s data types are built on a small number of abstractions, like Seqable, Associative, or Indexed.

	list	lazy-seq	map	set	vector
seq?	true	true	false	false	false
seqable?	true	true	true	true	true
associative?	false	false	true	false	true
counted?	true	false	true	true	true
indexed?	false	false	false	false	true
ifn?	false	false	true	true	true

“Abstraction” in this case refers to having shared functions that work across a number of concrete types. Take for example an equality check. Comparing two vectors is very different from comparing two numbers, you would need a separate implementation for each. And yet we have a single function that does both. The equality check automatically adjusts itself to its inputs. This is called “polymorphism”, from the Greek for “many shapes”. You can also say that it “dispatches” to the right implementation based on the type of its arguments.

(= [1 2 3] [1 2 3])
(= 5 7)

To achieve this, JVM based Clojure makes use of the facilities that Java provides for defining these kind of abstractions. Java calls these interfaces. Clojure’s data structures are Java classes that implement these interfaces. This way Clojure achieves the best performance that the host has to offer, both for data access, and for method dispatch based on type.

Here’s an example of one of these abstractions. All of Clojure’s persistent collections implement this interface. They all have to provide implementations for how to count the number of items in the collection, how to add an item to the collection, how to create an empty collection, and how to do an equivalence check.

public interface IPersistentCollection extends Seqable {
    int count();
    IPersistentCollection cons(Object o);
    IPersistentCollection empty();
    boolean equiv(Object o);
}

Other interfaces that Clojure uses internally include ISeq, Associative, Indexed, and Counted.

clojure.lang.ISeq
clojure.lang.Sequential
clojure.lang.Associative
clojure.lang.Counted
clojure.lang.Indexed
clojure.lang.IFn
clojure.lang.IMeta

Defining these in Java was necessary to bootstrap the language, but we’ve come a long way since then, and now the same facilities are also available to the programmer from inside Clojure.

You can define new abstractions with definterface, and define new types that implement these abstractions with deftype. When you do this there is really nothing sitting between your code and the JVM. You get efficient field access and high-performing method dispatch, as if your code was written in Java directly. These constructs generate Java classes under the hood, and so they are also useful for exposing Clojure code to Java or other JVM languages.

The downside is that lose the rich and elegant semantics that Clojure’s built-in types provide. You can make your own types behave like Clojure’s built-ins by implementing the same abstractions, but you have to put in the work. None of that comes for free when using deftype.

Clojure also has it’s own mechanism for polymorphism called “protocols”, as well as a version of deftype that provides a lot of extra facilities, called defrecord, which is more generally useful for application code. I’ll focus first on interfaces and types. Protocols and records will be explored in the next episode.

;; low level
(definterface ,,,)
(deftype ,,,)

;; application level
(defprotocol ,,,)
(defrecord)

I already showed you examples of Java interfaces. With definterface you can define these directly from Clojure. It’s not that commonly used, especially since protocols are often a better alternative, but it’s there if you need it.

(definterface Coercible
  (to-string [])
  (to-int []))

An interface by itself doesn’t do antything yet, to provide implementations of interfaces, you use defrecord, or deftype.

Let’s see what that looks like by implementing a binary tree. A binary tree is a very basic data structure, making it’s easy to implement and fun to play around with.

In a binary tree, each node has a value and two child nodes, we call these the left and the right subtree. All values in the left subtree of a node are lower than the node’s value, and all values in the right subtree are greater than the node’s value.

Because of this property, descending into the tree comes down to doing a binary search. This makes it fast to check if a certain value is present. Traversing the tree depth-first you get all values back in increasing order, so in that sense it acts as a sorted collection.

To implement this I’ll create a type with three fields: value, left, and right. I’ll call this type Node, since it form a node in the tree. This data structure is recursive, so having a type for a Node is enough to create complete trees.

deftype takes the name of the type, and then a vector form with the field names.

Class names in Java have to be capitalized, and so it is common to do the same in Clojure. The JVM doesn’t enforce this though, so it’s entirely possible to use lowercase names as well.

(ns ep23deftype.binary-tree)

(deftype Node [value left right])

This generates bytecode for a Java class with the same name. As with other Java classes, if you want to reference it from Clojure, you need to import it into the namespace.

Clojure namespaces contain vars, and a Java class is not a var, so instead this class is defined in a Java package, with its name derived from the namespace name. Package names can’t contain dashes, so instead use underscores.

Now that the class has been imported, you can call its constructor, which takes positional arguments that correspond with its fields.

(ns ep23deftype.scratch
  (:import ep23deftype.binary_tree.Node))

(Node. 17 nil nil)

In ClojureScript this distinction isn’t relevant, and you can require and :refer the type itself to access its constructor.

;; ClojureScript only!

(ns ep23deftype.scratch
  (:require [ep23deftype.binary-tree :refer [Node]]))

(Node. 17 nil nil)

Now instead of remembering this distinction, you can require the arrow constructor function that automatically gets generated. It’s a regular function, so you use require/refer as with any Clojure or ClojureScript function.

(ns ep23deftype.scratch
  (:import ep23deftype.binary_tree.Node)
  (:require [ep23deftype.binary-tree :refer [->Node]]))

(Node. 100 nil nil)
(->Node 100 nil nil)

Now that you have constructed a Node, you can access its fields with dot forms. Keep in mind that in ClojureScript you need to add a dash to make it clear you are accessing a field, and not calling a method.

;; clojure
(.value (->Node 100 nil nil)) ;;=> 100

;; clojurescript
(.-value (->Node 100 nil nil)) ;;=> 100

This Node type isn’t doing much yet, let’s have it participate in the abstraction for seqs. This way you immediately get compatibility with most functions in clojure.core, like first, rest, or map. It also means you can start populating trees with conj and into.

We’ll implement the ISeq interface, which has four methods. First add the name of the interface to the deftype form, followed by the method implementations. The ISeq interface contains first, next, more, and cons.

The first argument to each method will always be the node itself, followed by any extra arguments. You don’t always need this this reference though, since the fields value, left, and right are also directly accessible in the method bodies.

Although it looks like these methods “close over” the fields, they are not actually closures, and trying for example to wrap the deftype in a let form will not work as you would expect.

(deftype Node [value left right]
  clojure.lang.ISeq
  (first [this] ,,,)
  (next [this] ,,,)
  (more [this] ,,,)
  (cons [this x] ,,,))

The details of how these methods work are beyond the scope of this episode, so I’m going to fast forward a bit here. As always all code is on Github, you can find the link in the show notes.

The main things to note are that these methods work recursively. You can see first and next recursing into the left subtree.

The other thing to note is that, since this is a functional data structure, I’m constructing new nodes whenever something needs updating. There’s even a bit of structural sharing, like a real grown-up persistent data structure.

As you would expect instances of Node will be immutable. It is possible to mark fields as mutable, but you need a very good understanding of how mutability works on the host level, and it’s not a topic I will cover.

The full implementation can be found on Github

(deftype Node [value left right]
  clojure.lang.ISeq
  (first [_] (if left
               (first left)
               value))
  (more [this] (let [n (next this)]
                 (if (nil? n) () n)))
  (next [_] (if left
              (if (.left left)
                (Node. value (next left) right)
                (Node. value (.right left) right))
              right))
  (cons [this x] (cond
                   (nil? value)
                   (Node. x nil nil)

                   (= x value)
                   this

                   (< x value)
                   (Node. value
                          (if left
                            (conj left x)
                            (Node. x nil nil))
                          right)

                   (> x value)
                   (Node. value
                          left
                          (if right
                            (conj right x)
                            (Node. x nil nil))))))

I’ll add two more interfaces to make Clojure happy. These nodes are seqable, since they are already seqs they can just return themselves. Finally also add Sequential. This is just an empty interface, so there are no methods to define, but for some reason Clojure checks for Sequential rather than Seqable before calling seq.

These kind of little anomalies make it clear that these abstractions have grown organically throughout Clojure’s design history. You’ll find in general that things are better organized in ClojureScript, which had the benefit of starting over with a clean slate.

This does mean that types are not readily portable between Clojure and ClojureScript

(deftype Node [value left right]
  clojure.lang.Sequential

  clojure.lang.Seqable
  (seq [this] this)

  clojure.lang.ISeq
  ,,,)

And now it’s time to have some fun! By convention the code will treat a node with a nil-value as an empty tree, so create an empty node by setting all fields to nil, then use conj or into to populate it. You can add a bunch of random numbers into a tree to see if the sorting works.

Because a node is a seq, Clojure shows it as such, and because the tree keeps itself sorted, we get the numbers back in ascending order. Nice.

(def EMPTY_TREE (->Node nil nil nil))
(into EMPTY_TREE (take 10 (repeatedly #(rand-int 100))))
;;=> (12 21 22 51 54 62 78 80)

Note that, since we implemented Java interfaces, the functions that we defined are Java methods, rather than Clojure functions. To call them you would have to use interop forms. It just so happens that Clojure’s core functions call these methods internally, so you don’t really notice.

(def tree (into EMPTY_TREE (take 10 (repeatedly #(rand-int 100)))))
(.seq tree)
(.more tree)
(.cons tree 55)

(seq tree)
(rest tree)
(conj tree 55)

Our type isn’t quite finished yet. Try to check if two instances are equivalent. This causes an exception, seems we’re still missing some methods.

(= (into EMPTY_TREE [5 4 6 9]) (into EMPTY_TREE [5 4 9 6]))
;;=> Unhandled java.lang.AbstractMethodError

Have another look at ISeq. It defines four methods, but also extends the IPersistentCollection interface, so we need to implement that one as well.

I’ll leave implementing these as an exercise for eager learners. You can find the full implementation on Github.

public interface IPersistentCollection extends Seqable {
  int count();
  IPersistentCollection cons(Object o);
  IPersistentCollection empty();
  boolean equiv(Object o);
}

So you can implement interfaces, as well as protocols, but that’s for next episode, but you can also override methods from java.lang.Object. All Java classes inherit from this Object class, which provides a dozen methods that all objects share. Most of these you probably want to leave alone, but if you’re using deftype and not implementing IPersistentCollection, then it’s a good idea to override equals.

(deftype Pair [x y]
  Object
  (equals [me you]
    (and (instance? Pair you)
         (= x (.x you))
         (= y (.y you)))))

Clojure’s equality check falls back to this equals method, and if you use the default implementation you will get identity semantics, instead of the more useful value semantics.

;; without custom equals
(= (->Pair 4 5) (->Pair 4 5))    ;;=> false

;; with custom equals
(= (->Pair 4 5) (->Pair 4 5))    ;;=> true

In ClojureScript Object can be used to add arbitrary methods to a type. Javascript doesn’t have interfaces, but sometimes code will still expect specific methods to be available on an object. Therefore this loophole was introduced.

;; clojurescript
(deftype Pair [x y]
  Object
  (vectorLength [_]
    (js/Math.sqrt (+ (* x x) (* y y)))))

(.vectorLength (->Pair 3 2)) ;;=> 3.605551275463989

A final useful thing you can do is adding type hints on the fields using metadata. For instance, you can mark the value field as being of type long, meaning a 64 bit integer.

These type hints serve two purposes. When using a primitive type, like int, long, or boolean, the field in the generated class will be of this type, meaning only values of the given type can be assigned to the field. Assigning something else, say a String to a field of type long, will yield an exception.

The main reason for using a type hint like this however isn’t type safety, but it’s to prevent Clojure from using “boxed” primitives. With boxed primitives, each number gets wrapped into its own object, and unwrapped again when it’s needed to compute something.

This boxing and unboxing adds overhead, so if your code does intensive data processing and arithmetic then using primitive type hints could help speed things up.

(deftype Node [^long value left right]
  ,,,)

Adding type hints for non-primitive types, does not influence the generated field type. Say I mark the value field as being of type String. You could still assign something else to the field and Clojure wouldn’t complain, you just might get a ClassCastException later on.

This type annotation does have a purpose, however. Have a look at the cons method. It’s comparing the inserted value with the value in the node, to see if it should be inserted in the left or right subtree. Using < or > doesn’t work with Strings, so instead I’ll use the compareTo method of String, which compares two strings lexigographically.

When Clojure comes across this kind of interop call, it has to figure out the type of object being used before it can actually make the call. Doing that at runtime incurs a cost. By adding the type hint, Clojure assumes value will always be a String, and so it generates optimized code specialized for Strings, avoiding runtime checks.

(deftype Node [^String value left right]
  ,,,
  clojure.lang.ISeq
  (cons [this x]
    (cond
      (nil? value) (->Node x nil nil)
      (= x value) this

      (pos? (.compareTo value x))
      (->Node value
              (if left
                (conj left x)
                (->Node x nil nil))
              right)

      (neg? (.compareTo value x))
      (->Node value
              left
              (if right
                (conj right x)
                (->Node x nil nil)))))
  ,,,)

Now this stuff comes pretty close to micro-optimizing, there are probably better places to save a few cycles, but if you’re really worried about the bit of overhead this reflection causes, then you can find out if you’re affected by setting the dynamic var *warn-on-reflection* to true.

With this flag on, you’ll get a warning whenever Clojure needs to use reflection to figure out the type of something, which is an indication that you could speed things up by adding a type hint. *warn-on-reflection* needs to be set for each source file individually, that way you won’t get swamped with warnings from third party libraries.

(def *warn-on-reflection* true)

Finally to wrap up let’s have another quick look at ClojureScript. Here’s the ClojureScript version of the binary tree.

deftype in ClojureScript also creates types in the host environment, in other words: Javascript classes. But Javascript doesn’t have interfaces. Being dynamically typed means there is less need to make abstract interfaces explicit. Instead people rely on “duck typing”, assuming classes implement methods with specific names.

Because named abstractions are core to Clojure’s design, Clojurescript’s data structures make use of Clojure’s own mechanism for named abstractions: protocols. So ISeq, which is an interface in Clojure, is a protocol in ClojureScript. However, you can implement protocols in deftype the same way you would implement interfaces.

There are a few more things to pay attention to when writing types for Clojurescript. Clojurescript’s protocols are more fine-grained then the interfaces that Clojure uses. For example, count, equiv and empty are all part of the IPersistentCollection interface, but in Clojurescript each of these has their own protocol, ICounted, IEquiv, and IEmptyableCollection respectively.

The method names defined by Clojurescript’s protocols all start with a dash. The function without a dash in cljs.core will delegate to this dashed version, just like how functions in clojure.core delegate internally to interop forms. Finally don’t forget to use dot-dash when accessing fields.

(deftype Node [value left right]
  ISeqable
  (-seq [this] this)

  ISeq
  (-first [_] ,,,)
  (-rest [this] ,,,)

  INext
  (-next [_] ,,,)

  ICollection
  (-conj [this x] ,,,)

  IEquiv
  (-equiv [this o] ,,,)

  IEmptyableCollection
  (-empty [_] ,,,)

  ICounted
  (-count [_] ,,,)

  IPrintWithWriter
  (-pr-writer [coll writer opts] ,,,))

This has been a fairly exhaustive exposition on deftype, I hope you enjoyed it. Till next time!

deftype and definterface