Existing Dispatch Methods
Dispatch is the process of mapping a function call to a specific function based on its arguments. Most of the time this is done at runtime through the binding phase, however it usually lacks of modularity.
Dispatch by Type
The first way dispatch has been implemented is through function overloading. Two functions share the same name and depending on the type of the argument, a choice will be made to call the right one.
int sqr(int i) { return i * i; } // int version
float sqr(float i) { return i * i; } // float version |
int sqr(int i) { return i * i; } // int version
float sqr(float i) { return i * i; } // float version
When entering the Oriented Object world, there is a more powerful way to dispatch that is not only based on the type but also the type hierarchy. You can allow an object of type A to use the method implementation of one of its children.
class A { public: virtual void print() = 0; };
class B : public A { public: void print() { std::cout < < "B" << std::endl; }; };
class C : public A { public: void print() { std::cout < < "C" << std::endl; }; };
void doPrint(A& a) {
// A doesn't have a definition of the print method
// There is an implicit dispatching to determine which of the B::print or C::print
// will be called. This is done at runtime
a.print();
} |
class A { public: virtual void print() = 0; };
class B : public A { public: void print() { std::cout < < "B" << std::endl; }; };
class C : public A { public: void print() { std::cout < < "C" << std::endl; }; };
void doPrint(A& a) {
// A doesn't have a definition of the print method
// There is an implicit dispatching to determine which of the B::print or C::print
// will be called. This is done at runtime
a.print();
}
This is a single dispatch since we could see the print function this way: void print(B this) { ... }. In C++ we are limited to only one dispatch, even if Stroustrup proposed a way to support multimethods in C++. The main problem is that it's being limited to types.
Dispatch by Constant Value
There are ways to use other criteria in order to dispatch, for example the use of numerical constants. In C++ the way to do it is to use templates.
// General case
template < int N >
struct fact {
enum { value = N * fact< N - 1 >::value };
};
// Specialization for n = 0
template <>
struct fact< 0 > {
enum { value = 1 };
}; |
// General case
template < int N >
struct fact {
enum { value = N * fact< N - 1 >::value };
};
// Specialization for n = 0
template <>
struct fact< 0 > {
enum { value = 1 };
};
You have a code that will run differently depending on the parameter. We can now write functions that work for specialized types and that takes in account their type hierarchy and for specialized cases represented with numerical constants.
If you want to do fancier things, you are stuck! Your only way to achieve the result you expect is to write custom branching yourself. This is where Full dispatch comes in action.
Full Dispatch
Full Dispatch instead of redirecting to the right function based on hard-coded parameters such as the type or the equality of the argument with some constant, allows you to provide a function for each argument.
This way, you will be able to dispatch the function based on the criterion you want. You are no more stuck with a special subset of the language.
You would like to write something like this:
int fact(int n : n == 0 || n == 1) { return 1; }
int fact(int n) { return n * fact(n - 1); } |
int fact(int n : n == 0 || n == 1) { return 1; }
int fact(int n) { return n * fact(n - 1); }
Implementation
To dispatch, we have to know two informations for each overriding method: the actual function and a list of boolean function to test against the parameters.
I've chosen to store it as an array of overriding method, where the overriding is stored as an array containing in first element the actual function followed by the argument conditions.
The dispatching function is trivial to write, you just have to walk through that table and if all the arguments match the conditions then call it.
function fullDispatch(arg, list) {
outer: for (var i = 0; i < list.length; ++i) {
if (list[i].length - 1 !== arg.length) {
// Arguments length is different than number of conditions, no need to continue
continue;
}
for (var j = 0; j < arg.length; ++j) {
if (typeof list[i][j + 1] === 'function' && !list[i][j + 1](arg[j])) {
// Condition fail, try next overriding function
continue outer;
}
}
// Execute the right function
return list[i][0].apply(this, arg);
}
output.error('no dispatch found');
} |
function fullDispatch(arg, list) {
outer: for (var i = 0; i < list.length; ++i) {
if (list[i].length - 1 !== arg.length) {
// Arguments length is different than number of conditions, no need to continue
continue;
}
for (var j = 0; j < arg.length; ++j) {
if (typeof list[i][j + 1] === 'function' && !list[i][j + 1](arg[j])) {
// Condition fail, try next overriding function
continue outer;
}
}
// Execute the right function
return list[i][0].apply(this, arg);
}
output.error('no dispatch found');
}
And here is the code to use it for the factorial function:
var fact = function () {
return fullDispatch(arguments, fact.list);
}
fact.list = [
[function (n) { return 1; },
function (n) { return n === 0 || n === 1; }],
[function (n) { return n * fact(n - 1); },
null]
]; |
var fact = function () {
return fullDispatch(arguments, fact.list);
}
fact.list = [
[function (n) { return 1; },
function (n) { return n === 0 || n === 1; }],
[function (n) { return n * fact(n - 1); },
null]
];
Helper functions
Most of the time, the condition functions will be trivial to write and will make the code unreadable because of the verbose way to declare an anonymous function.
The first step to make this cleaner was to allow null to be used when you don't want to impose any condition on the argument. It means "always return yes" and avoid a useless function call.
Then, we want to avoid to write basic conditions such as "is zero" or "is negative". Using the power of lambda function in association with closure, it's possible to write generics helpers to make these with no effort.
var helper = {};
// Combination
helper.or = function (f, g) { return function (x) { return f(x) || g(x); }; };
helper.and = function (f, g) { return function (x) { return f(x) && g(x); }; };
helper.not = function (f) { return function (x) { return !f(x); }; };
// Primitives
helper.Value = function (n) { return function (x) { return x === n; }; };
helper.StrictNegative = function (x) { return x < 0; };
// Primitive Combinations
helper.Zero = helper.Value(0);
helper.Negative = helper.or(helper.StrictNegative, helper.Zero);
helper.StrictPositive = helper.not(helper.or(helper.Zero, helper.StrictNegative));
helper.Positive = helper.not(helper.StrictNegative); |
var helper = {};
// Combination
helper.or = function (f, g) { return function (x) { return f(x) || g(x); }; };
helper.and = function (f, g) { return function (x) { return f(x) && g(x); }; };
helper.not = function (f) { return function (x) { return !f(x); }; };
// Primitives
helper.Value = function (n) { return function (x) { return x === n; }; };
helper.StrictNegative = function (x) { return x < 0; };
// Primitive Combinations
helper.Zero = helper.Value(0);
helper.Negative = helper.or(helper.StrictNegative, helper.Zero);
helper.StrictPositive = helper.not(helper.or(helper.Zero, helper.StrictNegative));
helper.Positive = helper.not(helper.StrictNegative);
Of course, the shown primitive combinations could be written directly but this shows you how to construct and use complex functions based on few bricks.
Final Result
This is an example of the ackermann function written with the Full Dispatch method and the little helper functions.
var ackermann = function () {
return fullDispatch(arguments, ackermann.list);
}
ackermann.list = [
[function (m, n) { return n + 1; },
helper.Zero,
null],
[function (m, n) { return ackermann(m - 1, 1); },
helper.StrictPositive,
helper.Zero],
[function (m, n) { return ackermann(m - 1, ackermann(m, n - 1)); },
helper.StrictPositive,
helper.StrictPositive]
]; |
var ackermann = function () {
return fullDispatch(arguments, ackermann.list);
}
ackermann.list = [
[function (m, n) { return n + 1; },
helper.Zero,
null],
[function (m, n) { return ackermann(m - 1, 1); },
helper.StrictPositive,
helper.Zero],
[function (m, n) { return ackermann(m - 1, ackermann(m, n - 1)); },
helper.StrictPositive,
helper.StrictPositive]
];
Write Less, Do More
The current version works well but is the syntax is too heavy. In order to make this work we have to copy each time the fullDispatch call which isn't good. We can use a function generator to do the work.
We want to put the conditions first, since they will tend to be smaller, they will appear nicely in one line just before the function definition. And having a setter could be interesting, this would allow to check the input and hide the structure from the user.
Applying these modifications, we would have a code that look like this:
var ack = FullDispatch();
ack.add([Zero, null], function (m, n) { return n + 1; });
ack.add([StrictPositive, Zero], function (m, n) { return ack(m - 1, 1); });
ack.add([StrictPositive, StrictPositive], function (m, n) { return ack(m - 1, ack(m, n - 1)); });
ack.add([null, null], function (m, n) { return 0; }); |
var ack = FullDispatch();
ack.add([Zero, null], function (m, n) { return n + 1; });
ack.add([StrictPositive, Zero], function (m, n) { return ack(m - 1, 1); });
ack.add([StrictPositive, StrictPositive], function (m, n) { return ack(m - 1, ack(m, n - 1)); });
ack.add([null, null], function (m, n) { return 0; });
Which is a pretty nice result. This is not as short as the haskell code but this doesn't use any syntaxic sugar from the language and can be used with any kind of argument conditions.
ackermann 0 n = n+1
ackermann (m+1) 0 = ackermann m 1
ackermann (m+1) (n+1) = ackermann m (ackermann (m+1) n)
ackermann _ _ = 0 |
ackermann 0 n = n+1
ackermann (m+1) 0 = ackermann m 1
ackermann (m+1) (n+1) = ackermann m (ackermann (m+1) n)
ackermann _ _ = 0
To make this work we create a function that is going to to the real dispatch and augment it with the setter and the function list.
var FullDispatch = function () {
// Create the function that does the real dispatch
var object = function () {
return fullDispatch(arguments, object.list);
};
// Give the setter to the function
object.add = function (conds, func) {
object.list.push([func].concat(conds))
}
// Initialize the function list
object.list = [];
return object;
}; |
var FullDispatch = function () {
// Create the function that does the real dispatch
var object = function () {
return fullDispatch(arguments, object.list);
};
// Give the setter to the function
object.add = function (conds, func) {
object.list.push([func].concat(conds))
}
// Initialize the function list
object.list = [];
return object;
};
Demo
The code demonstrated here can been seen working in a demo.
Follow-Up
This little library is working well as it is. There is still some work to do in this field. First, we have to find uses for this pattern. I haven't thought yet of any uses of it and the example provided do not show the real benefit of such a tool. I am pretty sure now this is known and implemented some of you will find how to use it!
The second point is performance issues. Having such a modular dispatch system is great for expressiveness but come at a price. The overhead is pretty huge. One dispatch of a call costs at most n * m where n is the number of overriding functions and m is the number of arguments.
Functions can be added a way that only one (or two) conditions are tested each time. By mimicking the way you would write a branching using if-then-else, the overhead is one function call per condition (and per argument).
It's certainly enough to avoid when performance is required, however I am confident this is acceptable in most conditions compared to the flexibility it gives. Benchmarks would be more than welcome.
