[bitc-dev] Iterators

[Hannes Mehnert]

Hi,


I suggest the paper from Olin Shivers "The anatomy of a loop: a story of
scope of control" (http://portal.acm.org/citation.cfm?id=1086368).

Your suggested iterator is implemented similarly in Dylan, called
forward-iteration-protocol there,
http://www.opendylan.org/books/drm/Collections_Overview#HEADING-60-4
http://www.opendylan.org/books/drm/Collection_Operations#IX-1846
(syntax of for
http://www.opendylan.org/books/drm/Rewrite_Rule_Examples#HEADING-86-13).

The forward-iteration-protocol returns eight values. The returned
functions (next-state, current-element) need a state as argument, which
you have to pass around.

Basic iteration (for is translated to a call to f-i-p by the for-macro):
  let mylist = #(1, 2, 3, 4);
  for (x in mylist)
    format-out("%=\n", x);
  end;

Loop all even elements of a list, using f-i-p:
  let mylist = #(1, 2, 3, 4);
  let (init, limit, next, end?, key, elt)
    = forward-iteration-protocol(mylist);
  for (x = init then next(mylist, next(mylist, x)),
       until: end?(mylist, x, limit))
    let ele = elt(mylist, x);
    format-out("%=\n", ele);
  end;

or:
  let myvector = #[1, 2, 3, 4];
  for (i from 0 below myvector.size by 2)
    format-out("%=\n", myvector[i]);
  end;



Hannes

Jonathan S. Shapiro wrote:
> So I was scratching my head about iterators, and I don't see why
> something like the following would not work.
> 
> An iterator is a structure or capsule having methods value(), next(),
> and hasNext().  value() returns the value at the current "position".
> next() returns an iterator over the "rest" of the collection.
> hasNext() tests for termination.
> 
> Given a construct like this, "forall" is simply a procedure that
> applies a function to all values:
> 
>    forall: (fn (by-ref (Iterator 'a)) (fn 'a -> ()) -> ())
> 
> I'ld have to scratch my head a second about "fold", but I'm sure it's
> comparably straightforward. The main issue here is to ensure that
> appropriate inlining happens so that the higher-order nature of the
> construct gets compiled out appropriately.
> 
> shap