Claus Reinke wrote:
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 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].
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 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...