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