JMatch: Iterable Pattern Matching

http://www.cs.cornell.edu/Projects/jmatch/

by jules • 17 years ago

26 3 17 years ago

cs.cornell.edu

jules• 17 years ago

For those who click the link and think "Ahhrg Java -close-", read on. This is a very advanced pattern matching system that's far more powerful than the one in O'Caml/Haskell.

Pattern matching tries to find values for the variables in a formula such that the formula produces some value. For example if we define:

    type list = Pair(int,list) | Empty

    case v of
      Pair(n, rest) -> ...
      Empty -> ...

Now the pattern matcher tries to find values for n and rest such that the expression `Pair(n,rest)` evaluates to `v`.

JMatch extends this in several ways: it lets you define your own pattern matchers, and it extends pattern matching to cases when there are multiple ways of binding the variables.

If we have `lst = [1,2,3]` then the pattern `x in lst` has multiple solutions: `x=1, x=2` and `x=3`. Similarly the pattern `x in lst && y in lst && x <= y` has 6 solutions. You can iterate over the solutions of a pattern:

    foreach(x in lst && y in lst && x <= y){ ... }

In general you can have

    foreach(<boolean formula>) {...}

given that you have defined pattern matchers for calls in the boolean formula.

Iterating over the indices/values of an array:

    foreach(x == arr[i]){ print(i); print(x); }

This iterates over all values of x and i such that `x == arr[i]` is true.

syntax slightly simplified (& types omitted) in examples

Check out page 8 of [http://www.cs.cornell.edu/Projects/jmatch/jmatch.pdf]. It's a Lisp (sexp) pretty-printer in forward mode and an un-pretty-printer (aka parser) in backward mode!

akkartik• 17 years ago

Googling around I see Ehud Lamm got waay excited about it in 2003. http://lambda-the-ultimate.org/classic/message5496.html

kingkawn• 17 years ago

For a minute I thought this was Jdate, and I rushed to downvote. Nvm.

JMatch: Iterable Pattern Matching

Related Stories