lambda-match example - from parser combinators to grammar combinators

[Claus Reinke]

Some of you have asked me whether I could provide more convincing
examples for lambda-match, or whether the shortcomings of Haskell
addressed in this proposal will be of practical relevance to the typical
seasoned Haskeller without specific interests in language design.

There are of course the various themes of views, pattern abstractions,
and first-class patterns, which could be built on top of lambda-match,
but I'd like to follow a slightly different angle first, inspired by an 
interesting off-list remark in response to the lambda-match proposal:

    I do consider myself a fairly seasoned Haskell programmer, and 
    to be honest, I have to admit that I rarely if ever have missed 
    composable pattern matching at the source level. Of course, that 
    could be because I subconsciously just work around the problem, 
    being used to Haskell as it is.

I do indeed believe that the problem of non-compositional pattern
match has been around in Haskell for so long that many of today's
Haskellers are no longer even aware of the issue, and of how much
it affects them.

So, here is one slightly less trivial example of using lambda-match, 
which happens to stand for a large group of possible applications, 
and for one particular area where the lack of compositional patterns
has influenced the Haskeller's world-view: 

Ever since I took up Haskell, I have wondered why Haskellers tend 
to specify their grammars not just twice (abstract + concrete), but 
thrice (abstract + parsing + unparsing).

The majority of seasoned Haskellers seems to accept that there must 
be parsers+pretty-printers, read+show, serialize+de-serialize, etc., and
that changing concrete syntax must involve making fixes in two separate 
bits of code, often even following two separate coding patterns.

But if one looks at so-called parser combinators, there is very little in
them that is parser-specific - usually only the literal parsers determine
that we are talking about parsing, whereas the majority of combinators
can be used just as well for other syntax-directed tasks. Still, people
tend not to reuse their combinator-based grammars for anything but
parsing.

I submit that one of the main reasons for this is that Haskellers have
come to accept that they can construct, but not deconstruct algebraic 
types in a compositional way (hence the use of parser combinators
for converting Strings into algebraic data types, and the use of more
pedestrian means for showing the latter as Strings; pretty-printing
libraries do at least use combinators, but do not reuse the grammars
specified through parser combinators).

Please have a look at the example (which needs both syntax patch 
and library from the proposal ticket, if you actually want to run it *,
but the ideas should be reasonably obvious even without): 

it specifies a concrete and abstract syntax for lambda calculus, and
the relationships between the two levels of syntax, using an algebraic
data type for the abstract syntax, and a grammar built with monadic
combinators for the rest. fairly standard, but for the following:

language and library support for monadic data parsing via 
lambda-match allow us to mix data parsing and string parsing in the 
same monadic framework, using the same "grammar combinators" 
to specify the concrete syntax and its relation to the abstract syntax
just once, in one piece of code.

we can use that single grammar for parsing, unparsing, or indeed, 
for mixtures of both (see the examples). A long time ago, I used 
something like this (then sadly without language support) to 
implement a syntax-oriented editor, with parsing and formatted
printing from a single grammar.

Although I haven't worked this out, I suspect that the technique 
would also apply to protocol-based applications: instead of 
writing client and server separately (and then trying to prove 
that they fit together and follow two sides of the same protocol), 
one might try to write a single grammar for the protocol between 
them, toggling mode at the appropriate points, and then client 
and server would simply be two instances/uses of the same 
grammar in its two start modes (so the server would generate 
prompts, parse requests, and generate responses, and the 
client would expect prompts, generate requests, and parse 
responses).

have fun;-)
claus

* I have submitted the syntax patch for the GHC head repository,
*  but GHC HQ are reluctant to apply the patch as long as there
*  is no obvious general interest (someone else but myself, and 
*  not just in private email to myself;-) in using these features. If 
*  you want to investigate lambda-match in GHC, to make up your
*  mind about whether or not you like the proposal (at the moment,
*  we're only talking about the daily snapshots of GHC head, not 
*  about long-term support in GHC, let alone inclusion in Haskell'!), 
*  please let yourself be heard!

    (more adventurous souls can of course apply the patch from the
    ticket themselves and recompile GHC;-)

    I have also updated the proposal ticket with a list of motivation 
    bullet-points for lambda-match:

    http://hackage.haskell.org/trac/haskell-prime/ticket/114
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PunP.hs
Type: application/octet-stream
Size: 3513 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-prime/attachments/20061111/02998e0e/PunP.obj