[Haskell-cafe] Parsers are monadic?

[Paul Hudak]

Hi Claus.  I am sympathetic with your comments regarding monads and 
continuations.  It's interesting to note that the original I/O system in 
Haskell was based on streams and continuations.  The continuation 
version had two continuations in fact -- one for success and one for 
failure.  For example, readFile had the type:

    readFile :: Name -> FailCont -> StrCont -> Behaviour

Here StrCont was the success continuation, which took a string (the file 
contents) as argument.  I rather liked the flexibility that this offered 
-- since I/O errors were fairly common, it made sense to give success 
and failure equal status.  The down-side of using continuations is that 
you have to carry them around explicitly, so one might argue that they 
clutter the code a bit, and that was one of the advantages of switching 
to monads.  On the other hand, one could argue that having them explicit 
makes things in some way clearer.

All of this is described in fair detail in the History of Haskell paper, 
by the way (see http://portal.acm.org/toc.cfm?id=1238844).  It's worth 
noting that, in comparing continuation and monadic program fragments, we 
comment in that paper:

    Although these two code fragments have a somewhat imperative
    feel because of the way they are laid out, it was really the advent
    of do-notation—not monads themselves—that made Haskell programs
    look more like conventional imperative programs (for better
    or worse). This syntax seriously blurred the line between purely
    functional programs and imperative programs, yet was heartily
    adopted by the Haskell Committee. In retrospect it is worth asking
    whether this same (or similar) syntactic device could have been
    used to make stream or continuation-based I/O look more natural.

Best wishes,   -Paul


Claus Reinke wrote:
>> The standard, naïve approach to monadic parsing is very nice, but
>> inefficient. So *please read* some material based on Hutton&Meijer
>> approach, but don't stay there, read something more modern,
>
> since we thereby seem to have left the phase of simple answers to
> simple questions;-) i'd like to raise a pet issue of mine. my own first
> combinator parsers (inspired by Wadler's "How to replace failure
> by a list of successes", but adapted to a call-by-value language)
> were based on continuations.
>
> ..
>
> ok, now everybody has had time to chime in with "monadic parsers
> are based on continuations" or "continuations are just one specific
> monad". so let me return to the particular issue i'm interested in:
> contrary to monadic parsers, those continuation-based parsers
> had *two* continuations, one for success, one for failure. and
> that seemed to be a very natural match for the problem.
>
> for all that i like monadic programming in general, i often feel
> that it is biased towards handling only the success path well,
> by offering built-in support for a single continuation only. for
> instance, one can use (Either String) as a parser monad with
> error messages, but it isn't straightforward to express error
> handling into that format, preserving both success and failure-
> related info (such as reporting the error corresponding to the
> longest partially successful parse). also, negation does not
> seem to be an easy fit (succeed if a specific parser would
> not be successful at the current point; this seems to require
> monad-specific information, so perhaps there's a
> MonadNegate class missing?).
>
> has anyone else had similar experiences with expressive limitations
> of monadic programming? things that one might be able to work
> around, but that don't feel as natural or simple as they should be?
> things that one hasn't been able to express at all (such as Swierstra
> & Duponcheel's static analysis of combinator parsers which
> inspired Hughes's proposal to use arrows)?
>
> claus