# lambda-match vs PMC

Claus Reinke claus.reinke at talk21.com
Tue Nov 7 20:28:49 EST 2006

Hi Wolfram,

> > - matchings are not first-class expressions in PMC
>
> The most important aim of the original PMC was to be a confluent rewriting
> system that emulates Haskell pattern matching
> ..
> So I needed only those operations on matchings that are somehow implicit''
> in Haskell pattern matching, and I did not need matching variables etc.

understood. sorry if my message suggested that our aims were the same!-)
and as your earlier message indicated, one could nevertheless use
PMC-inspired constructs to replace Haskell pattern matching with
something more modular.

btw, while my proposal ticket does link to your email, it doesn't make your
alternative proposal explicit - would you mind elaborating your proposal into
the two alternative proposals and their pros & cons (I have been told that
my current ticket is already rather long, so it will be better to have two

> > in spite of the monadic semantics, there are no monads in the type system,
>
> Just like in ML.
>
> In fact, just like in pure expression Haskell, which,
> from the point of view taken in the MPC2006 paper,
> still relies on a lifting monad to add undefined to constructed types.

where fail raises an exception, so you might want to be explicit about both
the expression and the matching monad. which would mean to have these

> > A "running commentary" in computational lambda-calculus,
>
> The main problem I see with that
> is that the computational lambda-calculus only sugars away ONE monad,
> while, in the MPC paper, we are dealing with TWO monads.

use several instances of computational lambda-calculus in our code, and
while each of those instances could be explained through one such calculus,
one calculus (at least in original form) wouldn't be sufficient to cover current
practice.

> In the lambda-match proposal there is the remark:
> >
> > -- we use Maybe as the default matching monad, but [] can be fun, too..

the code carefully leaves open which matching monad to choose, but provides
some help for common default choices, such as Maybe, Either String, and [].
I'm tempted to make (Either String) the default, as it makes it easy to preserve
error messages (although I should use a newtype, to avoid instance conflicts).

> In PMC (see the MPC paper)
> you can change not only the matching monad,
> but also the expression monad, for example:
> * a Maybe monad in the matching failure as exceptions'' view
>    of the pattern guards paper [Erwig-PeytonJones-2001],
> *  a list monad in functional-logic programming.

we can still do most of that, we just have to be explicit about both monads.
as one example, the function "ok", used to define match-failure in do-notation,
merges the match monad and the monad of the do-block. another example
is "nest", which merges two nested match-monads. using lists of successes
should also work, although we don't have logic variables (not unless we
use non-standard data structures that allow for them). propagating match
failure through exceptions probably suffers from similar problems (need
to use monadic rather than pure code).

> To me, it looks like the main difference between the lambda-match library
> and Tullsen's pattern matching combinators [PADL 2000] is that the
> lambda-match library also includes the same pointwise lifting'' of the
> monadic operations into function types that we use in the MPC paper.

that is strange - if you re-read that paper (I did after your email), I think
you'll find very little actual overlap with the lambda-match proposal. of
course, both start from the same idea, namely to replace pattern matching
with "monadic data parsing", but most of the details are rather different.

one might also say that Tullsen's work is more ambitious, in making not
only match failure and fall-through explicit in a MonadPlus, but also
matching itself (through various pattern combinators and syntactic sugar).
this is the main reason I did not mention his paper as related work in
the proposal - it would only confuse the issues. of course, I have been
working on my own versions of first class patterns, based on the
lambda-match proposal, and -so far- no further syntax extensions, but
that isn't part of the lambda-match proposal.

so, lambda-match is a smaller step, both syntactically and semantically,
and has been specifically targetted to be suited for Haskell'. it also aims
to lay the groundwork for refactoring Haskell pattern matching into
something simpler, more compositional, and more expressive (first-class
patterns tend to include pattern abstractions and views), after Haskell'.

Henrik has pointed out to me that I should make these aims and
expected advantages more explicit in my proposal ticket, which I'll
try when I next update it (I'm recompiling ghc and libraries to check
whether I've missed any syntax conflicts, updates after that..).

> Since PMC handles this as a language extension,
> it only concerns the semantics, not the type system.

(this referred to the lifting of lambda-matches to multiple parameters)

I could be wrong, but when you elaborate your own proposal, I think
you'll find that both n-ary patterns and the choice of monads will need
to be reflected in the type system, as most other properties of interest

once we start to distinguish nested match monads, "curried" matches
are no longer as easy to use as n-ary matches, so while you may say
that this is merely a convenience, I think it is of practical importance.

and I've tried to be careful not to use disputed features such as
overlapping instances, etc., which led to the pedestrian approach of
wrapping matches in Match constructors. this is nothing but a tag
to serve as a base-case for any type-level recursions over the
parameters of n-ary matches, which therefore are straightforward.

> Since the lambda-match proposal does it as a library, it has to
> be done inside the language, leading to the type-class artistry
> involving declarations like the following:

hmm. speaking for myself, I wouldn't be interested in Haskell's
design if I didn't want to use it. and if I want to use Haskell, it
would seem odd to handle parts of my proposal as language
extensions unless Haskell is not expressive enough to handle
those parts as libraries.

I don't claim that it was straightforward to come up with the
type classes (separating Lift and MonadPlus, separating Ex
from Lift, and the details of Nest, all took some work), but
apart from Nest, the results are not difficult to read or use,
and even nest does seem to pose few problems in use.

in fact, I put a lot of work into trying to achieve the latter,
by reducing the potential for ambiguities (hence the functional
dependencies that make Ex look more complicated), and
by keeping to the common subset of Hugs/GHC.

there are a few cases where things could be easier, eg,
kind annotations (scheduled for Haskell', I think) in
MatchMonad, or type patterns in class declarations (which
would permit me to make the purpose of Ex more obvious
-as it is from the type of ex- while still being able to express
the functional dependencies).

As for all embedded DSLs, I would like to be able to add
syntax transformations without changing the Haskell
implementation, and I would like to add error message
postprocessing the same way (so that I could define DSL-
specific syntax and error messages as part of a library),
but I have to make do with what Haskell provides..

> > -- extract (with function) from inner match monad
> > -- (extraction is lifted over lambda-match parameters;
> > --  we cannot express all functional dependencies,
> > --  because the inner c could be a function type)
> > class Ex a c da dc | da -> a, dc da -> c, da c -> dc {- , dc a c -> da -} where
> >   ex :: (a -> c) -> da -> dc
>
> So probably this is a seemingly innocuous extension to do notation
> with the potential for some quite spectacular type error messages...

we are not talking about an extension to do notation. we are trying
to expose a language feature that was previously only available
implicitly, via do notation or case.

yes, the type errors messages can be formidable, but mostly due to
our old enemy, the monomorphism restriction (how an implementation
issue that should at best result in a performance warning was ever
permitted to enter the language definition, let alone be such an
annoying obstacle to *programming with functions*, is beyond
me - I do hope this mistake will finally be corrected in Haskell'!!).

having said that, I would again point out that I've tried to make the
library useable, and while I haven't been entirely successful wrt to
ease of use, the type errors do seem to be helpful most of the time
(translating missing constraints into the class members helps), and
explicit type declarations do not seem to be needed as often as
one might fear for this kind of type-class programming (ymmv,
of course, so you'll have to try for yourself, and let me know!-).

> And, from my point of view, all it achieves over my tentative
> PMC proposal is to avoid the two language extensions of
> alternatives inside lambda abstractions, and argument supply
> (match ... with ...), at the cost of a different language extension.

as I mentioned, the monads will need to be explicit in Haskell,
which throws into doubt the idea of not having n-ary matches, as
well as raising all the problems of how to handle nested monads,
and how to reduce ambiguities while still allowing the monads to
be chosen as needed.

keeping alternatives inside lambda abstractions as anything other
than syntactic sugar does not seem to make the main impact of
the suggested change as clear as providing for single alternatives
plus composition: pattern match failure and fall-through have
become programmable, no longer tied to a language construct.

my proposal tries to be a compromise, by providing most (all?)
features of PMC, as well as foundations for monadic data parsing
in general, using syntactic sugar only where absolutely necessary,
proposal through to a prototypical implementation and Haskell'
ticket, though - if you can come up with something that does
provide the same features as lambda-match, without its difficulties,
I'd like to know about it!

> (I am also afraid that the |'' notation might be dangerous.
> To emphasise its character as a monadic lambda'',
> I would rather consider something like \>'', to be typeset $\lambda_{>}$.
> )

I chose the '|' because it is already reserved, but cannot be
used in that position (*), and because it is already associated with
alternatives in data types. the notation needs to be very lightweight,
because several lambda-matches will be normally be used together
with (+++) and parenthesis, to cover alternative cases, and the '|'
does provide a nice visual aid in connecting these separate cases
by layout. I'm not completely tied to this syntax, but anything else
I've tried so far seems unable to provide similar benefits in practice
(including your \>, which neither aligns well, nor suggests the case
alternatives - even if you meant \>>; and we are concerned more
operator/keyword (like "proc" for arrows).

note also that this is *not* the "monadic lambda" one might expect,
because it embeds the body of the lambda-match in a return. one
might want to add a lambda-do as well:

[| '\>' <patterns> 'do' <statements> |]
==>
\ <variables> -> do {<patterns> <- return (<variables>)
; <statements> }

or, using lambda-match to define lambda-do:

\> <patterns> do <statements>
=
ok \$ (| <patterns> -> do <statements>)

but I decided not to make that part of the present proposal.

Claus

(*) actually, when recompiling ghc and libraries from scratch, I
of a list comprehension, one uses a do-block with more than
one statement, and layout instead of explicit {}, then it is not
clear whether one sees the last expression in the do-block or
the first qualifier of the list comprehension..

(don't laugh, that actually occurs, in Data/Array/Base;-). to
avoid complications, and because lambda-matches are meant
to be passed as parameters to higher-order functions such as
splice and (+++) anyway, I've now changed the patch to
require parens around all lambda-matches, and from this
safe position I'm looking for places where the parens are
not needed (the way the grammar is organised does not
always make it easy to differentiate these places).