Patterns that evaluate

Patterns that evaluate

[Jacques Carette]

I recently wrote some ocaml code which "worked", but not as I 
intended...  The test cases I tried worked, but I should have tested 
harder.  Apparently I was under the mistaken impression that OCaml's 
pattern-matching was more "first class"!  So I wrote (in part):

let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
                                                 | ({st = Some e}, _) -> e2

and I expected it to work.  Only a code review by a colleague 'found' 
this bug in my code.

Question: would it be a difficult extension?  This seemed so "natural", 
I just "used" the feature before it was quite there yet ;-).

Jacques

PS: I guess I had first-class patterns on the brain; Maple has them 
[under the misleadingly-named function "typematch"] (but that's 
cheating, I know) and W. Kahl's Pattern Matching Calculus allows it, and 
I wrote a joint paper with Wolfram describing a categorical semantics 
for the PMC.

Re: [Caml-list] Patterns that evaluate

[Jon Harrop]

On Tuesday 13 February 2007 22:04, Jacques Carette wrote:
> I recently wrote some ocaml code which "worked", but not as I
> intended...  The test cases I tried worked, but I should have tested
> harder.  Apparently I was under the mistaken impression that OCaml's
> pattern-matching was more "first class"!  So I wrote (in part):
>
> let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
>
>                                                  | ({st = Some e}, _) -> e2
>
> and I expected it to work.  Only a code review by a colleague 'found'
> this bug in my code.
>
> Question: would it be a difficult extension?  This seemed so "natural",
> I just "used" the feature before it was quite there yet ;-).

F# just introduced active patterns, which does what you want AFAIK. Of course, 
you must disambiguate that from the OCaml's current interpretation of the 
above (binding "e").

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Patterns that evaluate

[Jacques Carette]

Jon Harrop wrote:
> F# just introduced active patterns, which does what you want AFAIK. Of course, 
> you must disambiguate that from the OCaml's current interpretation of the 
> above (binding "e").
>   
Yes, of course - but I would be more than happy to do that.

Jacques

Re: [Caml-list] Patterns that evaluate

[Edgar Friendly]

Jon Harrop wrote:
> On Tuesday 13 February 2007 22:04, Jacques Carette wrote:
>> I recently wrote some ocaml code which "worked", but not as I
>> intended...  The test cases I tried worked, but I should have tested
>> harder.  Apparently I was under the mistaken impression that OCaml's
>> pattern-matching was more "first class"!  So I wrote (in part):
>>
>> let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
>>
>>                                                  | ({st = Some e}, _) -> e2
>>
>> and I expected it to work.  Only a code review by a colleague 'found'
>> this bug in my code.
>>
>> Question: would it be a difficult extension?  This seemed so "natural",
>> I just "used" the feature before it was quite there yet ;-).
> 
> F# just introduced active patterns, which does what you want AFAIK. Of course, 
> you must disambiguate that from the OCaml's current interpretation of the 
> above (binding "e").
> 
The two options I see are:
1) noting a re-binding, and automatically testing against the value of 
that previous binding
2) extra syntax (maybe || instead of | before active match constructs)

In the first case, there's backwards compatibility issues.  Wouldn't it 
be useful to have the compiler warn on such uses, to make people aware 
of rebindings performed in their code?

E.

Re: [Caml-list] Patterns that evaluate

[Gerd Stolpmann]

Am Mittwoch, den 14.02.2007, 12:20 -0600 schrieb Edgar Friendly:
> Jon Harrop wrote:
> > On Tuesday 13 February 2007 22:04, Jacques Carette wrote:
> >> I recently wrote some ocaml code which "worked", but not as I
> >> intended...  The test cases I tried worked, but I should have tested
> >> harder.  Apparently I was under the mistaken impression that OCaml's
> >> pattern-matching was more "first class"!  So I wrote (in part):
> >>
> >> let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
> >>
> >>                                                  | ({st = Some e}, _) -> e2
> >>
> >> and I expected it to work.  Only a code review by a colleague 'found'
> >> this bug in my code.
> >>
> >> Question: would it be a difficult extension?  This seemed so "natural",
> >> I just "used" the feature before it was quite there yet ;-).
> > 
> > F# just introduced active patterns, which does what you want AFAIK. Of course, 
> > you must disambiguate that from the OCaml's current interpretation of the 
> > above (binding "e").
> > 
> The two options I see are:
> 1) noting a re-binding, and automatically testing against the value of 
> that previous binding
> 2) extra syntax (maybe || instead of | before active match constructs)
> 
> In the first case, there's backwards compatibility issues.  Wouldn't it 
> be useful to have the compiler warn on such uses, to make people aware 
> of rebindings performed in their code?

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?

I guess this simple question is one of the reasons why such a feature is
not in the language up to now.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Patterns that evaluate

[Denis Bueno]

On 2/14/07, Gerd Stolpmann <info@gerd-stolpmann.de> 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?
>
> I guess this simple question is one of the reasons why such a feature is
> not in the language up to now.

I agree with Gerd: equality is a hard thing to get right.

For many months now I have been working on a compiler for a constraint
solving language, and I always need to spend a significant amount of
time, after the creation of each data structure, defining comparisons
on instances of those structures. Usually there is one that defines an
ordering for the purpose of using instances as keys in a Map; and
sometimes there are additional equivalence relations that compare
different aspects of structures.

The principle then, applied to this problem, is: immediately *someone*
is going to need a comparison function other than the ones above. And
if there is no support for such functions, many people will consider
the feature useless for all but the simplest of tasks. If there is
support, it will become a question of just how convenient that support
is.

These aren't necessarily un-answerable questions; but they are not easy.

-Denis

Re: [Caml-list] Patterns that evaluate

[Jacques Carette]

Gerd Stolpmann wrote:
> 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?
>   

I would definitely favour structural equality, since that meshes well 
with pattern-matching's semantics.  Anything else would seem hard to 
justify, but that's just my opinion.

Jacques

Re: [Caml-list] Patterns that evaluate

[Gerd Stolpmann]

Am Mittwoch, den 14.02.2007, 14:11 -0500 schrieb Jacques Carette:
> Gerd Stolpmann wrote:
> > 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?
> >   
> 
> I would definitely favour structural equality, since that meshes well 
> with pattern-matching's semantics.  Anything else would seem hard to 
> justify, but that's just my opinion.

It is easy to have another opinion (and that's the basic problem). There
is a good reason to prefer physical equality: pattern matching
decomposes physically anyway, so this equality looks more natural. On
the other hand, the existing string matching (match s with "literal")
compares string contents. 

It is already a mess.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Patterns that evaluate

[Nathaniel Gray]

On 2/13/07, Jacques Carette <carette@mcmaster.ca> wrote:
> I recently wrote some ocaml code which "worked", but not as I
> intended...  The test cases I tried worked, but I should have tested
> harder.  Apparently I was under the mistaken impression that OCaml's
> pattern-matching was more "first class"!  So I wrote (in part):
>
> let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
>                                                  | ({st = Some e}, _) -> e2
>
> and I expected it to work.  Only a code review by a colleague 'found'
> this bug in my code.

I guess I'm not seeing it.  How did you expect it to work?  Is this
what you mean:

... | ({st = Some v}, _) when v = e -> e2

Is there some functionality that you're looking for that when clauses
don't provide?

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

Re: [Caml-list] Patterns that evaluate

[Edgar Friendly]

Gerd Stolpmann wrote:
> Am Mittwoch, den 14.02.2007, 14:11 -0500 schrieb Jacques Carette:
>> Gerd Stolpmann wrote:
>>> 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?
>>>   
>> I would definitely favour structural equality, since that meshes well 
>> with pattern-matching's semantics.  Anything else would seem hard to 
>> justify, but that's just my opinion.
> 
> It is easy to have another opinion (and that's the basic problem). There
> is a good reason to prefer physical equality: pattern matching
> decomposes physically anyway, so this equality looks more natural. On
> the other hand, the existing string matching (match s with "literal")
> compares string contents. 
> 
> It is already a mess.
> 
> Gerd

If I have to, I think I can satisfy both structural and physical 
equality with different tokens:

If you want:
* structural equality, use |= to prefix the pattern case
* physical equality, use |== to prefix the pattern case
* something else, use | and when to specify whatever explicit guard you 
want.

Does this satisfy all parties?

E.

Re: [Caml-list] Patterns that evaluate

[Jon Harrop]

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

Re: [Caml-list] Patterns that evaluate

[Jacques Carette]

Nathaniel Gray wrote:
> On 2/13/07, Jacques Carette <carette@mcmaster.ca> wrote:
>> So I wrote (in part):
>>
>> let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
>>                                                  | ({st = Some e}, _) 
>> -> e2
>>
>> and I expected it to work.  Only a code review by a colleague 'found'
>> this bug in my code.
>
> I guess I'm not seeing it.  How did you expect it to work?  Is this
> what you mean:
>
> ... | ({st = Some v}, _) when v = e -> e2
Yes. that is what I meant.

> Is there some functionality that you're looking for that when clauses
> don't provide?
No, there is not.  I was just (mistakenly) assuming that the "more 
pleasant" syntax for this ``worked''.

Explanation: when I was a language designer, I learned a lot from user 
'mistakes' like this.  Such mistakes told me of the mismatch between 
user expectations and current reality.  So I try to take the time to 
document my own 'mistakes'. 
Philosophy: if I don't take the time to give feedback, why should I 
expect users of my own work to be any different?

Jacques

PS: there is no real functionality that I am looking for that Turing 
Machines don't provide (or C or Java or ...).  And yet I prefer 
languages like (Meta)OCaml and Haskell.  The "raw functionality" 
argument does not seem to be the optimal way to look at these issues, IMHO.

Re: [Caml-list] Patterns that evaluate

[Jacques Carette]

[Many excellent ideas on Active Patterns removed]

Jon Harrop wrote:
> 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)
>   
Following ideas of Barry Jay, this could be even more simply written as
let rec rewrite rule = function
  | u _ as f -> rule f
  | b(f, g) -> b(rewrite rule f, rewrite rule g)

where u and b are supposed to be bound (to respectively unary and binary 
constructors).

Yes, the 'type' of the function rewrite needs higher-order polymorphism 
(or polytypism or ...) to work.  See Tim Sheard's Omega for one rather 
nice way to do that.

Jacques

Re: [Caml-list] Patterns that evaluate

[Martin Jambon]

On Tue, 13 Feb 2007, Jon Harrop wrote:

> On Tuesday 13 February 2007 22:04, Jacques Carette wrote:
> > I recently wrote some ocaml code which "worked", but not as I
> > intended...  The test cases I tried worked, but I should have tested
> > harder.  Apparently I was under the mistaken impression that OCaml's
> > pattern-matching was more "first class"!  So I wrote (in part):
> >
> > let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
> >
> >                                                  | ({st = Some e}, _) -> e2
> >
> > and I expected it to work.  Only a code review by a colleague 'found'
> > this bug in my code.
> >
> > Question: would it be a difficult extension?  This seemed so "natural",
> > I just "used" the feature before it was quite there yet ;-).
>
> F# just introduced active patterns, which does what you want AFAIK. Of course,
> you must disambiguate that from the OCaml's current interpretation of the
> above (binding "e").

That's funny, I posted a syntax extension that does that one week ago,
but I didn't know it was already implemented in F#.
http://caml.inria.fr/pub/ml-archives/caml-list/2007/02/e397c716c448a0aeff92b7af709bb1b4.en.html
http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx

"Active patterns" seems to be another name for "simple views" or
vice-versa.

It converged to an extremely similar solution, so it must be a good one
:-)

It doesn't solve the original problem though, which IMHO is better solved
with a standard "when" guard as mentioned earlier.



Martin

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

Re: [Caml-list] Patterns that evaluate

[Jacques Garrigue]

From: Martin Jambon <martin.jambon@ens-lyon.org>
> On Tue, 13 Feb 2007, Jon Harrop wrote:
> > On Tuesday 13 February 2007 22:04, Jacques Carette wrote:
> > > I recently wrote some ocaml code which "worked", but not as I
> > > intended...  The test cases I tried worked, but I should have tested
> > > harder.  Apparently I was under the mistaken impression that OCaml's
> > > pattern-matching was more "first class"!  So I wrote (in part):
> > >
> > > let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
> > >
> > >                                           | ({st = Some e}, _) -> e2
> > >
> > > and I expected it to work.  Only a code review by a colleague 'found'
> > > this bug in my code.
> > >
> > > Question: would it be a difficult extension?  This seemed so "natural",
> > > I just "used" the feature before it was quite there yet ;-).
> >
> > F# just introduced active patterns, which does what you want AFAIK. Of course,
> > you must disambiguate that from the OCaml's current interpretation of the
> > above (binding "e").
> 
> That's funny, I posted a syntax extension that does that one week ago,
> but I didn't know it was already implemented in F#.
> http://caml.inria.fr/pub/ml-archives/caml-list/2007/02/e397c716c448a0aeff92b7af709bb1b4.en.html
> http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx
> 
> "Active patterns" seems to be another name for "simple views" or
> vice-versa.
> 
> It converged to an extremely similar solution, so it must be a good one
> :-)
> 
> It doesn't solve the original problem though, which IMHO is better solved
> with a standard "when" guard as mentioned earlier.

Martin, I think you have a lot of good points here.
"when" clauses were exactly introduced in order to solve this kind of
problems.
However, I agree with the other Jacques that reusing an existing
variable in a pattern-matching is a common error, so it might be a
good idea to have a warning for that. Unused variable warnings were
introduced relatively recently, and there is still work to do on
misuse of variables. Note that reusing variable names is a common
idiom, so we don't want to disallow it completely, but "masking a
local variable in a pattern matching with several branches", as done
above, looks like something very suspicious.

The other question is on views. They could maybe help in this case,
using a parameterized view that checks equality with it parameter, but
this seems far-fetched. However, they have plenty of other
applications where they would be very useful.

As with any extension, an important question with views is whether
they should be in the language, as in F#, or supported by the
preprocessor as you did. After all, pattern-matching in Scheme is
entirely based on macros, and people are perfectly happy with
that. Why is it not the case in ML? Because, thanks to typing, we can
check exhaustivity and overlapping, and use this information to detect
error and optimize compilation. Unfortunately, views do not allow
that, so there seems to be less incentive to make them a core
feature. There was a lot written about the need for views to be proved
bijective before they can be mixed freely with pattern-matching, but
such proof doesn't seem practical for now.
This may explain why, while they look like a natural extension of
pattern-matching, they are not a standard feature.

Jacques Garrigue

Re: [Caml-list] Patterns that evaluate

[skaller]

On Wed, 2007-02-14 at 16:10 -0500, Jacques Carette wrote:
> Nathaniel Gray wrote:

> > I guess I'm not seeing it.  How did you expect it to work?  Is this
> > what you mean:
> >
> > ... | ({st = Some v}, _) when v = e -> e2
> Yes. that is what I meant.
> 
> > Is there some functionality that you're looking for that when clauses
> > don't provide?
> No, there is not.  I was just (mistakenly) assuming that the "more 
> pleasant" syntax for this ``worked''.

It is a common wish, but has many problems IMHO.

First, it isn't very general. When clause has form:

	  | ... x ... when P(x) ->

which can express a lot more than merely one of the three
equality operators. Indeed, P doesn't even have to be a
known function -- it can be a function value.

Second, the translation:

	| .. e .. ->   to | .. x .. when x = e -> 

without extra lexical marks distinguishing
pattern variables from local variables, and more generally
patterns from expressions, would be extremely fragile:

	let h = 1 in 
	match x with
	| h :: t -> ...

The meaning of this matching appears to be to match
a list starting with 1, binding t to the tail .. but
it all depends on whether t is a symbol in the context
of this fragment. The meaning would change if t were
not in the context and a programmer introduced it:

(* no t here *)
....
let ...

     | h :: t ->

Now the programmer adds a new global variable

let t = [2]

...


and it changes the meaning of the implementation of
a function which one would expect was abstracted and localised.

Thirdly it leaves open the issue of non-linear patterns:

	| x , x -> ...

The first x binds to the first component of a tuple ..
what does the second x do?? Easily solved with a when
clause:

	| x, y when x = y -> ...

Fourth, when clauses have a restriction that they do not
allow introduction of extra bindings. I often need that:

	| C  x | D with x = 1 -> ... x ....

where I'm introducing a default for one branch. 
I also often match nasty patterns in many places and really
wish I could name them:

	pattern p(x) = C x
	match e with | p(x) -> ...

doesn't provide active patterns, but it would be quite useful.
This can be done with a match composition already too:

	let p e = 
		try match e with C x -> x 
		with _ -> raise MatchFailure
	..
	try let x = p e in ..with MatchFailure -> (* next case *)

but it is messy (hard to compose).

Jacques said:

> Is there some functionality that you're looking for that when clauses
> > don't provide?
> No, there is not.

and that's basically wrong. He's not telling the truth here :-> 
He IS looking for something more general, specifically

	| f a -> ..

where f is pattern match variable. Ocaml currently requires f to be
a constructor, that is, a constant. Any notion of advanced
pattern matching would have to allow match variables to bind
to constructors. 

IF we're going to extend pattern matching it should do this:

http://www-staff.it.uts.edu.au/~cbj/Publications/pattern_calculus.ps

IMHO of course.. :)

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

Re: [Caml-list] Patterns that evaluate

[Jon Harrop]

On Thursday 15 February 2007 00:26, Jacques Garrigue wrote:
> As with any extension, an important question with views is whether
> they should be in the language, as in F#, or supported by the
> preprocessor as you did. After all, pattern-matching in Scheme is
> entirely based on macros, and people are perfectly happy with
> that. Why is it not the case in ML? Because, thanks to typing, we can
> check exhaustivity and overlapping, and use this information to detect
> error and optimize compilation. Unfortunately, views do not allow
> that...

Actually, I believe F# implements that in some form.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Patterns that evaluate

[Jacques Carette]

skaller wrote:
> It is a common wish, but has many problems IMHO.
> First, it isn't very general. 
Fallacious argument: OCaml has records, so there is no need for tuples 
which are less general.  Yet it has them. 
The point is to balance generality with convenience.  That is why 
redundancy in a language may be a pain for the compiler writers, but can 
make a big difference to the users.

Note that I was not suggesting, ever, that OCaml's current 
pattern-matching be 'broken' by blindly adding 'active' views.  A 
different syntax would seem to make sense. 

> [...] and more generally
> patterns from expressions, would be extremely fragile:
>
> 	let h = 1 in 
> 	match x with
> 	| h :: t -> ...
>
> The meaning of this matching appears to be to match
> a list starting with 1, binding t to the tail .. but
> it all depends on whether t is a symbol in the context
> of this fragment. The meaning would change if t were
> not in the context and a programmer introduced it:
>   
Sure.  But that is the normal semantics of the rest of OCaml you're 
complaining about here!  Yes, having a pattern-matching mechanism which 
is context dependent (like the rest of OCaml) instead of always working 
in an empty environment is different, that is expected.

Personally, I find that I don't write programs with a lot of variable 
shadowing, I tend to use new names in matches.  And no globals.  I 
consider them both to be bad style ;-)


> Thirdly it leaves open the issue of non-linear patterns:
> 	| x , x -> ...
>   
If x had a value, this would not be a problem at all.  It is only a 
problem in the 'binding' case.

> I also often match nasty patterns in many places and really
> wish I could name them:
>
> 	pattern p(x) = C x
> 	match e with | p(x) -> ...
>
> doesn't provide active patterns, but it would be quite useful.
>   
Agreed, that would be nice.

Regarding Jay-style matching: I was _expecting_ some kind of active 
patterns to work, I _want_ Jay style patterns.  Very different!

Jacques

Re: [Caml-list] Patterns that evaluate

[skaller]

On Thu, 2007-02-15 at 08:41 -0500, Jacques Carette wrote:
> skaller wrote:
> > It is a common wish, but has many problems IMHO.
> > First, it isn't very general. 
> Fallacious argument: OCaml has records, so there is no need for tuples 
> which are less general.  Yet it has them. 

It isn't an argument, it's a bullet point.

> The point is to balance generality with convenience.  

Yes, I agree.

> > patterns from expressions, would be extremely fragile:

> Sure.  But that is the normal semantics of the rest of OCaml you're 
> complaining about here! 

That's only partly true. In much of ocaml, you can use local
construction such as 

	let x = expr in expr

which names the variable 'x' to be used in 'expr'. There are
issues of hijacking of course. However with the pattern thing,
the issue is not *which* definition of x you're referring to,
but whether you're referring to one at all -- or actually
introducing one.

Current patterns have two name classes: pattern match variables
(lower case first letter) and constructors (upper case first
letter or backtick for polymorphic variants, or perhaps
a #term for them).

Adding a third category suggests a new lexical mark, to keep
the 'kind' of the symbol lexically determinate.

[Yes, I know Ocaml implicitly introduces variables not
only in patterns .. but also type variables]

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

Re: [Caml-list] Patterns that evaluate

[Nathaniel Gray]

On 2/14/07, Jacques Carette <carette@mcmaster.ca> wrote:
> Nathaniel Gray wrote:
> > On 2/13/07, Jacques Carette <carette@mcmaster.ca> wrote:
> >> So I wrote (in part):
> >>
> >> let buildsimp cast e f1 f2 = fun e1 -> fun e2 -> match (e1,e2) with
> >>                                                  | ({st = Some e}, _)
> >> -> e2
> >>
> >> and I expected it to work.  Only a code review by a colleague 'found'
> >> this bug in my code.
> >
> > I guess I'm not seeing it.  How did you expect it to work?  Is this
> > what you mean:
> >
> > ... | ({st = Some v}, _) when v = e -> e2
> Yes. that is what I meant.
>
> > Is there some functionality that you're looking for that when clauses
> > don't provide?
> No, there is not.  I was just (mistakenly) assuming that the "more
> pleasant" syntax for this ``worked''.
>
> Explanation: when I was a language designer, I learned a lot from user
> 'mistakes' like this.  Such mistakes told me of the mismatch between
> user expectations and current reality.  So I try to take the time to
> document my own 'mistakes'.
> Philosophy: if I don't take the time to give feedback, why should I
> expect users of my own work to be any different?

That's fine.  I just wasn't sure what you expected to happen.  I made
the same mistake myself when I was learning OCaml, but I don't think
it's something that should be changed.  It's good to minimize new user
mistakes, but you need to make a distinction between mistakes that new
users make once and never make again versus those that cause ongoing
grief.  I think this is definitely the former.  It only takes one
"bite" to make you understand that pattern matches don't compute.

One potential "solution" to this problem for new users would be a
compiler warning when you shadow an existing variable in an explicit
pattern match.

> PS: there is no real functionality that I am looking for that Turing
> Machines don't provide (or C or Java or ...).  And yet I prefer
> languages like (Meta)OCaml and Haskell.  The "raw functionality"
> argument does not seem to be the optimal way to look at these issues, IMHO.

Maybe, but the "it's all equivalent to Turing machines" argument is
pointless outside of formal proofs.  Proposing some syntactic sugar
for 'when' clauses is a very different thing from, say, proposing type
classes and operator overloading, even though neither one has any
impact on what the language can compute.

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

RE: [Caml-list] Patterns that evaluate

[Don Syme]

> > Because, thanks to typing, we can
> > check exhaustivity and overlapping, and use this information to detect
> > error and optimize compilation. Unfortunately, views do not allow
> > that...
>
> Actually, I believe F# implements that in some form.

Jon's jumping the gun a little: we have indeed recently redesigned active patterns for F# and I'll be writing up the details in the next few days, in a blog entry I guess. The implementation will also be in the next F# release.

There are still plenty of issues with using active patterns, especially in languages with side effects - how many times do you run those discrimination functions? Possible approaches to this issue were addressed by Chris Okasaki's paper on views for Standard ML, and the current specification we're using for F# is that "if we need to run an active discrimination function on a given input once, we can run it on the same input as many times as we wish within the given pattern match".  That is somewhat unsatisfactory semantically if the functions have visible side effects, but we want to strongly discourage such discriminator functions, in much the same way that side effects are strongly discouraged by the functions that implement the C# and F# property notations.  So I believe will be OK in practice, though I can see why people might find it distasteful (though if you don't choose this semantics then exponential code blow up looks hard to avoid, including in realistic code).

In any case our main aim has really been to explore the design space and find out how useful these things actually are in practice, and see if there's a reasonable version of this stuff that might make it into C# or a similar language.

BTW this work was done by Gregory Neverov over last summer during his internship at MSR. This led to me discussing the issue with a bunch of functional languages folk, including Martin Odersky, who was looking at the issue in Scala, along with Burak Emir.  Then I showed Greg's prototype to Simon Peyton Jones, which led to him making a proposal for views for Haskell, which led to Martin Jambon looking at the issue from the OCaml perspective (and going beyond what we had in the F# prototype in some interesting ways).

Cheers
don




-----Original Message-----
From: caml-list-bounces@yquem.inria.fr [mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of Jon Harrop
Sent: 15 February 2007 03:58
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Patterns that evaluate

On Thursday 15 February 2007 00:26, Jacques Garrigue wrote:
> As with any extension, an important question with views is whether
> they should be in the language, as in F#, or supported by the
> preprocessor as you did. After all, pattern-matching in Scheme is
> entirely based on macros, and people are perfectly happy with
> that. Why is it not the case in ML? Because, thanks to typing, we can
> check exhaustivity and overlapping, and use this information to detect
> error and optimize compilation. Unfortunately, views do not allow
> that...

Actually, I believe F# implements that in some form.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Patterns that evaluate

[Oliver Bandel]

On Thu, Feb 15, 2007 at 12:43:22PM -0800, Nathaniel Gray wrote:
[...]
> One potential "solution" to this problem for new users would be a
> compiler warning when you shadow an existing variable in an explicit
> pattern match.
[...]

Shadowing an existing "variable": isn't this the normal way how FPLs
"do it"?

It's: the inner (local) environment overwrites the outer environments
and that's, how FPLs are doing it. A new binding to a name.

Should all re-bindings be worth a warning?
if not: which should create a warning, which not?

Is this necessary in pattern matches only?

Ciao,
   Oliver