Changes between Version 6 and Version 7 of ViewPatternsNew


Ignore:
Timestamp:
Jul 18, 2007 4:56:36 PM (8 years ago)
Author:
danl
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatternsNew

    v6 v7  
    333333Of 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. 
    334334 
     335== Compilation == 
     336 
    335337== Features views can have == 
    336338 
     
    358360 
    359361Our proposal ''integrates with type classes'': a single "view" can decompose multiple different data types.   
     362 
     363== Related work == 
     364 
     365=== Uses of Views ===  
     366 
     367The 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. 
     368 
     369The abstractional power views offer can also be put to good use when designing data structures, as the following papers show 
     370 
     371  * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. 
     372  * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze:  A Simple Implementation Technique for Priority Search Queues] 
     373  * 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. 
     374 
     375=== [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] === 
     376 
     377Wadler's paper was the first concrete proposal.  It proposed a top-level view 
     378declaration, together with functions ''in both directions'' between the view type 
     379and the original type, which are required to be mutually inverse.   
     380This allows view constructors to be used in expressions 
     381as well as patterns, which seems cool. Unfortunately this dual role proved 
     382problematic for equational reasoning, and every subsequent proposal restricted 
     383view constructors to appear in patterns only. 
     384 
     385=== [http://haskell.org/development/views.html Burton et al views (1996)] === 
     386 
     387This proposal is substantially more complicated than the one above; in particular it 
     388requires new form of top-level declaration for a view type. For example: 
     389{{{ 
     390  view Backwards a of [a] = [a] `Snoc` a | Nil 
     391     where 
     392     backwards [] = Nil 
     393     backwards (x:[]) = [] `Snoc` x 
     394     backwards (x1:(xs `Snoc` xn)) = (x1:xs) `Snoc` xn 
     395}}} 
     396Furthermore, it is in some ways less expressive than the proposal here; 
     397the (n+k) pattern, Erlang `bits` pattern, and `regexp` examples are not 
     398definable, because all rely on the value input feature. 
     399 
     400I think this proposal is substantially the same as "Pattern matching and 
     401abstract data types", Burton and Cameron, JFP 3(2), Apr 1993. 
     402 
     403=== [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] === 
     404 
     405Okasaki's design is very similar to Burton et al's, apart from differences due 
     406to the different host language.  Again, the value input feature is not supported. 
     407 
     408=== [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] === 
     409 
     410Erwig's proposal for active patterns renders the Set example like this: 
     411{{{ 
     412data Set a = Empty | Add a (Set a) 
     413 
     414pat Add' x _ = 
     415  Add y s => if x==y then Add y s 
     416             else let Add' x t = s 
     417                  in Add x (Add y t) 
     418 
     419delete x (Add' x s) = s 
     420delete x s          = s 
     421}}} 
     422This requires a new top-leven declaration form `pat`; and I don't think it's nearly  
     423as easy to understand as the current proposal.  Notably, in the first equation for 
     424`delete` it's ahrd to see that the second `x` is a bound occurrence; this somehow 
     425follows from the `pat` declaration. 
     426 
     427Still the proposal does support the value input feature. 
     428 
     429=== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] === 
     430 
     431Active Desctructors (ADs) are defined by a new form of top-level declaration.  Our 
     432singleton example would look like this: 
     433{{{ 
     434  Sing x match [x] 
     435}}} 
     436Here '''match''' is the keyword, and `Sing` is the AD.  ADs are quite like view patterns: 
     437the can do computation, and can fail to match.  But they are definitely not normal  
     438Haskell functions, and need their own form of top-level declaration.  They even have 
     439a special form of type to describe them. 
     440 
     441The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the 
     442new form of type. 
     443 
     444They also introduce a combining form for ADs, to make a kind of and-pattern.  For 
     445example, suppose we had 
     446{{{ 
     447  Head x match (x:_) 
     448  Tail x match (_:xs) 
     449 
     450  f :: [a] -> [a] 
     451  f ((Head x)@(Tail ys)) = x:x:ys 
     452}}} 
     453Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)` 
     454against the argument, binding `x` and `ys` respectively.  We can model that with view patterns: 
     455{{{ 
     456  headV (x:xs) = Just x 
     457  headV []     = Nothing 
     458 
     459  tailV (x:xs) = Just xs 
     460  tailV []     = Nothing 
     461 
     462  f (both -> (headV => x, tailV => ys)) = x:x:ys 
     463}}} 
     464 
     465An to duplicating the value is to compose the functions: 
     466{{{ 
     467  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c) 
     468  (f @ g) x = do { b <- f x; c <- g x; return (b,c) } 
     469 
     470  f :: [a] -> [a] 
     471  f (headV @ tailV -> (x,ys)) = x:x:ys 
     472}}} 
     473This is a little clumsier: the "`@`" combines functions, with a kind of positional 
     474binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear 
     475that `headV` binds `x` and `tailV` binds `y`. 
     476 
     477=== [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] === 
     478 
     479This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although 
     480it is joint-authored, the transformational-pattern idea is Martin's.)  Transformational patterns 
     481are very close to what we propose here.  In particular, view functions are ordinary Haskell functions, 
     482so that the only changes are to patterns themselves. 
     483 
     484There are two main differences (apart from syntax).  
     485First, transformational patterns didn't have the value input feature, althought it'd be easy  
     486to add (indeed that's what we've done). Second, transformational patterns as described by 
     487Erwig do no stripping of the `Maybe` (see "Possible extension 2" above). 
     488 
     489=== [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] === 
     490 
     491Simon 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. 
     492 
     493Here 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). 
     494 
     495The feature is implemented in F# 1.9. Some code snippets are below. 
     496{{{ 
     497    let (|Rect|) (x:complex) = (x.RealPart, x.ImaginaryPart) 
     498    let (|Polar|) (x:complex) = (x.Magnitude , x.Phase) 
     499 
     500    let mulViaRect c1 c2 =  
     501        match c1,c2 with  
     502        | Rect(ar,ai), Rect(br,bi) -> Complex.mkRect(ar*br - ai*bi, ai*br + bi*ar) 
     503 
     504    let mulViaPolar c1 c2 =  
     505        match c1,c2 with  
     506        | Polar (r1,th1),Polar (r2,th2) -> Complex.mkPolar(r1*r2, th1+th2) 
     507 
     508    let mulViaRect2  (Rect(ar,ai))   (Rect(br,bi))   = Complex.mkRect(ar*br - ai*bi,  
     509                                                                      ai*br + bi*ar) 
     510    let mulViaPolar2 (Polar(r1,th1)) (Polar(r2,th2)) = Complex.mkPolar(r1*r2, th1+th2) 
     511}}} 
     512And for views: 
     513{{{ 
     514    open System 
     515     
     516    let (|Named|Array|Ptr|Param|) (typ : System.Type) = 
     517        if typ.IsGenericType        then Named(typ.GetGenericTypeDefinition(),  
     518                                               typ.GetGenericArguments()) 
     519        elif not typ.HasElementType then Named(typ, [| |]) 
     520        elif typ.IsArray            then Array(typ.GetElementType(),  
     521                                               typ.GetArrayRank()) 
     522        elif typ.IsByRef            then Ptr(true,typ.GetElementType()) 
     523        elif typ.IsPointer          then Ptr(false,typ.GetElementType()) 
     524        elif typ.IsGenericParameter then Param(typ.GenericParameterPosition,  
     525                                               typ.GetGenericParameterConstraints()) 
     526        else failwith "MSDN says this can't happen" 
     527 
     528    let rec freeVarsAcc typ acc = 
     529        match typ with 
     530        | Named (con, args) -> Array.fold_right freeVarsAcc args acc 
     531        | Array (arg, rank) -> freeVarsAcc arg acc 
     532        | Ptr (_,arg)       -> freeVarsAcc arg acc 
     533        | Param(pos,cxs)    -> Array.fold_right freeVarsAcc cxs (typ :: acc)  
     534}}} 
     535 
     536=== [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] === 
     537 
     538Scala is an OO language with lots of functional features.  It has algebraic data types and 
     539pattern matching.  It also has a form of view called '''extractors''', which are 
     540pretty similar to view patterns, albeit in OO clothing.  Notably, by packaging a constructor 
     541and an extractor in a class, they can use the same class name in both expressions and terms,  
     542implicitly meaning "use the constructor in expressions, and use the extractor in patterns". 
     543 
     544The paper does a comparative evaluation of various OO paradigms for matching, and  
     545concludes that case expressions and extractors work pretty well. 
     546 
     547=== Pattern synonyms  === 
     548 
     549[http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms]  
     550are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see  
     551[http://people.cs.uchicago.edu/~jhr/papers/1992/tr-sml-const.pdf Abstract value constructors],  
     552Reppy & Aiken, TR 92-1290, Cornell, June 1992. 
     553 
     554The one way in which pattern synonyms are better than view patterns is that 
     555they define by-construction bi-directional maps.  Example 
     556{{{ 
     557  data Term = Var String | Term String [Term] 
     558   
     559  -- 'const' introduces a pattern synonym 
     560  const Plus a b = Term "+" [a,b] 
     561 
     562  f :: Term -> Term 
     563  f (Plus a b) = Plus (f a) (f b) 
     564  f ... = ... 
     565}}} 
     566With pattern views, we'd have to write two functions for the "plus" view: 
     567{{{ 
     568  plus :: Term -> Term -> Term 
     569  plus a b = Term "+" [a,b] 
     570 
     571  isPlus :: Term -> Maybe2 Term Term 
     572  isPlus (Term "+" [a,b]) = Just2 a b 
     573  isPlus other            = Nothing 
     574 
     575  f :: Term -> Term 
     576  f (isPlus -> a b) = plus (f a) (f b) 
     577}}} 
     578But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration; 
     579and are much more limited than view patterns (by design they cannot do computation). 
     580 
     581=== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] === 
     582 
     583First Class Patterns is an approach that attempts to 
     584add the minimum of syntax to the language which---in combination with 
     585pattern combinators written within the language---can achieve everything 
     586and more that Haskell patterns can do.  They have the value-input feature. 
     587 
     588The advantages are  1) They are simpler than Haskell's patterns;  2) Patterns are first class. 
     5893) The binding mechanism (the pattern binder) is orthogonal to the the pattern combinators: 
     590the hope is that one can stop changing the syntax/semantics of patterns and concentrate on writing the 
     591combinators (as Haskell functions). 
     592 
     593The disadvantages are as follows: 1) An extra syntactic construct that binds variables, the pattern binder, is required. 
     5942) Even with pattern binders, simple patterns look clunkier than Haskell's patterns. 
     5953) No attempt is made to check for exhaustiveness of patterns. 
     5964) 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. 
     597 
     598The examples at the top of this page would look like this with first class patterns: 
     599{{{ 
     600  f = {%sing n} .-> n+1 
     601                |>> 0 
     602 
     603  g =  {%sing True}  .-> 0 
     604    .| {%sing False} .-> 1 
     605                     |>> 2   
     606}}} 
     607=== First class abstractions === 
     608 
     609Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.  By a "first class abstraction" I mean a value of type 
     610(''something'' `->` ''something'') 
     611with a syntax something like 
     612(`\` ''pattern'' `->` ''result''). 
     613The 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.   
     614 
     615Here are the ones I know of 
     616 
     617 * [http://hackage.haskell.org/trac/haskell-prime/ticket/114 Claus Reinke's lambda-match proposal] 
     618 * [http://ttic.uchicago.edu/~blume/pub-cat.html Matthias Blume: Extensible programming with first-class cases] (ICFP06) 
     619 
     620All these proposals are more or less orthogonal to this one. For example, Reinke 
     621proposes a compositional syntax for lambda abstractions  
     622`(\p -> e)` where pattern matching failure on `p` can be caught and composed 
     623with a second abstraction. Thus 
     624{{{ 
     625   (| Just x -> x+1 ) +++ (| Nothing -> 0 ) 
     626}}} 
     627combines two abstractions, with failure from the first falling through to the seoond.   
     628 
     629None of these proposals say 
     630anything about the patterns themselves, which in turn is all this 
     631proposal deals with.  Hence orthgonal. 
     632 
     633=== Barry Jay: First class patterns === 
     634 
     635A 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. 
     636