Chapter 4. Multimethod polymorphism

This chapter covers

• Polymorphism and its types
• Clojure multimethods for ad hoc polymorphism
• Using multi-argument dispatch
• Querying, modifying, and creating dispatch hierarchies

You should now know how to use Clojure’s types and functions and even write some fairly advanced higher-order functions, but you may still be wondering how to build larger systems with functional programming. In this chapter, you’ll learn how to use the most powerful and flexible tool Clojure has for creating and using abstractions in large programs: multimethods.

4.1. Polymorphism and its types

Polymorphism is the ability to use multiple types as though they were the same—that is, you can write the same code to operate on many different types. This kind of abstraction allows you to substitute different types or implementations without having to change all code that touches objects of those types. Polymorphism’s ability to reduce the surface area between different parts of a program and easily substitute some parts for other parts is what makes some form of it essential in larger systems. In a certain sense polymorphism provides the ability to create your own abstractions.

There are multiple ways to achieve polymorphism, but three are common to many languages: parametric, ad hoc, and subtype polymorphism. We’ll concentrate on what these look like in Clojure without multimethods but also glance at how other languages achieve the same kinds of polymorphism.

4.1.1. Parametric polymorphism

You’ve actually already come in contact with polymorphism in Clojure. As you saw in chapter 2, functions such as get, conj, assoc, map, into, reduce, and so on accept many different types in their arguments but always do the correct thing. Clojure collections are also polymorphic because they can hold items of any type. This kind of polymorphism is called parametric polymorphism because such code mentions only parameters and not types. It’s common in dynamically typed languages because such languages by their nature don’t often mention types explicitly. But it’s also present in some statically typed programming languages, both object-oriented languages such as Java and C# (where it’s called generics) and functional programming (OO) languages such as ML and Haskell.

This kind of polymorphism is usually invisible in Clojure: you just use the built-in function and collection types, and the Clojure runtime works out what should happen or throws an exception (or often returns nil) if the type doesn’t work with that function. Underneath the covers are Java classes and interfaces checking types and implementing the polymorphism. It’s possible in Clojure to create new types that work with Clojure built-in functions such as conj using a mix of Java interop and user-defined Clojure types: we’ll demonstrate this technique in chapter 9.

But in Clojure if you want to create your own parametrically polymorphic functions, you need to look to other kinds of polymorphism to implement them. This seems like a curious statement: How can you implement one type of polymorphism using another? How can a piece of code represent two kinds of polymorphism simultaneously? Polymorphism is often a matter of perspective: from the perspective of the calling code (the code using your functions and types), your code can appear parametrically polymorphic—that’s often precisely the goal. But internally, hidden from the caller, your code may use a form of polymorphism that’s explicit about types. That’s where the other two forms of polymorphism come in.

4.1.2. Ad hoc polymorphism

Ad hoc polymorphism is simply enumerating each possible type a function can use and writing an implementation for each one. You can recognize this pattern in Clojure easily: some function is called on the argument to produce a dispatch value, and cond, case, or condp selects an implementation with a matching dispatch value to produce a result. Here’s an example polymorphic function that simply returns a string naming its argument’s type:

public class TypeNamer extends Object {
    // ...
    public String typeName(String thing) { return "string"; }
    public String typeName(PersistentVector thing) {
        return "vector";
    }
}

Notice that this example of ad hoc polymorphism doesn’t allow calling code to “train” the ad-hoc-type-namer function to understand new types—you can’t add new clauses to the condp expression without rewriting the function. This property is called closed dispatch because the list of available implementations (that is, to which you can dispatch) can’t be changed from the outside. But you can implement open dispatch by keeping the implementations outside your type-naming function:

Ad hoc polymorphism is simple and easy to understand, but it’s done from the perspective of the implementations that use a type, not from the perspective of the types being used. The next form of polymorphism is more from the type’s perspective.

4.1.3. Subtype polymorphism

So far we’ve been concentrating on the functions that are polymorphic, but the types can also be polymorphic. Subtype polymorphism is a kind of polymorphism where one type says it can be substituted for another so that any function that can use one type can safely use the other. Stated more simply, one type says it’s “a kind of” another type, and code that understands more general kinds of things will automatically work correctly with more specific things of the same general kind.

Subtype polymorphism is the dominant kind of polymorphism in OO languages and it’s expressed as class or interface hierarchies. For example, if a Person class inherits from (or extends) an Animal class, then any method that works with Animal objects should automatically work with Person objects too. Some dynamic OO languages also allow a form of subtype polymorphism (called structural subtyping) that doesn’t use an explicit hierarchy or inheritance. Instead methods are designed to work with any objects that have the necessary structure, such as properties or methods with the correct names. Python, Ruby, and JavaScript all allow this form of subtyping, which they call duck typing.

Clojure can use Java classes and interfaces through its Java interop features and Clojure’s built-in types participate in Java interfaces and class hierarchies. For example, remember in a footnote in chapter 2 we briefly mentioned that Clojure map literals may be array-map when they’re small but become hash-map when they get larger? In Java there’s an abstract class that they share, as you can see in the following example:

By writing code that knows how to use APersistentMap, you know it works with any subtype using your single implementation; it even works for types that don’t exist yet as long as they’ll extend APersistentMap.

Clojure also offers some ways to create subtypes of your own using multimethod hierarchies (which we’ll look at later in this chapter) or protocols (which we’ll discuss in chapter 9), but beyond this Clojure offers no rigid notion of subtyping. The reason is that subtyping, while powerful because it allows you to write fewer implementations of functions, can also be restraining if applied too broadly because there’s often no one, single, universally applicable arrangement of types. For example, if you’re writing geometry code, it may be simpler for some functions to see a circle as a special case of an ellipse but for others to view an ellipse as a special case of a circle. You may also have a single thing belong to multiple, nonoverlapping type hierarchies at the same time: a person is a kind of material body to a physicist but a kind of animal to a biologist. More importantly, Clojure is focused on data and values, not types: the programming-language type used to contain some information (such as a map, list, or vector) is independent of the problem-domain type (such as animal, vegetable, or mineral), and it’s the latter that should be the focus. But this means your own code, and not your programming language, will need to distinguish somehow between maps that represent animals and maps that represent minerals or to know that an animal can be represented with either a list form or a map form.

Multimethods provide features to express both ad hoc and subtype polymorphism and even to express multiple different kinds of subtype polymorphism at the same time. Let’s leave polymorphic theory behind us now and look more concretely at how multimethods can help you write polymorphic code.

4.2. Polymorphism using multimethods

For the rest of the chapter we’re going to focus exclusively on how to use multimethods to write polymorphic code, specifically to meet the needs of a hypothetical expense-tracking service you’re building.

4.2.1. Life without multimethods

Consider the situation where the expense-tracking service you’ve written has become popular. You’ve started an affiliate program where you pay referrers if they get users to sign up for your service. Different affiliates have different fees. Let’s begin with the case where you have two affiliates: mint.com and google.com.

You’d like to create a function that calculates the fee you pay to the affiliate. For the sake of illustration, let’s decide you’ll pay your affiliates a percentage of the annual salary the user makes. You’ll pay Google 0.01%, Mint 0.03%, and everyone else 0.02%. You’ll write this without polymorphism first (you’ll accept percentage values as straight numbers and you’ll translate them by multiplying by 0.01 within the function):

You should be able to recognize affiliate-fee as an example of closed dispatch, ad hoc polymorphism, which uses :referrer as a dispatch function. It also has a default implementation to use if no match is found.

The biggest problem with the affiliate-fee function is the closed dispatch: you can’t add new affiliates without rewriting affiliate-fee. Now let’s look at how you’d solve this problem with multimethods.

4.2.2. Ad hoc polymorphism using multimethods

Before you implement the same functionality using multimethods, let’s take a moment to understand their syntax. Multimethods use a pair of macros: defmulti defines a multimethod and how to produce a dispatch value with which to find an implementation. The defmethod macro defines an implementation for a specific dispatch value. In other words, defmulti acts as the first clause of a case expression, and each defmethod acts as a single test-and-result pair of a case expression. This is what affiliate-fee looks like as a multimethod:

defmulti

Multimethods are declared using the defmulti macro. Here’s a simplified general form of this macro:

(defmulti name docstring? attr-map? dispatch-fn & options)

name is the name of the multimethod used to invoke it and to add implementations using defmethod. docstring? and attr-map? are optional documentation and metadata arguments—the same as in defn. The required dispatch-fn function is a regular Clojure function that accepts the same arguments that are passed in when the multimethod is called. The return value of dispatch-fn is the dispatch value used to select an implementation. The options are key-value pairs to provide optional specifications. There are only two options: :default, to select a new default dispatch value, and :hierarchy, to use a custom dispatch value hierarchy. Here’s an example with a custom default:

A few notes before we continue. First, notice that you can use a plain keyword :referrer as a dispatch function: this is a common idiom where the argument to the defmethod is always a map and you want to dispatch by the value of one of its keys. Second, because you had to redefine the defmulti, all the existing defmethods were lost: see the following sidebar for more discussion of the issues surrounding redefining a defmulti. We’ll talk about the :hierarchy option later: it’s used for subtype polymorphism.

defmethod

Implementations of a multimethod declared with defmulti are added with the defmethod macro, which looks like a normal (docstring-less) defn except with a dispatch value between the name and the arguments:

(defmethod multifn dispatch-value & fn-tail)

This creates a concrete implementation for a previously defined multimethod. The multifn identifier should match the name in the previous call to defmulti. The dispatch-value will be compared with the return value of the dispatch-fn from earlier to determine which method will execute. The fn-tail is the body of the implementation and accepts anything you’d put inside a (fn ...) form, including argument destructuring. Normally this is just an argument vector followed by a function body, but multiple arities are okay, too:

(defmethod my-multi :default [arg] "body")
(defmethod my-many-arity-multi :default
  ([] "no arguments")

  ([x] "one argument")
  ([x & etc] "many arguments"))

defmethod will create a normal function from its function body and mutate the original defmulti object to add this function to its dispatch map under the dispatch-value key. You can inspect the dispatch map of a multimethod using the functions get-method and methods. get-methods takes a multimethod and a dispatch value and returns an implementation function for that value using the same dispatch logic as calling the multimethod directly. methods just returns the entire dispatch map for a multimethod. Let’s see an example using the affiliate-fee multimethod from earlier:

You can also remove multimethod implementations using remove-method and remove-all-methods. remove-method removes the implementation for a dispatch value. Note that unlike get-method, the dispatch value to remove must be an exact match. Finally, remove-all-methods removes all implementations of a multimethod.

We’ve covered the basics of multimethods for ad hoc polymorphism using a single dispatch value to select a matching implementation. Now you’re going to see how multimethods can consider multiple dispatch values to select an implementation.

4.2.3. Multiple dispatch

Imagine your expense-tracking service is even more successful than before and the affiliate program is working great. So great, in fact, that you’d like to pay more profitable users a higher fee. This would be a win-win situation for the affiliate network and your service. Here are a few more example users with a :rating key to indicate the user’s profit rating:

(def user-1 {:login "rob"     :referrer "mint.com"   :salary 100000
             :rating :rating/bronze})
(def user-2 {:login "gordon"  :referrer "mint.com"   :salary 80000
             :rating :rating/silver})
(def user-3 {:login "kyle"    :referrer "google.com" :salary 90000
             :rating :rating/gold})
(def user-4 {:login "celeste" :referrer "yahoo.com"  :salary 70000
             :rating :rating/platinum})

Now let’s consider the business rules shown in table 4.1.

Table 4.1. Affiliate fee business rules

From the rules it’s clear that there are two values based on which fee percentage is calculated: the referrer and the profit rating. In a sense, the combination of these two values is the affiliate fee type. Because you’d like to dispatch on this virtual type, comprising two values, you’ll create a function that computes the pair:

(defn fee-category [user]
  [(:referrer user) (:rating user)])
;=> #'user/fee-category
(map fee-category [user-1 user-2 user-3 user-4])
;=> (["mint.com"   :rating/bronze]
     ["mint.com"   :rating/silver]
     ["google.com" :rating/gold]
     ["yahoo.com"  :rating/platinum])

You’ll use fee-category as your dispatch function for another multimethod, profit-based-affiliate-fee:

This reads a lot like the table with business rules, and adding new rules is still quite easy and doesn’t involve modifying existing code. But how does this code work in practice?

All the business rules in table 4.1 are applied and the default fee is used if there’s no affiliate program with the user’s combination of referrer and rating. But notice that you did have to duplicate some code: the business rules treat gold and platinum profit ratings the same, but you still had to write a separate method (with the same implementation) for each. Duplicate defmethods that differ only by dispatch value are a strong hint that those dispatch values are the same kind of thing. This isn’t something ad hoc polymorphism can help you with, but subtype polymorphism is great for removing redundant implementations. Fortunately, multimethods can make use of subtype polymorphism, as you’ll see in the next section.

4.2.4. Subtype polymorphism using multimethods

Your profit-rating infrastructure is in place, but you still have some duplicated code you’d like to get rid of: namely, your implementations for the gold and platinum ratings of mint.com and google.com are the same. When you point this out to the business folks, they elaborate that the ratings are actually in a hierarchy: bronze and silver are basic-level and gold and platinum are premier-level profit ratings. In other words, bronze and silver are both “kinds of” basic profit ratings, and gold and platinum are “kinds of” premier profit ratings, as illustrated in figure 4.1.

Figure 4.1. The hierarchy of profit rating levels as explained by the business folks. You can use this external-facing classification to simplify your code by defining a dispatch hierarchy reflecting this structure.

This talk of “kinds” is a big hint that you’re dealing with subtype polymorphism here. Multimethods enable you to build and query your own hierarchies of types (represented by namespaced keywords) using a family of functions: derive, underive, isa?, parents, ancestors, and descendants.

Building and querying type hierarchies

The derive function is used to establish a “kind of” or subtype relationship between two types. Multimethods represent types as keywords or Java classes.

The ordinary form of derive takes two arguments: a keyword representing a type and another keyword representing the parent. (You can remember this argument order by thinking “derive x from y,” “x is a kind of y,” or “x is a child of y.”) In the two-argument form, derive will mutate a global hierarchy to establish the type relationship. Because you’re mutating a global hierarchy, derive requires that your keywords have a namespace to reduce the chance of name collisions. (This requirement is relaxed for independent hierarchies, as explained later.) Here’s an example implementing the hierarchy described in figure 4.1:

If you make a mistake or simply want to change the hierarchy, you can use the underive function to remove type relationships: it takes the same arguments as derive.

Now that you’ve created your hierarchy, how do you see it? The most important function is isa?: this is the function multimethods use internally to determine what method to select for a dispatch value. You can also use parents, ancestors, and descendants to inspect the hierarchy more directly. Here’s an example using the hierarchy you just made:

Now you can use this hierarchy in a simple example multimethod that returns an appropriate greeting depending on a user’s profit rating:

(defmulti greet-user :rating)
;=> #'user/greet-user
(defmethod greet-user :rating/basic [user]
  (str "Hello " (:login user) .))
;=> #<MultiFn clojure.lang.MultiFn@d81fe85>
(defmethod greet-user :rating/premier [user]
  (str "Welcome, " (:login user) ", valued affiliate member!"))
;=> #<MultiFn clojure.lang.MultiFn@d81fe85>
(map greet-user [user-1 user-2 user-3 user-4])
;=> ("Hello rob." "Hello gordon." "Welcome, kyle, valued affiliate member!" "Welcome, celeste, valued affiliate member!")

Notice that even though you supplied only two method implementations, the multimethod was able to correctly handle all four profit ratings by considering the subtype relationships you defined using derive. Can this help you remove some duplicate code from the profit-based-affiliate-fee methods? Yes!

Subtypes and multiple-dispatch

Multimethods let you combine multiple-dispatch and type hierarchies. If you return a vector from your dispatch function, the multimethod will consider each item in the vector separately with isa? when trying to find a matching implementation. So you can finally clean up your profit-based-affiliate-fee code to remove those annoying duplicates:

Not only have you removed some duplicate code, but you’ve also captured more precisely the intention of the business rules and protected the code against future changes to the profit-rating levels. So subtype polymorphism allowed you to reduce code duplication by sharing implementations (something it’s especially good at), but it also introduces some complexity that you’ll learn to manage in the next section.

Resolving method ambiguities

There’s a downside to using subtyping with multiple dispatch: it introduces the possibility of ambiguity. This is best demonstrated by an example. Suppose your expense-tracking service has gotten so popular that it has expanded to become a massive multiplayer online role-playing game. You still have your users and profit ratings, but now you want users to be able to size up other users before going into battle. Here’s a first draft of the size-up multimethod, which takes two users—an observer and an observed—and returns a description of the observer for the observed:

The problem here is that the type system, combined with multiple dispatch, introduces an ambiguity about which method implementation should be used: Do platinum users look scrawny to other platinum users, or do they shimmer with an unearthly light like themselves?

Suppose you decide that platinum users should shimmer to other platinum users, not look scrawny. There are a few ways you could remove the ambiguity. First, you could avoid the use of :rating/ANY in the scrawny defmethod and instead enumerate every rating that isn’t platinum. But this means you’ve duplicated code again: you need a defmethod for at least :rating/basic and :rating/gold, and they both will have the same body. Further, you need to remember to add more cases if more profit ratings are added in the future. A second possibility is to add an explicit [:rating/platinum :rating/platinum] method, but this also means you’ll need to duplicate the “shimmers” code.

Clojure offers a third possibility: you can explicitly prefer one implementation over another using the prefer-method function. This function takes the multimethod and a pair of dispatch values and instructs the multimethod to prefer the first dispatch value over the second when there’s an ambiguity between the two. Here’s an example:

Using prefer-method you’re able both to avoid duplicate code and to future-proof it against modifications to the rating hierarchy.

You’ve now learned all there is to know about multimethods except for one last rarely used feature, which we’ll examine next.

User-defined hierarchies

All the multimethods we’ve defined and the hierarchies you’ve derived so far have been inspecting and mutating a single, program-wide global hierarchy. In most cases this is fine, but Clojure’s multimethods also allow you to create your own blank hierarchy and use it explicitly instead of using the invisible global hierarchy. Most of the macros and functions we’ve introduced in this chapter also accept an optional hierarchy argument, which you can create with the make-hierarchy function. Here’s a whirlwind tour of its use:

There are a few important differences between this code with an explicit hierarchy and the code you’ve been writing up until now using the global hierarchy. First, you call make-hierarchy to create a new (empty) hierarchy. A hierarchy is really just a map with three familiar-looking keys—it’s not anything special. Second, derive and underive have three-argument forms that accept a hierarchy, but these don’t return nil like their two-argument forms. Instead, they return a new hierarchy map and don’t mutate the existing map. Third, notice that the three-argument form of derive doesn’t require namespaced keywords; because the hierarchy is empty and isolated there isn’t as much concern about type name collisions as there is in the global namespace. Fourth, a multimethod is created to use a custom hierarchy by calling defmulti with the :hierarchy keyword option. You must pass the hierarchy as a var, not a plain map. It would be impossible to change the type hierarchy later if you were to pass a plain (immutable) map. Instead you pass a var containing the hierarchy map, and the multimethod derefs it every time it needs to call isa?. This is demonstrated in the previous code by adding the :d type to the hierarchy after defining the method: note that the change is seen by letter?.

Why would you ever want to create your own hierarchy? There are two primary reasons. The first is hierarchy isolation: if you use an independent hierarchy, you’re never in danger of someone’s code accidentally changing your type relationships while manipulating the global hierarchy. In fact, it’s even possible to make your type hierarchy completely nonextensible simply by making it private to your library and inaccessible to other namespaces (for example, by using ^:private or a closure). This allows other code to add their own methods but not their own types, which may occasionally be desirable. Because hierarchies are isolated, derive’s three-argument form also relaxes the requirement that your types have a namespace, so you can name your types bare keywords like :letter. Note, however, that your own hierarchies are not isolated from the Java type hierarchy! (isa? (make-hierarchy) java.lang.String java.lang.Object) still returns true!

The second reason you might want your own hierarchy is if multiple methods share the same types but dispatch according to different (possibly contradictory) type hierarchies. A classic example is circles and ellipses: an area function may be able to say that a :circle is a kind of :ellipse and use the same formula (2πwh) to calculate the area for both, but a stretch function may need to make the opposite assumption and implement ellipse-stretching as a special case of circle-stretching.^[1] Separate multimethod hierarchies are used very rarely in Clojure, but they’re available if you need them.

¹

The discussion of whether a circle is an ellipse or vice versa is so classic in subtype polymorphism and object-oriented programming that it has its own name: the circle–ellipse problem; see http://en.wikipedia.org/wiki/Circle-ellipse_problem.

4.3. Summary

We began this chapter by defining polymorphism as the ability to use multiple types as though they were the same—to substitute one type for another without changing code. We then distinguished three different kinds of polymorphism: parametric, ad hoc, and subtype. Parametric polymorphism is where the types aren’t mentioned at all; ad hoc is where multiple implementations name types explicitly but provide a parametric interface; subtype is where types are placed in a hierarchy so they can share implementations transparently.

We then introduced multimethods in the context of ad hoc polymorphism and showed how they enable explicit mapping of types to implementations (via a dispatch function and value) but are still extensible with new types from the outside (called open dispatch). We then showed how you could dispatch with multiple different values at the same time (called multiple dispatch).

We then discussed how multimethods have subtype polymorphism features as well because they allow you to build your own type hierarchies with derive that are matched with isa?. You were able to combine subtype polymorphism with multiple dispatch to eliminate duplicated code. But this introduced the possibility of dispatch values with ambiguous method implementations, but you were able to resolve these ambiguities using prefer-method. Finally, you saw that it’s possible for each multimethod to have its own independent type hierarchy.

This chapter covered an interesting feature of Clojure, and using it in the right situation will make your programs richer. The next chapter will focus on another great capability of Clojure: seamless interoperability with Java code.