Changes between Initial Version and Version 1 of Ticket #114


Ignore:
Timestamp:
Nov 2, 2006 9:17:35 AM (9 years ago)
Author:
simonpj@…
Comment:

Improve formatting

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #114 – Description

    initial v1  
    11== name: == 
    2     '''introduce lambda-match (explicit match failure and fall-through)''' 
     2'''introduce lambda-match (explicit match failure and fall-through)''' 
    33 
    44== summary: == 
    5     Haskell 98 provides *two different translations* of lambda 
    6     abstractions involving pattern matching, only one of which is 
    7     directly accessible (Section 3.3 - the other is embedded in the 
    8     translation of do-notation, see "ok" in Section 3.14). 
     5Haskell 98 provides *two different translations* of lambda 
     6abstractions involving pattern matching, only one of which is 
     7directly accessible (Section 3.3 - the other is embedded in the 
     8translation of do-notation, see "ok" in Section 3.14). 
    99 
    10     providing explicit source notation for the second translation, 
    11     substantially simplifies programmability of pattern-match 
    12     fall-through by reification of pattern-match failure, two  
    13     central language features that are so far only available 
    14     through the built-in, non-composable case construct. 
     10Providing explicit source notation for the second translation, 
     11substantially simplifies programmability of pattern-match 
     12fall-through by reification of pattern-match failure, two  
     13central language features that are so far only available 
     14through the built-in, non-composable case construct. 
    1515 
    1616== what: == 
    17     in Section 3.3, the translation for conventional lambda 
    18     abstractions with patterns is given as 
     17In Section 3.3, the translation for conventional lambda 
     18abstractions with patterns is given as 
    1919{{{ 
    2020    [| \p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of  
    2121                                      (p1,..,pn) -> e 
    2222}}} 
    23     with xi fresh identifiers, and pattern-match failure resulting in 
    24     _|_. the latter is unfortunate, and results in partial functions the 
    25     coverage of which cannot be combined, but it is forced by  
    26     translation into conventional lambda calculus. 
     23with xi fresh identifiers, and pattern-match failure resulting in 
     24_|_. the latter is unfortunate, and results in partial functions the 
     25coverage of which cannot be combined, but it is forced by  
     26translation into conventional lambda calculus. 
    2727 
    28     since computational lambda calculus (\-M) has become a central part 
    29     of Haskell programming practice, there shall be an alternative form 
    30     of lambda abstraction, dubbed here '''lambda-match''', with associated 
    31     translation into \-M: 
     28since computational lambda calculus (\-M) has become a central part 
     29of Haskell programming practice, there shall be an alternative form 
     30of lambda abstraction, dubbed here '''lambda-match''', with associated 
     31translation into \-M: 
    3232{{{ 
    3333    [| |p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of  
     
    3535                                         _ -> fail "no match" } 
    3636}}} 
    37     ''[note1: this is the translation in principle - in practice, to enable composition of lambda-matches without further language extensions, a slight modification is needed, wrapping the right-hand sides of the case in a Match constructor, see library, examples, and patch]'' 
     37''[note1: this is the translation in principle - in practice, to enable composition of lambda-matches without further language extensions, a slight modification is needed, wrapping the right-hand sides of the case in a Match constructor, see library, examples, and patch]'' 
    3838 
    39     a library for composing these lambda-matches provides for 
    40     composition of alternative lambda-matches ( {{{(+++)}}} ), match failure 
    41     ({{{nomatch}}}, {{{matchError <message>}}}) and embedding of the explicit  
    42     match monad into pure expressions ({{{splice}}}, where  
    43     {{{ \p1..pn->e = splice |p1..pn->e }}}, also {{{spliceE}}} -preserving 
    44     error messages by using {{{(Either String)}}} as the match monad, and 
    45     {{{allMatches}}}, using the {{{[]}}} monad to deliver all successful matches). 
    46     other lambda-match related auxiliaries include {{{caseOf}}} as a  
    47     user-defined version of {{{case _ of _}}}, argument supply to matches 
    48     ( {{{(>|)}}} ), and joining of nested matches (so that, for instance 
     39a library for composing these lambda-matches provides for 
     40composition of alternative lambda-matches ( {{{(+++)}}} ), match failure 
     41({{{nomatch}}}, {{{matchError <message>}}}) and embedding of the explicit  
     42match monad into pure expressions ({{{splice}}}, where  
     43{{{ \p1..pn->e = splice |p1..pn->e }}}, also {{{spliceE}}} -preserving 
     44error messages by using {{{(Either String)}}} as the match monad, and 
     45{{{allMatches}}}, using the {{{[]}}} monad to deliver all successful matches). 
     46other lambda-match related auxiliaries include {{{caseOf}}} as a  
     47user-defined version of {{{case _ of _}}}, argument supply to matches 
     48( {{{(>|)}}} ), and joining of nested matches (so that, for instance 
    4949{{{ 
    5050    nest $ |<outer>-> |<inner>-> expr = |<outer> <inner>-> expr 
    5151}}}  
    52     ). 
     52). 
    5353 
    54     ''[note2: an alternative translation would use do-notation instead of case as the target: 
     54''[note2: an alternative translation would use do-notation instead of case as the target: 
    5555{{{ 
    5656     [| |p1 .. pn-> e |] = \x1 .. xn-> do {  
     
    5858                            return e } 
    5959}}} 
    60     both translations easily accomodate guards and pattern guards as well, the former by building on existing support for these two features in case constructs, the latter without requiring any previous implementation of pattern guards, by lifting (pattern)guards into the match monad: 
     60both translations easily accomodate guards and pattern guards as well, the former by building on existing support for these two features in case constructs, the latter without requiring any previous implementation of pattern guards, by lifting (pattern)guards into the match monad: 
    6161{{{ 
    6262    [| pat <- expr |] = pat <- return expr 
    6363    [| expr |]        = guard expr 
    6464}}}  
    65     ]'' 
     65]'' 
    6666 
    6767== implementation impact: == 
    68     minimal - limited to an extension in parser/desugarer, employing 
    69     previously inaccessible syntax for lambda-match, and a slight 
    70     variation of the existing lambda translation; also adds a small 
    71     library to support composition of matches. 
     68minimal - limited to an extension in parser/desugarer, employing 
     69previously inaccessible syntax for lambda-match, and a slight 
     70variation of the existing lambda translation; also adds a small 
     71library to support composition of matches. 
    7272 
    73     ''[note3: an updated draft of the composition library and a patch for GHC (about a dozen new lines in the parser, unchanged from the original proposal email) are provided as attachments to this proposal, together with some examples (updated since original email). please add patches for other Haskell implementations, and test whether they can handle the library code (tried for Hugs and GHC)]'' 
     73''[note3: an updated draft of the composition library and a patch for GHC (about a dozen new lines in the parser, unchanged from the original proposal email) are provided as attachments to this proposal, together with some examples (updated since original email). please add patches for other Haskell implementations, and test whether they can handle the library code (tried for Hugs and GHC)]'' 
    7474 
    7575== context: == 
    76     as has been pointed out in the thread on replacing and improving 
    77     pattern guards, Haskell's pattern matching support, even before 
    78     pattern guards, is monolithic (built-in case is the only way to handle 
    79     multiple alternative matches) rather than compositional (lambdas 
    80     represent individual alternatives, but cannot be composed on  
    81     match fall-through). this implies increased complexity of the language 
    82     definition and limited expressiveness of its features, when compared  
    83     with alternative models (eg, adapting Wolfram's pattern match  
    84     calculus for Haskell). see, eg.: 
     76as has been pointed out in the thread on replacing and improving 
     77pattern guards, Haskell's pattern matching support, even before 
     78pattern guards, is monolithic (built-in case is the only way to handle 
     79multiple alternative matches) rather than compositional (lambdas 
     80represent individual alternatives, but cannot be composed on  
     81match fall-through). this implies increased complexity of the language 
     82definition and limited expressiveness of its features, when compared  
     83with alternative models (eg, adapting Wolfram's pattern match  
     84calculus for Haskell). see, eg.: 
    8585 
    86     http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html 
    87     http://www.haskell.org/pipermail/haskell-prime/2006-October/001720.html 
    88     http://www.haskell.org/pipermail/haskell-prime/2006-October/001723.html 
    89     http://www.haskell.org/pipermail/haskell-prime/2006-October/001724.html 
     86http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html 
     87http://www.haskell.org/pipermail/haskell-prime/2006-October/001720.html 
     88http://www.haskell.org/pipermail/haskell-prime/2006-October/001723.html 
     89http://www.haskell.org/pipermail/haskell-prime/2006-October/001724.html 
    9090 
    91     as well as the PMC home page 
     91as well as the PMC home page 
    9292 
    93     http://www.cas.mcmaster.ca/~kahl/PMC/ 
     93http://www.cas.mcmaster.ca/~kahl/PMC/ 
    9494 
    95     and a newer thread discussing some differences between 
    96     this lambda-match proposal and PMC 
     95and a newer thread discussing some differences between 
     96this lambda-match proposal and PMC 
    9797 
    98     http://www.haskell.org/pipermail/haskell-prime/2006-October/001823.html 
     98http://www.haskell.org/pipermail/haskell-prime/2006-October/001823.html 
    9999 
    100     in principle, replacing Haskell's current pattern matching support 
    101     with a simpler, more compositional model, and defining the current 
    102     constructs on top of that new core is the way forward, IMHO. in 
    103     practice, however, I suspect that the committee is less than tempted 
    104     to introduce such a substantial simplification for Haskell'. 
     100in principle, replacing Haskell's current pattern matching support 
     101with a simpler, more compositional model, and defining the current 
     102constructs on top of that new core is the way forward, IMHO. in 
     103practice, however, I suspect that the committee is less than tempted 
     104to introduce such a substantial simplification for Haskell'. 
    105105 
    106     the present proposal is an attempt at a compromise, suggesting a 
    107     minimal language change to introduce compositional pattern-match 
    108     failure and fall-through. with lambda-match, it implements only a  
    109     single language extension (as syntactic sugar), delegating the rest 
    110     of the functionality to a library. without the sugar, the result of the 
    111     by-hand translation becomes so hard to read as to be near  
    112     unusable, while the chosen form of sugaring allows to provide 
    113     most of the language features discussed in the earlier threads to 
    114     be provided as a library. this does seem to be a useable balance. 
     106the present proposal is an attempt at a compromise, suggesting a 
     107minimal language change to introduce compositional pattern-match 
     108failure and fall-through. with lambda-match, it implements only a  
     109single language extension (as syntactic sugar), delegating the rest 
     110of the functionality to a library. without the sugar, the result of the 
     111by-hand translation becomes so hard to read as to be near  
     112unusable, while the chosen form of sugaring allows to provide 
     113most of the language features discussed in the earlier threads to 
     114be provided as a library. this does seem to be a useable balance. 
    115115 
    116     building constructs of the simpler pattern-match model on top of  
    117     the more complex one is somewhat irksome from a language design 
    118     perspective, but does at least gain the expressiveness of the simpler  
    119     model. if programmers make substantial use of this new functionality  
    120     in Haskell' (as I strongly suspect they will - I have been doing similar  
    121     translations by hand for some time now), it will be up to Haskell'' to  
    122     turn the table, and to define the current complex model on top of a  
    123     compositional one.  
     116building constructs of the simpler pattern-match model on top of  
     117the more complex one is somewhat irksome from a language design 
     118perspective, but does at least gain the expressiveness of the simpler  
     119model. if programmers make substantial use of this new functionality  
     120in Haskell' (as I strongly suspect they will - I have been doing similar  
     121translations by hand for some time now), it will be up to Haskell'' to  
     122turn the table, and to define the current complex model on top of a  
     123compositional one.  
    124124 
    125     as a preview of this anticipated language refactoring;), it is instructive  
    126     to compare the two alternative translations of lambda-match sketched  
    127     above: 
     125as a preview of this anticipated language refactoring;), it is instructive  
     126to compare the two alternative translations of lambda-match sketched  
     127above: 
    128128 
    129     - the first directly builds on the existing, complex case constructs with their built-in (pattern) guards and match fall-through support; this eases adding the new, simpler features to implementations that support the old, complex ones (like GHC), but completely foregoes any attempt to simplify those implementations in the process; ''[the attached patch for GHC follows this route]'' 
     129 * the first directly builds on the existing, complex case constructs with their built-in (pattern) guards and match fall-through support; this eases adding the new, simpler features to implementations that support the old, complex ones (like GHC), but completely foregoes any attempt to simplify those implementations in the process; ''[the attached patch for GHC follows this route]'' 
    130130 
    131     - the second translation avoids any direct reference to case, employing do-notation instead; this requires slightly more effort, eg. in translating pattern guards into the match monad, but is eminently suitable for adding the new features to implementations that do not support pattern guards yet, or that simply want to reduce the number of built-in constructs. ''[patchers for Hugs, etc., might want to follow this route?]'' 
     131 * the second translation avoids any direct reference to case, employing do-notation instead; this requires slightly more effort, eg. in translating pattern guards into the match monad, but is eminently suitable for adding the new features to implementations that do not support pattern guards yet, or that simply want to reduce the number of built-in constructs. ''[patchers for Hugs, etc., might want to follow this route