[Haskell-cafe] Fwd: Semantics of iteratees, enumerators,
wren ng thornton
wren at freegeek.org
Mon Aug 23 23:41:25 EDT 2010
Conal Elliott wrote:
> For anyone interested in iteratees (etc) and not yet on the iteratees
> mailing list.
> I'm asking about what iteratees *mean* (denote), independent of the various
> implementations. My original note (also at the end below):
>> With the encouragement & help of Conrad Parker, I've been looking at
>> iteratees, enumerators, enumeratees. I can find plenty written about them,
>> but only about benefits and implementation. In sifting through chunks,
>> error/control messages, and continuations, I find myself longing for a
>> precise semantic basis. I keep wondering: what simpler & precise semantic
>> notions do these mechanisms implement? Has anyone worked out a denotational
>> semantics for iteratees, enumerators, enumeratees -- something that
>> simplifies away the performance advantages & complexities? I've worked out
>> something tentative, but perhaps I'm covering old ground.
I believe the denotation of an iteratee is the transition function for
an automaton (or rather a transducer). I hesitate to speculate on the
specific kind of automaton without thinking about it, so maybe finite,
maybe deterministic, but then again maybe not.
The core idea of iteratees vs conventional parsing strikes me as the
same as the build/foldr vs unfoldr/destroy dichotomy. That is,
ultimately we have a non-recursive producer, a non-recursive consumer,
and a recursive driver. In build/foldr the producer is "flat" and we
factor the recursion into the consumer; whereas in unfoldr/destroy we
factor the recursion into the producer and the consumer is flat.
Thus, I think iteratees are just the (non-recursive) transition
function. The recursion for applying the transition function is done
elsewhere, namely in the data/driver. Whereas in conventional parsing,
the parser contains both the transition function and the recursion for
driving the automaton until it hits an accepting/error state, and the
data is just a flat stream. This is why conventional parsers don't have
a Partial/More constructor: they don't expose the intermediate states of
the automaton. Since iteratees only take a single step before returning,
they do expose those intermediate states and so they need to have a
constructor for them.
More information about the Haskell-Cafe