Implementing CLOS-Style Multimethods In JavaScript For A Simple Asset Pipeline And A Text Adventure Game

June 26, 2015Dan Yoder and Giles Bowkett

Update: We’ve streamlined our multimethods implementation.

Multimethods are a powerful form of dynamic dispatch that trace back to Lisp in the mid-1980s.And possibly farther. There’s a Usenet reference to a language called EC1 that may have had a similar construct as early as 1971. Multimethods offer a powerful, flexible, and functional programming-friendly alternative to conventional OOP. Even better, the power of multimethods has recently become available to JavaScript (or any language that can be translated into JavaScript, like CoffeeScript or ClojureScript).

Multimethods might seem obscure, but they’re a useful paradigm. We’ll illustrate with an asset pipeline and a text adventure game.

We’ll start with a classic example from OOP, in CoffeeScript.

OOP’s Dynamic Dispatch

Say you’re writing a program about animals moving around. You might write a move() function. And you might define an Animal class, with a Fish subclass, and change that move() function into a method:

fish.move()

fish might get its move method from a Fish class, which in turn overrides the move implementation from its Animal superclass, because moving across the land is different from moving through the water.

You may recognize this as a pretty standard feature in object-oriented programming languages. But JavaScript isn’t really object-oriented, or at least, not in the classical way. All it really does is use objects to locate functions. So what really happens is that it’s going to need to know whether move means Animal.move or Fish.move. So V8Presuming that you use Node or Chrome to run your JavaScript. turns fish.move into a function that does a lookup to find out which move function is really being called.

We could write that lookup function ourselves instead of having V8 generate it. We could define fish.move like this:

fish.move = lookup("move")

where lookup returns a move function appropriate for moving through water. And in fact this is pretty much what JavaScript does, under the hood. But it only does this for methods, not ordinary functions.

How JavaScript Maps Methods To Functions

Any time you call this:

fish.move()

JavaScript sees it more like this:

lookup(Fish, "move")

Or this:

lookup(Animal, "move")

(Along with some special, context-managing mojo.)

In other words, JavaScript adds invisible type-checking to your function calls. Only for the first argument and only if you call the function as a method, but it’s still there. It’s just hidden in plan sight. And JavaScript uses that implicit first argument to identify which function you want.

Using Multimethods Instead Of OOP

JavaScript does this because it doesn’t really have methods at all. Any JavaScript method is really just a function, but the compiler or the interpreter knows how to track down which function you mean whenever you ask it to give you a method. But since it’s really all functions, and JavaScript gives us first-class functions, we can write our own function to do the lookup. Here’s how it might work:

# define move to be a lookup function
move = MethodLookupTable.create

# add entries to our lookup table
MethodLookupTable.define move, Fish, (fish) -> # ...
MethodLookupTable.define move, Animal, (animal) -> # ...

When we call move, the exact function that will get called depends on the type of animal we’re passing in. Just as it would if we had defined move on objects and called it as a method. Because that’s what a method invocation actually looks like, under the hood.

Of course, this is a lot of trouble to do something manually which JavaScript already does under the hood. But now we can ask ourselves another question: why limit our dispatching to just the first argument?

For method definitions on objects, it’s easy to understand. The implicit first argument is the only one that’s typed. So that’s the only information V8 has to generate the lookup function. Another reason is that, at least in JavaScript, the lookup depends on inheritance.Or, more accurately, on the prototype chain. The lookup table runs on that first argument.

But we don’t have to do it that way. We can store the lookup table with the function! That frees us up to do lookups on more than just the first argument. In fact, we can do lookups based on anything we want.

Here’s an (extremely inefficient) implementation of the Fibonacci sequence, with the first two values “hard-coded” using multimethods that allow for overloading by value as well as type. This works just like the previous example, but we’ve changed MethodLookupTable to Method for simplicity, and added a docstring.

fib = Method.create "Fibonacci sequence"

# Hard-code the first two elements of the sequence
Method.define fib, 1, 1
Method.define fib, 2, 1

# And then the general case
Method.define fib, Number, (n) -> (fib n - 1) + (fib n - 2)

# Test it out
assert (fib 5) == 5

This is pretty powerful stuff. In fact, it’s pretty much how Haskell functions work. But we said this technique could be very pragmatic and useful, so we won’t stress the Haskell angle.

Instead, consider an asset pipeline for a Web server. When we get an HTTP request for an asset, say, a Web page, we know the path and we know the format the client is requesting (ex: text/html).

A typical solution: do a lookup on the path to get an asset object. We want to render the object, but we don’t know whether the given asset can be rendered into that format. We could write some conditional logic to check the supported formats for the asset.

if format in asset.formats
  asset.render format

Or we could define format-specific render methods.

if asset["render#{format}"]?
  asset["render#{format}"]()

This is how a lot of existing asset pipelines work. But with our new lookup that dispatches on all the arguments, we can just write method definitions for the supported combinations.

render = Method.create "Render an asset in a given format"

# define a default that simply throws an unsupported format exception
Method.define render, Asset, String, (asset, format ) ->
  throw new Error "Unsupported format #{format} for #{asset.constructor}"

# define valid combinations
Method.define render, StylusAsset, "css", -> # ... render stylus to css
Method.define render, JadeAsset, "html", -> # ...
Method.define render, CoffeeScriptAsset, "javascript", -> # ...

And here we have multimethods in action.

Now that we have a practical understanding of multimethods, let’s define them.

A method is a dispatch function that delegates to a second function based on the type of its (implicit) first argument. A multimethod is a dispatch function that delegates based on the values of all of its arguments.

JavaScript is a primarily functional language, with entirely optional support for the object-oriented paradigm — less because that paradigm is awesome, and more because it’s just very well-known. Dynamic dispatch is one of the nice advantages of object-oriented programming. But OOP might be overrated, and multimethods give you dynamic dispatch without tying you into every other idea of OOP. So you get a nice blend of power and flexibility.

CLOS And ClojureScript Implementations

Multimethods have a long and rich history, possibly going as far back as 1971. In 1988, when the Common Lisp Object System was introduced, it contained a variation on multimethods, called generic functions. Our render example would look like this in CLOS:

(defgeneric render (asset format)
  :documentation "Render an asset in a given format")

(defmethod render ((asset stylus-asset) (eql "css"))
  ; render stylus to CSS
)

(defmethod render ((asset jade-asset) (eql "html"))
  ; ...
)

(defmethod render ((asset coffeescript-asset) (eql "javascript"))
 ; ...
)

The spirit of CLOS has been tranmuted into the browser via ClojureScript, which also implements multimethods. Here’s how render might look in ClojureScript.

(defmulti render (fn [asset format] [(type asset) format]))

(defmethod render [stylus-asset :css] [asset format]
  ; render stylus to CSS
)

(defmethod render [jade-asset :html] [asset format]
  ; ...
)

(defmethod render [coffeescript-asset :javascript] [asset format]
  ; ...
)

The big difference with ClojureScript is that we have to provide the dispatch function when we define the multimethod. This is potentially faster and more flexible than a one-size fits all dispatch function. On the other hand, it’s a little bit tedious to have to think about the dispatch function every time you want to use multimethods. For example, suppose we want to specialize render for a singleton asset. We’d need to change the dispatch function first and possibly even the method signatures themselves to do that.

Fairmont’s Multimethods

Of course, we wouldn’t have bothered with all this if we didn’t actually have a working implementation for you.Inspired somewhat by Kris Jordan’s 2011 Clojure-inspired implementation and corresponding blog post, although our version is closer to the CLOS implementation. In fact, we just dropped multimethods into Fairmont, our CoffeeScript utility library. You can npm install fairmont and start using them.

Here’s how our multimethods work. We iterate through all the available method definitions and find the best match by checking each argument against the definition.

We score each match based on a set of precedence rules, from highest to lowest:

All the arguments must match, otherwise the score is zero. If no match is found, the default method will be selected. (Unless redefined, default will simply throw a TypeError.)

The method definition can either be a value or a function. If it’s a function, the function is run using the given arguments. Otherwise, the value is returned directly. (For definitions where the value is itself a function, you must wrap the function inside another function.)

As a nod to Clojure, you can provide a map function, which will transform the arguments for matching purposes, and which provides a flexibility similar to the ClojureScript implementation’s.

Adventures in Multimethods

To understand how you can use Fairmont multimethods in CoffeeScript or JavaScript, let’s consider a whimsical example: the game Adventure. Back when dinosaurs roamed the planet, a programmer named Scott Adams adapted a game called Adventure for the TRS-80. Adventure spawned an entire genre of games — which still persists today with odd little indie games like Varicella and Lost Pig, And Place Under Ground — and is also credited with being a pioneering work of interactive fiction. The basic idea is simple. You give commands to the game, like go north or take treasure. These commands change the state of the world the character lives in, by changing locations or adding possessions and so on.

Let’s start with a simple REPL for interacting with the game. We’ll use Node’s readline API to do the read and loop parts.

readline = require "readline"

cli = readline.createInterface process.stdin, process.stdout

cli.setPrompt "What do you want to do? > "

cli.on "line", (input) ->
  evaluate input
  cli.prompt()

We also need evaluate and print, which will tokenize the input and pass it to a command processor, and then print whatever is returned.

{to_lower, w} = require "fairmont"

evaluate = (string) ->
  print (command (w to_lower string)..., state)

print = (x) -> console.log x

With that out of the way, we can get to the fun stuff. Let’s start with defining command as a multimethod.

{Method} = require "fairmont"
command = Method.create (operator, operands..., state) ->
  [ operator, operands, state ]

Method.define command, String, Array, Object, ->
  say "I'm sorry. I don't know how to do that."

Our command multimethod has a map function, which groups the command operands into an array for matching purposes. We also define a default method for when we can’t find a matching command. This relies on the precedence rules we described above. Value-matches have a higher precedence than type matches, so what we’re doing here is defining a lowest-precedence rule as a fallback in case we don’t have any other matches.

From there, we can define the actual commands, using string values, which will have a higher precedence. Let’s start with a very basic command: describe.

Method.define command, "describe", Array, Object, (operator, state) ->
  describe state.location

In this case, describe has no operands. However, the operands array in our map function will just be empty—it will still match the Array type specifier. Within the function, we simply call the describe function, with the location indicated by state.location.

Let’s implement describe next.

describe = Method.create()

Method.define describe, "castle hall", ->
  "You are in a great hall within the castle.
  There is a staircase in front of you.
  There are torches mounted on the walls."

We’ve added an initial location, the castle hall, along with a description. This function just returns the description of the castle hall as a string. Our REPL will print this string out when our command is executed.

Let’s start with that. We need only fire up the REPL to have our first iteration up and running. Let’s set the initial state, describe it, and go.

state =
  location: "castle hall"
  inventory: []

evaluate "describe"
cli.prompt()

Let’s try running our initial version of Adventure.

$ coffee --nodejs --harmony src/version-1.coffee
You are in a great hall within the castle. There is a staircase in front of you. There are torches mounted on the walls.
What do you want to do? > describe
You are in a great hall within the castle. There is a staircase in front of you. There are torches mounted on the walls.
What do you want to do? > take torch
I'm sorry. I don't know how to do that.
What do you want to do? > _

This isn’t much of an adventure so far, since all we can do is keep describing the same place. Let’s make it possible to move around.

Method.define describe, "castle mezzanine", ->
  if "torch" in state.inventory
    "You are on a broad mezzanine within the castle.
    There are long halls to your right and left.
    The stairway is behind you.
    There is a suit of armor on display."
  else
    "It is too dark to see except for
    the stairway behind you."

Method.define command, "go", Array, Object, (operator, direction, state) ->
  go direction, state.location

go = Method.create()

Method.define go, String, String, (direction, place) ->
  "I'm sorry but you can't go that way."

Method.define go, "forward", "castle hall", ->
  describe (state.location = "castle mezzanine")

Method.define go, "back", "castle mezzanine", ->
  describe (state.location = "castle hall")

We’ve defined a new location—the castle mezzanine—which requires that you have a torch to really see anything. (Remember, there are torches mounted on the walls in the castle hall.) We’ve added a new command, go, along with a fallback for when you try to go somewhere you can’t. Finally, we add the ability to go back and forth between the hall and the mezzanine.

Let’s try playing again.

$ coffee --nodejs --harmony src/version-2.coffee
You are in a great hall within the castle. There is a staircase in front of you. There are torches mounted on the walls.
What do you want to do? > go forward
It is too dark to see except for the stairway behind you.
What do you want to do? > go back
You are in a great hall within the castle. There is a staircase in front of you. There are torches mounted on the walls.
What do you want to do? > take torch
I'm sorry. I don't know how to do that.
What do you want to do? > _

We’re stuck again. We can move around, but we can’t see anything without the torch. We need a way to bring the torch with us.

Method.define command, "take", Array, Object, (operator, object, state) ->
  take object, state.location

take = Method.create()

Method.define take String, String, ->
  "I'm sorry, but you can't take that."

Method.define take, "torch", "castle hall", ->
  if !("torch" in state.inventory)
    state.inventory.push "torch"
    "You have taken one of the torches."
  else
    "You already have a torch."

By now, the pattern should be familiar. We define a new command, which delegates to another multimethod, take. We define a fallback in case you try to take something that isn’t there. And then we make it possible to take a torch from the mezzanine, provided you don’t already have one.

Let’s try this again, this time grabbing the torch along the way.

$ coffee --nodejs --harmony src/version-3.coffee
You are in a great hall within the castle. There is a staircase in front of you. There are torches mounted on the walls.
What do you want to do? > take torch
You have taken one of the torches.
What do you want to do? > go forward
You are on a broad mezzanine within the castle. There are long halls to your right and left. The stairway is behind you. There is a suit of armor on display.
What do you want to do? > go left
I'm sorry but you can't go that way.
What do you want to do? > _

We’ll leave the rest of the game to you. But hopefully, it’s easy to see how multimethods help here. We can simply keep adding to what we already have. At no point did we have to go back and add to a class definition, a switch statement, or anything else. We just keep adding method definitions. This is an indicator of good design: adding things doesn’t break any existing code.

Multimethods Are Functional

We’ve talked a lot about how we can dispatch based on both values and types, and even predicate functions. We can also do so on any argument we’re passed, not just the first one. But we haven’t discussed the major benefits of doing this: we’re now dealing with ordinary functions instead of methods. This means we can use a functional style of programming. We can compose or curry or combine multimethods with any other functions.

We could do this with ordinary methods too, by calling bind or otherwise wrapping them. But we’d be effectively retrofitting one paradigm to fit into another. With multimethods, we’re just extending the functional paradigm to support dynamic dispatch.

Put another way, multimethods are a natural way to introduce types in a functional way, to a language without typed functions. Going back to our render example, we can use render with Fairmont’s other methods that are designed to support a functional style of programming. Let’s suppose we want to render an entire collection of assets. We can just write:

each render, assets

just like we would with any other function. Only this will do something slightly different for each asset because render is a multimethod.

Summary

Multimethods are a powerful form of dynamic dispatch, arguably more powerful even than method dispatch in object-oriented programming. Using multimethods, we can code in an additive manner, dispatch off values and predicates as well as types, and leverage the power of functional programming. And now their long and storied history includes JavaScript environments, via libraries like Fairmont and languages like ClojureScript.

Have fun!