This is a simplification and generalization of Christophe Rhodes' extensible sequence protocol. It is generalized in the sense that it does not rely on the sequence having a stable indexing or finite size (although several operations are not sensible on infinitely large operands). It is simplified in the sense that, these things being irrelevant, there are fewer functions to define (but also an attendant loss of functionality).
There are reimplementations of many CL sequence functions and related. They are generic functions, but methods can only be defined as an optimization; behavior of iterables must be wholly specified by their methods on the protocol functions (see below).
Keyword arguments relating to their nature as sequences have been removed from the general signatures, e.g. from-end. They keep keyword arguments relating their function, e.g. test-not or count. Other keyword arguments, including the sequence arguments, are passed on unmolested to make-iterator, which can do whatever with them.
Some functions have been skipped because they only make sense on ordered sequences: subseq, replace, reverse, mismatch, search, and sort. reduce is not implemented because its from-end argument specifies both an iteration order and an associativity direction; instead there are foldl and foldr. position and etc. are defined, but may return silly results on non-sequences.
The functions map, map-into, concatenate, and merge are available but have a different interface. For example, map takes an "accumulator" as its first argument rather than a type, and an "iterator" object instead of sequences. These are returned by the accumulator and iterator functions respectively. These two functions take an iterable object as their first argument, and keyword arguments valid to make-iterator on that object for the rest, and return encapsulated objects for accumulator and iterator states, as described in the protocol below.
As an example, consider the following code: (map (accumulator nil :from-end t) #'1+ (iterator (vector 4 5 6) :start 1)). The accumulator has a list as its prototype argument, so map will return a list. :from-end t means it will accumulate results in reverse. (iterator (vector 4 5 6) :start 1) will iterate over 5 (because of the :start) and then 6 and then stop. So, first (1+ 5) = 6 is accumulated, then (1+ 6) = 7; now the iterator has run out so map returns its result. Because of :from-end t, this is (7 6) rather than (6 7).
Compiler macros on these functions will expand them into loops when passed arguments of the form (iterator ...) and (accumulator ...). This increases code size but means the encapsulation objects are never consed.
Still working out what it should look like. There are do-iterator and do-iterator-elements exposed at the moment; given an object and an iterator form, they bind a setfable place and a variable (respectively) and then proceed sort of like dolist.
There are basically just two functions. Readers who are total dorks, i.e. know some Haskell or languages even nerdier than Haskell, may recognize them as limited forms of catamorphism and anamorphism respectively.
Unlike extensible sequences, there is no required superclass for "iterable" objects. I have also, at least for now, skipped the "simple" protocol. As such, only one function needs to be defined for an object to be iterable:
Generic Function MAKE-ITERATOR
Syntax: make-iterator object &key => iterator, limit, step, endp, elt, (setf elt)
Arguments and Values:
- iterator - whatever object is convenient.
- limit - ditto.
- step - a function of two arguments: the object and an iterator, which returns an iterator.
- endp - a function of three arguments: the object, an iterator, and the limit, which returns a generalized boolean.
- elt - a function of two arguments: the object and an iterator, which returns an element of the object.
- (setf elt) - a function of three arguments: a new value, the object, and an iterator, which returns the new value.
Description:
Methods on this function implement the iteration protocol. The state of iteration is represented by the returned iterator object; this object is only used as an argument to the other returned functions, so it can be whatever. The limit represents some kind of marker for detecting the iteration being complete.
An iteration proceeds as follows. First, endp is called to see if the iteration is complete; if it is, calling any of the three functions on that iterator has undefined consequences (i.e. the implementor need not care). Then, elt can be used to retrieve the "current" element of the object, whatever that means for the given iteration; similarly (setf elt) can be used to change the current element. Finally, a new iterator object is returned from a call to the step function and the process repeats.
make-iterator methods can take arbitrary keys. For example, a sequence may take start, end, and from-end keyword arguments so that a subsequence and order may be specified without additional consing. A hash table might take an indicator for whether keys or values are the "elements" being considered.
The protocol is designed to minimize consing; thus the multitudinous return values rather than just returning closures.
Rather than the extensible sequences' make-sequence-like and adjust-sequence functions, which generally expect the object to have a size, here there is instead an "accumulation" protocol. An accumulator is an object in the process of being built up; for example for a list, you could use the common idiom of maintaining a head and then a tail, which is set to fresh conses in its cdr repeatedly.
Generic Function MAKE-ACCUMULATOR
Syntax: make-accumulator object &key => accumulator, index, accumulate, finalize
Arguments and Values:
- accumulator - whatever object is convenient.
- index - ditto.
- accumulate - a function of three arguments: a new value, the accumulator, and the index, which returns a new index.
- finalize - a function of two arguments: the accumulator, and the index, which returns a completed object.
Description:
Defines the protocol for building up an object. object serves as a prototype, i.e. an object of the same type will be constructed, but object's elements are probably not relevant.. accumulate is repeatedly called with new values to add to the object. Once all values have been added, finalize is called and returns a completed object; after this, calling either function may result in undefined behavior.
make-accumulator methods should be prepared to accept any keyword arguments that are allowed for the make-iterator method on the same object, but they may be interpreted differently or simply ignored. For example, a start keyword argument would not stop an accumulated sequence from starting at zero, but in concert with an end argument may define the initial size for the accumulated sequence.