This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Patterns that evaluate
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-02-14 (21:12) From: Jon Harrop Subject: Re: [Caml-list] 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 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

```