My own awkward-looking translations were driven by having found two tool's in Haskell that come close to this ideal, even if the syntax is awkward: the mapping of pattern-match failure to "fail" in do-notation, and the use of "fail msg=mzero" in MonadPlus. By these means, matchings (lambdas with patterns and explicit match failure) can be represented as do-blocks:
lhs->rhs ==> \x->do { lhs <- return x; return rhs } (1)
and then be composed (the examples I gave moved the \s to the front instead and used "mplus" to compose matchings, but we could also lift the compositions to function-level instead), and finally "spliced" back (turning explicit into implicit match failure) using fromJust or suchlike. Adding pattern guards into this translation was straightforward - they simply go between the two returns. Note that it is very much this issue of 'monadic choice' in the case of
hey, that's great! so the lifting we are looking for is simply
lift match = (>>= (return . match)) . return
right? wrong, unfortunately. Looking more closely at the translation of do-notation in 3.14 of the Report, we see that it actually creates a new function by syntactic rather than semantic manipulation (in fact mapping the problem of fall-through back to a multi-equation first, then to "fail"), so we have no hope of reproducing the nice behaviour wrt pattern-match failure without using the do-notation, and all the syntax noise that implies. The MPC2006 paper has a section describing *which* monad that Haskell98 "bakes in" to its syntactic-level translation. So we agree with your observation that there is a whole 'design space' of what to do on match failure, but Haskell 98 bakes a particular choice in. See that section for how other published papers "bake in" other choices, and how large
Claus Reinke wrote: pattern-match failure which is dealt with (in gory, assembly-level categoretical terms) in the MPC2006 paper you can find at http://www.cas.mcmaster.ca/~kahl/PMC/ (disclaimer: I am a co-author of that particular paper). An early draft of this paper relied heavily on `mplus` with an extra condition -- until it was realized that very few monads satisfy this! This is where 'function lifting' came in, where we essentially add enough arrows "on the left" (in a completely deterministic and typed manner, see the boxed-; and boxed-+ definitions) to pull failure up to the right type, so that failure could be dealt with at the 'right time'. It is only function types that introduce complications -- all other types are quite straightforward to deal with. [Deleted: Claus' derivation of a monadic lifting of pattern-match failure which sure looks equivalent/ very close to what was in our MPC2006 paper]. the design space can really be [for example, using the List monad leads to quite interesting ideas, as does using LogicT].
I'm not sure whether Wolfram suggested only a simplication of the specification of pattern matching or an actual reification of the concepts of matching, composition of matching, and splicing of matchings into multi-alternative lambdas. Wolfram's PMC [1] is an all-out reification of the concepts of matching, composition, splicing, etc. The biggest thing it doesn't handle are some of Barry Jay's excellent ideas on generic pattern-matching (see http://www-staff.it.uts.edu.au/~cbj/patterns/). The issue, as far as I see it, is that although Barry's latest ideas are first-rate, they seem extremely difficult to 'type' [and getting PMC to 'type' was really non-trivial].
And one of the things that would make possible is to replace some previously built-in and non-composable notions, like pattern-match fall through and composition of rule alternatives, by a smaller, yet more expressive core. And that is always a worthwhile goal for language redesign, isn't it?-) Agreed!
Jacques [1] Proper attribution: the PMC is Wolfram's, I just thought it was so cool that I insisted on 'helping' him with the type system...