Sunday, March 13, 2005

Multiple Dispatch as Pattern Matching

I've always found explanations of multiple dispatch confusing for some reason. I like to divide it into two concepts: pattern matching and static vs. dynamic type information.

Static dispatch resolves a reference to a method name at compile-time using nothing but static type information. Haskell's type classes are an example. Dynamic (single) dispatch uses runtime "type" information to resolve the reference at runtime and select which method to apply based on the most specific "type" of the receiver.

If we want to make this description more consistent with the type theorists' view that types are static entities (roughly--let's ignore dependent types) and that so-called runtime type information is really just tags, then we can instead describe overriding as a sort of distributed syntax for pattern matching with implicit predicates checking the runtime tag of the receiver. The clauses of the pattern match are automatically ordered by the language implementation in order of specificity, so the most specific tag that matches wins. (Of course, this matching can be implemented by crawling up the class hierarchy, but with certain static guarantees like absence of class loaders, you could optimize this to a case dispatch on only those classes that implement a version of the method.)

If we extend pattern matching to compare the runtime tags of both the receiver and all the arguments, and pick the most specific match of all the arguments, we have multiple dispatch.

Although Java's overloading looks like multiple dispatch, it's a restricted form, because method references are resolved at compile-time based only on static type information. We might call it "static multiple dispatch." But apparently according to the standard terminology, "multiple dispatch" is assumed to be dynamic.

No comments: