Replacing and improving pattern guards with PMC syntax

[Claus Reinke]

I'm not sure I follow all the details, but I think I agree ;) with Wolfram
on several points, even if I've arrived there via a different route. 

Some of this may sound strange to those who equate "declarative" 
with "equational", so let me state in advance that I do not agree with 
that particular notion - expression-level programs, such as parsers 
built from parser combinators, can be just as declarative as equations.

However, I do agree that pattern matching has become a problem
in functional languages (I once knew a fpl where that part of the
language and implementation was of roughly the same complexity
as the whole rest of it), and Haskell is unfortunately no exception. 
The problem is not that there is syntactic sugar for pattern matching,
but that this isn't sugar coating at all - there is functionality hidden
in there that cannot be provided by the remainder of the language.

In other words, pattern matching and associated "sugar" become
part of Haskell's core, which thus becomes more complex,
without offering sufficient compensation in terms of expressiveness.

The particular issue at hand is not that case is modeled after let
rather than after lambda, but that pattern match failure and fall
through are built-in concepts that cannot be programmed in the 
language but have to be dealt with in specific syntactic forms. 
Following the old adage of "simplicity through generality", I 
would prefer instead if we would have available language-
constructs for matchings, composition of matchings, and 
"splicing" of such rule sets back into expressions ("\" in 
Wolfram's description). 

Then pattern match fall-through would be programmable, 
patterns matching constructs could be composed as easily 
as parser combinators (as an added bonus, getting closer 
to first-class patterns), case, multi-equations, and do-notation 
would become true syntactic sugar, and Haskell's core 
would finally start to become simpler, for once.

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.

Now, instead of repeatingWolfram's arguments about case
and multi-equations, let's have a look at do-notation, as used
in (1): it is obvious that this part of the translation is the source
of the awkwardness I mentioned, as the right-hand side of (1)
has a lot more syntax noise than the left-hand side. What we
really want here is some way of "lifting" lambda-abstractions
so as to make potential pattern-match failures explicit and
handleable. Perhaps we can get rid of some of that syntax
noise? 

    \x->do { lhs <- return x; return rhs }
-->
    \x->(return x >>= \lhs->return rhs)
-->
    \x->(>>= (\lhs->return rhs)) (return x)
-->
    (>>= (return . (\lhs->rhs))) . return

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.

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. Personally,
I'd very much like to see the latter, as this issue frequently
confronts me, eg., when embedding domain-specific languages
and their patterns in Haskell.

When Haskell came into being, it started from the lambda
calculus, but nowadays, a substantial portion of Haskell
programs use various monads to capture program patterns.
If Haskell was designed today, monads would not be a 
late add-on with some syntax to be translated away, but 
they would be at the core of the language, with other 
features translated away into that generalised core. 

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?-)

Cheers,
Claus

PS. Outside of Haskell98, we can come closer to defining
    that lift function, but it gets rather ugly. Here is a first 
    approximation:

lift match = \x->either (fail . show) return $!
                 unsafePerformIO $
                 (return $! Right $! match x) 
                 `Control.Exception.catch` (return . Left)

Main> lift head ([False]::[Bool]) >>= print
False
Main> lift head ([]::[Bool]) >>= print
Program error: user error (pattern match failure: head [])
Main> lift head ([]::[Bool]) `mplus` (Just True)
Just True
Main> lift head ([False]::[Bool]) `mplus` (Just True)
Just False