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...
_______________________________________________
Haskell-prime mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-prime
