InternalizeExternalIterators

Last edit April 4, 2012

InternalIterators are convenient. They take up very little space, they reveal the intention of the code and they provide a mechanism for localizing and reusing the code that lives in their function parameters. They are also inflexible, however. They cannot iterate over more than one collection at a time, they cannot be paused or stopped in the middle and they can only implement a single traversal strategy. ExternalIterators, on the other hand, can do all of these things. Unfortunately, they are dumb, they must be told every step to be taken even though they are almost always told to do the exact same thing. What we would like is the ability to easily and compactly express our intention the way we can with InternalIterators while still having the degree of control provided by ExternalIterators.

Therefore:

InternalizeExternalIterators by using ExternalIterators to implement InternalIterators. Collections implement a set of standard InternalIterators that allow most normal traversals: forward, reverse, MapFunction, FoldFunction, etc. But they also provide ExternalIterators that allow more exotic iterations to be implemented. These algorithms are implemented as InternalIterators so that they can be used just like the standard InternalIterators. They can be implemented as member functions in a class derived from the collection (in which case the ExternalIterators can have "protected" access), as free functions, as GenericFunctions that implement ExternalPolymorphism, or as traits (http://www.iam.unibe.ch/~scg/Research/Traits/). Does this have anything to do with TraitsTemplates?

DylanLanguage has this pattern. Collections provide methods for forward-iteration-protocol, reverse-iteration-protocol, and, if appropriate, table-protocol. These return a group of functions that provided the normal iterator functionality - initial-state, next-state, finished-state?, current-element, and current-element-setter. Algorithms can use these to iterate through the collection, but rarely do.

Instead, they use the InternalIterators defined in terms of these iteration protocols. Dylan provides methods for do, map (& map-into, map-as, etc.), reduce, choose, etc. Most programs use these instead of the internal iterators for most collection operators.

If your language supports coroutines, light-weight processes, continuations, or other such beasts, you can also externalize an InternalIterator. In such cases, the Therefore: equals Maybe, depending on other tradeoffs:

Here's how you can externalize an internal iterator in Scheme:

  (define (externalize iterator)
    (letrec ((iterator-return #f)
	     (produce-next-value
	       (lambda (dummy)
		 (iterator
		   (lambda (value)
		     (call-with-current-continuation
		       (lambda (cc)
			 (set! produce-next-value cc)
			 (iterator-return (list value))))))
		 (iterator-return '()))))
      (lambda ()
	(call-with-current-continuation
	  (lambda (return)
	    (set! iterator-return return)
	    (produce-next-value 'dummy))))))

Example use, response of the Scheme system prepended with ==>.

  (define (internal-iterator f)
     (f 1)
     (f 2)
     (f 3)
     (f 4))

  (define external-iterator (externalize internal-iterator))

  (external-iterator)
  ==> (1)
  (external-iterator)
  ==> (2)
  (external-iterator)
  ==> (3)
  (external-iterator)
  ==> (4)
  (external-iterator)
  ==> ()

This is a nice example, but should be moved to ExternalIterationUsingContinuations.

CategoryObjectFunctionalPatterns