[Haskell-cafe] Parsers are monadic?
claus.reinke at talk21.com
Wed Jul 4 20:26:11 EDT 2007
>> (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
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?-)
More information about the Haskell-Cafe