Previous chapter: #25: Exit Extent (Change)

Dylan Design Notes

Dylan Design Notes: #26: New Iteration Protocol (Change)

#26: New Iteration Protocol (Change)

Version 1, January 1994 Copyright (c) 1993-1994, Apple Computer
This Design Note specifies a revised iteration protocol for Dylan. The new iteration protocol is complex, but allows better performance than the original specification. Note that the iteration protocol is intended to be used primarily by creators of new collection classes, rather than by users of collections. In practice, most iterations will be hidden inside for and the other standard iteration functions.
Remove the following functions from the language.
initial-state
next-state
current-element
copy-state
current-key
final-state
previous-state
Add the following functions to the language:
forward-iteration-protocol collection  [Generic  Function]
        #values (initial-state          <object>)
                (limit                  <object>)
                (next-state             <function>)
                (finished-state?        <function>)
                (current-key            <function>)
                (current-element        <function>)
                (current-element-setter <function>)
                (copy-state             <function>)
The values returned by this function are used to implement iteration over the collection argument. Only the collection argument this function was called with may be used as the collection argument to functions returned by this function. Only the initial-state object and state objects returned by the next-state and copy-state functions may be used as the state argument to functions returned by this function. Only the limit object may be used as the limit argument to the finished-state? function.
initial-state
The initial iteration state object.
limit
A value that may be used by the finished-state? function to determine whether the iteration has been completed.
next-state collection state => new-state
This function steps the iteration by producing a new state from the associated collection and state. The next-state function may or may not modify the state argument; it is an error to use a state value after it has been passed to the associated next-state function. The copy-state function provides a mechanism for saving a particular state in an iteration for later resumption.

finished-state? collection state limit => boolean
This function returns #t if the iteration of the collection has been completed, i.e., there are no other elements of the collection to consider. It returns #f otherwise. It is an error to use a finished state in a call to the associated next-state, current-element, current-key or current-element-setter functions.
current-key collection state => key
This function returns the unique key associated with state in the collection. If the current-key function were called once with each state value produced during an iteration over a collection, the resulting sequence of values would contain every key from the collection exactly once.
current-element collection state => element 
This function returns the element of collection currently indicated by state.

current-element-setter collection state value => value
This function sets the element of collection indicated by state to value and returns value. If the collection is not mutable, i.e. is not a generalized instance of <mutable-collection>, this function instead signals an error.
copy-state collection state => new-state
This function returns a state which represents the same point in the iteration over collection as is represented by state.
backward-iteration-protocol collection  [Generic  Function]
        #values (final-state            <object>)
                (limit                  <object>)
                (previous-state         <function>)
                (finished-state?        <function>)
                (current-key            <function>)
                (current-element        <function>)
                (current-element-setter <function>)
                (copy-state             <function>)
Some collection classes that are stable under iteration additionally support the ability to iterate in the reverse of the natural order, by providing a method on the generic function backward-iteration-protocol. The values returned by this function are analogous to the corresponding values returned by forward-iteration-protocol, except that the final-state object indicates the last element in the collection and the previous-state returns a state for the preceding element.

Reworked examples appear below.

Example from p.123

define method do1 (f :: <function>, c :: <collection>)
  let (init, limit, next, end?, key, elt) = 
forward-iteration-protocol(c);
  for (state = init then next(c, state),
            until end?(c, state, limit))
    f(elt(c, state));
  end for;
end method do1;

Examples from p.125

define method key-sequence (c :: <collection>)
  let (init, limit, next, end?, key, elt) = 
forward-iteration-protocol(c);
  for (result = #() then pair(key(c, state), result),
            state = init then next(c, state),
            until end?(c, state, limit))
  finally
    result
  end for;
end method key-sequence;

define method do-with-keys
                (f :: <function>, c :: <explicit-key-collection>)
  let (init, limit, next, end?, key, elt) = 
forward-iteration-protocol(c);
  for (state = init then next(c, state),
            until end?(c, state, limit))
         f(key(c, state), elt(c, state));
  end for;
end method do-with-keys;

Examples from p.126

define method do-with-keys (f :: <function>, c :: <sequence>)
  let (init, limit, next, end?, key, elt) = 
forward-iteration-protocol(c);
  for (key :: <integer> from 0,
            state = init then next(c, state),
            until end?(c, state, limit))
         f(key, elt(c, state));
  end for;
end method do-with-keys;

define constant no-default = pair(#f, #f);

define method element (c :: <explicit-key-collection>, elt-key,
                                  #key default: default (no-default))
  let (init, limit, next, end?, key, elt) = 
forward-iteration-protocol(c);
  for (state = init then next(c, state),
            until (end?(c, state, limit) | (key(c, state) = elt-key)))
  finally
         if (!end?(c, state, limit)) elt(c, state);
         else if (default == no-default) error(...);
           else default;
      end if;
    end if;
  end for;
end method element;

define method element (c :: <sequence>, elt-key,
                                  #key default: default (no-default))
  let (init, limit, next, end?, key, elt) = 
forward-iteration-protocol(c);
  for (index from 0,
            state = init then next(c, state),
            until (end?(c, state, limit)) | (index == elt-key)))
  finally
    if (!end?(c, state, limit)) elt(c, state);
    else if (default == no-default) error(...);
           else default;
      end if;
    end if;
  end for;
end method element;

Examples from p.128

define method element-setter
                (c :: <mutable-sequence>, elt-key :: <integer>, new-value)
  let (init, limit, next, end?, key, elt, setter)
                = forward-iteration-protocol(c);
  for (index :: <integer> from 0,
            state = init then next(c, state),
            until ((index == elt-key) | end?(c, state, limit)))
  finally
    if (end?(c, state, limit)) error(...);
    else setter(c, state, new-value);
    end if;
  end for;
end method element-setter;

define method element-setter
                (c :: <mutable-explicit-key-collection>, elt-key, new-value)
  let (init, limit, next, end?, key, elt, setter)
                = forward-iteration-protocol(c);
  for (state = init then next(c, state),
            until (end?(c, state, limit) | (key(c, state) = elt-key)))
  finally
         if (end?(c, state, limit)) error(...);
         else setter(c, state, new-value);
         end if;
  end for;
end method element-setter;

Examples from p.129

define method do2 (f :: <function>, c1 :: <collection>, c2 :: 
<collection>)
  let keys = intersection(key-sequence(c1), key-sequence(c2));
  let (init, limit, next, end?, key, elt)
                = forward-iteration-protocol(keys);
  for (state = init then next(keys, state),
            until end?(keys, state, limit))
    let key = elt(keys, state);
    f(c1[key], c2[key]);
  end for;
end method do2;

define method do2 (f :: <function>, c1 :: <sequence>, c2 :: <sequence>)
  let (init1, limit1, next1, end1?, key1, elt1)
                = forward-iteration-protocol(c1);
  let (init2, limit2, next2, end2?, key2, elt2)
                = forward-iteration-protocol(c2);
  for (state1 = init1 then next1(c1, state1),
            state2 = init2 then next2(c2, state2),
            until (end1?(c1, state1, limit1) | end2?(c2, state2, limit2)))
    f(elt1(c1, state1), elt2(c2, state2));
  end for;
end method do2;

Examples from p.130

define method map-into1 (target :: <mutable-collection>,
                                    f :: <function>,
                                    source :: <collection>)
  let keys = intersection(key-sequence(target), key-sequence(source));
  let (init, limit, next, end?, key, elt)
                = forward-iteration-protocol(keys);
  for (state = init then next(keys, state),
            until end?(keys, state, limit))
    let key = elt(keys, state);
    target[key] := f(source[key]);
  end for;
end method map-into1;

define method map-into1 (target :: <mutable-sequence>,
                                    f :: <function>,
                                    source :: <sequence>)
  let (init1, limit1, next1, end1?, key1, elt1, setter)
                = forward-iteration-protocol(target);
  let (init2, limit2, next2, end2?, key2, elt2)
                = forward-iteration-protocol(source);
  for (state1 = init1 then next1(target, state1),
            state2 = init2 then next2(source, state2),
            until (end1?(target, state1, limit1) |
              end2?(source, state2, limit2)))
    setter(target, state1, f(elt2(source, state2)));
  end for;
end method map-into1;

Some new examples, for <list> and <vector>:

define method forward-iteration-protocol (c :: <vector>)

  local method next-state(c, s :: <integer>) => s :: <integer>;
          s + 1;
        end method;
  local method finished-state?(c, s :: <integer>, l :: <integer>)
          s >= l;
        end method;
  local method current-key(c, s :: <integer>) => k :: <integer>;
          s;
        end method;
  local method current-element(c :: <vector>, s :: <integer>)
          c[s];
        end method;
  local method current-element-setter(c :: <vector>,
                                      s :: <integer>,
                                      e)
          c[s] := e;
        end method;
  local method copy-state(c, s :: <integer>) => s :: <integer>;
          s;
        end method;
  values(0,     # initial state
         size(c),       # limit
         next-state,
         finished-state?,
         current-key,
         current-element,
         current-element-setter,
         copy-state);
end method;

define method backward-iteration-protocol (c :: <vector>)
  local method previous-state(c, s :: <integer>) => s :: <integer>;
          s - 1;
        end method;
  local method finished-state?(c, s :: <integer>, l :: <integer>)
          s < 0;
        end method;
  local method current-key(c, s :: <integer>) => k :: <integer>;
          s;
        end method;
  local method current-element(c :: <vector>, s :: <integer>)
          c[s];
        end method;
  local method current-element-setter(c :: <vector>,
                                      s :: <integer>,
                                      e)
          c[s] := e;
        end method;
  local method copy-state(c, s :: <integer>) => s :: <integer>;
          s;
        end method;
  values(size(c) - 1,   # final state
         0,     # limit (not used)
         previous-state,
         finished-state?,
         current-key,
         current-element,
         current-element-setter,
         copy-state);
end method;

define method forward-iteration-protocol (c :: <list>)
  local method next-state(c, s :: <list>) => s :: <list>;
          tail(s);
        end method;
  # This assumes a dotted list is not valid as a sequence
  local method finished-state?(c, s :: <list>, l :: <list>)
          s == l;
        end method;
  # Use this one to make a dotted list a valid sequence
  local method alternate-finished-state?(c, s :: <list>, l)
          not(instance?(s, <pair>));
        end method;
  local method current-key(c :: <list>, s :: <list>) => k :: <integer>;
          local method search(l :: <list>, k :: <integer>)
            if (l == s) k; else search(tail(l), k + 1); end if;
          end method;
          search(c, 0);
        end method;
  local method current-element(c, s :: <list>)
          head(s);
        end method;
  local method current-element-setter(c, s :: <list>, e)
          head(s) := e;
        end method;
  local method copy-state(c, s :: <list>) => s :: <list>;
          s;
        end method;
  values(c,     # initial state
         #(),   # limit
         next-state,
         finished-state?,
         current-key,
         current-element,
         current-element-setter,
         copy-state);
end method;
# lists do not support backward-iteration-protocol

Notes

The new iteration protocol allows better code quality achieved more easily for iterations where there is sufficient type and sealing information present to allow the various parts of the protocol to be inlined, because the type of the state is not a union type.

The new iteration protocol allows better performance for iterations that have insufficient type and sealing information present to be inlined.

The limit value, which is used as the limit argument to the finished-state? function, allows those collections for which it is appropriate to do so to compute some value once when the protocol functions are determined, rather than recomputing it for each call to the finished-state? function. For some collections it might be the size, while others might ignore this argument. This is increased overhead for <list> iteration (except when the iteration protocol functions end up inlined), but decreased overhead for <simple-object-vector> iteration, especially when the iteration protocol functions end up inlined. In some cases an optimizing compiler could get the same effect in the inlined case through common subexpression removal, but this proposal is also concerned with the efficiency of the non-inlined case.

The iteration protocol functions receive the logically redundant collection and limit arguments so that these functions do not have to be closures, which are more expensive than simple methods both to make and to call in many implementations. This is a compromise of elegance for the sake of efficiency. The state argument would also be logically redundant if the copy-state function did not exist, or if it returned a new set of functions instead of a state.

In addition, a function that tests for the end of an iteration seems more aesthetic than the magical #f value specified in the Dylan book.

Next chapter: #27: Pseudo-Generic Mappers (Change)