There was a discussion last month on the SRFI 228 mailing list about this, and I would like to discuss it further.

To quote from the rationale of SRFI 158 (Generators and Accumulators):

> The main purpose of generators is high performance. Although SRFI 41 streams can do everything generators can do and more, SRFI 41 uses lazy pairs that require making a thunk for every item. Generators can generate items without consing, so they are very lightweight and are useful for implementing simple on-demand calculations.

This is a good rationale; however, SRFI 158 generators have a flaw compared to SRFI 41 lazy streams, namely that they have a fixed sentinel value, the eof-object. This conveniently makes the port procedures read, read-line, read-char, etc. generators for the current-input-port (although whether even this is a good idea is debatable), but it means that streams of datums encapsulated in generators cannot actually contain an eof-object. The conversion from other container types such as lists, vectors etc. is thus not lossless. Also, SRFI 158 generators are imperative and depend on mutable state.

Unfortunately, we probably can’t take (scheme generator) out of R7RS and replace it completely by something else, as it was voted in in the Red edition and thus far, John seems resistant to incompatible changes between editions. But nonetheless I think it would be worth considering if we *can* do better.

I proposed a solution to the first problem: generators become one-argument procedures instead of thunks, and return their single argument, instead of the eof-object, when exhausted. This makes code making correct use of iterators slightly more verbose, but can to some extent be retro-specced in by making the eof-object the default sentinel when none is explicitly passed. This does not resolve the second problem, however — generators would still be imperative.

Marc Nieper-Wißkirchen proposed a completely new API of functional iterators as two-argument procedures: (iterator next end), where next is a two-argument procedure receiving a new iterator plus the next item in the sequence, and end is a thunk called when the sequence is exhausted. He provided this example of converting an iterator to a list:

(define (iterator->list it)
  (let f ((it it))
    (it (lambda (it val)
          (cons val (f it)))
        (lambda () '()))))

Here’s the inverse conversion (by me, assuming I understand the proposal correctly):

(define (list->iterator ls)
  (lambda (next end)
    (if (null? ls) (end)
        (next (list->iterator (cdr ls)) (car ls)))))

My initial objection to this proposal was that, like streams of lazy pairs, this involves consing on every step and thus doesn’t have the performance benefit of generators. Marc assured me that this was not the case and non-consing implementations are possible; initially he convinced me, but now I’m not sure again. list->iterator requires a new closure to be created at every step, and that doesn’t seem surmountable, even by changing the design. (Compare the SRFI 158 implementation of list->generator: <https://github.com/scheme-requests-for-implementation/srfi-158/blob/32aed9/srfi-158-impl.scm#L90-L96>) If we want to get into debates about what a Sufficiently Smart Compiler could do, maybe this can be as efficient as SRFI 158, but on basic implementations this will be slower.

So is there a use case for functional iterators? If I want to iterate the same list more than once, or in different threads, I can just call list->generator multiple times on it, and they don’t share any state except the list itself. They require only one closure to be consed for each time you want to go from start to finish, rather than at each step. And if for some reason I would like to start sharing state in the middle of an iteration, well, there is the example of the Python itertools.tee, also built on an imperative iteration protocol: <https://docs.python.org/3/library/itertools.html#itertools.tee>

Evidently the voters on the Red Edition ballot were okay with an iteration pattern which doesn’t allow the eof-object to occur in sequences. Are Marc and I being excessively paranoid about this restriction?

(I am ignoring the question of accumulators for now, although similar questions can be asked about the wisdom of their design, too. But answering the questions about one essentially automatically answers most important questions about the other, imo.)

Daphne