Changes between Version 1 and Version 2 of Ticket #114


Ignore:
Timestamp:
Nov 9, 2006 2:42:53 PM (9 years ago)
Author:
claus
Comment:

make motivations explicit, and separate context from core proposal

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #114 – Description

    v1 v2  
    4848( {{{(>|)}}} ), and joining of nested matches (so that, for instance
    4949{{{
    50     nest $ |<outer>-> |<inner>-> expr = |<outer> <inner>-> expr
     50    nest (|<outer>-> (|<inner>-> expr)) = (|<outer> <inner>-> expr)
    5151}}}
    5252).
     
    7171library 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, changed from the original proposal email only in requiring parentheses) 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
    75 == context: ==
     75== motivation: ==
     76
     771. patterns/guards in lambda abstractions are of limited use if match failure cannot be handled
     78
     79  - match failure in lambda abstractions can only lead to an exception
     80
     812. the only direct way of handling match-failure and fall-through to other alternatives, without something like lambda-match, is not by composing alternatives, but within the built-in construct case; a slightly more indirect way employs the built-in do notation, where again the functionality is not available to (monadic) composition, but only within the do notation
     82
     833. workarounds to mimick the functionality of lambda-match without syntactic sugar (translating into lambda+do or lambda+case) are so cumbersome and unreadable as to be unusable in practice (translating into lambda+list-comprehension is almost readable, but restricted to lists). compare:
     84{{{
     85  (|(Just x)-> x)
     86
     87  \fresh->do { Just x <- fresh; return x }
     88
     89  \fresh->case fresh of { Just x -> return x; _ -> fail "no match" }
     90
     91  \fresh->[ x | Just x <- [fresh] ]
     92}}}
     93
     944. since the functionality is already available in the language, and even explicitly used in the report for a feature as frequently used as the do notation, there should be a language construct making this functionality directly accessible
     95
     96  - the functions named "ok", constructed in Section 3.14 of the report, can be expressed directly using lambda-match (the library contains a function {{{ok}}} for this purpose)
     97{{{
     98  do { p <- e; stmts } = e >>= ok (|p-> stmts)
     99}}}
     100
     1015. unlike lambda, lambda-match truly expresses a single alternative in a case statement, as a first-class language expression - it can be named, passed as parameter or result, manipulated as a function, and composed with other alternatives. as a corollary, lambda, case, and other monadic abstractions can be defined easily in terms of lambda-match and its support library
     102{{{
     103  - splice (|x->expr) = \x->expr
     104
     105  - case expr of { pat -> expr; ..} = caseOf expr $ (| pat -> expr ) +++ ..
     106
     107  - ok (|pat->do statements) = \fresh->do { pat <- return fresh; statements }
     108}}}
     109
     1106. while the present proposal suggests lambda-match as a small extension to the language, it also lays the groundwork for a major simplification
     111
     112  - as points 4 and 5 indicate, several core constructs of Haskell need no longer be considered as built into the language, but become user-definable; this would simplify the language definition, implementations, teaching, learning, and tool building
     113
     1147. although the present lambda-match proposal is fairly conservative, it also aims to lay the groundwork for a substantial increase in language expressiveness
     115
     116  - the fundamental idea, used here only to reify pattern-match failure and fall-through, is that of replacing built-in pattern matching with user-definable monadic data parsers and associated combinators
     117
     118  - this same idea lies at the heart of a more radical decomposition of pattern-matching, which has been studied in the literature as first-class patterns (eg, Tullsen, PADL2000)
     119
     120  - having pattern-match alternatives as first-class language constructs also paves the way for user-defined pattern abstractions, or more generally, views (various literature)
     121
     122this completes the main part of this proposal.
     123
     124----
     125
     126== context and references: ==
     127
    76128as has been pointed out in the thread on replacing and improving
    77129pattern guards, Haskell's pattern matching support, even before
    78130pattern guards, is monolithic (built-in case is the only way to handle
    79131multiple alternative matches) rather than compositional (lambdas
    80 represent individual alternatives, but cannot be composed on
     132seem to represent individual alternatives, but cannot be composed on
    81133match 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.:
     134definition, limited expressiveness of its features, and more difficult
     135reasoning, when compared with alternative models (eg, Wolfram Kahl has
     136suggested to adapt his pattern match calculus for Haskell). see, eg.:
    85137
    86138http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html
     
    130182
    131183 * 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
     184
     185finally, while it is not directly relevant for the present proposal,
     186Tullsen's PADL 2000 paper investigates one way in which monadic data
     187parsing can be built on to go beyond first-class match alternatives
     188all the way to first-class patterns:
     189
     190http://citeseer.ist.psu.edu/tullsen00first.html
     191
     192this, in turn, relates directly to Views and PatternSynonyms.