* Fred Lunnon <fred.lunnon@gmail.com> [Jun 10. 2014 18:10]:
I scratched my head over this, but now I think these "iterators" must be the same thing as loopless generators --- see http://en.wikipedia.org/wiki/Loopless_algorithm This topic has surfaced previously on math-fun, with respect to various combinatorial problems; two insights have arisen during my investigations.
Firstly, that a decent object-oriented / ADT programming environment greatly facilitates the implementation and useability of such tools.
Secondly, recursion -- hoary standby of so many programming courses -- and looplessness seem mutually incompatible. Converting one type of algorithm into the other is a process which somehow should be mechanical, but in practice always proves next to impossible in nontrivial situations.
If you have a recursive routine that would be loopless, the cascade of returns when a stack of calls is just at end implies a "loop". If there'd be an instruction "call next level with return address of caller of this level" then you'd be there. Now read up on the BER trick (in TAOCP and/or) the two(?) original papers, and you'll see. I wish that explanation would have been given in TAOCOP (or _anywhere_ else)! One particularly (IMO) nice feature of the subset-lex orders is that they are (often) loopless without O(n) extra storage (BER trick, Knuth calls the array "focus" pointers), not even O(1) extra storage is needed, but O(0), that is, none. Best, jj
Fred Lunnon
[...]