## The Iteration Protocol

All collections implement aniteration protocolthat allows iteration to be specified abstractly. Many higher level operations on collections can be defined in terms of only the iteration protocol.The iteration protocol centers on the notion of a "state" object for an iteration. Each collection class chooses its own most appropriate representation for an iteration state, and only the functions of the iteration protocol are affected by this choice.

Use of the iteration protocol is based on the assumption that the collection over which iteration occurs remains static for the duration of the iteration. That is, arbitrary changes to a mutable collection while an iteration is in progress may cause the iteration to produce incorrect results.

In general, two or more iterations over the same collection are not guaranteed to produce the same values in the same order, even if the collection is unaltered (but see the next section on Iteration Stability).

The iteration protocol consists of the following two functions:

forward-iteration-protocolcollection[Generic Function]

=>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 eight values returned by this function are used to implement iteration over the

collectionargument. Only thecollectionargument this function was called with may be used as thecollectionargument to functions returned by this function. Only theinitial-stateobject and state objects returned by thenext-stateandcopy-statefunctions may be used as thestateargument to functions returned by this function. Only thelimitobject may be used as thelimitargument to thefinished-state?function.

initial-stateThe initial iteration state object.

limitA value that may be used by the

finished-state?function to determine whether the iteration has been completed.

next-statecollection state=>new-stateThis function "steps" the iteration by producing a new state from the associated

collectionandstate.Thenext-statefunction may or may not modify thestateargument; it is an error to use a state value after it has been passed to the associatednext-statefunction. Thecopy-statefunction provides a mechanism for saving a particular state in an iteration for later resumption.

finished-state?collection state limit=>booleanThis function returns

#tif the iteration of the collection has been completed, i.e., there are no other elements of the collection to consider. It returns#fotherwise. It is an error to use a finished state in a call to the associatednext-state,current-element,current-keyorcurrent-element-setterfunctions.

current-keycollection state=>keyThis function returns the unique key associated with

statein thecollection. If thecurrent-keyfunction were called once with eachstatevalue produced during an iteration over a collection, the resulting sequence of values would contain every key from the collection exactly once.

current-elementcollection state=>elementThis function returns the element of

collection"currently indicated" bystate.

current-element-settervaluecollection state=>valueThis function sets the element of

collectionindicated bystatetovalueand returnsvalue.If the collection is not mutable, i.e. is not a generalized instance of<mutable-collection>, this function instead signals an error.

copy-statecollection state=>new-stateThis function returns a state which represents the same point in the iteration over

collectionas is represented bystate.

backward-iteration-protocolcollection[Generic Function]

=>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 eight values returned by this function are analogous to the corresponding values returned byforward-iteration-protocol, except that thefinal-stateobject indicates the last element in the collection and theprevious-statereturns a state for the preceding element.An example of the use of the iteration protocol is the following definition of a single-argument version of the

dofunction: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;## The Table Protocol

Tables, also known as hashtables, map arbitrary keys to elements. Table keys may be any object, including complex objects such as strings. Each table has an associatedequivalence predicatewhich is used to compare keys. The table maps keys that are equivalent under the predicate to the same table element.An equivalence predicate is a boolean function of two arguments that returns true if and only if the arguments are "the same" according to some specified criteria. For a function to be used as an equivalence predicate, it must be reflexive, commutative, and transitive. That is, for a function F and any arguments X, Y, and Z in the domain of F, it must be true that (1) F(X,X) is true, (2) F(X,Y) is true if and only if F(Y,X) is true, and (3) if both F(X,Y) and F(Y,Z) are true then F(X,Z) is true.

An

equivalence class(for an equivalence predicate) is a set of objects, or potential objects, that are all the same under the specified equivalence predicate and different from all objects not in the class. (This "class" is not meant to refer to Dylan classes as indefine class.)An object is said to be

visibly modifiedwith respect to an equivalence predicate if the modification changes the equivalence class of the object. The modifications that are visible to an equivalence predicate are determined by the definition of the predicate.If an object X is a key in a table T and is visibly modified with regard to the test function of T, then the consequences are unspecified if any of the following objects are used as a key in any subsequent operations on T:

Each table also has an associated

- The original object, X.
- Some object Y that is in the same equivalence class (as determined by the test function) as X prior to the modification of X.
- Some object Z that is in the same equivalence class (as determined by the test function) as X after the modification of X.
hash function, which is a function that relates table keys and table elements by computinghash codes. A hash code is a conceptual object consisting of ahash idand its associatedhash state. (It is not an actual Dylan object.) A hash id is an integer encoding of an object. A hash state is an object of implementation-dependent type which is associated with a particular hash id and can be used by the implementation to determine whether the hash id has been invalidated. All hash functions have one argument, a key, and return two values, a hash id and a hash state, which together represent the hash code.Each hash function is associated with a specific equivalence predicate, and must obey the following constraints:

In addition, a hash function should have the property that the hash ids computed by it are well distributed over the range of possible values. That is, it should be unlikely that two randomly chosen equivalence classes have the same valid hash id.

- The domain of the hash function must include the domain of valid arguments to the corresponding equivalence predicate. A hash function need not be defined for all Dylan objects, only those which are acceptable as arguments to the equivalence predicate.
- All objects in a given equivalence class have the same (
=) valid hash id, where validity is determined from the associated hash state.

table-protocoltable[Generic Function] =>test-function hash-function

The class<table>provides an implementation of the Iteration Protocol, using the functiontable-protocol. Every concrete subclass of<table>must provide or inherit a method fortable-protocol.table-protocolreturns the following functions:

test-functionkey1 key2=>booleanThe

test-functionis used to compare keys. It returns true if the keys are members of the same equivalence class according to the table's equivalence predicate.

hash-functionkey=>idstateThe

hash-functioncomputes the hash code of thekey, using the hash function associated with the table's equivalence predicate. The hash code is returned as two values,id(an integer) andstate(a hash state).Users can choose either to define a new subclass of

<table>for every test function they use, or to define a generic subclass of<table>which holds its test function and hash function in slots, according to their particular needs.

table-protocolobject-table[G. F. Method] =>test-function hash-function

The method for<object-table>returns==as thetest-functionandobject-hash(described below) as thehash-function. It could be written asdefine method table-protocol (table :: <object-table>) => test-function :: <function>, hash-function :: <function>; values(\==, object-hash); end method table-protocol;

merge-hash-codesid1 state1 id2 state2#keyordered[Function]

=>merged-id merged-stateThis function computes a new hash code by merging the argument hash codes in some implementation dependent way.

id1,id2, andmerged-idare all integers.state1,state2, andmerged-stateare all hash states.orderedis a boolean and determines whether the algorithm used to perform the merge is permitted to be order dependent. If#f, which is the default, then the merged result must be independent of the order in which the argument pairs are provided. If true, then the order of the argument pairs matters because the algorithm used need not be either commutative or associative in this case. Providing a true value fororderedis recommended when doing so will not cause the hash function to violate the second constraint on hash functions, because it may result in a better distribution of hash ids.

[Constant]$permanent-hash-state

An implementation-dependent hash state that indicates that the associated hash id is always valid, and does not depend on any mutable property of the object that can be changed without a visible modification to the object.

object-hashobject=>id state[Function]

This is the hash function for the equivalence predicateNext section: Iteration Stability and Natural Order==. It is made available as a tool for writing hash functions in which the object identity of some component of a key is to be used in computing the hash code. It returns a hash id (an integer) and associated hash state for the object, computed in some implementation dependent manner. The values returned byobject-hashwhen called repeatedly on the same object might not be the same for each call. If theidvalue changes then thestatevalue will also change.