Pattern-matching destructors ?

Pattern-matching destructors ?

[David Teller]

   Hi everyone,

 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 ? 


Thanks in advance,
 David

-- 
David Teller ------------------------------------------
Security of Distributed Systems -----------------------
-- http://www.univ-orleans.fr/lifo/Members/David.Teller
----- Laboratoire d'Informatique Fondamentale d'Orleans

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

[Alain Frisch]

David Teller wrote:
>  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".

Views?

-- Alain

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

[Jon Harrop]

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

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

[Jean-Christophe]

David Teller a écrit :
> 
>  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.

I don't see why a lot of information in AST nodes is getting into the 
way of pattern-matching. When decorating ASTs, you basically replace a 
type definition such as

type t =
   | A
   | B of b
   | C of string * t * t
   | D of t list

by two mutual recursive types

type t =
   { node : t_node;
     ... a lot of information here, in other fields ... }

and t_node =
   | A
   | B of b
   | C of string * t * t
   | D of t list

As you can see, this is a purely local modification: three lines were 
inserted (between "type t" and "=").

As for pattern-matching, this is exactly the same: the modification is 
only local. Indeed, your recursive function over type t, which was 
looking like

let rec f = function
   | A -> ...
   | B b > ...
   | C (s, t1, t2) -> ... (f t1) ... (f t2) ...
   | D l -> ...

is turned into

let rec f t =
   f_node t.node

and f_node = function
   | A -> ...
   | B b > ...
   | C (s, t1, t2) -> ... (f t1) ... (f t2) ...
   | D l -> ...

Again we only inserted new lines between "let rec f" and "= function".

I agree that nested pattern-matching is slightly different, though. But 
as already said by somebody else, you can match against field node only, 
which looks like

   | C (s, {node=A}, {node=D l}) -> ...

I don't see that as really intrusive.

Hope this helps,
--
Jean-Christophe

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

[David Teller]

On Tue, 2007-10-16 at 19:44 +0200, Jean-Christophe wrote:
> David Teller a écrit :
> > 
> >  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.
> 
> I don't see why a lot of information in AST nodes is getting into the 
> way of pattern-matching. 

Okay, it is possible to write it in a rather concise manner. But it
still exposes somewhat too much information for my taste. I'll look at
Martin's camlp4 extension.

> When decorating ASTs, you basically replace a 
> type definition such as
> 
> type t =
>    | A
>    | B of b
>    | C of string * t * t
>    | D of t list
> 
> by two mutual recursive types

Well, I actually have about 15 recursive types, which does make it
somewhat more difficult, in part because my records need to have
different field names. Now, I guess I can just parametrize your second
type t upon t_node.

Thanks for the answers,
 David


-- 
David Teller ------------------------------------------
Security of Distributed Systems -----------------------
Project JStify: Static Analysis for JavaScript 2  -----
-- http://www.univ-orleans.fr/lifo/Members/David.Teller
----- Laboratoire d'Informatique Fondamentale d'Orleans