Re: [Caml-list] Pattern-matching destructors ?

[Jon Harrop <jon@ffconsultancy.com>]

On Tuesday 16 October 2007 16:20:45 David Teller wrote:
>  I'm currently working on static analysis of JavaScript 2. For this, I
> need to keep lots of informations in each node of my AST, including
> things such as line/column (for better error messages), unique
> identifier (for storing inferred information), etc. As things progress,
> I fear that the number of such informations is growing prohibitive and
> very much getting into the way of pattern-matching.
>
>  However, I do remember reading on this list a discussion regarding the
> possibility of extending pattern-matching so as to allow matching
> against user-defined criteria rather than constructors -- I'm afraid I
> don't remember the name of these criteria, possibly "destructors" or
> "queries".
>
>  As far as I remember this discussion, the feature was present in F# (or
> at least planned), but not in OCaml. Could anyone tell me if things have
> evolved on the OCaml side, perhaps with a little camlp4 magic ?

You are referring to the pattern matching extension called "views" that is 
implemented in F# and called "active patterns" there. The primary use of 
active patterns in F# is to provide a view of an existing data structure that 
looks like a variant type and can be destructured using pattern matching. For 
example, to view a .NET XML DOM tree (a tree of objects) as the simple 
variant type used by OCaml's excellent xml-light library.

That is certainly a great language feature and is all the more important in a 
language that wants to interrogate non-native (i.e. non-F#) APIs like 
the .NET libraries. However, this feature is overkill for your situation 
because you have complete control over the data structure used. As Jeff has 
already said: you want to bundle your metadata into a record so that you can 
choose whether or not to dissect it in the pattern match.

From what you have said, you might want to abstract your metadata into a 
record:

  type 'node meta = {loc: int; char: int; id: int; node: 'node}

Your AST might become:

  type expr_aux =
    | Int of int
    | Var of string
    | UnOp of [`Neg] * expr
    | BinOp of [`Add | `Sub | `Mul | `Div] * expr * expr
  and expr = {loc: int; char: int; id: int; node: expr_aux};;

And your functions become:

# let loc_of e = e.loc;;
val loc_of : expr -> int = <fun>

# let rec eval assoc e =
    match e.node with
    | Int n -> n
    | Var v ->
        (try assoc v with Not_found -> invalid_arg (string_of_int e.loc)) 
    | UnOp(`Neg, f) -> -eval assoc f
    | BinOp(op, f, g) ->
        let f = eval assoc f and g = eval assoc g in
        match op with
        | `Add -> f + g | `Sub -> f - g
        | `Mul -> f * g | `Div -> f / g;;
val eval : (string -> int) -> expr -> int = <fun>

You might use it like this:

# let assoc = function _ -> raise Not_found;;
val assoc : 'a -> 'b = <fun>
# let mk e = {loc=0; char=0; id=0; node=e};;
val mk : expr_aux -> expr = <fun>
# eval assoc (mk(BinOp(`Add, mk(Int 3), mk(Int 4))));;
- : int = 7

Interestingly, I recently discovered that case classes are Scala's answer to 
this problem. IMHO, this ordinary ML answer is just fine.

This topic and many others are described in detail with working examples in 
the OCaml Journal.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e