Changes between Version 9 and Version 10 of ViewPatternsNew


Ignore:
Timestamp:
Jul 19, 2007 10:11:03 AM (8 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