Program like Proteus — a beginner’s guide to polymorphism in JavaScript

Polymorphism — the ability to write a single function that handles many data-types — is a fundamental form of abstraction. Indeed, abstraction and polymorphism, considered abstractly, describe exactly the same thing. And since it is obvious that there are many kinds abstraction, it will be no surprise that there are many kinds of polymorphism. In this post we will describe those kinds, and devote some thought to the forms of polymorphism that we can implement in JavaScript, with a focus on how and why we might wish to import the Clojurian concept of protocols.

If you enjoy this post, please do clap 👏 , share, and follow 🐦 … It is truly appreciated!

The expression problem

The so-called “expression problem” is a useful starting point for considering the advantages of different forms of polymorphism, since it exposes the limitations of the polymorphism peculiar to Java, which is often conflated with polymorphism in general. In an OOP context, “polymorphism” almost always means just one thing: the overriding of inherited methods to facilitate calling the same method on different objects (so, for example, the chapter on OOP in Eloquent JavaScript). The overriding methods will have different implementation details, but a consistent purpose, providing a single interface for manipulating different data types.

What is the “expression problem”? Unfortunately, the forms of data that an application will consume, and the operations it will need to perform on that data, are not likely to remain constant throughout its lifetime. So imagine we are suddenly presented with a new datatype, perhaps from an external library. How do we make it consumable by the interfaces that we constructed to handle data with a different structure? Either:

• Go back and change our interfaces so they support the new datatype, which violates the O in SOLID (open for extension, closed for modification).
• Wrap the new datatype inside an adapter object, which results in code proliferation.
• Directly add or override the methods required by our interfaces on the new datatype (monkey-patching), which is risky.

Clojurians are especially fond of this problem since (as they declare) it has finally been solved in Clojure, which provides a different kind of polymorphism through multimethods and protocols. Protocols allow us to specify certain functions as an interface, implement these functions differently for different data types, having them dispatch on the type of the first argument, and extend them to new datatypes, all without any risk of namespace collision. They permit this because, unlike in the classical object-oriented model, the functions that implement protocols are not stored on the datatypes, but on a namespace which may be reserved just for them (examples to follow). In The Joy of Clojure, Fergus and Hauser paradoxically describe polymorphism as one of the “powerful aspects of OOP” which has been “improved” by Clojure (not an OOP language!).

While the expression problem is helpful in provoking us to think about alternative forms of polymorphism, its treatment is too often overdetermined by the comparison with Java. In JavaScript, the more common and ready to hand solutions are the first or the third in the bullet points above: we change our interfaces, or we use monkey-patching. These solutions are not as bad as they are made out to be, and they are also forms of polymorphism. Moreover, the basic idea behind protocols can be implemented in any dynamically typed languaged. While we may not be able to take advantage of the JVM’s ability to accelerate type-conditional dispatch, we are primarily interested in increasing the maintainability and flexibility of our code. It’s time, then, for a broader look at polymorphism, but first we need a clearer understanding of what polymorphism is.

Polymorphism is not ‘an aspect of OOP’!

So what is polymorphism really?

(Diagram after Cardelli and Wegner (1985), with embellishments).

First, polymorphism is either ad hoc or universal. Ad hoc polymorphism is when a function call results in a dispatch to one of one or more type-specific (monomorphic) functions, depending on the argument type. Either the argument is coerced to a single type, so only one implementation is necessary, or the function is overloaded with different implementations for each type. Static (early/compile-time) binding of the function call to the function body is possible because the set of possible types and implementations is predefined and finite. Subtype polymorphism is the polymorphism particular to OOP: a method of class A can be called with an infinite number of types, namely, any class which inherits from class A. The call will then get dynamically bound to the implementation on the particular subtype. The definition of polymorphism given by Fergus and Hauser encompasses both overloading and subtype polymorphism, but leaves out others.

Parametric polymorphism is the meaning more familiar in functional programming circles, and describes a function which can be called with an infinite number of types unrelated by inheritance. It relies on a single functional form being the same for multiple types: the function performs the same operation whatever type is passed. A simple example is the identity function. The form is always the same, irrespective of type. This requirement contrasts with the ability of ad hoc polymorphic functions to dispatch to qualitatively different implementations. While it first might seem strange that a function capable of handling an infinity of types can be statically compiled, it makes sense if we think of types simply as sets of values. So the type Int is already an infinite set, namely, the infinity of integers. The type forall a (a type to be provided to a parametrically polymorphic function, where a is the type variable) is just another type, defining the set of all values included by Int, Bool, String, etc.

We should not confuse parametric polymorphism in general with the specific property called relational parametricity, which is a restrictive formalisation of what it means for a function to have a single ‘form’ invariant with respect to its type parameters. To put it simply, a function has relational parametricity if it does not need to inspect its input types to perform an operation. Think of a function length, which takes a list containing any type(s). If it can iterate over the list, it never needs to inspect the types inside the list to determine the length. A function that inspects its type parameters and makes a decision on them cannot be relationally parametric, but may still be presented at the language level as parametrically polymorphic. For example, imagine we decided that the length of lists containing a certain type should always be 0, or we wished to have non-deterministic handling of errors.

Finally, the rank of a polymorphic function refers its ability to instantiate its type parameters with types that are themselves polymorphic. If the function is rank-n, it can accept arbitrarily higher order polymorphic types. A rank-1 polymorphic function accepts only monomorphic types as parameters.

These distinctions are to some extent heuristic. Subtype polymorphism, for example, has been interpreted as a specific kind of parametric polymorphism (in which the set of types is “bounded” by a property defining a family) as well as a kind of coercion (from supertype to subtype). See the dotted lines in the diagram. One form of polymorphism can be implemented in the guise of another. Templates in C++ allow functions to be defined that accept an infinity of types, giving the effect of parametric polymorphism, but to achieve this the compiler in fact creates separate functions for each type ad hoc. Conversely, ad hoc polymorphism with type classes in Haskell is implemented by the compiler using parametric polymorphism. It will be no surprise that the ad hoc polymorphism achieved by Clojurian protocols is implemented in Java using subtype polymorphism. In JavaScript everything is blurred (and different things can go on under the hood), but by the same token we can easily create interfaces that mimic any of these forms of polymorphism. To the extent that the distinctions are anyway heuristic, maybe we should not say “mimic”, but “implement”!

Polymorphism in JavaScript

Let’s look at an extract of the equality function from the Ramda library.

switch (type(a)) {
    case 'Arguments':
    case 'Array':
    case 'Object':
      if (typeof a.constructor === 'function' &&
          _functionName(a.constructor) === 'Promise') {
        return a === b;
      }
      break;
    case 'Boolean':
    case 'Number':
    case 'String':
      if (!(typeof a === typeof b && identical(a.valueOf(), b.valueOf()))) {
        return false;
      }
      break;
    case 'Date':
      if (!identical(a.valueOf(), b.valueOf())) {
        return false;
      }
      break;
    case 'Error':
      return a.name === b.name && a.message === b.message;
    case 'RegExp':
      if (!(a.source === b.source &&
            a.global === b.global &&
            a.ignoreCase === b.ignoreCase &&
            a.multiline === b.multiline &&
            a.sticky === b.sticky &&
            a.unicode === b.unicode)) {
        return false;
      }
      break;
	 // it goes on!

This is a common form of polymorphism in JavaScript. Unlike in statically typed languages, nothing intervenes at the level of function definition to prevent us writing one function that handles several types in several ways. Every value is effectively already ‘boxed’ by a monomorphic reference type (‘everything is an object’) so that every function is parametrically polymorphic over what the boxes contain. The difference between parametric polymorphism here and in a language like Haskell is the severing of the link between parametric polymorphism and relational parametricity.

There is active debate in the Ramda community about whether and how to extend support to datatypes from Highland, Flyd, Immutable and other libraries (see here, here and various related PRs). One proposed approach is to continue to build up the function body to support as many types as possible. If we need to add new behaviour for types we already know about, we simply inspect the type and add another case within the function body. All remaining types are handled by dispatching to the generic method if it is present. Hence we find, for example:

if (typeof a.equals === 'function' || typeof b.equals === 'function') {
    return typeof a.equals === 'function' && a.equals(b) &&
           typeof b.equals === 'function' && b.equals(a);
  }

An alternative approach is to introduce a stricter form of type checking. So instead of checking for a generic equals method, which may support a wide range of data types with unpredictable results, Ramda would demand a specific equals function, flagged in some way as type-specific, and deliberately exclude other non-native types. This code was recently added to the equals function:

if (typeof a['fantasy-land/equals'] === 'function' || typeof b['fantasy-land/equals'] === 'function') {
    return typeof a['fantasy-land/equals'] === 'function' && a['fantasy-land/equals'](b) &&
           typeof b['fantasy-land/equals'] === 'function' && b['fantasy-land/equals'](a);
  }

This approach is not practically incompatible with adding switch statements to identify different types, but the philosophy behind it is different. The responsibility for ensuring compatibility is shifted from the interface provider to the data provider (and so to the monkey-patcher).

These approaches seem to promote, respectively, the modification of the existing interface and monkey patching, safely enabled by the addition of the specific type namespace (in this case, “fantasy-land”). The first approach makes the library more versatile; the second makes it more predictable. The first extends horizontally the range of basic functionality; the second extends vertically the potential for achieving new functionality by composition. The first reduces error by reducing the need for additional code; the second reduces error by clarifying the contract.

Who cares about the expression problem in this debate? No one really believes that either the datatypes to be consumed or Ramda’s interface should be ‘closed for modification’. The question is not about the best way to make a new datatype consumable by pre-existing interfaces, but rather whether we have designed, or should, or can, design those interfaces for specific datatypes in the first place. One way to think of a dynamically typed language is that it is a language which gives us the freedom to construct the type system most appropriate for a particular situation. In particular, we must choose whether to develop a strongly typed interface or a weakly typed interface. These terms are not out of place. Although ‘types’ in JavaScript are merely objects that conform to different specifications (‘duck types’), do not be deceived: ducks can be examined with infinitely varying degrees of rigour.

Protocols

There is another way in which we could make our equals function polymorphic: use protocols. First we define a protocol. That is, we declare all the functions of which objects passed to Ramda will be capable. In Clojure, the protocol would be stored on the current namespace; in JavaScript, we must assign it to a variable.

const Ramda = new Protocol('equals', 'map', 'add', /* and the rest! */)

Next, we set about implementing the protocol for different data types. We are free to leave functions undefined where they do not make sense:

Ramda.extendTo(String, {
  equals: (a, b) => a === b,
  map: (a, f) => a.split('').map(f),
  add: (a, b) => a + b
})

Ramda.extendTo(Date, {
  equals: (a, b) => identical(a.valueOf(), b.valueOf()),
  add: (a, b) => new Date(Number(a) + Number(b))
  // map not implemented
})

We can then use the protocol like this:

Ramda.equals('hello', 'world') // false
Ramda.equals(new Date(1), new Date(1)) // true

Ramda functions can now be extended to any data type without the need to modify any baroque switch statements. In addition, since implementations are passed as objects, when different data types require similar implementations, we can nicely de-duplicate our code by extracting implementations into variables and merging or plucking them as required (in general, JavaScript favours composition over inheritance). Note that in reality we would probably have several protocols defined, grouping functions in a sensible manner. An object would be able to extend more than one protocol if necessary. More than likely (since this is Ramda), these groups would correspond to algebraic types: Functor, Semigroup, etc.

A simplistic implementation of the aforegoing might run as follows:

class Protocol {
  // accept a list of method-names
  constructor(...methods) {
    this.implementations = {};
    // and create a method for each
    methods.forEach(method => {
      // that will dispatch to an implementation stored on the type of the first argument
      this[method] = (type, ...args) => {
        // with the convention that an object's type is given by its constructor
        return this.implementations[type.constructor][method](type, ...args);
      } 
    });
  }
  // register implementations for a type
  extendTo(typeConstructor, implementation) {
    const typed = this.implementations[typeConstructor] = {};
    Object.keys(implementation)
      .forEach(method => {
        typed[method] = implementation[method];
      });
  }
}

Various refinements of this basic implementation would be possible. We should certainly add error handling. We could allow our protocol specification to flag which argument(s) we want to dispatch on. We could add more rigorous type-checking if we wish to restrict what types can be passed to the protocol. We could provision extension to null or undefined (greatly simplifying null checking). We could set up the dispatching function to accept a custom type-checking function a la Clojure's multi-methods. That might make the system slower and clunkier to use, but would address a major problem with this basic implementation, which is that the constructor property is a rather coarse indicator of an object's type (and liable to be altered by minification). If we had all of these features, we would end up with something similar to the concept of an environment in the strongly typed functional libraries Sanctuary and Bilby. But the attraction of protocols is partly that we do not need to take the typing this far. We do examine some metadata (the constructor, in this case, but it could be something else) that is distinct from the functionality that we actually care about (the method), so we sit somewhere between strict typing and blindly dispatching to an equals method.

Dictionary passing

The discussion in the Haskell community about the usefulness of type classes (essentially, statically typed protocols that also act as constraints) is interesting to consider when thinking about protocols in JavaScript, especially as Elm seems to have bought into the idea that type classes are unnecessary. The argument is that instead of registering implementations to a protocol and accessing them through that, one should keep them at hand and pass them manually to the functions that require them every time (so-called “dictionary-passing style”):

const implementations = {
  string: {
  	equals: (a, b) => identical(a.valueOf(), b.valueOf()),
  	add: (a, b) => new Date(Number(a) + Number(b))
  },
  date: { /* etc. */ }
};

const equals = (impl, a, b) => impl.equals(a, b);

equals(implementations.string, 'hello', 'world')

The simplicity of this approach has much to recommend it. In terms of the rigidity of the type system it demands, it sits somewhere between blind dispatching and protocols. We are still able to write a complete specification for how a type should behave without a jungle of cases. But we are now able to specify two different sets of behaviour for the same type while reusing the same equals function (just pass in a different dictionary). Since we are aware of what we are passing into the function, we are at less risk of encountering unpredictable behaviour if, for example, we forget exactly how a function is defined for a particular type. But by the same token we have more things to keep track of: we cannot simply use the interface without caring about what type we pass in. These are perhaps always the pros and cons of unwrapping abstractions.

Appendix: benchmarking switch vs. protocols

In order to gain a rough impression of the performance implications of using protocols, I implemented an alternative equals function in Ramda (equals2) and ran it against the existing function with benchmark.js (code here):

> ramda@0.23.0 bench /Users/sg/protocols/ramda
> scripts/benchRunner "equals" "equals2"
┌────────────────────────┬────────────────────────┬────────────────────────┐
│ ramda (switch) equals  │ Hertz                  │ Margin of Error        │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (int, int)     │ 464,292                │ 0.99%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (int, int)       │ 11,147,227             │ 0.82%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (Date, Date)   │ 593,867                │ 0.98%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (Date, Date)     │ 88,141                 │ 0.97%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (Error, Error) │ 558,842                │ 0.89%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (Error, Error)   │ 575,533                │ 0.98%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (RegExp, RegE… │ 535,599                │ 1.00%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (RegExp, RegExp) │ 84,428                 │ 0.91%                  │
└────────────────────────┴────────────────────────┴────────────────────────┘
┌────────────────────────┬────────────────────────┬────────────────────────┐
│ protocol equals        │ Hertz                  │ Margin of Error        │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (int, int)     │ 220,384                │ 0.92%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (int, int)       │ 10,623,065             │ 0.91%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (Date, Date)   │ 250,979                │ 0.95%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (Date, Date)     │ 66,945                 │ 1.01%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (Error, Error) │ 252,426                │ 1.08%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (Error, Error)   │ 68,635                 │ 0.97%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ unequal (RegExp, RegE… │ 233,653                │ 0.96%                  │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (RegExp, RegExp) │ 65,226                 │ 0.93%                  │
└────────────────────────┴────────────────────────┴────────────────────────┘

The implementation with switch appears to be around twice as fast. Of course, these results are difficult to trust. The equal (Error, Error) result in particular appears anomalous. When testing just this case the result was:

> ramda@0.23.0 bench /Users/sg/protocols/ramda
> scripts/benchRunner "equals2"

┌────────────────────────┬────────────────────────┬────────────────────────┐
│ protocol equals        │ Hertz                  │ Margin of Error        │
├────────────────────────┼────────────────────────┼────────────────────────┤
│ equal (Error, Error)   │ 220,541                │ 1.07%                  │
└────────────────────────┴────────────────────────┴────────────────────────┘

Further reading

The starting point for acquiring a more in depth understanding of polymorphism is On Understanding Types, Data Abstraction, and Polymorphism by Luca Cardelli and Peter Wegner, which can be supplemented by On Understanding Data Abstraction, Revisited by William Cook.

For more on the tricky concept of relational parametricity, see Theorems For Free! by Philip Wadler. This highly technical article is helpfully elucidated by Bartosz Milewski in Parametricity: Money for Nothing and Theorems for Free.

Type classes are usefully presented against the broader background of polymorphism in How to make ad hoc polymorphism less ad hoc by Philip Wadler and Stephen Blott.

Proteus by Andrea Alciato, Livre d’Emblemes 1542

Written by Sam Galson — Software engineer at YLD.

Interested in JavaScript? Read more about it here:

React is just JavaScript

Rolling your own Redux with React Hooks and Context