Changes between Version 9 and Version 10 of ViewPatternsNew


Ignore:
Timestamp:
Jul 19, 2007 10:11:03 AM (7 years ago)
Author:
danl
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatternsNew

    v9 v10  
    3131In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against. 
    3232 
    33 To make programming with such interfaces more convenient, we add a new kind of pattern called a ''view pattern''.  View patterns permit calling the view function inside the pattern and matching against the result: 
     33View patterns permit calling the view function inside the pattern and matching against the result: 
    3434{{{ 
    3535   size (view -> Unit) = 1 
     
    3737}}} 
    3838 
    39 In general, a view pattern is written 
     39That is, we add a new form of pattern, written  
    4040{{{ 
    4141   expression -> pattern 
     
    4747'''Scoping''' for ''expr `->` ''pat: 
    4848 * The variables bound by the view pattern are the variables bound by ''pat''. 
    49  * Any variables in ''expr'' are bound occurrences. 
     49 * Any variables in ''expr'' are bound occurrences.  Variables bound by patterns to the left of a view pattern expression are in scope.  For example: 
    5050   * In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments. 
    5151{{{ 
     
    5353   example f (f -> 4) = True 
    5454}}} 
    55    * However, pattern variables do not scope over the pattern in which they are bound. 
    56 {{{ 
    57    -- doesn't work 
    58    example :: (String -> Integer, String) -> Bool 
    59    example (f, f -> 4) = True 
     55   * Variables can be bound to the left in tuples and data constructors: 
     56{{{ 
     57   example :: ((String -> Integer,Integer), String) -> Bool 
     58   example ((f,_), f -> 4) = True 
    6059}}} 
    6160 
     
    8079                    | Cons a (JList a) 
    8180}}} 
    82 Here we've chosen that the view type only exposes the cons/nil structure one level at a time: the second argument to `Cons` is a join-list---but that's of course up to the programmer.   
     81Here we've chosen that the view type only exposes the cons/nil structure one level at a time: the second argument to `Cons` is a join-list, not a view of it---but that's of course up to the programmer.   
    8382 
    8483The implementation of the view: 
     
    117116==== Partial views ==== 
    118117 
    119 Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections inverting each constructor: 
     118Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections optionally inverting each constructor: 
    120119 
    121120{{{ 
     
    172171{{{ 
    173172  parsePacket :: ByteString -> ... 
    174   -- FIXME: requires scoping inside the same pattern. 
    175173  parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ... 
    176174}}} 
    177 This parses 3 bits to get the value of `n`, and then parses `n` bits to get the value of `val`. 
     175This parses 3 bits to get the value of `n`, and then parses `n` bits to get the value of `val`.  Note that this example uses the left-to-right scoping in the inner tuple: the first component is jused in the view expression in the second. 
    178176 
    179177==== N+k patterns ==== 
     
    222220}}} 
    223221 
    224 -- FIXME: loss of sharing? 
     222(However, this might cause a loss of sharing.) 
    225223 
    226224==== Iterator Style ==== 
     
    238236 
    239237   unfoldr :: (b -> Maybe (a, b)) -> b -> [a]  
    240    unfoldr f (f -> Just (a, b)) = a : unfoldr f b 
     238   unfoldr f (f -> Just (a, unfoldr f -> b)) = a : b 
    241239   unfoldr f other         = [] 
    242240}}} 
     
    244242== Further Syntactic Extensions == 
    245243 
    246 Next, we describe two syntactic extensions that we may implement.   
     244Next, we describe two further syntactic extensions that we will implement.   
    247245 
    248246=== Implicit Maybe === 
     
    272270==== Implicit Tupling ==== 
    273271 
    274 A further syntactic extension would be to have implcit Maybes with implicit tupling, so that multiple patterns after the `=>` are implicitly tupled.  Then you could write: 
     272A further syntactic extension would be to have implcit Maybes with implicit tupling: multiple patterns after the `=>` are implicitly tupled.  Then you could write: 
    275273{{{ 
    276274   size (outArrow => t1 t2) = size t1 + size t2 
     
    279277=== Implicit View Functions === 
    280278 
    281 Total views have one syntactic disadvantage relative to the iterated case that we started with: you have to repeat the name of the view function in each clause!  We now describe a method for eliding the name of the view function.   
     279Total views have one syntactic disadvantage relative to the iterated-case style definition that we started with: you have to repeat the name of the view function in each clause!  We now describe a method for eliding the name of the view function.   
    282280 
    283281The idea is that we distinguish a particular type class as a hook into the pattern compiler.  The class has the following interface: 
     
    287285}}} 
    288286 
    289 Then, you can leave off the expresion in a view pattern, writing `->` ''pat'', to mean `view -> ` ''pat''.  For example: 
     287Then, you can leave off the expresion in a view pattern, writing (`->` ''pat''), to mean `view -> ` ''pat''.  For example: 
    290288{{{ 
    291289   size (-> Unit) = 1 
     
    310308 
    311309This way, you don't have to write the name of the view function in each case.  However, there is a still a syntactic marker saying that the case isn't an ordinary pattern match, which may be useful in understanding the performance of the code.   
     310 
     311Of course, you can only use one view function for each hidden-type/view-type pair this way, since you can only have one instance of the class. 
    312312 
    313313==== Functional dependencies ==== 
     
    332332 
    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. 
     334The downside of these versions is that you can only have one view for a type (when `a` determines `View a`) or you can only use a type as a view of one type (when `b` determines `Hidden b`) with the implicit syntax. 
    334335 
    335336== Compilation == 
    336337 
    337338View patterns can do arbitrary computation, perhaps expensive. 
    338  
    339339It's reasonable to expect the compiler to avoid repeated computation when pattern line up in a column, as in `size` at the top of the page.  In pattern-guard form, common sub-expression should achieve the same effect, but it's quite a bit less obvious.  We should be able to give clear rules for when the avoidance of repeat computation is guaranteed. 
    340340 
     
    345345=== Value input feature === 
    346346 
    347 Our proposal has the ''value input'' feature: the view function can be passed parameters; in a function definition, those parameters can mention previous arguments.  For example, this permits a view function itself to be passed as an argument, so patterns, in a sense, become first class. 
     347Our proposal has the ''value input'' feature: the view function can be passed parameters; and those those parameters can mention variables bound by patterns to the left.  For example, this permits a view function itself to be passed as an argument, so patterns, in a sense, become first class. 
    348348 
    349349=== Implicit `Maybe` feature === 
     
    355355Our proposal does not have the ''transparent ordinary patterns'' feature: view patterns are written differently than ordinary patterns. 
    356356There are pros and cons both ways: 
    357 The advantage of having transparent ordinary patterns is that you can replace a concrete datatype with an abstract type and a view without changing client code.  A disadvantage is that view patterns can do arbitrary computation, perhaps expensive, so it's good to have a syntactic marker that some computation beyond ordinary pattern matching may be going on.  Another disadvantage is that transparent ordinary patterns require a larger language extension than just a new form of pattern, so that certain names may be declared to be view constructors for a type.  We consider our proposal's implicit view syntax `(-> e)` to be a nice compromise between the two alternatives.   
     357The advantage of having transparent ordinary patterns is that you can replace a concrete datatype with an abstract type and a view without changing client code.  A disadvantage is that view patterns can do arbitrary computation, perhaps expensive, so it's good to have a syntactic marker that some computation beyond ordinary pattern matching may be going on.  Another disadvantage is that transparent ordinary patterns require a larger language extension than just a new form of pattern, so that certain names may be declared to be view constructors for a type.  We consider our proposal's implicit-view-function syntax `(->` ''pat''`)` to be a nice compromise between the two alternatives.   
    358358 
    359359=== Nesting === 
    360360 
    361 Our proposal has the ''nesting'' feature: view patterns nest inside other patterns, and other patterns nest inside them. Nexting is perhaps the biggest practical difference between view patterns and pattern guards. 
     361Our proposal has the ''nesting'' feature: view patterns nest inside other patterns, and other patterns nest inside them. Nesting is perhaps the biggest practical difference between view patterns and pattern guards. 
    362362 
    363363=== Integration with type classes === 
     
    366366 
    367367== Related work == 
    368  
    369 === Uses of Views ===  
    370  
    371 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. 
    372  
    373 The abstractional power views offer can also be put to good use when designing data structures, as the following papers show 
    374  
    375   * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. 
    376   * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze:  A Simple Implementation Technique for Priority Search Queues] 
    377   * 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. 
    378368 
    379369=== [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] === 
     
    433423=== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] === 
    434424 
    435 Active Desctructors (ADs) are defined by a new form of top-level declaration.  Our 
    436 singleton example would look like this: 
     425Active Destructors (ADs) are defined by a new form of top-level declaration.   
     426 
     427Where we'd write 
     428{{{ 
     429   sing :: [a] -> a option 
     430   sing [x] = x  
     431}}} 
     432The equivalent active destructor would be 
    437433{{{ 
    438434  Sing x match [x] 
     
    443439a special form of type to describe them. 
    444440 
    445 The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the 
    446 new form of type. 
     441The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the new form of type. 
    447442 
    448443They also introduce a combining form for ADs, to make a kind of and-pattern.  For 
     
    455450  f ((Head x)@(Tail ys)) = x:x:ys 
    456451}}} 
    457 Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)` 
    458 against the argument, binding `x` and `ys` respectively.  We can model that with view patterns: 
     452Here `(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: 
    459453{{{ 
    460454  headV (x:xs) = Just x 
     
    467461}}} 
    468462 
    469 An to duplicating the value is to compose the functions: 
     463An alternative to duplicating the value is to compose the functions: 
    470464{{{ 
    471465  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c) 
     
    475469  f (headV @ tailV -> (x,ys)) = x:x:ys 
    476470}}} 
    477 This is a little clumsier: the "`@`" combines functions, with a kind of positional 
    478 binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear 
    479 that `headV` binds `x` and `tailV` binds `y`. 
     471This 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`. 
    480472 
    481473=== [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] === 
     
    556548Reppy & Aiken, TR 92-1290, Cornell, June 1992. 
    557549 
    558 The one way in which pattern synonyms are better than view patterns is that 
    559 they define by-construction bi-directional maps.  Example 
     550The one way in which pattern synonyms are better than view patterns is thatn they define by-construction bi-directional maps.  Example 
    560551{{{ 
    561552  data Term = Var String | Term String [Term] 
     
    580571  f (isPlus -> a b) = plus (f a) (f b) 
    581572}}} 
    582 But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration; 
    583 and are much more limited than view patterns (by design they cannot do computation). 
     573But 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). 
    584574 
    585575=== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] === 
     
    6005904) 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. 
    601591 
    602 The examples at the top of this page would look like this with first class patterns: 
     592The singleton example above would like this: 
    603593{{{ 
    604594  f = {%sing n} .-> n+1 
     
    639629A 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. 
    640630 
     631=== Uses of Views ===  
     632 
     633The 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. 
     634 
     635The abstractional power views offer can also be put to good use when designing data structures, as the following papers show 
     636 
     637  * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. 
     638  * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze:  A Simple Implementation Technique for Priority Search Queues] 
     639  * 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. 
     640