Patterns that evaluate
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20070214 (21:12) 
From:  Jon Harrop <jon@f...> 
Subject:  Re: [Camllist] Patterns that evaluate 
On Wednesday 14 February 2007 18:55, Gerd Stolpmann wrote: > You are a bit quick. Before discussing syntax it is more important to > define the semantics of such patterns. I mean we have already three > predefined kinds of equality in O'Caml: > >  ( == ) >  ( = ) >  (fun x y > compare x y = 0) > > I admit I do not prefer any one of them. So which equality should be > used to test whether the variable is equal to the matched part of the > value? None, I think. Pattern matching is clearly an awesome tool, and there are many ways that OCaml's pattern matching can be improved upon. To me, active patterns are about applying userdefined functions to test partial matches. So I would want the user to explicitly supply the appropriate comparison function, as you do with Set and Map. There are many places where this is advantageous. My favourite example is term rewriting. Assuming the existence of +: and *: operators to add and multiply symbolic expressions, we can currently write a symbolic derivative function: let rec d f x = match f with  Var y when x=y > Int 1  Int _  Var _ > Int 0  Add(f, g) > d f x +: d g x  Mul(f, g) > f *: d g x +: g *: d f x That is already nicer than most other languages but there is plenty of room for improvement. Before we even get to active patterns, we can add operator overloading to use + and * instead: let rec d f x = match f with  Var y when x=y > Int 1  Int _  Var _ > Int 0  Add(f, g) > d f x + d g x  Mul(f, g) > f * d g x + g * d f x That's a bit better. Why not have infix operators as constructors and deconstructors: let rec d f x = match f with  Var y when x=y > Int 1  Int _  Var _ > Int 0  f + g > d f x + d g x  f * g > f * d g x + g * d f x But we often want more than that. Consider a function that naively performs the substitution a+b > c taking commutativity into account: let rec mem x = function  Int _  Var _ as f > f=x  Add(f, g)  Mul(f, g) as e > mem_rec e x f  mem_rec e x g and mem_rec e x f = match e, f with  Add _, Add _  Mul _, Mul _ > mem x f  Add _, _  Mul _, _ > false  _ > assert false let rec sub = function  Int _  Var _ as f > f  Add _ as e when mem (Var "a") e && mem (Var "b") e > Var "c" +: sub(e : Var "a" : Var "b")  Add(f, g) > Add(sub f, sub g)  Mul(f, g) > Mul(sub f, sub g) That could be written much more elegantly, something like this: let rec rewrite rule = function  Int _  Var _ as f > rule f  Add(f, g) > Add(rewrite rule f, rewrite rule g)  Mul(f, g) > Mul(rewrite rule f, rewrite rule g) let sub = function  Var "a" + Var "b" + t > Var "c" + t  expr > expr let sub = rewrite sub where the pattern Var "a" + Var "b" + t searches the symbolic expression for "a" and "b" and puts the remainder in t. So the "+" is an active pattern that takes two patterns as arguments and matches if it can split an expression into an addition of the two patterns. This active pattern can then be made arbitrarily clever with respect to how it slices and dices the data structure. Better yet, the code is no longer tied to the underlying representation of terms, so the inefficient representation of a sum as a list of Add cells can be replaced by a mapping from terms to their multiples, which can then be searched in O(log n) time instead of O(n) time. Given that these kinds of ideas have been around for so long (that Haskell views paper), I'm surprised that people have implemented active patterns in more languages.  Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists