Matching for JavaScript

Yeah, matching is a good concept.

OMeta: pattern-matching language

I'm a tad surprised I hadn't already blogged this, but OMeta is a language for expressing pattern matches. It can be embedded in Python as PyMeta. Interestingly, PyMeta includes a parser for TermL (about which see next post).

Pattern-matching a la OMeta/XSLT/what have you is definitely going to be one of the modes supported by Decl, but I still don't really grok it. So ... OMeta. For study and illumination.

TXL: Tree Transformation Language

I essentially think of Decl macros or maps or whatever as falling into two categories: first is the text expression of a template, but the other works on tree structures.

Googling on "tree transformation" is a useful exercise, and five minutes perusal finds me two good links: TXL (the tree transformation language) is precisely what I want to be able to do (with a rule-based approach), and then there's an interesting paper ("A Language for Bidirectional Tree Transformations") by the Unison guys at UPenn about reversible lenses that act between tree structures, which is of course my map concept. (I should probably read everything they're doing.)

So those need to be read carefully. I'm sure there's more.

Pattern matching

I still haven't quite got my head around pattern matching, but I think I'm getting closer. The Wikipedia article on pattern matching largely addresses Haskell and Mathematica (both of which provide pattern matching as part of the language). There's a Sub::PatternMatching in Perl, which ... almost does what I'm looking for, and there's Data::Match, which I remember finding earlier this year. And of course XSLT is based on pattern matching as well.

Essentially, a pattern is a structure with holes. These holes may be named, and we can also make assertions about the holes, like hole A and hole B have to have the same content, but that's the basic upshot. When applied to one or more targets, the pattern is an iterator; it can return more than one match.

Chained together, these matches are AI's "unification", a powerful technique that can find multiple solutions to a given question posed in terms of predicate assertions over a universe of data. Pattern matching is unification, quite literally (although the converse is not true; unification includes things that aren't pattern matching).

Oh, wait. I said that the pattern matcher is an iterator - that's true, it can be used in a "data mode", but we can also associate actions with patterns to move the pattern matcher into an "action mode", and I think in the case of Class::Declarative, this mode is going to be easier to conceptualize. This is the mode used in functional languages such as Haskell (I'm basing this statement on the introduction to Sub::PatternMatching), and now that I think about it, XSLT as well.

When applying a series of patterns to a given data structure in this model, we can think of the series as a kind of "case" selector. Each match runs a bit of code, and the named bindings in the match are passed to the code as its call parameters. We could also disassociate the matches and the code by defining events that would fire, invoking code defined elsewhere (making more general coding easier).

All that remains is to start thinking of some use cases and coding some likely-looking expressions of patterns. WWW::Mechanize and HTML::TreeBuilder are such obvious candidates here; we're essentially doing what parsley does in this case.