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.
6 Responses to "Pattern matching in JavaScript"
If you're interested, JavaScript 2 will contain "switch-type", which is a thinly disguised form of pattern-matching. It's something intermediary between Lisp-style patterns and OCaml-style patterns, with the ability to match against anything (statically typed or not) except objects whose constructors are private.
The thing I really dislike with JS 2 is that it has nothing to do with JS anymore. The decision to have a class based object orientation instead of the wonderful prototype based objects is, imho, a huge mistake.
JavaScript's beauty is the conciseness of the language, it's simplicity (yet power) and it's expressiveness. JS 2 adds far too much constructs and is so different from JS that I might never use it.
I know that ECMA is working on backward compatibility, but trying to transform that great little scripting language into a full fleshed class oriented programming language is nonsense.
Anyway, all that to say that I really dislike ES4
Hi Adrien, great post.
I totally agree with your vision about JS2.
[...] Friggeri has been playing with pattern matching in JavaScript a la functional [...]
[...] Diigo Diary 02/27/2008 分類於 Diigo Diary — benxshen @ 8:35 上午 Friggeri.net : Archive : Pattern matching in JavaScript [...]
Honi soit legate left buy cytotec dead hand held.
Leave a Reply