Home » forums » LtU Forum

beyond multi-methods

Predicate Dispatching: A Unified Theory of Dispatch by Michael Ernst, Craig Kaplan, and Craig Chambers, ECOOP'98 [gud-ecoop98.ps.gz] introduced the concept of predicate dispatching which

... generalizes previous method dispatch mechanisms by permitting arbitrary predicates to control method applicability and by using logical implication between predicates as the overriding relationship. The method selected to handle a message send can depend not just on the classes of the arguments, as in ordinary object-oriented dispatch, but also on the classes of subcomponents, on an argument's state, and on relationships between objects. This simple mechanism subsumes and extends object-oriented single and multiple dispatch, ML-style pattern matching, predicate classes, and classifiers, which can all be regarded as syntactic sugar for predicate dispatching.

A simple example that implements zip:

type List;
  class Cons subtypes List { head:Any, tail:List};
  class Nil subtypes List;

signature Zip(List, List): List;

method Zip(lst1, lst2) when lst1@Cons and lst2@Cons {
   return Cons(Pair(lst1.head, lst2.head),
               Zip(lst1.tail, lst2.tail)); }

method Zip(lst1, lst2) when lst1@Nil or lst2@Nil { return Nil; }

This is better than multi-methods because

... a lexicographic ordering for multimethods [Ste90] is error-prone and unnatural, and programmers are not warned of potential ambiguities. In a traditional (singly- or multiply-dispatched) object-oriented language without the ability to order cases, either the base case of Zip must be written as the default case for all pairs of List objects (unnaturally, and unsafely in the face of future additions of new subclasses of List), or three separate but identical base methods must be written: one for Nil×Any, one for Any×Nil, and a third for Nil×Nil to resolve the ambiguity between the first two. In our experience with object-oriented languages (using a pointwise, not lexicographic, ordering), these triplicate base methods for binary messages occur frequently.
By el-vadimo at 2008-09-20 15:49 | LtU Forum | previous forum topic | next forum topic | other blogs | 5593 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

the dynamic version

Something very similar is possible (and seems to work well) in strongly, dynamically typed languages (e.g., lisps).

Methods are written in two parts: a predicate expression examining arguments and a body to implement the corresponding generic. The predicates of all of the methods can be compiled into a large tree of conditional statements whose consequent clauses are method bodies -- that large tree is the "generic function".

A set of method definitions is "legal" only if there are no ambiguities. There are two kinds of ambiguity recognized. It is ambiguous if the predicate for method A implies and is implied by the predicate for method B. It is ambiguous if both method A and method B can "match" the arguments yet A's predicate does not imply and is not implied by B's predicate. In the case where both A and B match arguments, and A implies B, but B does not imply A, the method body for A is used (the "most specific" predicate wins).

A generic function in this dynamic view is naturally a decision tree and this has attractive benefits: (1) It is certainly easy to optimize such a tree statically in many attractive ways. (2) Given a decision tree program, it can be easy to rewrite incrementally, on the fly, in meaning preserving ways but which perform the type checks in a different order (thus shortening the code path to some method bodies while lengthening the path to others -- a form of cached dispatching).

A natural extension is to liberalize the sub-language used by method predicates to such an extent that in some cases there is not always any way to prove that method A's predicate does imply (or does not imply) method B's. A programmer can resolve that form of ambiguity by explicit declaration (e.g., "consider A to be more specific than B").

It's nice the way that work on static typing so often, as in this case, identifies what look from the dynamic side like "staticly analyzable subsets" of dyanmic languages (whether for safety or optimization or both or...).

-t

By Thomas Lord at Sat, 2008-09-20 19:24 | login or register to post comments

A DSL for dispatching?

Dispatching has gone from static function pointer to virtual table lookup to multi-methods and pattern-match to this paper's predicate dispatching, which looks like a DSL to me.

If we are going to add a layer of indirection to function calling anyway, why not just expose the mechanism to the programmer so they can use the full power of the language for dispatching instead of another DSL.

Python and Ruby both has modules you can import for multi-methods, I am sure you can write modules to do predicate dispatching as well. While the integration of the feature isn't perfect, I feel it is the correct direction instead of offering support directly in the language.

By Lida Tang at Sun, 2008-09-21 01:11 | login or register to post comments

Predicate dispatch and module systems

How would you design a module system for languages with predicate dispatch?

By Jules Jacobs at Sun, 2008-09-21 15:31 | login or register to post comments

modules for multimethods

It looks like Chambers has given this question some thought:

By el-vadimo at Mon, 2008-09-22 13:18 | login or register to post comments

What I've got so far

I wrote a ruby module that does multi-methods last night, after finding the current modules not 'pretty' or complete enough. :)

I haven't gotten boolean expression part working yet, but there are some previous work I could draw upon, like SQLDSL, and Criteria.

Here is what using it looks like

class Foo
multi do
function bar(a == Integer, b == Integer) => %q{
p a + b
}

function bar(a == Integer, b == String) => %q{
p b * a
}

function bar(a == Integer, b == 0) => %q{
p "short cut"
}
end
end

foo = Foo.new
foo.bar 4, 2 # prints 6
foo.bar 4, "h" # prints "hhhh"
foo.bar 4, 0 # prints "short cut"

I am going to extend the system to support the when clause so you can use it like this


function zip(a, b).when(a == nil | b == nil) => %q{
return nil
}

The difficult part will be making sure you have a total ordering and a complete tautology, but those are algorithmic challenges and doesn't change the fact that predicate dispatch is doable right within the Ruby syntax.

By Lida Tang at Mon, 2008-09-22 03:22 | login or register to post comments