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