Common Lisp Package: TCR.SEQUENCE-ITERATORS

* Required Libraries This library depends on parse-declarations, available at http://common-lisp.net/project/parse-declarations/ * Notes on the API This library has not been publically released yet. The API as described here should be pretty stable, and changes should hopefully only happen as additions. (No guarantee on that, of course.) If you find use of this library, I'm eager to receive feedback about inconveniences or improvements to the API. * Examples There's a presentation available at http://common-lisp.net/~trittweiler/talks/sequence-iterators-2009.pdf which is an introduction to the library, including examples. * Acknowledgements I'd like to thank Paul Khuong and Christophe Rhodes for valuable comments regarding details of the API.

README:

FUNCTION

Public

CANONICALIZE-KEY (KEY-DESIGNATOR)

Canonicalizes `key-designator' to a function object. If `key-designator' is NIL, the IDENTITY function is returned.

CANONICALIZE-TEST (TEST &OPTIONAL TEST-NOT)

Canonicalizes `test' and `test-not' to a function object. If both are given, an error is signaled. If both are NIL, the EQL function is returned.

MAKE-SEQUENCE-LIKE (SEQUENCE LENGTH &REST KEYS &KEY (INITIAL-ELEMENT NIL IEP) (INITIAL-CONTENTS NIL ICP))

Returns a new sequence of length `length' and of the same type as `sequence'. The parameters `initial-element' and `initial-contents' specify how the new sequence is supposed to be initialized. Only one of them can be passed at a time.

VALIDATE-SEQUENCE-BOUNDS (SEQUENCE START END &OPTIONAL LENGTH)

Signals an error of type SEQUENCE-BOUNDING-INDICES-ERROR if `start', and `end' are not valid /bounding indices/ for sequence `sequence'. If `start' is NIL, the bounds are assumed to start at the first element of `sequence'. If `end' is NIL, the bounds are assumed to end at the length of `sequence'. If `length' is NIL, the length of the sequence is computed as by LENGTH. (The purpose of this parameter is to avoid having to compute the length twice if you already had to do so.) This function returns `sequence', and the possibly updated values of `start', `end', and `length'.

Private

%MAKE-SEQUENCE-ITERATOR (SEQUENCE &KEY START END FROM-END)

Returns an iterator thunk that returns three values: a boolean flag that is true, if an element is returned, the current sequence index, and the current sequence element.

ENSURE-FUNCTION (FUNCTION-DESIGNATOR)

Returns the function designated by FUNCTION-DESIGNATOR: if FUNCTION-DESIGNATOR is a function, it is returned, otherwise it must be a function name and its FDEFINITION is returned.

MAKE-GENSYM-LIST (LENGTH &OPTIONAL (X G))

Returns a list of LENGTH gensyms, each generated as if with a call to MAKE-GENSYM, using the second (optional, defaulting to "G") argument.

PARSE-BODY (BODY &KEY DOCUMENTATION WHOLE)

Parses BODY into (values remaining-forms declarations doc-string). Documentation strings are recognized only if DOCUMENTATION is true. Syntax errors in body are signalled and WHOLE is used in the signal arguments when given.

PARSE-ORDINARY-LAMBDA-LIST (LAMBDA-LIST)

Parses an ordinary lambda-list, returning as multiple values: 1. Required parameters. 2. Optional parameter specifications, normalized into form (NAME INIT SUPPLIEDP) where SUPPLIEDP is NIL if not present. 3. Name of the rest parameter, or NIL. 4. Keyword parameter specifications, normalized into form ((KEYWORD-NAME NAME) INIT SUPPLIEDP) where SUPPLIEDP is NIL if not present. 5. Boolean indicating &ALLOW-OTHER-KEYS presence. 6. &AUX parameter specifications, normalized into form (NAME INIT). Signals a PROGRAM-ERROR is the lambda-list is malformed.

REQUIRED-ARGUMENT (&OPTIONAL NAME)

Signals an error for a missing argument of NAME. Intended for use as an initialization form for structure and class-slots, and a default value for required keyword arguments.

Undocumented

%NORMALIZE-DOSEQUENCE-BINDING-ARG (ARG)

%PARSE-DO-SEQUENCE-ITERATORS-CLAUSES (CLAUSES)

%PARSE-DOSEQUENCES-CLAUSES (CLAUSES)

REVERSED-LIST-OF-PTRS (LIST START END)

MACRO

Public

CHECK-SEQUENCE-BOUNDS (SEQ-PLACE START-PLACE END-PLACE &OPTIONAL LENGTH-PLACE &ENVIRONMENT ENV)

This is a convenience wrapper around VALIDATE-SEQUENCE-BOUNDS to automatically assign its return values to the specified places. As the return type of VALIDATE-SEQUENCE-BOUND is known, your Common Lisp implementation may henceforth be able to derive the types of the places.

DO-SEQUENCE-ITERATOR ((VAR ITERATOR &OPTIONAL RESULT) &BODY BODY)

This is a convenience wrapper around DO-SEQUENCE-ITERATORS*.

DO-SEQUENCE-ITERATORS (((VAR ITERATOR &OPTIONAL RESULT) &REST MORE-CLAUSES) &BODY BODY)

DO-SEQUENCE-ITERATORS advances multiple sequence iterators at once. In each iteration, all iterators are run in _parallel_. If no iterator exhausts, the `var's, which may be of the form (`elt' `idx'), will be bound to the elements produced, and `body' is executed. If, however, an iterator exhausts, the `result' form of the clause denoting the exhausted iterator will be evaluated (in an environment where all the variables are still bound to the elements as produced in the previous iteration), and returned. If several iterators exhaust, each respective `result' form will be returned as multiple values (in the order the respective clauses appeared.) `body' is executed in an implicit TAGBODY, and the iteration is performed in an implicit BLOCK named NIL.

DO-SEQUENCE-ITERATORS* (((VAR ITERATOR &OPTIONAL RESULT) &REST MORE-CLAUSES) &BODY BODY)

DO-SEQUENCE-ITERATORS* advances multiple sequence iterators at once. It relates to DO-SEQUENCE-ITERATORS as DO* relates to DO. In each iteration, the iterators are run and checked for exhaustion _sequentially_. For each element produced by the currently executed iterator, the respective `var' is bound to this element. If no iterator exhausts, `body' will be executed. If, however, an iterator exhausts, the iteration will terminate at that point, and the `result' form of the clause denoting the currently executed iterator is evaluated and returned. The form is evaluated in an environment where all the `var's belonging to iterators already executed are bound to the elements produced in the current iteration, and the other variables are bound to the elements produced during the previous iteration. `body' is executed in an implicit TAGBODY, and the iteration is performed in an implicit BLOCK named NIL.

DOSEQUENCE ((VAR SEQUENCE &OPTIONAL RESULT &KEY START END FROM-END PLACE) &BODY BODY &ENVIRONMENT MACRO-ENV)

DOSEQUENCE iterates over the elements of `sequence' with `var' bound to each element in turn, starting from `start' until `end'; if `from-end' is T, the iteration is performed in reverse order. Instead of a symbol, `var' can be a list of two elements (`elt' `index') where `elt' is bound to the current element, and `index' to its index into the sequence. An implicit block named NIL surrounds DOSEQUENCE, hence RETURN may be used to terminate the loop immediately. Otherwise `result' is returned at the end of the loop. `body' is executed in an implicit TAGBODY. `result' is processed at a time where `var' (or `elt') is bound to the last element, and `index' (if given) to the index of the last element. If `place' is given, a /generalized reference/ for `place' is defined within the lexical scope of `body' such that a) an invocation of (`place') will (re)access the current element in the sequence, and such that b) an invocation of (SETF (`place') `new-value') will destructively set the current element in `sequence' to `new-value'. It is unspecified whether the SETF function updates `var' (or `elt', respectively.) Beyond that, CLHS 3.6 applies. The bounding indices `start' and `end' are _not_ checked for validity. It is unspecified whether DOSEQUENCE establishes a new binding for `var' on each iteration, or only establishes one initial binding and assigns to it on subsequent iterations.

DOSEQUENCES* (((VAR SEQUENCE &OPTIONAL RESULT &KEY START END FROM-END PLACE) &REST MORE-CLAUSES) &BODY BODY)

DOSEQUENCES* iterates through multiple sequences at once. Each iterator is run sequentially until one exhausts; the `result' form belonging to the clause of the iterator that exhausts first, is returned. For detailed information on the way the iterators are run, see DO-SEQUENCE-ITERATORS*. For a description of the format of each clause, see DOSEQUENCE.

WITH-SEQUENCE-ITERATOR ((ITERATOR-NAME SEQUENCE &KEY START END FROM-END PLACE) &BODY BODY)

Within the lexical scope of `body', `iterator-name' is defined via FLET such that each successive invocation of (`iterator-name') will yield all the elements of `sequence', one by one, starting from `start' until `end'; if `from-end' is T, in reverse order. The /bounding indices/ `start', and `end' are _not_ checked for validity upfront; to achieve that, use CHECK-SEQUENCE-BOUNDS. Each invocation of the iterator form returns the following three values: 1. A generalized boolean that is true if an element is returned. 2. The element itself. 3. The index of the element in the sequence. If `place' is given, a /generalized reference/ for `place' is defined within the lexical scope of `body' such that a) an invocation of (`place') will (re)access the current element in the sequence, and such that b) an invocation of (SETF (`place') `new-value') will destructively set the current element in `sequence' to `new-value'. Beyond that, CLHS 3.6 applies. Consequences are undefined if `place' is referenced or assigned to before `iterator' has run, or after `iterator' has exhausted. Consequences are undefined if a closure that closes over the iterator form (or `place') is executed outside the dynamic extent of WITH-SEQUENCE-ITERATOR. Consequences are undefined if multiple threads invoke the iterator concurrently.

Private

Undocumented

DEFINE-API (NAME LAMBDA-LIST TYPE-LIST &BODY BODY)

DOLISTS (CLAUSES &BODY BODY)

WITH-SEXP-BUILDER ((START-SYMBOL &REST STUFF) &BODY BODY)

GENERIC-FUNCTION

Public

Undocumented

SEQUENCE-OUT-OF-BOUNDS-ERROR--END (CONDITION)

SEQUENCE-OUT-OF-BOUNDS-ERROR--INDEX (CONDITION)

SEQUENCE-OUT-OF-BOUNDS-ERROR--SEQUENCE (CONDITION)

SEQUENCE-OUT-OF-BOUNDS-ERROR--START (CONDITION)

CONDITION

Public

Undocumented

SEQUENCE-BOUNDING-INDICES-ERROR

SEQUENCE-INDEX-ERROR

SEQUENCE-OUT-OF-BOUNDS-ERROR