Polymorphism That Just Works

Code JavaScript much? Have you ever complained about how the arguments object is not a real array? Ditto for NodeLists, right? Isn't it unsettling that if you care about compatibility with older browsers, you can't rely on useful array methods like map, filter, reduce, or even indexOf? Good thing we have underscore and lodash. If you are using a MVC framework that requires you to use their own collection class, it's yet another layer of translation and mental overhead: interacting with a Backbone.Collection or an Ember.Array requires talking to a different API vs a plain vanilla JavaScript array. But, you would think: an array is an array is an array, right? Why is this so hard?

Have you ever designed an object oriented API with crystal clear interfaces for interacting with your objects, only to later find out that someone else has made another library with the same purpose but a slightly different and incompatible API? If one wrote an application using one API and wanted to switch to the other, she would have to rewrite each of the differing integration points - places where her application uses the original API. Where is polymorphism when you need it?

Polymorphism

In the above scenario, if the engineer were to want to make her application more generic and be able to switch between the two "implementations" at a moment's notice, she would design a new API which normalizes the differences between the two APIs, then write wrappers for each of the two originals which adheres to this new API. This is a use of polymorphism. However, the maneuver to get there has some palpable overhead:

  1. The work of implementing the wrappers for each of the original implementations.
  2. The work of switching all of the legacy code which used one or the other of the original APIs to the new "unifying" API.

#1 is tedious but tractable. #2 is more problematic: its difficulty is directly proportional to the amount of legacy code you have. No, actually it's more. If you take the view of all the code there is from a community perspective, there's all the code that's running out there. This maneuver is impossible when you have a large amount of legacy you care about keeping: such is the case with many early mistakes in the design of JavaScript.

Frozen

To avoid the above overhead, what we do is API standardization. When an API becomes widely used, it's probably not ever changing again. That's why it's so important to get them right the first time, and that's why we have technical committees deliberating endlessly about what the best API should be. However,

  1. There's little we can do about historical mistakes that are already there. cougharguments objectcough
  2. Even a group of super smart individuals aren't infallible to making mistakes.

A Different Polymorphism

Which brings us to the point of this post: I will demonstrate an alternate technique for implementing polymorphism - as opposed to interfaces or duck typing. This technique solves some if not all of the above problems. It is currently used in the Haskell, Clojure, and Rust realms. Haskell's answer to polymorphism is type classes. Clojure has a similar concept called protocols. Rust has traits. You are not required to be familiar with Haskell, Clojure, or Rust to understand the rest of this post. Instead of talking in terms of either of those, I will demonstrate a hand-rolled implementation of the concept in JavaScript.

A Protocol

I will use Clojure's terminology: protocols. A protocol is very much like an interface in statically typed languages like Java or C#, but with the difference that the fact that a particular class implements a particular protocol is not tied to the implementation of that class.

Let's see an example. We have a class User (I am using ES6 classes because that's how hip I am).

class User {
  constructor(id, name, dateOfBirth) {
    this.id = id;
    this.name = name;
    this.dateOfBirth = dateOfBirth;
  }
}

I want to able to check two users to see if they are really the same person. In "classical" JS-style polymorphism, I would simply use duck typing, and make a method to implement the comparison.

class User {
  ...
  equals(other) {
    return this.id === other.id;
  }
}
...
> bob.equals(robert)
true

Then, if you create another class - say Vehicle - which also contains the same equals method, you can also use .equals() with Vehicles - that's polymorphism!

With protocols, I would first define a protocol which I will call Equal. If JS had a protocol feature, it might look like:

protocol Equal {
  equals(one, other);
}

Then, I would declare that all instances of User implements the Equal protocol:

User implements Equal {
  equals(one, other) {
    // one is of type User. We also assume that other is of type User
    return one.id === other.id;
  }
}

A bit of technicality: although equals takes two arguments, only the type of the first argument is used for choosing the actual equals implementation. This is how protocols in Clojure works, although Haskell's type class system is more generic and can allow dispatching off of arguments in any position.

Once this is established, you would be able to test equality by using Equal.equals() not only for users but for any class that implements Equal:

> Equal.equals(bob, robert)
true
> Equal.equals(tesla, bimmer)
false

Protomorphism

Of course you realize that the syntax in the above section is completely made up and not runnable. Not to worry, I implemented this as a module: protomorphism. The syntax is not as pretty but it allows you to do the same thing. Instead of

protocol Equal {
  equals(one, other);
}

, you would write

const protocol = require('protomorphism');

const Equal = protocol({
  equals: function(one, other){}
});

, and instead of

User implements Equal {
  equals(one, other) {
    return one.id === other.id;
  }
}

, you would write

Equal.implementation(User, {
  equals: function(one, other) {
    return one.id === other.id;
  }
});

and that's it! The next examples provided will be all runnable via protomorphism.

Example: Sorting

You could define a protocol for types that have a natural order, such as numbers or strings:

const Ordered = protocol({
  // compare should return:
  // 0 if one and other are the same
  // positive number if one comes before other
  // negative number if one comes after other
  compare: function(one, other){};
});

Ordered.implementation(Number, {
  compare: function(one, other) {
    return one - other;
  }
});

Ordered.implementation(String, {
  compare(one, other) {
    if (one === other) {
      return 0;
    } else if (one > other) {
      return 1;
    } else {
      return -1;
    }
  }
});

With these, you can actually define a generic sort method for arrays that will sort either an array of numbers or strings correctly, unlike the native sort():

function sort(arr) {
  return arr.sort(Ordered.compare);
}
...
> sort([12, 3, 24])
[ 3, 12, 24 ]
> sort(['Ileen', 'Ahmad', 'Jason'])
[ 'Ahmad', 'Ileen', 'Jason' ]

You can also use this sort function to sort anything else that implements Ordered, such as poker cards - I'll leave this as an exercise for the reader.

Example: Show

Another useful protocol is a way to return the string representation of an object for printing out while debugging.

protocol Show {
  // show returns a string representing object
  show(object);
}

User implements Show {
  show(user) {
    return `User(${user.id}, ${user.name})`;
  }
}
...
> Show.show(bob)
User(12, "Robert")

Again, we can retroactively have native types like number and string implement this protocol:

Show.implementation(Number, {
  show: function(n) { return String(n) }
});

Show.implementation(String, {
  show: function(s) { return JSON.stringify(s) }
});

And we might write a convinience function for printing out any object like:

function print(object) {
  console.log(Show.show(object));
}
...
> print(bob)
User(12, "Robert")
> print(5)
5
> print("Hello world")
"Hello world"

Example: Array-Like Things

Let's come back to the example of JavaScript's various array-like things. What if we simply created a protocol and allow all of them to speak it? To keep this example simple - the goal is to implement the generic utility functions: map, filter, and reduce, and allow them to be usable for arrays, the arguments object, as well as Backbone collections.

The Challenge

If you would rather try it on your own, please stop reading and go do that before coming back.

The Solution

To solve this problem - at the bare minimun, all you need is a protocol for iterating the collection. So I made:

const Iterable = protocol({
  // return the n-th item in the array
  each: function(arr, fn) {}
});

With this protocol, I can write generic implementations of 'map', 'filter', and 'reduce':

function map(arr, fn) {
  let values = [];
  Iterable.each(arr, function(item) {
    values.push(fn(item));
  });
  return values;
}

function reduce(arr, fn, initValue) {
  let value = initValue;
  Iterable.each(arr, function(item) {
    value = fn(value, item);
  });
  return value;
}

function filter(arr, fn) {
  let values = [];
  Iterable.each(arr, function(item) {
    if (fn(item)) {
      values.push(item);
    } 
  });
  return values;
}

The next step is to just make arrays, the arguments object, and Backbone collections implement the Iterator protocol. Since the arguments object's type is plain Object, I am having to tie the implement to the top-level Object type.

function _each(arr, fn) {
  for (let i = 0; i < arr.length; i++) {
    fn(arr[i]);
  }
}

Iterable.implementation(Array, {
  each: _each
});

// for the arguments object
Iterable.implementation(Object, {
  each: _each
});

Iterable.implementation(Backbone.Collection, {
  each: function(coll, fn) {
    coll.each(fn);
  }
});

That's it! Now we have map, filter, and reduce for each of these types.

> map([1, 2, 3], function(n) { return n * 2 })
[ 2, 4, 6 ]

> function fun() {
  return filter(arguments, function(n) { return n % 2 === 0 });
}
> fun(1, 2, 3, 4)
[ 2, 4 ]

> let coll = new Backbone.Collection()
> coll.add({number: 1});
> coll.add({number: 2});
> coll.add({number: 3});
> coll.add({number: 4});
> reduce(coll, function(sum, m) { return sum + m.get('number') }, 0)
10

That's awesome! But! There's actually a problem with this scheme: the result of map and filter always return an instance of array, regardless of what the original type of the array-like object was. I allowed this in order to keep this code example short. How would you go about making the map and filter methods return the same type as the original? This would be a interesting challenge for you - the reader.

What Makes Something Something?

Having gone through the exercises of using protocols as a means of implementing polymorphism, the question I need to address is: how is it better than what we had? Is it better at all? But first, we need to take a detour.

Various analogies have been used to explain object oriented programming. In particular, the concept of using inheritence to describe the "is-a" relationship - e.g. a cat is-an animal - has been ingrained in us. Should we model objects in our problem domains using an ontology - the same way that botanists classify plants? The problem is that ontology is simplistic and rigid. A cat is an animal, but a cat can also be a pet, and it can also be a playmate, and to a kitten, a cat is mother. Inheritence comes up short in modeling these scenarios.

The way that humans actually learn an "is-a" relationship is quite different, and is based on examples. To teach our children what a chair is, we give them examples of chairs. First, we show them a wooden stool, and they conclude: a chair is something that has four wooden legs. Then we show them a stainless steel stool, they'll update their definition to: something that has four legs. Then we show them a table with four legs, and they update their definition to: something with four legs and is for sitting. Then, we show them the exercise ball which you sit on for work. With enough examples, they ultimately come to the most generic definition of a chair.

What makes something something is not always based on their origin, but more often based on their characteristics and their roles, and these depend on the definition of a the word. "is-a" is definition-based. With this formulation, even a cat can be a friend.

There are times when you don't realize that something is something until you see it in a different light.

Beauty Or Old Lady

You may not have known the exercise ball was a chair, until you meet someone who uses it religiously as their office chair. In mathematics, if you can prove that a new problem is equivalent to an old problem by mapping each element of the new problem to each element of the old problem and seeing that all the properties of the old problem also hold in the new problem. Once you do that, any solution to the old problem can also be readily applied to the new problem. Such is the case for the traveling salesman problem and the hamiltonian cycle problem.

How Is This Different?

Now, let's come back and consider how protocols is different from classical polymorphism. Mainly, there are two key differences:

  1. The ability to retroactively make a class implement a protocol after that class has already been defined.
  2. Implementing a protocol does not modify the definition of the class itself.

The first is actually doable in JavaScript today: you can certainly modify the prototype object of any "class" in JavaScript. We've all - at one time or another - added extra convinience methods to Array.prototype, Object.prototype, Function.prototype, and more. Only, this is now considered bad practice, because we've been burned before. When the API of an object is modified, we run the risk breaking code which depend on the original API. This is why the second difference is important: implementing a protocol does not in anyway change the behavior of the class itself. This guaranteed isolation is what allows protocols to scale, and opens up the possibilities for reusing existing algorithms in new problem domains.

Summary

I have demonstrated an alternative way to formulate polymorphism than the traditional OO approach - interfaces and duck typing - which relies purely on the shape of objects. This approach is being used in several modern programming languages including Haskell, Clojure and Rust. It can be used in JavaScript to solve some of the thorny issues we have with the language today - I make implemented a proof of concept module protomorphism. Whether this will become the standard going forward is yet to be seen, but if nothing else, I hope that this article provides food for thought.

blog comments powered by Disqus