Changes between Version 1 and Version 2 of Ticket #114


Ignore:
Timestamp:
Nov 9, 2006 2:42:53 PM (8 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.