Predicate Dispatching

PredicateDispatching is a model of function application that includes SingleDispatch, MultiMethods, PatternMatching, and PredicateClasses. Instead of tying dispatching to types, methods can be dispatched upon through any arbitrary predicate. Regular dispatching falls out as a special case when the predicate is IS-A.

As modeled in the papers, PredicateDispatching has a syntax like this:

  gf this-is-a-generic-function (param 1, param2)
when param1@SomeClass { ... method 1 ... }// Class test
when param1@SomeClass and param2@SomeOtherClass { ... method 2 ... } // Conjunction
when param1@SomeClass and param1.component@Part { ... method 3 ... } // Destructuring
when param1@Ordered and test param1 < param2 { ... method 4 ... }// Arbitrary predicate
when param1@!ExcludedClass { ... method 5 ... }// Negation
when param1@Ordered or param2@!Forbidden { ... method 6 ... }// Disjunction
when innerPart <- param1.x 
  and test predicateHolds(innerPart) { ...method 7 ... }  // Binding

Methods may be defined at separate points in the program; the compiler coalesces them together into a single generic function.

SingleDispatch falls out as a special case when the first parameter is tested for class membership:

  method singleDispatch (param1, param2) when param1@BaseClass

MultiMethods fall out when each parameter is tested for class membership. Note that PredicateDispatching models multimethods where the order of arguments is insignificant, as in CecilLanguage or DylanLanguage. CLOS-style multimethods, with left-to-right precedence, are not supported.

method multiDispatch (param1, param2) when param1@FirstClass and param2@SecondClass

PatternMatching falls out when subcomponents are tested and the results are bound to variables:

  method patternMatch (fn, consCell) when
fn@Function and
consCell@Cons and not test consCell = nil and 
head <- consCell.car and
tail <- consCell.cdr

PredicateClasses fall out when you test for the base class and then add additional 'test' predicates for conditions:

  method predicateClass (var) when
var@BaseClass and
test firstCondition(var) and
test otherCondition(var)

Implementation strategies usually convert the predicates into disjunctive normal form, and then build a dispatch DAG to select methods for given conditions. Each 'or' leads to a given (potentially shared) method. Bound parameters have their variables eliminated through sharing the expression tree. 'test' predicates are evaluated before the DAG is entered, and then are class-tested for True and False. Class tests use a mixture of linear search (PolymorphicInlineCaches), BinarySearch, and array lookups, as guided by dynamic profile information.

A Lisp implementation is explained in ftp://publications.ai.mit.edu/ai-publications/2001/AITR-2001-006.pdf. A Javaish one is at http://www.cs.ucla.edu/%7Etodd/jpred/. It's also available in a toy Java interpreter; see http://www.cs.washington.edu/research/projects/cecil/www/Papers/gud.html.CecilLanguage has a similar feature (PredicateClasses) that could be viewed as a special case.

PatternMatchingViews is functionally equivalent to PredicateDispatching, and you can easily implement one in terms of the other.

Available papers include:

ftp://ftp.cs.washington.edu/homes/chambers/gud-ecoop98.ps.gz ftp://ftp.cs.washington.edu/homes/chambers/dispatching.ps.gz

There is also a practical Python implementation of the Chambers and Chen predicate dispatch algorithm, included as part of the current CVS version of PyProtocols?; see:

PredicateDispatching is a generalization of MultipleDispatch.

Basically, instead of basing the dispatch on an "is_a" check, you check whether a general predicate is valid on the argument. So, in imaginary syntax instead of writing:

 int foo( int a, int b):
  if a > 0 
return a
  else
return b-a

you'd write:

 int foo ( gt_zero? a, int b): return a
 int foo ( int a, int b): return b

Contributors: JonathanTang, Anonymous Donor(s)

Nice work Jonathan, good stuff, but I did lose interest when I read "No production or academic language currently implements the full predicate dispatching model". Cool stuff always seems to work like that!

OcamlLanguage and HaskellLanguage have "guard predicates", while PrologLanguage is done entirely with predicate dispatching (with quite a bit of restriction on the forms of the predicates). MercuryLanguage has even more flexible predicate dispatching. Strikes me that perhaps the paper's quite a bit old if it made that claim, or perhaps the author didn't really do much research to see how those languages' models maps onto the described one.

In some time, ClojureLanguage will probably get a predicate dispatch via it's core.match module: http://github.com/clojure/core.match

Why not switch to TableOrientedProgramming if you want this? SQL is the closest thing in common use.

Because TableOrientedProgramming provides nothing even remotely similar.

: Hmm... I think I caused this, so I should attempt to clarify this. I believe top is coming from a remark I made on RelationalAlternativeToXml, that the use of 'validation rules' is similar to predicate typing. What hasn't been done as of yet is a full mapping, such that the routine called at runtime is dependant on the validation rules (predicates) satisfied at that time.
: TableOrientedProgramming could be used to implement predicate dispatching (at a higher level than TuringCompleteness); it does not provide it out of the box. You can implement AspectOrientedProgramming using java; that doesn't mean it's trivial.
: --WilliamUnderwood
: Isn't that what ControlTables are used for? Filter rows by a predicate (WHERE clause), and then run the functions or snippets contained in the matching row(s). There is an example under DoubleDispatchExample. For a shortcut, imagine something such as "RUN snippetColumn FROM controlTable WHERE <condition>" --top
: Yes, it's close. But we don't want to repeat it every time we call a routine. Your snippet would be close to what I'd want for defining the routine (which might be what you meant); calling it should simply be a matter of specifying the routine name (aka the control table name) and the parameters (e.g., a row, string, etc), with the routine's boilerplate determining which 'snippetColumn' should actually be invoked. --cwillu
: Then your compiler is really acting like an interpreter in a way.
: If I understood the above correctly, then you'd actually have to store a predicate in the table along with their corresponding function, and you'd have to somehow execute each predicate, giving it access to the arguments of the call, in order to select the right function. Or each row would have one predicate per argument, perhaps. Then you would define new methods by inserting a new row. -- DanMuller
: Sort of but not quite. The nice thing about PredicateDispatching is that the compiler automatically detects when one predicate logically implies another (up to a point; arbitrary functions need to be identical in their ASTs, otherwise you run into undecidability problems) and select the most specific applicable method. Kind've like how Lisp multiple inheritance works, but with arbitrary predicates and not just classes. There's no easy way to do this in tables, short of building the dispatch DAGs that Cecil compilers use and storing them as edge representations. I'd rather not think of the running time of that.
: Actually, thinking of Top's comments again, I think there're problems even without inheritance. In a ControlTable, you're given a condition and want to find the code snippets that match that condition. In PredicateDispatching, you're given arguments and want to find the most specific condition that matches those arguments. The problem is reversed, and considerably harder. -- JonathanTang

The problem with predicate dispatching is that in practice the implementations are not one-to-one with the various combinations of parameters (predicates). The implementations tend to interweave and are assymetrical such that one activity may involve many combinations and others only one. It is kind of difficult to describe. VariationsTendTowardCartesianProduct also tries to describe this lumpy interweaving, although doesn't quite capture the spirit. I have yet to find a good way to articulate this problem.

Saying "this block of code goes with combination A and this block goes with combi B" is not good enough. The granularity needed is still smaller than that. IF statements are still the best for that kind of thing in my opinion because you can have 10 or 1 per block, sub-block, sub-sub-block, etc. Sure, you could divide the code into micro-blocks, but it's a cure worse than the desease. Often the real world just does not offer nice chunk-able abstractions. IF statements deal with the slop fairly well.

Perhaps some of it could be said like this: The space of all possible combinations forms a sparse hyper-array. IF statements generally filter out the "nulls" so that one is only looking at the non-null "cells". They also filter out some of the duplication in what would be the "parameters" of the predicates. Note that I am not claiming that IF statements are always the best solution, but rather they are often the least evil for semi-complex dispatching. Related: BusinessRulesMetabase.

Note that I am not saying there should necessarily be a single routine with a bunch of conditionals/switch-case clauses. Often it's best to divide up using a combination of techniques, including FunctionalProgramming, sub-classing, StepwiseRefinement, and conditionals, depending on the situation.

 --top

It looks like moving asserts and guard clauses into the parameter area, which would make for some serious horizontal scrolling and not save any coding. It may however help the compiler in creating new errors and warnings (passing an nullable variable into !IsNull?() method could warn you). But a sufficiently smart compiler should be able to parse guard clauses directly without language support.

--BrianG

It's not neccessary to put parameter area in one line

--Lumj

CategoryLanguageFeature, CategoryConditionalsAndDispatching, BusinessRulesMetabase