Extensible matching

TODO:

• syntax extension (now [ExtensionPattern] variant Tree...)
• capture and store environment in which pattern is defined
• negative tests

Refs:

• http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200244.pdf fast lists
• http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps views for ML
• http://www.haskell.org/development/views.html Haskell impl
• http://www5.cs.cornell.edu/~liujed/papers/padl03.pdf for Java

variant Tree {
  | Node { l : Tree; e : int; r : Tree; size : int; }
  | Nil

  Size : int { get { match (this) { | Node (_,_,_,s) => s | Nil => 0 } }

  public N (l : Tree, e : int, r : Tree) : Tree { 
    Node (l, e, r, l.Size + r.Size + 1)  
  }

  pattern N (l, e, r) =
    Node (l, e, r, _);
}

class List {
  public IsCons : bool { ... }
  public IsNil : bool { ... }
  public Head : int { ... }
  public Tail : list { ... }

  // always use IsCons to get non-exhaustive pattern warning
  pattern Cons (hd, tl) =
    List where (IsCons = true, Head = hd, Tail = tl);
  pattern Nil () =
    List where (IsCons = false);
}

match (some_list) {
  // transformed to: List where (IsCons = true, Head = 2, tail = List where (IsCons = false))
  | List.Cons (2, List.Nil) => ...
  // names in pattern definition are meaningful
  | List.Cons (tl = List.Nil, hd = 22) => ...
  ...
}

The basic idea is that when a type T has an extension pattern P, then when you match on objects of type T (which has to be known in advance, so it doesn't yet play well with type inference, or otherwise you have to use T.P) you can use P as a pattern.

Now if P is defined as P(x,y,z) = some_complex_pattern_using_x_y_z, then your usage of P(1,q,[_,2]) is transformed to some_complex_pattern_using_x_y_z with occurences of x replaced with 1, y with q and z with [_,2].

This may for example make regular classes pretend to be variants in matching, like in the list example above, where pattern Cons (hd, tl) is defined to be List where (IsCons = true, Head = hd, Tail = tl), which is just a class-pattern with property calls inside.