Changes between Version 6 and Version 7 of ViewPatternsNew

Timestamp:

07/18/07 09:56:36 (6 years ago)

Author:

danl

Comment:

--

ViewPatternsNew

@@ -333 +333 @@
 Of course, a programmer can always use all three type classes explicitly; it's just a question of which one should be the default.  We plan to try them out before deciding.
 
+== Compilation ==
+
 == Features views can have ==
 
@@ -358 +360 @@
 
 Our proposal ''integrates with type classes'': a single "view" can decompose multiple different data types.  
+
+== Related work ==
+
+=== Uses of Views === 
+
+The observations from [http://citeseer.ist.psu.edu/356396.html Okasaki: Breadth-First Numbering - Lessons ... ] suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of.
+
+The abstractional power views offer can also be put to good use when designing data structures, as the following papers show
+
+  * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees].
+  * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze:  A Simple Implementation Technique for Priority Search Queues]
+  * The the key idea of [http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz M.Erwig: Inductive Graphs and Functional Graph Algorithms] is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch.
+
+=== [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] ===
+
+Wadler's paper was the first concrete proposal.  It proposed a top-level view
+declaration, together with functions ''in both directions'' between the view type
+and the original type, which are required to be mutually inverse.  
+This allows view constructors to be used in expressions
+as well as patterns, which seems cool. Unfortunately this dual role proved
+problematic for equational reasoning, and every subsequent proposal restricted
+view constructors to appear in patterns only.
+
+=== [http://haskell.org/development/views.html Burton et al views (1996)] ===
+
+This proposal is substantially more complicated than the one above; in particular it
+requires new form of top-level declaration for a view type. For example:
+{{{
+  view Backwards a of [a] = [a] `Snoc` a | Nil
+     where
+     backwards [] = Nil
+     backwards (x:[]) = [] `Snoc` x
+     backwards (x1:(xs `Snoc` xn)) = (x1:xs) `Snoc` xn
+}}}
+Furthermore, it is in some ways less expressive than the proposal here;
+the (n+k) pattern, Erlang `bits` pattern, and `regexp` examples are not
+definable, because all rely on the value input feature.
+
+I think this proposal is substantially the same as "Pattern matching and
+abstract data types", Burton and Cameron, JFP 3(2), Apr 1993.
+
+=== [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] ===
+
+Okasaki's design is very similar to Burton et al's, apart from differences due
+to the different host language.  Again, the value input feature is not supported.
+
+=== [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] ===
+
+Erwig's proposal for active patterns renders the Set example like this:
+{{{
+data Set a = Empty | Add a (Set a)
+
+pat Add' x _ =
+  Add y s => if x==y then Add y s
+             else let Add' x t = s
+                  in Add x (Add y t)
+
+delete x (Add' x s) = s
+delete x s          = s
+}}}
+This requires a new top-leven declaration form `pat`; and I don't think it's nearly 
+as easy to understand as the current proposal.  Notably, in the first equation for
+`delete` it's ahrd to see that the second `x` is a bound occurrence; this somehow
+follows from the `pat` declaration.
+
+Still the proposal does support the value input feature.
+
+=== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] ===
+
+Active Desctructors (ADs) are defined by a new form of top-level declaration.  Our
+singleton example would look like this:
+{{{
+  Sing x match [x]
+}}}
+Here '''match''' is the keyword, and `Sing` is the AD.  ADs are quite like view patterns:
+the can do computation, and can fail to match.  But they are definitely not normal 
+Haskell functions, and need their own form of top-level declaration.  They even have
+a special form of type to describe them.
+
+The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the
+new form of type.
+
+They also introduce a combining form for ADs, to make a kind of and-pattern.  For
+example, suppose we had
+{{{
+  Head x match (x:_)
+  Tail x match (_:xs)
+
+  f :: [a] -> [a]
+  f ((Head x)@(Tail ys)) = x:x:ys
+}}}
+Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)`
+against the argument, binding `x` and `ys` respectively.  We can model that with view patterns:
+{{{
+  headV (x:xs) = Just x
+  headV []     = Nothing
+
+  tailV (x:xs) = Just xs
+  tailV []     = Nothing
+
+  f (both -> (headV => x, tailV => ys)) = x:x:ys
+}}}
+
+An to duplicating the value is to compose the functions:
+{{{
+  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c)
+  (f @ g) x = do { b <- f x; c <- g x; return (b,c) }
+
+  f :: [a] -> [a]
+  f (headV @ tailV -> (x,ys)) = x:x:ys
+}}}
+This is a little clumsier: the "`@`" combines functions, with a kind of positional
+binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear
+that `headV` binds `x` and `tailV` binds `y`.
+
+=== [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] ===
+
+This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although
+it is joint-authored, the transformational-pattern idea is Martin's.)  Transformational patterns
+are very close to what we propose here.  In particular, view functions are ordinary Haskell functions,
+so that the only changes are to patterns themselves.
+
+There are two main differences (apart from syntax). 
+First, transformational patterns didn't have the value input feature, althought it'd be easy 
+to add (indeed that's what we've done). Second, transformational patterns as described by
+Erwig do no stripping of the `Maybe` (see "Possible extension 2" above).
+
+=== [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] ===
+
+Simon started this design discussion after talking to Don Syme about F#'s '''active patterns''', which serve a very similar purpose. These combine both “total” discrimination (views) and “partial” discrimination (implicit maybe) into one mechanism. It does this by embedding the names of discriminators in the names of matching functions, via “values with structured names”.  Sample uses include matching on .NET objects and XML.
+
+Here is [http://blogs.msdn.com/dsyme/archive/2007/04/07/draft-paper-on-f-active-patterns.aspx a full paper describing the design], by Don Syme, Gregory Neverov, and James Margetson (April 2007).
+
+The feature is implemented in F# 1.9. Some code snippets are below.
+{{{
+    let (|Rect|) (x:complex) = (x.RealPart, x.ImaginaryPart)
+    let (|Polar|) (x:complex) = (x.Magnitude , x.Phase)
+
+    let mulViaRect c1 c2 = 
+        match c1,c2 with 
+        | Rect(ar,ai), Rect(br,bi) -> Complex.mkRect(ar*br - ai*bi, ai*br + bi*ar)
+
+    let mulViaPolar c1 c2 = 
+        match c1,c2 with 
+        | Polar (r1,th1),Polar (r2,th2) -> Complex.mkPolar(r1*r2, th1+th2)
+
+    let mulViaRect2  (Rect(ar,ai))   (Rect(br,bi))   = Complex.mkRect(ar*br - ai*bi, 
+                                                                      ai*br + bi*ar)
+    let mulViaPolar2 (Polar(r1,th1)) (Polar(r2,th2)) = Complex.mkPolar(r1*r2, th1+th2)
+}}}
+And for views:
+{{{
+    open System
+    
+    let (|Named|Array|Ptr|Param|) (typ : System.Type) =
+        if typ.IsGenericType        then Named(typ.GetGenericTypeDefinition(), 
+                                               typ.GetGenericArguments())
+        elif not typ.HasElementType then Named(typ, [| |])
+        elif typ.IsArray            then Array(typ.GetElementType(), 
+                                               typ.GetArrayRank())
+        elif typ.IsByRef            then Ptr(true,typ.GetElementType())
+        elif typ.IsPointer          then Ptr(false,typ.GetElementType())
+        elif typ.IsGenericParameter then Param(typ.GenericParameterPosition, 
+                                               typ.GetGenericParameterConstraints())
+        else failwith "MSDN says this can't happen"
+
+    let rec freeVarsAcc typ acc =
+        match typ with
+        | Named (con, args) -> Array.fold_right freeVarsAcc args acc
+        | Array (arg, rank) -> freeVarsAcc arg acc
+        | Ptr (_,arg)       -> freeVarsAcc arg acc
+        | Param(pos,cxs)    -> Array.fold_right freeVarsAcc cxs (typ :: acc) 
+}}}
+
+=== [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] ===
+
+Scala is an OO language with lots of functional features.  It has algebraic data types and
+pattern matching.  It also has a form of view called '''extractors''', which are
+pretty similar to view patterns, albeit in OO clothing.  Notably, by packaging a constructor
+and an extractor in a class, they can use the same class name in both expressions and terms, 
+implicitly meaning "use the constructor in expressions, and use the extractor in patterns".
+
+The paper does a comparative evaluation of various OO paradigms for matching, and 
+concludes that case expressions and extractors work pretty well.
+
+=== Pattern synonyms  ===
+
+[http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms] 
+are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see 
+[http://people.cs.uchicago.edu/~jhr/papers/1992/tr-sml-const.pdf Abstract value constructors], 
+Reppy & Aiken, TR 92-1290, Cornell, June 1992.
+
+The one way in which pattern synonyms are better than view patterns is that
+they define by-construction bi-directional maps.  Example
+{{{
+  data Term = Var String | Term String [Term]
+  
+  -- 'const' introduces a pattern synonym
+  const Plus a b = Term "+" [a,b]
+
+  f :: Term -> Term
+  f (Plus a b) = Plus (f a) (f b)
+  f ... = ...
+}}}
+With pattern views, we'd have to write two functions for the "plus" view:
+{{{
+  plus :: Term -> Term -> Term
+  plus a b = Term "+" [a,b]
+
+  isPlus :: Term -> Maybe2 Term Term
+  isPlus (Term "+" [a,b]) = Just2 a b
+  isPlus other            = Nothing
+
+  f :: Term -> Term
+  f (isPlus -> a b) = plus (f a) (f b)
+}}}
+But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration;
+and are much more limited than view patterns (by design they cannot do computation).
+
+=== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] ===
+
+First Class Patterns is an approach that attempts to
+add the minimum of syntax to the language which---in combination with
+pattern combinators written within the language---can achieve everything
+and more that Haskell patterns can do.  They have the value-input feature.
+
+The advantages are  1) They are simpler than Haskell's patterns;  2) Patterns are first class.
+3) The binding mechanism (the pattern binder) is orthogonal to the the pattern combinators:
+the hope is that one can stop changing the syntax/semantics of patterns and concentrate on writing the
+combinators (as Haskell functions).
+
+The disadvantages are as follows: 1) An extra syntactic construct that binds variables, the pattern binder, is required.
+2) Even with pattern binders, simple patterns look clunkier than Haskell's patterns.
+3) No attempt is made to check for exhaustiveness of patterns.
+4) No attempt is made to integrate with Haskell's patterns, the idea is a proposal for an alternative when one needs more than simple patterns.
+
+The examples at the top of this page would look like this with first class patterns:
+{{{
+  f = {%sing n} .-> n+1
+                |>> 0
+
+  g =  {%sing True}  .-> 0
+    .| {%sing False} .-> 1
+                     |>> 2  
+}}}
+=== First class abstractions ===
+
+Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.  By a "first class abstraction" I mean a value of type
+(''something'' `->` ''something'')
+with a syntax something like
+(`\` ''pattern'' `->` ''result'').
+The abstraction includes both the pattern and the result.  In contrast, view patterns tackle only the syntax of patterns; the pattern of a first-class abstraction.  
+
+Here are the ones I know of
+
+ * [http://hackage.haskell.org/trac/haskell-prime/ticket/114 Claus Reinke's lambda-match proposal]
+ * [http://ttic.uchicago.edu/~blume/pub-cat.html Matthias Blume: Extensible programming with first-class cases] (ICFP06)
+
+All these proposals are more or less orthogonal to this one. For example, Reinke
+proposes a compositional syntax for lambda abstractions 
+`(\p -> e)` where pattern matching failure on `p` can be caught and composed
+with a second abstraction. Thus
+{{{
+   (| Just x -> x+1 ) +++ (| Nothing -> 0 )
+}}}
+combines two abstractions, with failure from the first falling through to the seoond.  
+
+None of these proposals say
+anything about the patterns themselves, which in turn is all this
+proposal deals with.  Hence orthgonal.
+
+=== Barry Jay: First class patterns ===
+
+A yet more ambitious scheme is to treat patterns themselves as first class, even though they have free (binding) variables.  This is the approach that Barry Jay has taken in his very interesting project on the ''pattern calculus''.  His [http://www-staff.it.uts.edu.au/~cbj home page] has more info.
+