lambda-match vs PMC

Claus Reinke claus.reinke at
Sun Oct 29 12:14:28 EST 2006

It is encouraging that separate groups have come to similar approaches
wrt to more modular pattern match facilities (though perhaps it isn't all 
that surprising, eg, my own musings on this topic started after one of the
early functional logic programming high periods, in the early 1990s, and
have since been shaped by the developments in monadic and type class 
programming in Haskell; PMC seems to have come from a rewriting
background, shaped by monadic semantics and type theory; these 
would imply the same influences, moderated via different communities?).

There are, however, some differences that might be worth further
inspection. Referring to , 
and especially to the MPC 2006 paper, in no particular order, with 
no claim to completeness (and please read comments like "odd" as 
purely subjective, reflecting only my personal reactions as I'm trying 
to figure out the relation!-):

- matchings are not first-class expressions in PMC

the only syntactically correct way to mention a matching in an expression
is inside a splice ( {| match |} ). this is fairly surprising given the aims of 
PMC, as one would expect operations on matchings, matchings as 
parameters and results of functions, etc. .. until one notices that not 
only the operations on matchings, but

- *all* the interesting action in PMC is at the level of matchings, 
    not at the level of expressions

lambda-abstraction doesn't even exist at expression level, but is 
replaced by spliced matching; application exists, but is not needed,
because (f e) = {| e |> {| f |} |} (unless I'm mistaken?)

if one eliminated the oddity of having two applications, but only
one abstraction, the category of expressions would be nearly 
empty, apart from constructor terms, and the separation of 
expressions and matchings seems needed only to support 
conversions between the two:

{| _ |} :: Match -> Expression
^ _ ^ :: Expression -> Match 

which directly brings up the next oddity, in that there are no such
types in PMC:

- the difference between matchings and expressions is maintained 
    in the typing contexts/labels, not in the types

in spite of the monadic semantics, there are no monads in the type
system, and instead of 

     .. |- pattern |> match :: a -> m b 

(as Haskellers might expect to see), one has 

    .. |M- pattern |> match :: a -> b

I was looking into these details because I was trying to compare
lambda-match and PMC, and while most of the differences seemed
merely cosmetic at first, the one difference I couldn't account for was 
that PMC examples seemed to imply an implicit flattening of the 
monadic type structure, whereas I had to join nested lambda-matches 
explicitly (I would find the ability to join nested matchings quite useful
on occasion, but I fail to see how this could be done implicitly/
automatically, unless by giving up the ability to express nested matches).

if I now understand all these items correctly in combination, PMC is 
a flattened monadic framework, ie., one cannot even construct the 
equivalent of a ( <nested> :: m (m a))? or am I missing the obvious?-)


ps. after reading the MPC 2006 paper, I have to support the referees'
    recommendation: as one of many who only occasionally dive into
    the most shallow parts of category theory, I don't find the monadic
    semantics in its current presentation helpful. A "running commentary"
    in computational lambda-calculus, as apparently suggested by the
    referees, would have made all the difference (I think, because that 
    kind of presentation usually translates easily into Haskell;-). As it 
    stands, I fear you are limiting your audience needlessly.

    Couldn't match `Categories' against `Haskell'
        Expected type: Haskell
        Inferred type: Categories
    In the first argument of `readPaper', namely `PMC_MPC2006'
    In the definition of `it' : it = readPaper PMC_MPC2006

More information about the Haskell-prime mailing list