OO and pattern-matching


The analogies here are not perfect, partially because I'm glossing over details and using the verb "to be" for various purposes, but mostly because they are statements about mathematical ideals rather than programming language implementations.

Classes are a specific way, the object-oriented way, of describing types. The "is" here is one way: classes are types, but types need not be classes (consider algebraic datatypes). A type is the set of objects of that type. A set may be treated as a predicate for membership in that set. Predicates are patterns; specifically, a pattern is a predicate that also destructures the object it is called on. But the identity function is also a valid destructuring, so an arbitrary predicate can be translated into a pattern.

The "patterns" I am specifically talking of here are those found in functional languages like Haskell for argument matching or "case" statements, although other patterns like regexps also make sense (which means, working backward, that regexps are types! Strange but, in a sense, true). Given that classes are sets, it's easy to see that subclasses are subsets. All instances of a subclass are instances of the superclass; all elements of the subset are elements of the superset. And since the predicate corresponding to a set is the membership predicate, the subset predicate implies the superset predicate on any object.

So where are all these relations actually observed "in the wild" so to speak? In the object-oriented notion of inheritance of methods. We'll consider only singly-dispatched methods and single inheritance, to simplify things. In this case, when a method is called on an object, assuming the object implements it, a list of classes implementing this method is made, ordered from the object's class itself up through its list of superclasses to the most general class implementing that method. Then the implementation associated with the most specific class in this list is invoked, and if it needs to, it can invoke the next implementation in the list, "delegating" to its superclass; and that can in turn call the next method in the list, etc. (Of course, this is just a conceptual model; this list of implementing classes may be and usually is implicit in actual implementations.)

Now replace classes with predicates and replace methods with pattern-matching rules for a function using those predicates as patterns for their first argument (with the identity function used as the destructuring operation). And order the pattern-matching rules, not by their order in a source file (since they are scattered across source files), but by the implication relationships among them. Since we have only single-inheritance, single-dispatch, there is an unambiguous ordering from most to least specific for any object of any type for which there is a matching pattern, and it corresponds exactly with the order in which the methods would be dispatched.

This is not a hard conclusion to come to. The relation between classes, types, sets, and predicates is hardly original on my part. I may (or may not) be the first to make the extra connection between pattern-matching in functional languages and dynamic dispatch in OO languages, especially given that it's a purely imaginative one; no system in practice (that I know of) orders generalized pattern-matching rules by implication.