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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
