Replacing and improving pattern guards with PMC syntax

[Jacques Carette]

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