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,




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.





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

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


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:


just once, in one piece of code.


printing from a single grammar.



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

*  mind about whether or not you like the proposal (at the moment,


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



   http://hackage.haskell.org/trac/haskell-prime/ticket/114

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. 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. come to accept that they can construct, but not deconstruct algebraic types in a compositional way (hence the use of 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): 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 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 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). * 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 * 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! I have also updated the proposal ticket with a list of motivation bullet-points for lambda-match:

PunP.hs
Description: Binary data

_______________________________________________
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime