Re: [Caml-list] Patterns that evaluate

[Jon Harrop <jon@ffconsultancy.com>]

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 user-defined 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