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