Predicate Dispatching is a model of function application that includes Single Dispatch, Multi Methods, Pattern Matching, and Predicate Classes. 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, Predicate Dispatching has a syntax like this:
gf this-is-a-generic-function (param 1, param2) when param1@Som''''''eClass { ... method 1 ... } // Class test when param1@Som''''''eClass and param2@SomeO''''''therClass { ... method 2 ... } // Conjunction when param1@Som''''''eClass and param1.component@Part { ... method 3 ... } // Destructuring when param1@Ordered and test param1 < param2 { ... method 4 ... } // Arbitrary predicate when param1@!Exclude''''''dClass { ... 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.
Single Dispatch falls out as a special case when the first parameter is tested for class membership:
method singleDispatch (param1, param2) when param1@Bas''''''eClass
Multi Methods fall out when each parameter is tested for class membership. Note that Predicate Dispatching models multimethods where the order of arguments is insignificant, as in Cecil Language or Dylan Language. CLOS-style multimethods, with left-to-right precedence, are not supported.
method multiDispatch (param1, param2) when param1@Firs''''''tClass and param2@Secon''''''dClass
Pattern Matching 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
Predicate Classes 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 (Polymorphic Inline Caches), Binary Search, 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 www.cs.ucla.edu 
. It's also available in a toy Java interpreter; see www.cs.washington.edu . Cecil Language has a similar feature (Predicate Classes) that could be viewed as a special case.
Pattern Matching Views is functionally equivalent to Predicate Dispatching, 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 Py Protocols; see:
Predicate Dispatching is a generalization of Multiple Dispatch.
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: Jonathan Tang, 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!
Ocaml Language and Haskell Language have "guard predicates", while Prolog Language is done entirely with predicate dispatching (with quite a bit of restriction on the forms of the predicates). Mercury Language 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, Clojure Language will probably get a predicate dispatch via it's core.match module: github.com
Why not switch to Table Oriented Programming if you want this? SQL is the closest thing in common use.
Because Table Oriented Programming 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 Relational Alternative To Xml, 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.
Table Oriented Programming could be used to implement predicate dispatching (at a higher level than Turing Completeness); it does not provide it out of the box. You can implement Aspect Oriented Programming using java; that doesn't mean it's trivial.
Isn't that what Control Tables 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 Double Dispatch Example. For a shortcut, imagine something such as "RUN snippetColumn FROM controlTable WHERE " --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. -- Dan Muller
Sort of but not quite. The nice thing about Predicate Dispatching 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 Control Table, you're given a condition and want to find the code snippets that match that condition. In Predicate Dispatching, you're given arguments and want to find the most specific condition that matches those arguments. The problem is reversed, and considerably harder. -- Jonathan Tang
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. Variations Tend Toward Cartesian Product 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: Business Rules Metabase.
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 Functional Programming, sub-classing, Stepwise Refinement, 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 !Is Null() 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
See original on c2.com