JMatch [proxy]

The Wayback Machine - https://web.archive.org/web/20070816050303/http://www.cs.cornell.edu:80/Projects/jmatch/

The JMatch language extends Java with pattern matching that supports both data abstraction and iteration abstraction. Patterns are not tied to algebraic data constructors as in ML; instead, a single JMatch method may be used in several modes, some of which can serve as patterns. JMatch provides modal abstraction that simplifies the specification and implementation of abstract data types. These modes that may share a common implementation as a boolean formula. Thus, the specification, implementation, and use of iteration abstractions are made convenient, by automatically finding multiple solutions to a formula or pattern.

JMatch version 1.0 introduced interruptible iterators, a new language feature that makes iteration abstractions much easier to implement. The loop body controlled by the iterator may interrupt it with requests to perform work other than iteration. Interrupts are similar to exceptions, but propagate differently and have resumption semantics.

Publications and Reports

Jed Liu, Aaron Kimball, Andrew C. Myers. Interruptible Iterators, Proceedings of the 33rd ACM Symposium on Principles of Programming Languages (POPL'06), pp. 283–294, Jan. 2006.

Jed Liu, Andrew C. Myers. JMatch: Iterable Abstract Pattern Matching for Java, Proceedings of the 5^th International Symposium on Practical Aspects of Declarative Languages (PADL'03), pp. 110–127, New Orleans, LA, Jan. 2003. LNCS 2562.

Jed Liu, Andrew C. Myers. JMatch: Java plus Pattern Matching. Technical Report 2002-1878, Computer Science Dept., Cornell University. October 2002, revised April 2005. [ PDF | PostScript ]

Resources

Version 1.1.6 of the JMatch compiler was released 1 Nov, 2005.
To receive announcements of JMatch updates, send mail to andru@cs.cornell.edu
JMatch is built using the Polyglot extensible compiler framework.

Support

The development of the JMatch compiler has been supported by a number of funding sources, including ONR Grant N00014-01-1-0968, NSF Grant 0208642, an NSF CAREER award, and an Alfred P. Sloan Research Fellowship.

Andrew C. Myers and Jed Liu, Cornell University

JMatch code examples

A modal abstraction: A containment predicate and a tree iterator

boolean contains(Object elem) {
  if (left != null && value < elem) return left.contains(elem);
  if (value.equals(elem)) return true;
  if (right != null && value > elem) return right.contains(elem);
} iterates(elem) {
  foreach (left != null && left.contains(Object e)) yield e;
  yield value;
  foreach (right != null && right.contains(Object e)) yield e;
}

One formula implements both modes: concise, ensures consistency

boolean contains(Object elem) iterates(elem) (
  (left != null && elem < value && left.contains(elem)) ||
  elem = value ||
  (right != null && elem > value && right.contains(elem))
)

A client loop selecting elements matching a pattern

Set t = new RedBlackTree(); ...
foreach (t.contains(Point(int x, x*2))) { 
    print(x);
}

Balancing a red-black tree with pattern matching

static RBNode balance(int color, int value, RBTree left, RBTree right)
{
  if (color == BLACK) {
    switch (value,left,right) {
      case int z,
           RBNode(RED,int y,RBNode(RED,int x,RBTree a,RBTree b),RBTree c),
           RBTree d:
      case z, RBNode(RED,x,a,RBNode(RED,y,b,c)),d:
      case x, a, RBNode(RED,z,RBNode(RED,y,b,c),d):
      case x, a, RBNode(RED,y,b,RBNode(RED,z,c,d)):
        return RBNode(RED,y,RBNode(BLACK,x,a,b),RBNode(BLACK,z,c,d));
    }
  }
  return RBNode(color, value, left, right);
}

Inverting CPS conversion

static boolean FV(Expr e, String v) iterates(v) (
  e = Var(v) ||
  e = Lambda(String v1, Expr body) && FV(body, v) && !(v = v1) ||
  e = Apply(Expr fn, Expr arg) && (FV(fn, v) || FV(arg, v))
)

static Var freshVar(String base, Expr e) {
  boolean dummy = true;
  for (int i = 0; dummy; i++) {
      String var = base + i;
      if (!FV(e, var)) return Var(var);
  }
}
  returns() ( !FV(e, result.name) )

static public Expr convert(Expr e) returns(e) (
  Var k = freshVar("k", e) && (
    e = Var(String v1) &&
    result = Lambda(k, Apply(k, e))
  else
    e = Lambda(Var v2, Expr body) &&
    result = Lambda(k, Apply(k,
               Lambda(v2,
                 Lambda(k, Apply(convert(body), k)))))
  else
    e = Apply(Expr fn, Expr arg) &&
    Var f = freshVar("f", arg) &&
    result = Lambda(k, Apply(convert(fn),
               Lambda(f, Apply(convert(arg),
                 Lambda(Var("v"), Apply(Apply(f, Var("v")), k))))))
  )
)
...
Expr church_one = lambda("f", lambda("x", apply("f", "x")));
Expr cps_one = CPS.convert(church_one);
let CPS.convert(Expr e) = cps_one // e equals church_one!

JMatch