Request for complete pattern matching

Request for complete pattern matching

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 722 bytes --]


- Lazy constructor and function can not be matched ... and this is ennoying

I saw a post recently about lazy constructor and I can not write the
camlp4 extension I want because of the second limitation ...

It may be not clear what I mean by matching a function (looks impossible
;-). I mean something like

pattern <= expr expr expr       is a pattern

and a function f is matched by

p <= e1 ... eN      iff     f e1 ... eN is matched by p

(I do not care about the final syntax ...)
-- 

I know there is a BIG problem of ambiguity in the evaluation order for
complex pattern matching ...
The user should be warned about that. But this would not be a problem
for the application I have in mind.

Christophe Raffalli



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 894 bytes --]

Re: [Caml-list] Request for complete pattern matching

[Luc Maranget]

> 
> - Lazy constructor and function can not be matched ... and this is ennoying
I guess there must be a reason for not matching Lazy constructor, in fact
I see no constructor in the Lazy module. Maybe I am missing something here.


> 
> I saw a post recently about lazy constructor and I can not write the
> camlp4 extension I want because of the second limitation ...
> 
> It may be not clear what I mean by matching a function (looks impossible
> ;-). I mean something like
You bet.

> 
> pattern <= expr expr expr       is a pattern
> 
> and a function f is matched by
> 
> p <= e1 ... eN      iff     f e1 ... eN is matched by p
> 
> (I do not care about the final syntax ...)

I do not get the idea either, can you be a bit more specific ?
I have more or less the feeling that

match f with
 pattern <= expr expr expr -> bonga

means

match f expr expr expr with
p -> bonga 

Thus I hardly seen your point.

--Luc Maranget

Re: [Caml-list] Request for complete pattern matching

[Christophe Raffalli]

> 
> I do not get the idea either, can you be a bit more specific ?
> I have more or less the feeling that
> 
> match f with
>  pattern <= expr expr expr -> bonga
> 
> means
> 
> match f expr expr expr with
> p -> bonga 
> 

This is true ....

but how do you translate

match e with
  S(P(g) <= 0) -> g
| ....

answer :

match f with
   S(f) ->
	match f 0 with
	  P(g) -> ...
| ...

and as you see the "..." are duplicated !!!

you can get an exponential explosion in the size of the program.

The you have to give names to value in the "..." and you get very ugly 
programs ...


> Thus I hardly seen your point.
> 
> --Luc Maranget

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Caml-list] Request for complete pattern matching

[Michal Moskal]

On 11/22/05, Christophe Raffalli <christophe.raffalli@univ-savoie.fr> wrote:
> It may be not clear what I mean by matching a function (looks impossible
> ;-). I mean something like
>
> pattern <= expr expr expr       is a pattern
>
> and a function f is matched by
>
> p <= e1 ... eN      iff     f e1 ... eN is matched by p
>
> (I do not care about the final syntax ...)

Something like http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps
or http://nemerle.org/Extensible_matching ?

--
   Michal Moskal,
   http://nemerle.org/~malekith/

Re: [Caml-list] Request for complete pattern matching

[Christophe Raffalli]

Michal Moskal a écrit :
> On 11/22/05, Christophe Raffalli <christophe.raffalli@univ-savoie.fr> wrote:
> 
>>It may be not clear what I mean by matching a function (looks impossible
>>;-). I mean something like
>>
>>pattern <= expr expr expr       is a pattern
>>
>>and a function f is matched by
>>
>>p <= e1 ... eN      iff     f e1 ... eN is matched by p
>>
>>(I do not care about the final syntax ...)
> 
> 
> Something like http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps

No this is not the same ...

I just want to be able inside one single pattern to give arguments to a 
variable of the pattern (which shoud have a function type) and match the 
result.

However, you can maybe (I am not sure at all) implement views as a 
camlp4 extension of ocaml if you have this feature.


> or http://nemerle.org/Extensible_matching ?
> 
> --
>    Michal Moskal,
>    http://nemerle.org/~malekith/
> 

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Caml-list] Request for complete pattern matching

[Christophe Raffalli]

sejourne_kevin a écrit :
> Christophe Raffalli a écrit :
> 
>> - Lazy constructor and function can not be matched ... and this is 
>> ennoying
>>
>> I saw a post recently about lazy constructor and I can not write the
>> camlp4 extension I want because of the second limitation ...
>>
>> It may be not clear what I mean by matching a function (looks impossible
>> ;-). I mean something like
>>
>> pattern <= expr expr expr       is a pattern
>>
>> and a function f is matched by
>>
>> p <= e1 ... eN      iff     f e1 ... eN is matched by p
>>
>> (I do not care about the final syntax ...)
>>
> 
> You want something like that ?
> 
> let f = function
>       (x,y,z) when f x y z -> ...
>     | (x,y,z) when g x y z -> ...
>     | all_other_cases -> (static/compile_time)_error ...
> 

No this is not a problem of test. I want to be able to write

match e with
   (0 <= 0, g) -> g
| (f, 0 <= 0) -> f
| (f, g) -> fun x -> f x + g x

which means the same as

match e with
   (f, g) ->
   if f 0 = 0 then g else if g 0 = 0 then f else fun x -> f x + g x

- The first problem is that removing this feature is a hard translation, 
and I would like the compiler to do it

- The second problem is that I really need it to extend the pattern 
matching of ocaml using camlp4

Let us do a simple example (this is not what I am doing):

type 'a lazy = unit -> 'a

Lazy(e) := fun () ->  e (defined as a camlp4 macro to be sure that e is 
not evaluated)

and then

"Lazy(p)" in a pattern means "p <= ()" (this should also be a camlp4 
macro, but p <= () does not exist in the language)





> Should be hard to eval f and g before execution...
> 
> 
> 
> 
> 
> 
> Kévin.
> 
>     
> 
>     
>        
> ___________________________________________________________________________ 
> Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! 
> Messenger Téléchargez cette version sur http://fr.messenger.yahoo.com
> 

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Caml-list] Request for complete pattern matching

[Luc Maranget]

> 
> No this is not a problem of test. I want to be able to write
> 
> match e with
>   (0 <= 0, g) -> g
> | (f, 0 <= 0) -> f
> | (f, g) -> fun x -> f x + g x
> 
Well, I understand better and (as you may have guessed yourself!) I do
not incline to adopt the idea.

However provided you have some 'break' construct to transfert control to
next matching, you can perhaps compile your construct by syntactic 
transformation.


My idea is to transform your patterns into
normal ones, replacing p <= e1 e2 ... en by fresh variables (say v)
and then to match 'v e1 ... en' against p.

Here you have :

match e with
| (v1, g) -> (match v1 0 with 0 -> g |_ -> break)
| (f, v2) -> (match v2 0 with 0 -> f |_ -> break)
| f, g -> fun x -> f x + g x

At a little additional cost in complexity,
you can replace 'break' (which does not exists) by exceptions as follows

let x = e in
try (match x with
  | (v1, g) -> (match v1 0 with 0 -> g |_ -> raise Exit)
  | _ -> raise Exit)
with Exit ->
try (match x with
  | (f, v2) -> (match v2 0 with 0 -> f |_ -> raise Exit)
  | _ -> raise Exit)
with Exit ->
(match x with  f, g -> fun x -> f x + g x)


I am not familiar enough with Camlp4, but I have the feeling
that some purely syntactic compilation of your construct is doable.
Since, only from the presence of <=,
can you introduce the extra matchings and try .. with Exit) 
I am not saying it is easy, just that it looks feasible.

Typing and warnings are yet another issue!



-- Luc

Re: [Caml-list] Request for complete pattern matching

[Martin Jambon]

On Wed, 23 Nov 2005, Luc Maranget wrote:

>>
>> No this is not a problem of test. I want to be able to write
>>
>> match e with
>>   (0 <= 0, g) -> g
>> | (f, 0 <= 0) -> f
>> | (f, g) -> fun x -> f x + g x
>>
> Well, I understand better and (as you may have guessed yourself!) I do
> not incline to adopt the idea.
>
> However provided you have some 'break' construct to transfert control to
> next matching, you can perhaps compile your construct by syntactic
> transformation.
> 
> My idea is to transform your patterns into
> normal ones, replacing p <= e1 e2 ... en by fresh variables (say v)
> and then to match 'v e1 ... en' against p.
>
> Here you have :
>
> match e with
> | (v1, g) -> (match v1 0 with 0 -> g |_ -> break)
> | (f, v2) -> (match v2 0 with 0 -> f |_ -> break)
> | f, g -> fun x -> f x + g x
>
> At a little additional cost in complexity,
> you can replace 'break' (which does not exists) by exceptions as follows
>
> let x = e in
> try (match x with
>  | (v1, g) -> (match v1 0 with 0 -> g |_ -> raise Exit)
>  | _ -> raise Exit)
> with Exit ->
> try (match x with
>  | (f, v2) -> (match v2 0 with 0 -> f |_ -> raise Exit)
>  | _ -> raise Exit)
> with Exit ->
> (match x with  f, g -> fun x -> f x + g x)
>
>
> I am not familiar enough with Camlp4, but I have the feeling
> that some purely syntactic compilation of your construct is doable.
> Since, only from the presence of <=,
> can you introduce the extra matchings and try .. with Exit)
> I am not saying it is easy, just that it looks feasible.

That's basically what I did for Micmatch 
(http://martin.jambon.free.fr/micmatch.html).
It was not so simple to implement with Camlp4, but it works. Exceptions 
are used extensively as you describe. So it is actually possible to 
insert arbitrary computations into ML patterns! Of course the complexity 
is not O(size of the pattern) anymore.

For instance, you can write:

(* toto.ml *)
try
   while true do
     match read_line () with
 	/ upper / | / _* "." eos / -> print_endline "looks like a sentence"
       | "." | / ("bye"~ space*)+ / -> print_endline "Bye!"; exit 0
       | _ -> print_endline "???"
   done
with End_of_file -> ()

Notes:
- the stuff between slashes are regexps
- "." and the last _ are regular OCaml patterns
- regexps are replaced by an identifier which is matched after the 
arrow using library functions, then it is decided whether to jump to the 
next case or to execute the user-given expression.

Here is a session using the silly program above:

$ micmatch toto.ml
Hello
looks like a sentence
ho ho ho.
looks like a sentence
!@#$%^&
???
goodbye
???
bye bye
Bye!
$


> Typing and warnings are yet another issue!

Warnings regarding incomplete match cases can be suppressed by adding 
'when true' guards and superfluous catch-all cases.

Tail-call optimizations are preserved by this transformation:
(* f may raise an exception Exn, but not g which is tail-recursive.
    So we don't write this: *)
let rec g arg =
   ...
   try f x; g y
   with Exn -> h z

(* but that: *)
let rec g arg =
   ...
   (try
      f x;
      fun () -> g y
    with
      Exn -> fun () -> h z) ()


You can run "camlp4o pr_o.cmo -I `ocamlfind query micmatch_pcre` pa_micmatch_pcre.cma toto.ml"
to see the final ocaml code.

So it is definitely possible to create a generic camlp4 library which 
allows the insertion of custom tests/bindings into ocaml patterns. In 
addition to string/regexp matching, the library could be used for the 
following extensions:
- 'when' tests appearing inside of the pattern
- evaluation and matching of lazy data
- regular expressions over anything (lists, arrays, trees, ...)
- views (as far as I understand the concept)
- matching objects using method calls as record fields
- other?

I have no plan of implementing this myself, but it might be a good 
project for a student...


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Store and share your bioinformatics tips at http://wikiomics.org

Re: [Caml-list] Request for complete pattern matching

[skaller]

On Wed, 2005-11-23 at 12:56 -0800, Martin Jambon wrote:

> (* toto.ml *)
> try
>    while true do
>      match read_line () with
>  	/ upper / | / _* "." eos / -> print_endline "looks like a sentence"
>        | "." | / ("bye"~ space*)+ / -> print_endline "Bye!"; exit 0
>        | _ -> print_endline "???"
>    done
> with End_of_file -> ()
> 
> Notes:
> - the stuff between slashes are regexps
> - "." and the last _ are regular OCaml patterns
> - regexps are replaced by an identifier which is matched after the 
> arrow using library functions, then it is decided whether to jump to the 
> next case or to execute the user-given expression.

Why can't this be done with 'when' clause?

EG:

	| ... predicate ... -> ...

replace by 

	| ... variable .. when predicate(variable)

This would seem to fail only in that 'predicate' code
cannot refer to another predicate, since the variable
name is not known.

The 'break' implementation, however, may be overtly
more efficient (save duplicating predicate evaluations).

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Request for complete pattern matching

[Martin Jambon]

On Thu, 24 Nov 2005, skaller wrote:

> On Wed, 2005-11-23 at 12:56 -0800, Martin Jambon wrote:
>
>> (* toto.ml *)
>> try
>>    while true do
>>      match read_line () with
>>  	/ upper / | / _* "." eos / -> print_endline "looks like a sentence"
>>        | "." | / ("bye"~ space*)+ / -> print_endline "Bye!"; exit 0
>>        | _ -> print_endline "???"
>>    done
>> with End_of_file -> ()
>>
>> Notes:
>> - the stuff between slashes are regexps
>> - "." and the last _ are regular OCaml patterns
>> - regexps are replaced by an identifier which is matched after the
>> arrow using library functions, then it is decided whether to jump to the
>> next case or to execute the user-given expression.
>
> Why can't this be done with 'when' clause?
>
> EG:
>
> 	| ... predicate ... -> ...
>
> replace by
>
> 	| ... variable .. when predicate(variable)

It was not shown in my example, but the predicate can introduce bindings:

     |  String (predicate which also defines x) | Int x -> ...
     | _ -> ...


You can do this:

# let f = function
      `Int n
    | `String / (int as n : int) eos / -> 2 * n
    | _ -> -1;;
val f : _[> `Int of int | `String of string ] -> int = <fun>
# f (`Int 123);;
- : int = 246
# f (`String "2005");;
- : int = 4010
# f (`String "x");;
- : int = -1


> This would seem to fail only in that 'predicate' code
> cannot refer to another predicate, since the variable
> name is not known.
>
> The 'break' implementation, however, may be overtly
> more efficient (save duplicating predicate evaluations).
>
> -- 
> John Skaller <skaller at users dot sf dot net>
> Felix, successor to C++: http://felix.sf.net
>
>

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Store and share your bioinformatics tips at http://wikiomics.org

Re: [Caml-list] Request for complete pattern matching

[Luc Maranget]

> >Typing and warnings are yet another issue!
> 
> Warnings regarding incomplete match cases can be suppressed by adding 
> 'when true' guards and superfluous catch-all cases.

I mean that you will probably loose significant warnings,
with your idea you avoid spurious warnings.

-- 
Luc Maranget

Re: [Caml-list] Request for complete pattern matching

[Martin Jambon]

On Thu, 24 Nov 2005, Luc Maranget wrote:

>>> Typing and warnings are yet another issue!
>>
>> Warnings regarding incomplete match cases can be suppressed by adding
>> 'when true' guards and superfluous catch-all cases.
>
> I mean that you will probably loose significant warnings,
> with your idea you avoid spurious warnings.

Of course, but it's not worse than the equivalent if-then-else style that 
you would use otherwise, because in the general case there's no way of 
detecting missing or unused cases.

Pattern-matchings which don't use the syntax extension are conserved, so 
the warnings are still here like before in those cases.

See this session:

$ micmatch
         Objective Caml version 3.08.3

         Camlp4 Parsing version 3.08.3

# match Some "thing" with
       Some "abc" -> ()
     | None -> ();;
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Some ""
Exception: Match_failure ("", 1, 0).
# match Some "thing" with
      Some / "t"* (_* as s) / -> s
    | None -> "none";;
- : string = "hing"
# match Some "thing" with
      Some / "the" _* as s / -> s
    | None -> "none";;
Exception: Match_failure ("", 5, -56).




Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Store and share your bioinformatics tips at http://wikiomics.org

Re: [Caml-list] Request for complete pattern matching

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 2640 bytes --]


> 
> Well, I understand better and (as you may have guessed yourself!) I do
> not incline to adopt the idea.
> 
> However provided you have some 'break' construct to transfert control to
> next matching, you can perhaps compile your construct by syntactic 
> transformation.
> 
> 
> My idea is to transform your patterns into
> normal ones, replacing p <= e1 e2 ... en by fresh variables (say v)
> and then to match 'v e1 ... en' against p.
> 
> Here you have :
> 
> match e with
> | (v1, g) -> (match v1 0 with 0 -> g |_ -> break)
> | (f, v2) -> (match v2 0 with 0 -> f |_ -> break)
> | f, g -> fun x -> f x + g x
> 
> At a little additional cost in complexity,
> you can replace 'break' (which does not exists) by exceptions as follows
> 
> let x = e in
> try (match x with
>   | (v1, g) -> (match v1 0 with 0 -> g |_ -> raise Exit)
>   | _ -> raise Exit)
> with Exit ->
> try (match x with
>   | (f, v2) -> (match v2 0 with 0 -> f |_ -> raise Exit)
>   | _ -> raise Exit)
> with Exit ->
> (match x with  f, g -> fun x -> f x + g x)
> 
> 
> I am not familiar enough with Camlp4, but I have the feeling
> that some purely syntactic compilation of your construct is doable.
> Since, only from the presence of <=,
> can you introduce the extra matchings and try .. with Exit) 
> I am not saying it is easy, just that it looks feasible.
> 
> Typing and warnings are yet another issue!
> 

I agree that your translation works (I should try). I  am just wondering
about the cost (compared to a reasonable implementation inside the
compiler) ?

That would probably be not so dramatic ... except I should not transform
pattern matching that do not use the new extension ... the camlp4 code
will probably tripple what I have.

Moreover, I think I may use camlp4 for bindlib-3.0, because this really
is an extension of the language and not a library ... however I do not
think camlp4 extensions are a good thing in general, because it breaks
readability of code.

So for my extension of pattern matching with function application, I
think, I prefer to wait an adoption of a similar feature rather than
doing it myself. bindlib-3.0 will be ok without this extention of the
pattern matching.

One of the reason for my post, is that I think pattern matching should
be complete (one of the reason, is because then you can interpret the
semantics of the language by the interaction of a constructor and a
destructor ... this has something to do with a lot of reasearch work in
computational interpretation of classical logic ... and trying to move
the language in this direction looks fun ..., for instance have a look
at Herbelin's work)

> 
> -- Luc

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 894 bytes --]

Re: [Caml-list] Request for complete pattern matching

[Luc Maranget]

> 
> I agree that your translation works (I should try). I  am just wondering
> about the cost (compared to a reasonable implementation inside the
> compiler) ?
> 
More expansive as camlp4 than coded inside the compiler.
But well, is cost a real problem here ?



> That would probably be not so dramatic ... except I should not transform
> pattern matching that do not use the new extension ... the camlp4 code
> will probably tripple what I have.
Not necesssarily, I guess, there is no need to transform patterns
without <=. An easy way out would be to introduce a new kind of
match expressions (extend_match ...  with .. ) which would
be the only one to accept <= in patterns.

> 
> So for my extension of pattern matching with function application, I
> think, I prefer to wait an adoption of a similar feature rather than
> doing it myself. bindlib-3.0 will be ok without this extention of the
> pattern matching.
I may not have been as clear as I wish to: I will not implement this.
As you see, it is really complicated (think about or-patterns,
or nested <=, for instance).

However, something like 'break' could perhaps be introduced in
a forseable future.



-- Luc