proposal: introduce lambda-match (explicit match failure and fall-through)

[Claus Reinke]

name: 
    introduce lambda-match (explicit match failure and fall-through)

summary: 
    Haskell 98 provides *two different translations* of lambda
    abstractions involving pattern matching, only one of which is
    directly accessible (Section 3.3 - the other is embedded in the
    translation of do-notation, see "ok" in Section 3.14).

    providing explicit source notation for the second translation,
    substantially simplifies programmability of pattern-match
    fall-through by reification of pattern-match failure, two 
    central language features that are so far only available
    through the built-in, non-composable case construct.

what:
    in Section 3.3, the translation for conventional lambda
    abstractions with patterns is given as

    [| \p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of (p1,..,pn) -> e

    with xi fresh identifiers, and pattern-match failure resulting in
    _|_. the latter is unfortunate, and results in partial functions the
    coverage of which cannot be combined, but it is forced by 
    translation into conventional lambda calculus.

    since computational lambda calculus (\-M) has become a central part
    of Haskell programming practice, there shall be an alternative form
    of lambda abstraction, dubbed here lambda-match, with associated
    translation into \-M:

    [| |p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of 
                                            { (p1,..,pn) -> return e;
                                               _ -> fail "no match" }

    [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 and patch]

    a library for composing these lambda-matches shall provide for
    composition of alternative lambda-matches (+++), match failure
    (nomatch) and embedding of the explicit match monad into pure
    expressions (splice, where "splice |p1..pn->e = \p1..pn->e").

    [note2: an alternative translation would use do-notation instead
     of case as the target:

     [| |p1 .. pn-> e |] = \x1 .. xn-> do { 
                            (p1,..,pn) <- return (x1,..,xn); 
                            return e }

    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]

implementation impact:
    minimal - limited to an extension in parser/desugarer, employing
    previously inaccessible syntax for lambda-match, and a slight
    variation of the existing lambda translation; also adds a small
    library to support composition of matches.

    [note3: a first draft of the composition library and a patch for
     GHC (about a dozen new lines in the parser) are provided as 
     attachments to this proposal, together with some examples]

context:
    as has been pointed out in the thread on replacing and improving
    pattern guards, Haskell's pattern matching support, even before
    pattern guards, is monolithic (built-in case is the only way to handle
    multiple alternative matches) rather than compositional (lambdas
    represent individual alternatives, but cannot be composed on 
    match fall-through). this implies increased complexity of the language
    definition and limited expressiveness of its features, when compared 
    with alternative models (eg, adapting Wolfram's pattern match 
    calculus for Haskell). see, eg.:

    http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html
    http://www.haskell.org/pipermail/haskell-prime/2006-October/001720.html
    http://www.haskell.org/pipermail/haskell-prime/2006-October/001723.html
    http://www.haskell.org/pipermail/haskell-prime/2006-October/001724.html

    in principle, replacing Haskell's current pattern matching support
    with a simpler, more compositional model, and defining the current
    constructs on top of that new core is the way forward, IMHO. in
    practice, however, I suspect that the committee is less than tempted
    to introduce such a substantial simplification for Haskell'.

    the present proposal is an attempt at a compromise, suggesting a
    minimal language change to introduce compositional pattern-match
    failure and fall-through. with lambda-match, it implements only a 
    single language extension (as syntactic sugar), delegating the rest
    of the functionality to a library. without the sugar, the result of the
    by-hand translation becomes so hard to read as to be near 
    unusable, while the chosen form of sugaring allows to provide
    most of the language features discussed in the earlier threads to
    be provided as a library. this does seem to be a useable balance.

    building constructs of the simpler pattern-match model on top of 
    the more complex one is somewhat irksome from a language design
    perspective, but does at least gain the expressiveness of the simpler 
    model. if programmers make substantial use of this new functionality 
    in Haskell' (as I strongly suspect they will - I have been doing similar 
    translations by hand for some time now), it will be up to Haskell'' to 
    turn the table, and to define the current complex model on top of a 
    compositional one. 

    as a preview of this anticipated language refactoring;), it is instructive 
    to compare the two alternative translations of lambda-match sketched 
    above:

    - 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]

    - 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?]
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ControlMonadMatch.hs
Type: application/octet-stream
Size: 2364 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-prime/attachments/20061024/20d2a681/ControlMonadMatch-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: LambdaMatchExamples.hs
Type: application/octet-stream
Size: 2934 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-prime/attachments/20061024/20d2a681/LambdaMatchExamples-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: LambdaMatch.hunk
Type: application/octet-stream
Size: 895 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-prime/attachments/20061024/20d2a681/LambdaMatch-0001.obj