Pattern matching in JavaScript
This morning I was wondering if it would be possible to do some kind of pattern matching using JavaScript. So I fired up my vim and I started coding just after lunch, and I'm pretty happy with what I came up with : the answer is yes.
If you are impatient, you can jump to the example page1. If you are not, please read on.
My first thought was that when one does pattern matching, the idea behind is to be able to discriminate values (über switch) and be able to deconstruct complex structures. The latter requires the use of variables in the pattern. Without touching to the syntax, it is tricky to come up with something more elegant than the following solution :
var id = Math.random ();
var idname = Math.ceil (10000 * Math.random ());
this.variable = function (name) {
var o = {};
o.name = name;
o['__match_pattern_id'+idname] = id;
return o;
}
function is_variable (s) {
return (s &&
s['__match_pattern_id'+idname] &&
s['__match_pattern_id'+idname] == id);
}
// — snippet — //
Basically, each object is assigned to unique ids, and those are used to create objects which can be easily recognized without using too much black magic. The rest is pretty straightforward : it's some really basic one way unification, without any priority.
var _ = m.variable;
function fact (n) {
return m.match(n,
[
[ 0 , function ( ) { return 1 }],
[ _("n"), function (a) { return (a.n * fact(a.n -1)) }]
]);
}
The syntax is pretty clear too : match takes two arguments : first the element to match, and second an array of "couples" (in fact, arrays). Each of those contain a pattern and a function to call if the pattern is matched. As I said beford, all variables in the pattern are in fact dummy (recognizable) objects which will be detected while going down the structure of the pattern, and bound to the correct value.
There was one last point though : how to access the unified values in the function ? I went with the most obvious solution : dump everything in an object and pass it as an argument. This has one major drawback : it is not possible to use twice the same variable, but this is actually a good and sane thing.
Moreover, as I said before, there is no notion of priority based on how deep the matching goes, the first matched pattern is selected2. And there are of course no guards, though these would be quite easy to implement.
Feel free to comment.