Friday, May 30, 2008

Multiple Definitions

We had an interesting discussion at work yesterday debating whether Mathematica supports multimethods with its variety of pattern-matching. So I'm taking the opportunity to do a mini-survey of the multiple dispatch spectrum, starting with overloading. As far as Mathematica, it clearly gives you the power of selecting from multiple definitions based on runtime information; more on this in a minute.

Overloading allows you to write different definitions of a function or method, and the definition used when you call the function depends on the number and types of the arguments you pass them. That is, the overload resolution is done by the compiler at compile time with static type analysis. Whatever type your arguments are, and exactly those types, will determine which definition is chosen.

Multimethods let you write different definitions of a function or method, and the definition used when you call the function depends on the number and types of the arguments you pass to them, as examined at runtime. Now you can write one definition for a class, and specializations for its subclasses if so desired, and the definition will be chosen based on the actual type of the arguments at runtime.

You get into a fuzzy gray third area if the runtime values can also be used to select different definitions. This is where Mathematica lies, because its pattern matches can be used to differentiate between a list of at least one element and a list of at least two elements, or between the symbols Null and Infinity. What's useful for writing symbolic algorithms turns out to be useful for regular programmers.

It seems that ML's structural pattern matching is also in this fuzzy gray third area, and that helps me make an interesting connection. For my purposes, multiple dispatch is interesting because it's the way to do expression tree traversal. That is, it lets you write pretty printers and type checkers and the like without needing to code the dispatch yourself (if the node is actually a lambda abstraction, do this, but if it's a cons cell, do that). What I'm noticing now is that one way or another, multimethods and pattern matching are giving you the notational convenience that I enjoy in writing tree traversals, with still perhaps an edge to pattern matching on that score.


murphee said...

Hope you don't mind that I link my take on MultiDispatch vs Overloading:

Basically: I think the Mathematica style of pattern matching is the most general method (and slightly more flexible than the multidispatch implementations in or other systems as it doesn't just rely on a type tag to distinguish between types).

JFKBits said...

murphee: Mathematica's style is the most general in some sense, sure. Some people may not need this generality, and it may be that some multiple dispatchers are much faster than a fully-general value pattern matcher if all you're doing is dispatching based on type (which in Mathematica may be just matching the head). But, the generality of Mathematica's pattern matching fits well with its position as a rapid prototyping environment.

aog said...

You might look at CLOS, which had multi-methods, including value based dispatch. Heck, it even let you do multi-method combinators (e.g., pick between override and accumulate for instance, e.g. normal methods vs. constructors).

Or the C++ template language, which lets you do some multi-dispatch via pattern matching. You can even do dispatch for specific values, which is necessary to get recursion correct.

JFKBits said...

aog: Good to hear from you again. You're worrying me though; you're not justifying the "a" in "aog". I was expecting to get blasted here by you.

Anyway, yes I "want" to take a better look at CLOS, for some low-priority sense of "want." It's somewhere in between looking into Scala and hand-pulling the Queen Ann's lace in my backyard. Really, I am intruigued by CLOS but haven't got pushed over the edge to study it yet.

C++ template stuff is done at compile time though. It is interesting, though, can we say it's static pattern matching?

aog said...

Yes, the template stuff is all compile time, but it's a Turing complete language that executes in the compiler so it seems just as relevant from the point of view of your post. C++ templates are, IMHO, much easier to understand if you don't think of them as templates but as a functional language that generates runtime types.

I liked multi-dispatch. I am actually playing with a template library I built for C++ that lets you do a form of value based dispatch, which is very handy in certain situations.