[Haskell-cafe] Fwd: Semantics of iteratees, enumerators, enumeratees?

[wren ng thornton]

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.

-- 
Live well,
~wren