[Haskell-cafe] Parsers are monadic?

[Claus Reinke]

>> (b) i like my combinator grammars to be reversible, so that a single
>>     grammar specification can be used for both parsing and
>>     unparsing/pretty-printing.  that means i have to define the
>>     details myself anyway.
> 
> Oh cool - this is something I have wanted for a long time.  Anything
> released or otherwise available?

and i thought noone had noticed!-) nothing really released - i first used 
that technique in haskell for a prototype of the reduction system i was
modifying for my phd, many years ago. since reduction sytems had 
syntax oriented editors as interfaces, which i needed to model in my
prototype to get the right design context for the language extensions
i was working on, i needed parsing/unparsing/editing, and i didn't want 
three separate specifications to maintain for one and the same grammar. 

unfortunately, i ultimately had to implement things into the existing 
reduction systems (think the complexity of ghc and gdh combined, 
but written in .. c), so i had to put the haskell prototype aside while 
finishing my phd. when i finally emerged from that work, haskell had 
long moved on from 1.2, including substantial language changes, and 
as usual offering no tool support for porting large applications from 
one language version to the next (will haskell'  finally do better in 
this important aspect?-). 

i never got around to porting that prototype, and so i had shelved 
any idea of writing about the technique until recently, when i used it
again in a much smaller framework. but i have used the same basic 
technique, adapted to monadic combinators, for many years, and
every time i reimplement the ideas, i tend to play with alternative
ways of representing things, especially as the ways of combining
the parser and unparser aspects or error handling are concerned.

the latest such experiment is not necessarily the simplest variant, 
but i've just added some text explaining the basic ideas of grammar
combinators to the project log (fathom.txt, starting from line 482,
or search for 'grammar combinators'), and there's a grammar for 
a simple lambda-calculus (Lambda.hs, from line 210, or search 
for 'grammar'), so it should (might?-) be possible to work out the
basics from there. the more awkward bits (basic lexing/unlexing,
error handling, in Syntax.hs) are without documentation so far, 
but you might want to write those in a different way anyhow;-).

you can get the haskell code and project log via

    darcs get http://www.cs.kent.ac.uk/~cr3/fathom

or the project log directly at

    http://www.cs.kent.ac.uk/~cr3/fathom/fathom.txt

the experiment itself, dubbed 'fathom', might be interesting for 
other reasons, as it includes a straightforward embedding of 
conditional rewrite systems in haskell, extended to contextual 
rewriting, and used to specify normal-order and call-by-need 
lambda-calculi via a direct embedding of their reduction rules. 

this gives rather inefficient executable semantics, which are 
however very close to the operational semantics specifications 
one tends to find in papers/textbooks. and since they work as 
monadic text transformers (parse/reduce/unparse), one gets 
trivial little reduction systems for these calculi (there are even
some vim files, as i'm using vim as my user interface to those
mini-reduction systems, or am i using haskell to extend vim?-).

i doubt that everything will be obvious - there's a lot of text
explanation already in the project log, but not all of the code
is easily readable (Lambda.hs should be accessible, with the
help of the project log), and there's no other documentation yet.
please try the project log first, then feel free to ask questions!

oh, and please let me know if you like what you see?-)
claus