RE: [Caml-list] Views

["Manuel Fahndrich" <maf@microsoft.com>]

You might also want to look at a paper I wrote that is not referenced in
Okasaki's paper.

"Statically checkable pattern abstractions", ICFP'97.
http://research.microsoft.com/~maf/papers.htm#Misc 

In that paper we describe under what circumstances pattern matches with
pattern abstractions (views) can still be verified for exhaustiveness
and redundancy. This issue is not addressed in Okasaki's paper due to
the particular semantics he chooses, namely to construct explicit values
for the view and then match on those.

In our paper, we do not construct the view values, but simply generate
bindings for the free pattern variables. This raises a number of issues
w.r.t. the matching semantics, and redundancy and exhaustiveness
checking becomes non-trivial.
At the same time, the pattern matching becomes more expressive, and it
is possible to generate more efficient pattern matching code, without
the need to construct the view values.

The way in which pattern matching becomes more expressive is that one
can write a view pattern
	Contains(x) | Empty
for a list data type

One can then write a pattern

	case e of
	  Contains(5) => (* do case where list contains a 5 *)
            | Contains(x) => (* contains something, but no 5 *)
            | Empty => (* list is empty *)

As the example shows, the view transformation depends on nested
patterns, e.g., the code that runs over the list is different if we
match Contains(5), than if we match Contains(x).
In the latter case, which element should we return, which gets us into
the different possible match semantics (first, any, all).


-Manuel
 


-----Original Message-----
From: Chris Hecker [mailto:checker@d6.com] 
Sent: Friday, July 20, 2001 12:08 PM
To: Krishnaswami, Neel; caml-list@inria.fr
Subject: [Caml-list] Views


> Personally, I like views; here are some references
>so you can judge for yourself:
>http://www.cs.columbia.edu/~cdo/papers.html#ml98views
>http://cm.bell-labs.com/cm/cs/who/wadler/papers/view/view.dvi
>http://www.cs.orst.edu/~erwig/papers/abstracts.html#IFL96

Those are excellent!  Exactly what I wanted and have wanted for a while
when I realized that pattern matching didn't work on abstract types.  Is
there any chance of getting something like this into ocaml?  What do the
INRIA folks think about the idea?

Chris


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr