GENERIC-CL provides a generic function wrapper over various functions in the Common Lisp standard, such as equality predicates and sequence operations. The goal of this wrapper is to provide a standard interface to common operations, such as testing for the equality of two objects, which is extensible to user-defined classes and structures.

Usage

This library is divided into multiple systems each encapsulating a specific generic interface. The simplest way to use this library is to load the system GENERIC-CL, which loads all the interface subsystems, and use the GENERIC-CL package which exports all symbols in the COMMON-LISP package along with all the generic interface functions. This package should be used instead of COMMON-LISP.

The GENERIC-CL-USER exports all symbols in the CL-USER and GENERIC-CL packages. This package is intended to be used only at the REPL.

Using Specific Interface

If you don’t want to load all the generic interfaces, but only require a specific interface, such as the generic comparability interface, then load only the system which contains that interface and import its package.

The packages generally contain symbols which shadow those in the COMMON-LISP package, thus they cannot simply be used alongside COMMON-LISP. You’ll either have to manually import the shadowing symbols, with :SHADOWING-IMPORT-FROM or use the :MIX option to UIOP:DEFINE-PACKAGE.

The STATIC-DISPATCH-CL package should be used instead of CL in order to be able to optimize generic function calls. See https://github.com/alex-gutev/static-dispatch for more information.
Example: Using SHADOWING-IMPORT-FROM
;; Using comparison interface GENERIC-CL.COMPARISON

(defpackage my-pkg
  (:use :static-dispatch-cl)
  (:shadowing-import-from
    :generic-cl.comparison
    :equalp
    :=
    :/=))
Example: Using UIOP:DEFINE-PACKAGE
(uiop:define-package my-pkg
    (:use) ;; Necessary otherwise CL package is used

  ;; Packages listed earlier on shadow the packages listed after them

  (:mix :generic-cl.comparison
        :static-dispatch-cl)

  ...)

Comparison

System and package name: GENERIC-CL.COMPARISON.

The comparison interface provides functions for comparing objects in terms of equality, greater than, less than, greater than or equal to and less than or equal to relations.

EQUALP is the generic binary equality predicate function to implement for user-defined types. = and /= are the n-ary equality predicates similar to the functions with the same names in the COMMON-LISP package.

LESSP, LESS-EQUAL-P, GREATERP, GREATER-EQUAL-P are the generic binary comparison functions to implement for user-defined types. It is sufficient to just implement LESSP as the remaining functions have default methods that are implemented in terms of LESSP.

<, <=, >, >= are the n-ary comparison functions similar to the functions with the same names in the COMMON-LISP package.

EQUALP

Generic Function: EQUALP A B

Returns true if object A is equal to object B.

Methods
  • NUMBER NUMBER

    Returns true if A and B represent the same numeric value, by CL:=.

  • CHARACTER CHARACTER

    Returns true if A and B represent the same character, by CL:CHAR=.

  • CONS CONS

    Returns true if the CAR of A is equal (by EQUALP) to the CAR of B and if the CDR of A is equal (by EQUALP) to the CDR of B.

  • VECTOR VECTOR

    Returns true if A and B are vectors of the same length and each element of A is equal (by EQUALP) to the corresponding element of B.

  • ARRAY ARRAY

    Multi-dimensional arrays.

    Returns true if A and B have the same dimensions and each element of A is equal (by EQUALP) to the corresponding element of B.

  • STRING STRING

    Returns true if both strings are equal, by CL:STRING=.

  • PATHNAME PATHNAME

    Returns true if both PATHNAME objects are functionally equivalent, by UIOP:PATHNAME-EQUAL.

  • T T

    Default method.

    Returns true if A and B are the same object, by CL:EQ.

LIKEP

Generic Function: LIKEP A B

Returns true if A is similar to B, where similarity is defined as the same as equality however ignoring differences in certain aspects such as case in strings.

Methods
  • CHARACTER CHARACTER

    Returns true if A and B represent the same character ignoring differences in case. Compared using CL:CHAR-EQUAL.

  • CONS CONS

    Returns true if the CAR of A is similar (by LIKEP) to the CAR of B and if the CDR of A is similar (by LIKEP) to the CDR of B.

  • VECTOR VECTOR

    Returns true if A and B are vectors of the same length and each element of A is similar (by LIKEP) to the corresponding element of B.

  • ARRAY ARRAY

    Multi-dimensional arrays.

    Returns true if A and B have the same dimensions and each element of A is similar (by LIKEP) to the corresponding element of B.

  • STRING STRING

    Returns true if both strings are equal, ignoring differences in case. Compared using CL:STRING-EQUAL.

  • T T

    Default method.

    Returns true if (EQUALP A B) returns true.

=

Function: = X &REST XS

Returns true if all objects in XS are equal (by EQUALP) to X.

/=

Function: = X &REST XS

Returns true if at least one object in XS is not equal (by EQUALP) to X.

LESSP

Generic Function: LESSP A B

Returns true if object A is less than object B.

It is sufficient to just implement this function, for user-defined types, as the rest of the comparison functions have default (T T) methods which are implemented in terms of LESSP.
Methods
  • NUMBER NUMBER

    Returns true if the numeric value of A is less than the numeric value of B, by CL:<.

  • CHARACTER CHARACTER

    Returns true if the character code of A is less than the character code of B, by CL:CHAR<.

  • STRING STRING

    Returns true if the string A is lexicographically less than B, by CL:STRING<.

LESS-EQUAL-P

Generic Function: LESS-EQUAL-P A B

Returns true if object A is less than or equal to object B.

Methods
  • NUMBER NUMBER

    Returns true if the numeric value of A is less than or equal to the numeric value of B, by CL:<=.

  • CHARACTER CHARACTER

    Returns true if the character code of A is less than or equal to the character code of B, by CL:CHAR<=.

  • STRING STRING

    Returns true if the string A is lexicographically less than or equal to B, by CL:STRING<=.

  • T T

    Returns true if either A is less than B (by LESSP) or A is equal to B (by EQUALP).

    (or (lessp a b) (equalp a b))

GREATERP

Generic Function: GREATERP A B

Returns true if object A is greater than object B.

Methods
  • NUMBER NUMBER

    Returns true if the numeric value of A is greater than the numeric value of B, by CL:>.

  • CHARACTER CHARACTER

    Returns true if the character code of A is greater than the character code of B, by CL:CHAR>.

  • STRING STRING

    Returns true if the string A is lexicographically greater than B, by CL:STRING>.

  • T T

    Returns true if A is not less than or equal to B, by LESS-EQUAL-P.

    (not (less-equal-p a b))

GREATER-EQUAL-P

Generic Function: GREATER-EQUAL-P A B

Returns true if object A is greater than or equal to object B.

Methods
  • NUMBER NUMBER

    Returns true if the numeric value of A is greater than or equal to the numeric value of B, by CL:>=.

  • CHARACTER CHARACTER

    Returns true if the character code of A is greater than or equal to the character code of B, by CL:CHAR>=.

  • STRING STRING

    Returns true if the string A is lexicographically greater than or equal to B, by CL:STRING>=.

  • T T

    Returns true if A is not less than B, by LESSP.

    (not (lessp a b))

COMPARE

Generic Function: COMPARE A B

Returns:

:LESS

if A is less than B.

:EQUAL

if A is equal to B.

:GREATER

if A is greater than B.

The default T T method returns:

:LESS

if (LESSP A B) is true.

:EQUAL

if (EQUALP A B) is true.

:GREATER

otherwise.

<

Function: < X &REST XS

Returns true if each argument is less than the following argument, by LESSP.

<=

Function: <= X &REST XS

Returns true if each argument is less than or equal to the following argument, by LESS-EQUAL-P.

>

Function: > X &REST XS

Returns true if each argument is greater than the following argument, by GREATERP.

>=

Function: >= X &REST XS

Returns true if each argument is greater than or equal to the following argument, by GREATER-EQUAL-P.

MIN

Function: MIN X &REST XS

Returns the minimum argument.

The comparisons are performed by LESSP. Any one of the arguments which is less than or equal to the other arguments may be returned.

MAX

Function: MAX X &REST XS

Returns the maximum argument.

The comparisons are performed by GREATERP. Any one of the arguments which is greater than or equal to the other arguments may be returned.

Arithmetic

System and package name: GENERIC-CL.ARITHMETIC.

The arithmetic interface provides generic functions for arithmetic operations.

ADD, SUBTRACT, MULTIPLY, DIVIDE are the generic binary arithmetic functions, and NEGATE is the generic unary negation function, to implement for user-defined types.

+, -, *, / are the n-ary arithmetic functions similar to the functions with the same names in the COMMON-LISP package.

ADD

Generic Function: ADD A B

Returns the sum of A and B.

Methods
  • NUMBER NUMBER

    Returns (CL:+ A B).

SUBTRACT

Generic Function: SUBTRACT A B

Returns the difference of A and B.

Methods
  • NUMBER NUMBER

    Returns (CL:- A B).

MULTIPLY

Generic Function: MULTIPLY A B

Returns the product of A and B.

Methods
  • NUMBER NUMBER

    Returns (CL:* A B).

DIVIDE

Generic Function: DIVIDE A B

Returns the quotient of A and B. If A is the constant 1, the result should be the reciprocal of B.

Methods
  • NUMBER NUMBER

    Returns (CL:/ A B).

NEGATE

Generic Function: NEGATE A

Returns the negation of A.

Methods
  • NUMBER

    Returns (CL:- A).

+

Function: + X &REST XS

Returns the sum of all the arguments, computed by reducing over the argument list with the ADD function.

If no arguments are provided, 0 is returned. If a single argument is provided it is returned.

-

Function: - X &REST XS

Returns the difference of all the arguments, computed by reducing over the argument list with the SUBTRACT function.

If only a single argument is provided the negation of that argument is returned, by the NEGATE function.

*

Function: * X &REST XS

Returns the product of all the arguments, computed by reducing over the argument list with the MULTIPLY function.

If no arguments are provided, 1 is returned. If a single argument is provided it is returned.

/

Function: / X &REST XS

Returns the quotient of all the arguments, computed by reducing over the argument list with the DIVIDE function.

If only a single argument is provided, the reciprocal of the argument, (DIVIDE 1 X), is returned.

1+

Generic Function: 1+ A

Returns A + 1.

Methods
  • NUMBER

    Returns (CL:1+ A).

  • T

    Returns (ADD A 1).

1-

Generic Function: 1- A

Returns A - 1.

Methods
  • NUMBER

    Returns (CL:1- A).

  • T

    Returns (SUBTRACT A 1).

INCF

Macro: INCF PLACE &OPTIONAL (DELTA 1)

Increments the value of PLACE by DELTA, which defaults to 1, using the ADD function.

Effectively:

(setf place (add place delta))

DECF

Macro: DECF PLACE &OPTIONAL (DELTA 1)

Decrements the value of PLACE by DELTA, which defaults to 1, using the SUBTRACT function.

Effectively:

(setf place (subtract place delta))

MINUSP

Generic Function: MINUSP A

Returns true if A is less than zero.

Methods
  • NUMBER

    Returns (CL:MINUSP A).

  • T

    Returns true if A compares less than 0, by LESSP.

    (lessp a 0)

PLUSP

Generic Function: PLUSP A

Returns true if A is greater than zero.

Methods
  • NUMBER

    Returns (CL:PLUSP A).

  • T

    Returns true if A compares greater than 0, by GREATERP.

    (greaterp a 0)

ZEROP

Generic Function: ZEROP A

Returns true if A is equal to zero.

Methods
  • NUMBER

    Returns (CL:ZEROP A).

  • T

    Returns true if A is equal to 0, by EQUALP.

    (equalp a 0)

SIGNUM

Generic Function: SIGNUM A

Returns -1, 0 or 1 depending on whether A is negative, is equal to zero or is positive.

Methods
  • SIGNUM

    Returns (CL:SIGNUM A).

  • T

    Returns -1 if (MINUSP A) is true, 0 if (ZEROP A) is true, 1 otherwise.

ABS

Generic Function: ABS A

Returns the absolute value of A.

Methods
  • NUMBER

    Returns (CL:ABS A).

  • T

    If (MINUSP A) is true, returns (NEGATE A) otherwise returns A.

    (if (minusp a)
        (negate a)
        a)

EVENP

Generic Function: EVENP A

Returns true if A is even.

Methods
  • NUMBER

    Returns (CL:EVENP A)

  • T

    Returns (ZEROP (MOD A 2))

ODDP

Generic Function: ODDP A

Returns true if A is odd.

Methods
  • NUMBER

    Returns (CL:ODDP A)

  • T

    Returns (NOT (EVENP A))

FLOOR

Generic Function: FLOOR N D

Performs the division N/D if D is provided, otherwise equivalent to N/1, and returns the result rounded towards negative infinity as the first value, and the remainder N - result * D as the second return value.

Methods
  • NUMBER

    Returns (CL:FLOOR N D) if D is provided otherwise returns (CL:FLOOR N).

CEILING

Generic Function: CEILING N D

Performs the division N/D if D is provided, otherwise equivalent to N/1, and returns the result rounded towards positive infinity as the first value, and the N - result * D as the second return value.

Methods
  • NUMBER

    Returns (CL:CEILING N D) if D is provided otherwise returns (CL:CEILING N).

TRUNCATE

Generic Function: TRUNCATE N D

Performs the division N/D if D is provided, otherwise equivalent to N/1, and returns the result rounded towards zero as the first value, and the remainder N - result * D as the second return value.

Methods
  • NUMBER

    Returns (CL:TRUNCATE N D) if D is provided otherwise returns (CL:TRUNCATE N).

ROUND

Generic Function: ROUND N D

Performs the division N/D if D is provided, otherwise equivalent to N/1, and returns the result rounded towards the nearest integer as the first value, and the remainder N - result * D as the second return value.

If the result lies exactly halfway between two integers, it is rounded to the nearest even integer.

Methods
  • NUMBER

    Returns (CL:ROUND N D) if D is provided otherwise returns (CL:ROUND N).

MOD

Generic Function: MOD N D

Returns the remainder of the FLOOR operation on N and D.

Methods
  • NUMBER

    Returns (CL:MOD N D).

  • T

    Returns the second return value of (FLOOR N D).

REM

Generic Function: REM N D

Returns the remainder of the TRUNCATE operation on N and D.

Methods
  • NUMBER

    Returns (CL:REM N D).

  • T

    Returns the second return value of (TRUNCATE N D).

Object

System and package name: GENERIC-CL.OBJECT.

The object interface provides miscellaneous functions for manipulating objects, such as copying and type conversions.

COPY

Generic Function: COPY OBJECT &KEY &ALLOW-OTHER-KEYS

Return a copy of OBJECT.

If OBJECT is mutable, by some other functions, then the returned object should be distinct (not EQ) from OBJECT, otherwise the return value may be identical (EQ) to OBJECT.

This function may accept additional keyword arguments which specify certain options as to how the object should be copied. Methods specialized on containers accept a :DEEP keyword parameter, which if provided and is true a deep copy is returned otherwise a shallow copy is returned. If a user-defined type acts as a container or sequence then the COPY method for that type should also accept the :DEEP keyword argument.
Methods
  • CONS

    Returns a new list which contains all the elements in OBJECT. If :DEEP is provided and is true, the list returned contains a copy of the elements, copied using (COPY ELEM :DEEP T).

  • VECTOR

    Returns a new vector which contains all the elements in OBJECT. If :DEEP is provided and is true, the vector returned contains a copy of the elements, copied using (COPY ELEM :DEEP T).

  • ARRAY

    Multi-Dimensional Arrays.

    Returns a new array, of the same dimensions as OBJECT, which contains all the elements in OBJECT. If :DEEP is provided and is true, the array returned contains a copy of the elements, copied using (COPY ELEM :DEEP T).

  • STRUCTURE-OBJECT

    Returns a shallow copy of the structure object, using COPY-STRUCTURE.

  • T

    Simply returns OBJECT.

    This method is provided to allow sequences containing arbitrary objects to be copied safely, without signaling a condition, and to avoid having to write simple pass-through methods for each user-defined type.

    If an object can be mutated, and there is no specialized copy method for it, the constraints of the COPY function are violated.

COERCE

Generic Function: COERCE OBJECT TYPE

Coerce OBJECT to the type TYPE.

The default (T T) method simply calls CL:COERCE.

DEFCONSTANT

Macro: DEFCONSTANT SYMBOL VALUE &OPTIONAL DOCUMENTATION

Ensure that SYMBOL is a constant with a value that is equal, by GENERIC-CL:EQUALP to VALUE.

This means that if SYMBOL already names a constant, at the time of evaluating the DEFCONSTANT form, no condition will be signalled if its value is equal (by GENERIC-CL:EQUALP) to VALUE.

Implemented using ALEXANDRIA:DEFINE-CONSTANT

Container

System and package name: GENERIC-CL.CONTAINER.

The container interface provides generic functions for retrieving elements from containers, such as lists, arrays and hash-tables, and for querying various properties of containers, such as the container’s size.

All the following functions are applicable to both ordered containers, sequences, and unordered containers, such as hash-maps, however some only make sense when applied on sequences.

Creation

The following functions are for creating an empty container suitable for accumulating items using the Collector interface.

CLEARED

Generic Function: CLEARED CONTAINER &KEY &ALLOW-OTHER-KEYS

Return a new empty container of the same type, and with the same properties, as CONTAINER, suitable for accumulating items into it using the collector interface.

Individual methods may accept keyword parameters which specify certain options of the container which is to be created.
Methods
  • LIST

    Returns NIL.

  • VECTOR

    Returns an adjustable vector of the same length as CONTAINER, with the fill-pointer set to 0.

    If the :KEEP-ELEMENT-TYPE argument is provided and is true, the element type of the new vector is the same as the element type of CONTAINER.

MAKE-SEQUENCE-OF-TYPE

Generic Function: MAKE-SEQUENCE-OF-TYPE TYPE ARGS

Return a new empty sequence / container of type TYPE.

ARGS are the type arguments, if any.

The default method creates a built-in sequence of the same type as that returned by:

(make-sequence (cons type args) 0)

SEQUENCE-OF-TYPE

Function: SEQUENCE-OF-TYPE TYPE

Create a new sequence / container of type TYPE, using MAKE-SEQUENCE-OF-TYPE.

If TYPE is a list the CAR of the list is passed as the first argument, to MAKE-SEQUENCE-OF-TYPE, and the CDR is passed as the second argument. Otherwise, if TYPE is not a list, it is passed as the first argument and NIL is passed as the second argument.

Elements

ELT

Generic Function: ELT SEQUENCE INDEX

Return the element at position INDEX in the sequence SEQUENCE.

Methods
  • SEQUENCE T and VECTOR T

    Returns (CL:ELT SEQUENCE INDEX).

  • ARRAY INTEGER

    Multi-Dimensional Arrays.

    Returns (ROW-MAJOR-AREF SEQUENCE INDEX).

  • ARRAY LIST

    Multi-Dimensional Arrays.

    If length of INDEX matches array’s rank, returns (apply #'aref sequence index).

    If INDEX's length is less than the array’s rank, then returns a displaced array whose dimensions are SEQUENCE's unused dimensions (ie (nthcdr (array-dimensions sequence) (length index))) and which shares storage with the subarray of SEQUENCE specificied by INDEX.

(SETF ELT)

Generic Function: (SETF ELT) VALUE SEQUENCE INDEX

Set the value of the element at position INDEX in the sequence SEQUENCE.

Methods
  • T SEQUENCE T and T VECTOR T

    Returns (SETF (CL:ELT SEQUENCE INDEX) VALUE).

  • T ARRAY INTEGER

    Multi-Dimensional Arrays.

    Returns (SETF (ROW-MAJOR-AREF SEQUENCE INDEX) VALUE)

  • ARRAY LIST

    Multi-Dimensional Arrays.

    If length of INDEX matches array’s rank, returns (setf (apply #'aref sequence index) value).

    If INDEX's length is less than the array’s rank, then copies the contents of VALUE to the subarray (see ELT) specified by INDEX and then returns (elt sequence index). VALUE's dimensions must equal the unused dimensions of SEQUENCE (ie (nthcdr (array-dimensions sequence) (length index))).

FIRST

Generic Function: FIRST SEQUENCE

Return the first element in the sequence SEQUENCE.

Implemented for lists, vectors and multi-dimensional arrays. For multi-dimensional arrays, the first element is obtained by ROW-MAJOR-AREF.

The default method is implemented using GENERIC-CL:ELT, i.e. is equivalent to:

(elt sequence 0)

LAST

Generic Function: LAST SEQUENCE &OPTIONAL (N 0)

Return the N'th element from the last element of the sequence SEQUENCE.

N defaults to 0 which indicates the last element. 1 indicates the second to last element, 2 the third to last and so on.

Implemented for lists, vectors and multi-dimensional arrays. For multi-dimensional arrays, the last element is obtained by:

(row-major-aref sequence (- (array-total-size array) 1 n))

The default method is implemented using GENERIC-CL:ELT, i.e. is equivalent to:

(elt sequence (- (length sequence) 1 n))
The behaviour of this function differs from CL:LAST when called on lists, it returns the last element rather than the last CONS cell. The LASTCDR function performs the same function as CL:LAST.

LASTCDR

Function: LASTCDR LIST &OPTIONAL (N 1)

Return the CDR of the N'th CONS cell from the end of the list.

This function is equivalent to the CL:LAST function.

ERASE

Generic Function: ERASE SEQUENCE INDEX

Remove the element at index INDEX from the sequence SEQUENCE.

Destructively modifies SEQUENCE.
Methods
  • VECTOR T

    Shifts the elements following INDEX one element towards the front of the vector and shrinks the vector by one element.

    Signals a TYPE-ERROR if the vector is not adjustable.
This method is not implemented for lists as removing the first element of a list cannot be implemented (efficiently) as a side effect alone.

Container Size

LENGTH

Generic Function: LENGTH CONTAINER

Return the number of elements in the container CONTAINER.

If CONTAINER is an iterator, return the number of remaining elements following the iterator’s position.

This function is implemented for all Common Lisp sequences, returning the length of the sequence (by CL:LENGTH), and multi-dimensional arrays, returning the total number of elements in the array by ARRAY-TOTAL-SIZE.

EMPTYP

Generic Function: EMPTYP CONTAINER

Return true if the container CONTAINER is empty.

Implemented for lists, vectors and multi-dimensional arrays (always returns NIL).

CLEAR

Generic Function: CLEAR CONTAINER

Destructively remove all elements from the container CONTAINER.

Implemented for vectors.

ADJUST-SIZE

Generic Function: ADJUST-SIZE CONTAINER N &KEY ELEMENT

Return a new container with the same elements as CONTAINER however with its size changed to N.

If N is less than the number of elements in CONTAINER, the returned container contains only the first N elements of CONTAINER.

If N is greater than the number of elements in CONTAINER, the returned sequence contains all the elements of CONTAINER with an additional (LENGTH CONTAINER) - N elements initialized to the value of ELEMENT.

Methods are provided for lists and vectors. The default T method, implements this operation using the Iterator and Collector interfaces.

NADJUST-SIZE

Generic Function: NADJUST-SIZE CONTAINER N &KEY ELEMENT

Return a new sequence containing the same elements as CONTAINER however with its size changed to N.

CONTAINER may be destructively modified.

If N is less than the number of elements in CONTAINER, the returned container contains only the first N elements of CONTAINER.

If N is greater than the number of elements in CONTAINER, the returned sequence contains all the elements of CONTAINER with an additional (LENGTH CONTAINER) - N elements initialized to the value of ELEMENT.

Methods are provided for lists and vectors. The default T method, implements this operation using the Iterator and Collector interfaces.

Subsequences

SUBSEQ

Generic Function: SUBSEQ SEQUENCE START &OPTIONAL END

Return a new sequence that contains the elements of SEQUENCE at the positions in the range [START, END).

If SEQUENCE is an iterator, an iterator for the sub-sequence relative to the current position of the iterator is returned.

START is the index of the first element of the subsequence, with 0 indicating the start of the sequence. if SEQUENCE is an iterator, START is the number of times the iterator should be ADVANCE'd to reach the first element of the subsequence.

END is the index of the element following the last element of the subsequence. NIL (the default) indicates the end of the sequence. If SEQUENCE is an iterator, END is the number of times the iterator should be ADVANCE'd till the end position is reached.

Methods
  • SEQUENCE T

    Returns the subsequence using CL:SUBSEQ.

(SETF SUBSEQ)

Generic Function: (SETF SUBSEQ) NEW-SEQUENCE SEQUENCE START &OPTIONAL END

Replace the elements of SEQUENCE at the positions in the range [START, END), with the elements of NEW-SEQUENCE.

The shorter length of NEW-SEQUENCE and the number of elements between START and END determines how many elements of SEQUENCE are actually modified.

See SUBSEQ for more details of how the START and END arguments are interpreted.

Methods
  • SEQEUNCE SEQUENCE T

    Sets the elements of the subsequence using (SETF CL:SUBSEQ).

Iterator

System and package name GENERIC-CL.ITERATOR.

The iterator interface is a generic interface for iterating over the elements of sequences and containers.

Implemented for lists, vectors and multi-dimensional arrays.

Basic Usage
(loop
   with it = (iterator sequence) ; Create iterator for SEQUENCE
   until (endp it)               ; Loop until the iterator's end position is reached
   do
     (something (at it)) ; Do something with the current element
     (advance it))       ; Advance iterator to next element

Base Iterator Type

Structure: ITERATOR

This structure serves as the base iterator type and is used by certain methods of generic functions to specialize on iterators.

All iterators should inherit from (include) ITERATOR, in order for methods which specialize on iterators to be invoked.

A COPY method should be implemented for user-defined iterators.

Iterator Creation

ITERATOR is the high-level function for creating iterators, whereas MAKE-ITERATOR AND MAKE-REVERSE-ITERATOR are the generic iterator creation functions to implement for user-defined sequence types.

MAKE-ITERATOR

Generic Function: MAKE-ITERATOR SEQUENCE START END

Return an iterator for the sub-sequence of SEQUENCE, identified by the range [START, END).

START is the index of the first element to iterate over. 0 indicates the first element of the sequence.

END is the index of the element at which to terminate the iteration, i.e. 1 + the index of the last element to be iterated over. NIL indicates iterating till the end of the sequence.

MAKE-REVERSE-ITERATOR

Generic Function: MAKE-REVERSE-ITERATOR SEQUENCE START END

Return an iterator for the sub-sequence of SEQUENCE, identified by the range [START, END), in which the elements are iterated over in reverse order.

Even though the elements are iterated over in reverse order, START and END are still relative to the start of the sequence, as in MAKE-ITERATOR.

START is the index of the last element to visit.

END is the index of the element following the first element to be iterated over.

ITERATOR

Function: ITERATOR SEQUENCE &KEY (START 0) END FROM-END

Return an iterator for the sub-sequence of SEQUENCE identified by the range [START, END).

START (defaults to 0 - the start of the sequence) and END (defaults to NIL - the end of the sequence) are the start and end indices of the sub-sequence to iterate over (see MAKE-ITERATOR and MAKE-REVERSE-ITERATOR for more a detailed description).

If FROM-END is true a reverse iterator is created (by MAKE-REVERSE-ITERATOR) otherwise a forward iterator is created (by MAKE-ITERATOR).

Mandatory Functions

These functions must be implemented for all user-defined iterators.

AT

Generic Function: AT ITERATOR

Return the value of the element at the current position of the iterator ITERATOR.

The effects of calling this method, after the iterator has reached the end of the subsequence are unspecified.

ENDP

Generic Function: ENDP ITERATOR

Return true if the iterator is at the end of the subsequence, false otherwise.

The end of the subsequence is defined as the the position of the iterator after advancing it (by ADVANCE) from the position of the last element.

If the subsequence is empty ENDP should immediately return true.

The default T method calls CL:ENDP since this function shadows the CL:ENDP function.

ADVANCE

Generic Function: ADVANCE ITERATOR

Advance the position of the iterator to the next element in the subsequence.

After this method is called, subsequent calls to AT should return the next element in the sequence or if the last element has already been iterated over, ENDP should return true.

Optional Functions

Implementing the following functions for user-defined iterators is optional either because a default method is provided, which is implemented using the mandatory functions, or the function is only used by a select few sequence operations.

START

Generic Function: START ITERATOR

Return the element at the current position of the iterator, if the iterator is not at the end of the sequence. Otherwise return NIL.

The default method first checks whether the end of the iterator has been reached, using ENDP, and if not returns the current element using AT.

The default method is equivalent to the following:

(unless (endp iterator)
  (at iterator))

(SETF AT)

Generic Function: (SETF AT) VALUE ITERATOR

Set the value of the sequence element at the iterator’s current position.

The effects of calling this function when, the iterator is past the end of the subsequence are unspecified.
Implementing this function is only mandatory if destructive sequence operations will be used.

ADVANCE-N

Generic Function: ADVANCE-N ITERATOR N

Advance the iterator by N elements.

The position of the iterator, after calling this function, should be equivalent to the position obtained by calling ADVANCE N times.

The default method simply calls ADVANCE, on ITERATOR, N times.

Macros

Macros for iteratoring over a generic sequence. Analogous to CL:DOLIST.

DOSEQ

Macro: DOSEQ (ELEMENT SEQUENCE &REST ARGS) &BODY BODY

Iterate over the elements of a sequence, evaluating a list of forms at each iteration.

The iterator interface must be implemented for the sequence, the elements of which, are being iterated over.
An optimized expansion, which does not use the iterator interface, may be emitted if the type of sequence can be determined at compile-time and there is a MAKE-DOSEQ method for that type.
Arguments
ELEMENT

Name of the variable which receives the value of the current sequence element at each iteration. May also be a list in which case it is interpreted as a destructuring pattern, as if to DESTRUCTURING-BIND, according to which the element is destructured.

ARGS

Remaining arguments passed to the ITERATOR function. The following keyword arguments are recognized :START, :END and :FROM-END.

BODY

List of forms to evaluate at each iteration.

The forms are evaluated in an implicit PROGN, with the variables introduced by ELEMENT visible to these forms. The loop may be terminated early using RETURN-FROM to a NIL block, with the value returned from the DOSEQ form.

The forms may be preceded by one or more declarations.

Returns NIL unless a RETURN-FROM to block NIL is executed in BODY.

DO-SEQUENCES

Macro: DO-SEQUENCES (&REST SEQUENCES) &BODY BODY

Same as DOSEQ however for iterating over multiple sequences simultaneously.

Arguments
SEQUENCES

The sequences over which to iterate and the names of the variables which receive the values of their elements.

Each element is of the form (ELEMENT SEQUENCE &REST ARGS), which corresponds to the ELEMENT, SEQUENCE and ARGS arguments of DOSEQ.

BODY

List of forms to evaluate at each iteration, same as the body argument to DOSEQ

The forms may be preceded by one or more declarations.

DOSEQ!

Macro: DOSEQ! (NAME SEQUENCE &REST ARGS) &BODY BODY

Same as DOSEQ however allows for the sequence elements to be mutated.

The (SETF AT) function must be implemented for the sequence type.
Arguments
NAME

Name of the symbol-macro which expands to the place of the current sequence elements.

The symbol-macro can be used to either reference the element’s value or set the element’s value, using SETF.

ARGS

Remaining arguments passed to the ITERATOR function. The following keyword arguments are recognized :START, :END and :FROM-END.

BODY

List of forms to evaluate at each iteration.

The forms are evaluated in an implicit PROGN, with the symbol-macro introduced by NAME visible to these forms. The loop may be terminated early using RETURN-FROM to a NIL block, with the value returned from the DOSEQ form.

The forms may be preceded by one or more declarations.

Returns NIL unless a RETURN-FROM to block NIL is executed in BODY.

DO-SEQUENCES!

Macro: DO-SEQUENCES! (&REST SEQUENCES) &BODY BODY

Same as DOSEQ! however for iterating over multiple sequences simultaneously.

Arguments
SEQUENCES

The sequences over which to iterate and the names of the variables which receive the values of their elements.

Each element is of the form (NAME SEQUENCE &REST ARGS), which corresponds to the NAME, SEQUENCE and ARGS arguments of DOSEQ.

BODY

List of forms to evaluate at each iteration, same as the body argument to DOSEQ

The forms may be preceded by one or more declarations.

Low-Level Macros

These macros provide access to the iterator’s themselves, used to implement the high-level iteration macros, allowing for greater control over the iteration process.

WITH-ITERATORS

Macro: WITH-ITERATORS (&REST SEQUENCES) &BODY FORMS

Setup the iterator state for iterating over one or more sequences.

WITH-ITER-VALUE and WITH-ITER-PLACE, can be used within this macro to retrieve/set the element pointed to by the iterators and advance their positions.

This macro attempts to determine the type of each sequence and calls MAKE-DOSEQ to generate optimal iterator code for the given sequence types, rather than creating dynamic iterator objects. Falls back to the iterator interface, if the types of the sequences cannot be determined.
Arguments
SEQUENCES

List of sequences to create iterators for.

Each element is of the form (ITER SEQUENCE . ARGS), where ITER is a symbol with which the iterator is identified, SEQUENCE is the form producing the sequence to iterate over, and ARGS are the remaining iteration arguments, interpreted as the keyword arguments to the ITERATOR arguments.

Each ITER is a symbol that identifies the iterator, in WITH-ITER-VALUE and WITH-ITER-PLACE.

Iterator identifiers are in a namespace of their own that is they do not name lexical variables/symbol-macros nor functions/macros.
FORMS

A list of forms evaluated in an implicit TAGBODY, thus symbols are interpreted as tag names.

The WITH-ITER-VALUE macro can be used, within FORMS, to retrieve the current element of the sequence and advance the iterator to the next position.

The WITH-ITER-PLACE macro can be used, within FORMS, both to retrieve and set the value of the current element of the sequence, and advance the iterator to the next position.

The value of the last form is not returned, due to it being evaluated in a TAGBODY, instead NIL is returned. RETURN-FROM, to an outer BLOCK, should be used to return a value from this form.
Whilst the intended use of WITH-ITERATORS is to implement iteration macros, such as DOSEQ, the FORMS are only evaluated once. It is up to the user to implement the actual loop, using the provided TAGBODY facility.

WITH-ITER-VALUE

Macro: WITH-ITER-VALUE (PATTERN ITER) &BODY BODY

Bind the current element of a sequence, pointed to by an iterator, to a variable, and advance the iterator’s position to the next element.

This macro may only be used within the body of a WITH-ITERATORS macro.

The value of the element at the current position of the iterator, identified by ITER, is bound to the variable(s) specified by PATTERN, with the bindings visible to the forms in BODY.

If the iterator is already at the end of the sequence, a non-local jump to the end of the WITH-ITERATORS form, in which the iterator was introduced, is performed.

After binding the values, the position of the iterator is advanced to the next element in the sequence.

Arguments
PATTERN

A binding pattern specifying the variable(s) to which the value of the element, at the current position of the iterator, is bound.

This may either be a symbol, naming a variable, or a list which is interpreted as a DESTRUCTURING-BIND pattern.

ITER

Symbol identifying the iterator, that was given as the ITER argument to a parent WITH-ITERATORS form.

BODY

The body of the WITH-ITER-VALUE form, which consists of a list of forms optionally preceded by a number of declaration expressions.

BODY ::= DECLARATION* FORM*

The forms are evaluated in an implicit PROGN, with the value of the last form returned from the WITH-ITER-VALUE form. The binding(s) introduced by PATTERN are visible to the forms.

If there are no more elements in the sequence, the forms are not evaluated.

WITH-ITER-VALUES

Macro WITH-ITER-VALUES (&REST BINDINGS) &BODY BODY

Like WITH-ITER-VALUE except the values of multiple sequence elements are bound simultaneously.

If one of the iterators has reached the end of its sequence, a non-local jump is performed to the end of the WITH-ITERATORS form corresponding to the first iterator which has reached the end of its sequence.

Arguments
BINDINGS

A list of sequence element bindings as if to WITH-ITER-VALUE, each of the form (PATTERN ITER).

((pattern-1 iter-1) (pattern-2 iter-2) ... (pattern-n iter-n))

This is functionally equivalent to a series of nested WITH-ITER-VALUE forms.

(with-iter-value (pattern-1 iter-1)
  (with-iter-value (pattern-2 iter-2)
    (...
      (with-iter-value (pattern-n iter-n)
        ,@body))))

However unlike simply nesting WITH-ITER-VALUE forms, declarations occurring in BODY are handled properly and associated with the correct WITH-ITER-VALUE form, depending on which variable(s) they apply to.

BODY

The body of the WITH-ITER-VALUES form, which consists of a list of forms optionally preceded by a number of declaration expressions.

BODY ::= DECLARATION* FORM*

The forms are evaluated in an implicit PROGN, with the value of the last form returned from the WITH-ITER-VALUES form. The binding(s) introduced by PATTERN are visible to the forms.

If there are no more elements in at least one of the sequences, the forms are not evaluated.

WITH-ITER-PLACE

Macro: WITH-ITER-PLACE (NAME ITER &OPTIONAL MOREP) &BODY BODY

Bind a symbol to the place, suitable for use with SETF, of the current sequence element.

This macro may only be used within the body of a WITH-ITERATORS macro.

A symbol-macro, with identifier given by NAME, is introduced, which expands to the place, suitable for use with SETF, of the element at the iterator’s current position. This symbol-macro is visible to the forms in BODY.

If the iterator is already at the end of the sequence, a non-local jump to the end of the WITH-ITERATORS form, in which it was introduced, is performed, unless a MOREP variable name is given.

The iterator is also advanced to the next element of the sequence after all forms in BODY are evaluated. However, the iterator is only guaranteed to be advanced on a normal exit from the WITH-ITER-PLACE form. If a non-local jump is performed, via GO, RETURN-FROM or THROW, the iterator might not be advanced.

Arguments
NAME

Identifier of the symbol-macro to introduce.

Unlike in WITH-ITER-VALUE this must be a symbol and cannot be a destructuring pattern.
MOREP

Name of the variable, which is bound to true if there are more elements in the sequence following the iterator’s position, and to NIL if the end of the sequence has been reached.

If given and it is non-NIL, no checks are performed for whether the iterator has reached the end of its sequence, and hence the forms in BODY are not skipped. It is up to the programmer to check the value of this variable and performed whatever logic should be performed upon reaching the end of the sequence.

ITER

Symbol identifying the iterator, that was given as the ITER argument to a parent WITH-ITERATORS form.

BODY

The body of the WITH-ITER-PLACE form, which consists of a list of forms optionally preceded by a number of declaration expressions.

BODY ::= DECLARATION* FORM*

The forms are evaluated in an implicit PROGN, with the value of the last form returned from the WITH-ITER-PLACE form.

If there are no more elements in the sequence, and a MOREP variable has not been given, the forms are not evaluated, and a non-local jump is performed to the end of the WITH-ITERATORS, in which the iterator was introduced..

WITH-ITER-PLACES

Macro WITH-ITER-PLACES (&REST BINDINGS) &BODY BODY

Like WITH-ITER-PLACE except multiple places, for multiple sequences, are bound simultaneously.

If one of the iterators has reached the end of its sequence, and a corresponding MOREP variable has not been given, a non-local jump is performed to the end of the WITH-ITERATORS form corresponding to the first iterator which has reached the end of its sequence.

Arguments
BINDINGS

A list of sequence element place bindings as if to WITH-ITER-PLACE, each of the form (NAME ITER) or (NAME ITER MOREP).

((name-1 iter-1) (name-2 iter-2) ... (name-n iter-n))

This is functionally equivalent to a series of nested WITH-ITER-PLACE forms.

(with-iter-place (name-1 iter-1)
  (with-iter-place (name-2 iter-2)
    (...
      (with-iter-place (name-n iter-n)
        ,@body))))

However unlike simply nesting WITH-ITER-PLACE forms, declarations occurring in BODY are handled properly and associated with the correct WITH-ITER-PLACE form, depending on which variable(s) they apply to.

BODY

The body of the WITH-ITER-PLACES form, which consists of a list of forms optionally preceded by a number of declaration expressions.

BODY ::= DECLARATION* FORM*

The forms are evaluated in an implicit PROGN, with the value of the last form returned from the WITH-ITER-PLACES form. The symbol-macro(s) introduced in BINDINGS are visible to the forms.

DO-ITER-VALUES

Macro DO-ITER-VALUES (&REST ITERS) &BODY BODY

Iterate over the remaining elements following the positions of one or more iterators.

The list of forms in BODY are evaluated at each iteration, until one of the iterators reaches the end of its sequence.

May only be used inside a WITH-ITERATORS form.
ITERS

List of element value bindings.

Each element is of the form (PATTERN ITER), as if to WITH-ITER-VALUE, where PATTERN is the binding pattern, specifying the variable(s) which will receive the value of the current element and ITER is the identifier of the iterator, as given in the ITER argument of the WITH-ITERATORS form.

BODY

The body of the DO-ITER-VALUES form, which consists of a list of forms optionally preceded by a number of declaration expressions.

BODY ::= DECLARATION* FORM*

The forms are evaluated once for each element, after which each iterator is advanced to the next element in its sequence.

This form returns NIL.

When the end of a sequence is reached, a non-local jump to the WITH-ITERATORS form, corresponding to the sequence’s iterator, is performed. Thus any forms following the DO-ITER-VALUES form are skipped.

DO-ITER-PLACES

Macro DO-ITER-PLACES (&REST ITERS) &BODY BODY

Like DO-ITER-VALUES except the bindings to the places, with WITH-ITER-PLACE, are introduced, rather than bindings to the values of the sequence elements.

The list of forms in BODY are evaluated at each iteration, until one of the iterators reaches the end of its sequence.

May only be used inside a WITH-ITERATORS form.
ITERS

List of element place bindings.

Each element is of the form (NAME ITER), as if to WITH-ITER-PLACE, where NAME is the name of the symbol-macro expanding to the element place, and ITER is the identifier of the iterator, as given in the ITER argument of the WITH-ITERATORS form.

BODY

The body of the DO-ITER-PLACES form, which consists of a list of forms optionally preceded by a number of declaration expressions.

BODY ::= DECLARATION* FORM*

The forms are evaluated once for each element, after which each iterator is advanced to the next element in its sequence.

This form returns NIL.

When the end of a sequence is reached, a non-local jump to the WITH-ITERATORS form, corresponding to the sequence’s iterator, is performed. Thus any forms following the DO-ITER-PLACES form are skipped.

DOITERS

Macro: DOITERS (&REST ITERS) &BODY BODY

Iterate over one or more sequences with the sequence iterators bound to variables.

Each element of ITERS is a list of the form (IT-VAR SEQUENCE . ARGS), where IT-VAR is the variable to which the iterator is bound, SEQUENCE is the sequence which will be iterated over and ARGS are the remaining arguments passed to the ITERATOR function.

The bindings to the IT-VAR's are visible to the forms in BODY, which are executed once for each element in the sequence. After each iteration the sequence iterators are ADVANCE'd. The loop terminates when the end of a sequence is reached.

DOITER

Macro: DOITER (ITER &REST ARGS) &BODY BODY

The is the same as DOITERS except only a single sequence is iterated over.

Implemented Interfaces

This interface adds methods, when the system implementing the interface is loaded, specialized on ITERATOR's to the following functions:

LENGTH

Method: LENGTH (ITERATOR ITERATOR)

Returns the number of elements between the iterator’s current position (inclusive) and the end of the iterator’s subsequence.

This is implemented by advancing the iterator (by ADVANCE) till ENDP returns true, thus is a linear O(n) time operation.

More efficient specialized methods are provided for iterators to sequences for which the size is known.

SUBSEQ

Method: SUBSEQ (ITERATOR ITERATOR) START &OPTIONAL END

Returns a subsequence iterator which wraps a copy of the original iterator.

Optimization

The iteration macros, DOSEQ, DOSEQ!, and the corresponding macros for multiple sequences, can be optimized to generate specialized iteration code for a given sequence type so that the creation of iterator objects and the dynamic dispatch involving the iterator methods, can be avoided.

These are implemented in terms of the Low-Level Macros, specifically the WITH-ITERATORS family of macros. WITH-ITERATORS attempts to determine the type of each sequence and calls MAKE-DOSEQ to generate specialized iteration code.

The symbols documented in this section are contained in the GENERIC-CL.ITERATOR.OPTIMIZATION package, which is not exported by GENERIC-CL. Thus it has to be manually imported. It doesn’t contain nay shadowing symbols so it can simply be used.

MAKE-DOSEQ

Generic Function: MAKE-DOSEQ TYPE SEQUENCE ARGS TAG BODY ENVIRONMENT

Generate the WITH-ITERATORS expansion for a sequence of a given type.

Combination

This method has the SUBTYPE method combination, thus each method should have a single qualifier which is interpreted as a type specifier symbol.

When the generic function is called with a given sequence type, passed to the TYPE argument, the method with the most derived type, given in the qualifier, which is a subtype of TYPE is called.

Most derived means that if there are two methods with qualifiers which are a both subtypes of the type given in TYPE, the method with the qualifier that is a subtype of the other method’s qualifier, is called.

CALL-NEXT-METHOD and auxiliary methods are not supported by this combination.
Arguments
TYPE

The full sequence type as determined by the WITH-ITERATORS macro.

SEQUENCE

The form which produces the sequence.

ARGS

Remaining iterator arguments following the sequence.

These should be interpreted as they are in the ITERATOR function, that is the keyword arguments :START, :END and :FROM-END should be supported.

TAG

Name of the tag, in an enclosing TAGBODY form, to jump to, with GO, when the end of the sequence is reached.

BODY

List of forms comprising the body of the WITH-ITERATORS form. These may be preceded by a number of declaration expressions.

ENV

The environment in which the WITH-ITERATORS form is found.

Return Values

Methods of this function should return the following values:

  1. A list of bindings, as if by LET*, which are established before the first iteration and are visible to the body forms of the WITH-ITERATORS form.

    Each binding, in this list, may optional provide the following keyword arguments, after the init-form:

    :CONSTANT

    Flag for whether the variable should be treated as a constant

    If true and the init-form is a constant form, by CONSTANTP, the symbol is bound by SYMBOL-MACROLET, rather than LET*.

    A constant binding may only reference other bindings, preceding it, for which this flag is also true.
  2. The new body of the WITH-ITERATORS form. This body is passed to the MAKE-DOSEQ methods of the other sequences.

  3. A lexical macro definition defining the expansion of the WITH-ITER-VALUE for the sequence’s iterator.

    This should be a list of the form:

    (LAMBDA-LIST . BODY)

    where LAMBDA-LIST is the macro lambda-list and BODY is the macro definition body. A name should not be provided since one is automatically generated.

    The lambda-list should have the following arguments:

    (PATTERN &BODY BODY)

    where PATTERN is the binding pattern, corresponding to the PATTERN argument of WITH-ITER-VALUE, specifying the variable(s) which receive the value of the current sequence element.

    This may either be a symbol, naming a variable, or a list which should be interpreted as a DESTRUCTURING-BIND pattern.

    Use WITH-DESTRUCTURE-PATTERN to automatically support destructuring patterns. This also handles declarations correctly.

    BODY is the list of body forms of the WITH-ITER-VALUE form, corresponding to the BODY argument. These may be preceded by declarations some of which, might apply to variables in outer WITH-ITER-VALUE forms.

    The macro should expand to a form which:

    1. Checks whether the end of the sequence has been reached. If so jumps, using GO, to the tag name given in the TAG argument to MAKE-DOSEQ.

    2. Binds the current sequence element to the variable(s) specified in PATTERN

    3. Advances the position of the iterator to the next element in the sequence

    4. Evaluates the body forms.

    Declarations not applying to the variable(s) in PATTERN, should be placed in a LOCALLY form wrapping the macro expansion, in order for them to be processed by other WITH-ITER-VALUE forms. Additionally the macro should also recognize a body consisting of a single LOCALLY form, and process the declarations in that form as though they occurred directly in the body. WITH-DESTRUCTURE-PATTERN handles this automatically.

  4. A lexical macro definition defining the expansion of WITH-ITER-PLACE for the sequence’s iterator.

    This should be a list of the form:

    (LAMBDA-LIST . BODY)

    where LAMBDA-LIST is the macro lambda-list and BODY is the macro definition body. A name should not be provided since one is automatically generated.

    The lambda-list should have the following arguments:

    (NAME MOREP &BODY BODY)

    where NAME is the name of the symbol-macro to be introduced, expanding to the place of the current position of the iterator, corresponding to the NAME argument of WITH-ITER-PLACE.

    MOREP corresponds to the MOREP argument of WITH-ITER-PLACE, which is the name of the variable receiving a flag for whether there are more elements in the sequence (true), or whether the end of the sequence has been reached (NIL).

    BODY is the list of body forms of the WITH-ITER-PLACE form, corresponding to the BODY argument. These may be preceded by declarations some of which, might apply to symbol-macros introduced by outer WITH-ITER-PLACE forms.

    The macro should expand to a form which:

    1. If MOREP is NIL, checks whether the end of the sequence has been reached. If so jumps, using GO, to the tag name given in the TAG argument to MAKE-DOSEQ. If MOREP is non-NIL binds the variable given in MOREP to true if there are more elements in the sequence, or to NIL if the end of the sequence has been reached.

    2. Creates a lexical symbol-macro, with identifier NAME that expands to the place of the current position of the iterator.

    3. Evaluates the body forms.

    4. Advances the position of the iterator.

    Declarations not applying to the symbol-macro, should be placed in a LOCALLY form wrapping the macro expansion, in order for them to be processed by other WITH-ITER-PLACE forms. Additionally the macro should also recognize a body consisting of a single LOCALLY form, and process the declarations in that form as though they occurred directly in the body. WITH-VARIABLE-DECLARATIONS handles this automatically.

The macro ITER-MACRO, facilitates the creation of these lexical macro definitions, removing the need for multiple nested layers of backquotes. Use this macro when defining your own MAKE-DOSEQ methods.

ITER-MACRO

Macro: ITER-MACRO (&REST VARS) (&REST LAMBDA-LIST) &BODY BODY

Utility macro for generating lexical macro definitions for WITH-ITER-VALUE and WITH-ITER-PLACE.

This macro is intended to be used within MAKE-DOSEQ to facilitate the definition, by avoiding the need for nested backquotes, of the lexical macros, serving as the expansion of WITH-ITER-VALUE and WITH-ITER-PLACE for a given iterator type.

Arguments
VARS

List of variables to capture from the lexical scope of the ITER-MACRO form.

Lexical variables are generated for each variable that is listed, accessible to the definition body, which are set to the values of the equivalent variables evaluated in the scope of the ITER-MACRO form.

LAMBDA-LIST

Macro lambda-list (not evaluated).

BODY

The body of the macro definition, consisting of a list of forms optionally preceded by declaration expressions.

These are not evaluated but are literally inserted in the body of the macro definition. The forms have access to the variables listed in VARS, at the time the macro is expanded.

WITH-DESTRUCTURE-PATTERN

Macro WITH-DESTRUCTURE-PATTERN (VAR PATTERN) (FORMS-VAR DECL-VAR BODY-FORM) &BODY BODY

Automatically generate destructuring code if the binding pattern is a destructuring-bind pattern.

This macro allows a WITH-ITER-VALUE macro to be written whilst focusing only on the case where the binding pattern is a variable receiving the entire element value. The macro automatically generates destructuring code if the binding pattern is a list.

This macro also handles declarations automatically.

Arguments
VAR

Name of the variable receiving the name of the variable to which the element value is bound.

PATTERN

Form producing the binding pattern (evaluated).

FORMS-VAR

Name of the variable receiving the list of body forms of the WITH-ITER-MACRO.

DECL-VAR

Name of the variable receiving the list of declarations applying to the variable in VAR.

BODY-FORM

Form producing the WITH-ITER-VALUE body (evaluated).

BODY

List of forms evaluated in an implicit PROGN. The return value of the last form is returned as the macroexpansion of the WITH-ITER-VALUE, wrapped in the destructuring code if necessary.

May be preceded by declaration expressions.

The expansion returned should bind the variable in VAR to the value of the next element in the sequence and evaluate the forms in FORMS-VAR in the context of that binding.

Declarations

This macro takes care of handling declarations in the result returned by BODY-FORM. The declarations applying to the variables in the destructuring pattern, are inserted in the resulting destructuring-bind form, DECL-VAR is bound to the declarations applying to the variable given in VAR, and the remaining declarations are inserted in a LOCALLY form, wrapping the entire expansion.

WITH-VARIABLE-DECLARATIONS

Macro: WITH-VARIABLE-DECLARATIONS (&REST BINDINGS) FORMS-VAR BODY-FORM &BODY BODY

Split a body into the declarations, applying to specific variables, and its forms.

Intended to be used in the lexical macro definition for WITH-ITER-PLACE for a sequence type.
Arguments
BINDINGS

List of variables for which to extract the declarations.

Each element is of the form (DECL-VAR VAR), where DECL-VAR is the name of the variable which is to receive the list of declarations applying to the variable given by VAR (evaluated).

FORMS-VAR

Name of the variable receiving the list of forms in the body.

BODY-FORM

Form producing the body.

BODY

List of forms evaluated in an implicit PROGN, with the result returned by the last form included in the resulting expansion.

Expansion

The value returned by the macro is a LOCALLY form containing the declarations not applying to any of the variables listed in BINDINGS and the body of which is the form returned by the last form in BODY.

Collector

System and package name GENERIC-CL.COLLECTOR.

The collector interface is a generic interface for accumulating items into a sequence/container.

Implemented for lists and vectors.

While this interface is specified for sequences, it may also be implemented for unordered containers.
Basic Usage
;; Create collector for the sequence, in this case an empty list
(let ((c (make-collector nil)))
  (accumulate c 1)        ; Collect 1 into the sequence
  (accumulate c 2)        ; Collect 2 into the sequence
  (extend c '(3 4 5))     ; Collect 3, 4, 5 into the sequence
  (collector-sequence c)) ; Get the resulting sequence => '(1 2 3 4 5)

MAKE-COLLECTOR

Generic Function: MAKE-COLLECTOR SEQUENCE &KEY FRONT

Return a collector for accumulating items to the end of the sequence SEQUENCE.

If :FRONT is provided and is true, the items are accumulated to the front of the sequence rather than end.

The collector may destructively modify SEQUENCE however it is not required to do so and may accumulate items into a copy of SEQUENCE instead.

ACCUMULATE

Generic Function: ACCUMULATE COLLECTOR ITEM

Accumulate ITEM into the sequence associated with the collector COLLECTOR.

COLLECTOR-SEQUENCE

Generic Function: COLLECTOR-SEQUENCE COLLECTOR

Return the underlying sequence associated with the collector COLLECTOR.

The sequence should contain all items accumulated up to the call to this function.

The effects of accumulating items into the sequence, by ACCUMULATE or EXTEND, after this function is called, are unspecified.
The sequence returned might not be the same object passed to MAKE-COLLECTOR.

EXTEND

Generic Function: EXTEND COLLECTOR SEQUENCE

Accumulate all elements of the sequence SEQUENCE into the sequence associated with the collector COLLECTOR.

If SEQUENCE is an iterator all elements up-to the end of the iterator (till ENDP returns true) should be accumulated.

Implementing this method is optional as default methods are provided for iterators and sequences, which simply accumulate each element one by one using ACCUMULATE.

Methods

  • T ITERATOR

    Accumulates all elements returned by the iterator SEQUENCE (till (ENDP SEQUENCE) returns true), into the sequence associated with the collector.

    The elements are accumulated one by one using ACCUMULATE.

    The iterator is copied thus the position of the iterator passed as an argument is not modified.
  • T T

    Accumulates all elements of SEQUENCE, into the sequence associated with the collector.

    The elements are accumulated one by one using ACCUMULATE.

    The sequence iteration is done using the Iterator interface.

Sequence

System and package name GENERIC-CL.SEQUENCE

Generic sequence operations.

Generic function wrappers, which are identical in behavior to their counterparts in the COMMON-LISP package, are provided for the following sequence operations:

  • FILL

  • REPLACE

  • REDUCE

  • COUNT

  • COUNT-IF

  • COUNT-IF-NOT

  • FIND

  • FIND-IF

  • FIND-IF-NOT

  • POSITION

  • POSITION-IF

  • POSITION-IF-NOT

  • SEARCH

  • MISMATCH

  • REVERSE

  • NREVERSE

  • SUBSTITUTE

  • NSUBSTITUTE

  • SUBSTITUTE-IF

  • NSUBSTITUTE-IF

  • SUBSTITUTE-IF-NOT

  • NSUBSTITUTE-IF-NOT

  • REMOVE

  • DELETE

  • REMOVE-IF

  • DELETE-IF

  • REMOVE-IF-NOT

  • DELETE-IF-NOT

  • REMOVE-DUPLICATES

  • DELETE-DUPLICATES

Two methods are implemented, for all functions, which are specialized on the following types:

  • CL:SEQUENCE

    Simply calls the corresponding function in the COMMON-LISP package.

  • T

    Implements the sequence operation for generic sequences using the Iterator interface.

    The non-destructive functions only require that the Mandatory Iterator Functions, the Collector interface and CLEARED method are implemented for the sequence’s type.

    The destructive versions may additionally require that the optional (SETF AT) method is implemented as well.

The default value of the :TEST keyword argument is GENERIC-CL:EQUALP. This should be the default value when implementing methods for user-defined sequence types. The :TEST-NOT keyword arguments have been removed.

The following functions are identical in behavior to their CL counterparts, however are re-implemented using the iterator interface. Unlike the functions in the previous list, these are not generic functions since they take an arbitrary number of sequences as arguments.

  • EVERY

  • SOME

  • NOTEVERY

  • NOTANY

The following functions either have no CL counterparts or differ slightly in behavior from their CL counterparts:

FIND-IT

Generic Function: FIND-IT ITEM SEQUENCE &KEY FROM-END START END TEST KEY

Find an element in a sequence and return an iterator to the position at which it was found.

This is the same as FIND except it returns an iterator to the position at which an element is found rather than the element itself.

Arguments

ITEM

The item to find in the sequence.

SEQUENCE

The sequence to search.

FROM-END

If true the sequence is searched starting from the end.

START

Index of the starting position from which to search the sequence. By default searches from the start of the sequence.

END

Index of the position till which the sequence is searched. If NIL (the default) the entire sequence is searched.

TEST

Test function to use when comparing ITEM to elements of SEQUENCE. By default EQUALP.

KEY

Function which is applied on each element of SEQUENCE. The result returned is then compared to ITEM using TEST.

If the item was found in the sequence, returns the iterator to the first position, or last if FROM-END is true, at which it was found. If no such item was found, NIL is returned.

The iterator returned should point to the same sequence object that is passed to this function. This is to allow iterating over the remaining elements of the sequence and to allow for modifying the sequence.

FIND-IT-IF

Generic Function: FIND-IT-IF PREDICATE SEQUENCE &KEY FROM-END START END KEY

Find an element, which satisfies a predicate, in a sequence and return an iterator to the position at which it was found.

This is the same as FIND-IF except it returns an iterator to the position at which an element is found rather than the element itself.

Arguments

PREDICATE

A predicate function, of one argument, applied on each element of sequence. The element for which this function returns true, is returned.

SEQUENCE

The sequence to search.

FROM-END

If true the sequence is searched starting from the end.

START

Index of the starting position from which to search the sequence. By default searches from the start of the sequence.

END

Index of the position till which the sequence is searched. If NIL (the default) the entire sequence is searched. SEQUENCE.

KEY

Function which is applied on each element of SEQUENCE. The result returned is then passed to the predicate function.

Returns an iterator to the first item, or last if FROM-END is true, for which the predicate returns true. If no element is found, NIL is returned.

The iterator returned should point to the same sequence object that is passed to this function. This is to allow iterating over the remaining elements of the sequence and to allow for modifying the sequence.

FIND-IT-IF-NOT

Generic Function: FIND-IT-IF PREDICATE SEQUENCE &KEY FROM-END START END KEY

Find an element, which does not satisfy a predicate, in a sequence and return an iterator to the position at which it was found.

This is the same as FIND-IF-NOT except it returns an iterator to the position at which an element is found rather than the element itself.

Arguments

PREDICATE

A predicate function, of one argument, applied on each element of sequence. The element for which this function returns false (NIL), is returned.

SEQUENCE

The sequence to search.

FROM-END

If true the sequence is searched starting from the end.

START

Index of the starting position from which to search the sequence. By default searches from the start of the sequence.

END

Index of the position till which the sequence is searched. If NIL (the default) the entire sequence is searched. SEQUENCE.

KEY

Function which is applied on each element of SEQUENCE. The result returned is then passed to the predicate function.

Returns an iterator to the first item, or last if FROM-END is true, for which the predicate returns false. If no element is found, NIL is returned.

The iterator returned should point to the same sequence object that is passed to this function. This is to allow iterating over the remaining elements of the sequence and to allow for modifying the sequence.

MERGE

Generic Function: MERGE SEQUENCE1 SEQUENCE2 PREDICATE &KEY

Return a new sequence, of the same type as SEQUENCE1, containing the elements of SEQUENCE1 and SEQUENCE2.

The elements are ordered according to the function PREDICATE.

Unlike CL:MERGE this function is non-destructive.

NMERGE

Generic Function: MERGE SEQUENCE1 SEQUENCE2 PREDICATE &KEY

Same as MERGE however is permitted to destructively modify either SEQUENCE1 or SEQUENCE2.

SORT

Generic Function: SORT SEQUENCE &KEY TEST KEY

Return a new sequence of the same type as SEQUENCE, with the same elements sorted according to the order determined by the function TEST.

TEST is GENERIC-CL:LESSP by default.

Unlike CL:SORT this function is non-destructive.
For the default method to be efficient, efficient SUBSEQ and LENGTH methods should be implemented for the iterator type of SEQUENCE.

STABLE-SORT

Generic Function: STABLE-SORT SEQUENCE &KEY TEST KEY

Same as SORT however the sort operation is guaranteed to be stable, that is the relative order of elements of which neither compares less than the other, is preserved.

TEST is GENERIC-CL:LESSP by default.

Unlike CL:STABLE-SORT this function is non-destructive.
For the default method to be efficient, efficient SUBSEQ and LENGTH methods should be implemented for the iterator type of SEQUENCE.

NSORT

Generic Function: NSORT SEQUENCE &KEY TEST KEY

Same as SORT however is permitted to destructively modify SEQUENCE.

STABLE-NSORT

Generic Function: STABLE-NSORT SEQUENCE &KEY TEST KEY

Same as STABLE-SORT however is permitted to destructively modify SEQUENCE.

CONCATENATE

Generic Function: CONCATENATE SEQUENCE &REST SEQUENCES

Return a new sequence, of the same type as SEQUENCE, containing all the elements of SEQUENCE and of each sequence in SEQUENCES, in the order they are supplied.

Unlike CL:CONCATENATE does not take a result type argument.

NCONCATENATE

Generic Function: NCONCATENATE RESULT &REST SEQUENCES

Destructively concatenate each sequence in SEQUENCES to the sequence RESULT.

Returns the result of the concatenation.

Whilst this function is permitted to destructively modify RESULT and SEQUENCES, it is not required and may return a new sequence instead. Thus do not rely on this function for its side effects.

CONCATENATE-TO

Generic Function: CONCATENATE-TO TYPE &REST SEQUENCES

Concatenate each sequence in SEQUENCES into a new sequence of type TYPE.

The new sequence is created by passing TYPE to SEQUENCE-OF-TYPE.

MAP

Generic Function: MAP FUNCTION SEQUENCE &REST SEQUENCES

Create a new sequence, of the same type as SEQUENCE (by CLEARED), containing the result of applying FUNCTION to each element of SEQUENCE and each element of each SEQUENCE in SEQUENCES.

This function is equivalent (in behavior) to the CL:MAP function except the resulting sequence is always of the same type as the first sequence passed as an argument, rather than being determined by a type argument.

NMAP

Generic Function: NMAP RESULT FUNCTION &REST SEQUENCES

Destructively replace each element of RESULT with the result of applying FUNCTION to each element of RESULT and each element of each sequence in SEQUENCES.

Returns the resulting sequence.

Whilst this function is permitted to modify RESULT, it is not required to do so and may return the result in a new sequence instead. Thus do not rely on this function for its side effects.

MAP-INTO

Generic Function: MAP-INTO RESULT FUNCTION &REST SEQUENCES

Apply FUNCTION on each element of each sequence in SEQUENCES and accumulate the result in RESULT, using the Collector interface.

Returns the resulting sequence.

Whilst this function is permitted to modify RESULT, it is not required and may return the result in a new sequence instead. Thus do not rely on this function for its side effects.

MAP-TO

Generic Function: MAP-TO TYPE FUNCTION &REST SEQUENCES

Apply FUNCTION on each element of each sequence in SEQUENCES and store the result in a new sequence of type TYPE (created using SEQUENCE-OF-TYPE).

Returns the sequence in which the results of applying the function are stored.

This function is equivalent in arguments, and almost equivalent in behavior, to CL:MAP. The only difference is that if TYPE is a subtype of vector, the vector returned is adjustable with a fill-pointer. A NIL type argument is not interpreted as do not accumulate the results, use FOREACH for that.

MAP-EXTEND

Generic Function: MAP-EXTEND-TO FUNCTION SEQUENCE &REST SEQUENCES

Apply FUNCTION on each respective element of SEQUENCE, and of each sequence in SEQUENCES, accumulating, using the EXTEND method of the Collector Interface, the elements of the result, which is expected to be a sequence, in a sequence of the same type as SEQUENCE.

The resulting sequence is returned.

MAP-EXTEND-TO

Generic Function: MAP-EXTEND-TO TYPE FUNCTION &REST SEQUENCES

Apply FUNCTION on each respective element of each sequence in SEQUENCES, and accumulate, using the EXTEND method of the Collector Interface, the elements of the result, which is expected to be a sequence, in a sequence of type TYPE, created using SEQUENCE-OF-TYPE.

The resulting sequence is returned.

MAP-EXTEND-INTO

Generic Function: MAP-EXTEND-INTO RESULT FUNCTION &REST SEQUENCES

Apply FUNCTION on each respective element of each sequence in SEQUENCES, and accumulate, using the EXTEND method of the Collector Interface, the elements of the result, which is expected to be a sequence, in the sequence RESULT.

The resulting sequence is returned.

RESULT may be destructively modified, however that is not guaranteed thus this function should only be used for its return value, not its side effects.

FOREACH

Function: FOREACH &REST SEQUENCES

Apply FUNCTION on each element of each sequence in SEQUENCES.

Returns NIL.

Implemented Methods

This interface’s system also defines the following methods of the Container interface, implemented using the Iterator and Collector interfaces.

ELT

Method: ELT (SEQUENCE T) (INDEX T)

Creates an iterator for SEQUENCE, with start position INDEX, and returns the first element returned by the iterator.

(SETF ELT)

Method: (SETF ELT) (VALUE T) (SEQUENCE T) (INDEX T)

Creates an iterator for SEQUENCE, with start position INDEX, and sets the value of the element at the starting position of the iterator.

LENGTH

Method: LENGTH (CONTAINER T)

Returns the size of the container by creating an iterator and calling the LENGTH method specialized on the ITERATOR structure.

This is a linear O(n), in time, operation unless a more efficient method, which is specialized on the containers’s iterator type, is implemented.

EMPTYP

Method: EMPTYP (CONTAINER T)

Returns true if ENDP returns true for a newly created iterator for CONTAINER.

ADJUST-SIZE

Method: ADJUST-SIZE (CONTAINER T) (N T) &KEY ELEMENT

Requires the Iterator and Collector interfaces to be implemented for the container type.

NADJUST-SIZE

Method: NADJUST-SIZE (CONTAINER T) (N T) &KEY ELEMENT

Requires the Iterator and Collector interfaces to be implemented for the container type.

SUBSEQ

Method: SUBSEQ (SEQUENCE T) (START T) &OPTIONAL END

Requires the CLEARED method, the Iterator interface and Collector interface to be implemented for the sequence type.

(SETF SUBSEQ)

Method: (SETF SUBSEQ) (NEW-SEQUENCE T) (SEQUENCE T) (START T) &OPTIONAL END

Requires the Iterator interface to be implemented for both the types of SEQUENCE and NEW-SEQUENCE.

Requires the (SETF AT) method to be implemented for the iterator type of SEQUENCE.

Lazy Sequences

System and package name: GENERIC-CL.LAZY-SEQ

Lazy sequences are sequences in which the elements are only computed when they are actually referenced, rather than being computed immediately.

Lazy sequences are implemented with the LAZY-SEQ structure which is similar to a CONS cell, however the CDR, the TAIL slot of the LAZY-SEQ structure, stores a function which computes and returns the remainder of the sequence, rather than storing the sequence directly.

LAZY-SEQ Structure

Structure: LAZY-SEQ

Lazy sequence cell analogous to a CONS.

Slots
HEAD

The first element of the sequence. Can be accessed with the LAZY-SEQ-HEAD accessor function.

TAIL

A function of zero arguments which returns a LAZY-SEQ containing the remaining elements in the sequence. If there are no more elements the function returns NIL. Can be accessed with the LAZY-SEQ-TAIL accessor function.

Implemented Interfaces:
  • EQUALP function.

  • COPY function. Accepts the :DEEP keyword parameter which indicates whether the elements should also be copied.

  • COERCE function.

  • Mandatory Functions, of the Iterator interface.

  • MAKE-COLLECTOR function of the Collector interface.

    The method specialized on LAZY-SEQ's returns a collector for a LIST since it does not make sense to be collecting items, which have already been evaluated, into a LAZY-SEQ.
  • SUBSEQ function which returns the subsequence as a LAZY-SEQ.

  • Methods, specialized on LAZY-SEQ, are implemented for the following Sequence Operations and their destructive counterparts:

    • REMOVE

    • REMOVE-IF

    • REMOVE-IF-NOT

    • SUBSTITUTE

    • SUBSTITUTE-IF

    • SUBSTITUTE-IF-NOT

    • REMOVE-DUPLICATES

    These methods return a LAZY-SEQ with the sequence operation 'lazily' applied to the sequence.

    The destructive versions are identical to the non-destructive versions.

MAKE-LAZY-SEQ

Function: MAKE-LAZY-SEQ HEAD TAIL

Create a LAZY-SEQ with the HEAD slot initialized to HEAD and the TAIL slot initialized to TAIL.

TAIL must be a function of zero arguments that returns either a LAZY-SEQ containing the remaining elements in the sequence or NIL indicating there are no more elements.
For efficiency the function in TAIL should only compute the remainder of the sequence the first time it is called. Remaining calls to the function should simply return the previously computed result.
The LAZY-SEQ macro automatically wraps the form, which returns the remainder of the sequence, in a function.

LAZY-SEQ Macro

Macro: LAZY-SEQ HEAD &OPTIONAL TAIL

Create a LAZY-SEQ instance with the HEAD slot initialized to HEAD and the TAIL slot initialized to a function which evaluates the form TAIL.

The function only evaluates TAIL the first time it is call. Subsequent calls will simply return the previously computed result.

COERCE Methods

The following COERCE methods are provided which specialize on LAZY-SEQ's.

  • LAZY-SEQ (EQL 'LIST)

    Returns a list containing all the elements in the LAZY-SEQ.

    If the LAZY-SEQ is an infinite sequence, this function will never terminate.

CONCATENATE Methods

Method: CONCATENATE LAZY-SEQ &REST SEQUENCES
Method: NCONCATENATE LAZY-SEQ &REST SEQUENCES
Method: CONCATENATE-TO (EQL 'LAZY-SEQ) &REST SEQUENCES

Concatenates sequences to a lazy sequence.

The concatenation is done lazily, that is the elements of the sequences, in SEQUENCES, are only added to the lazy sequence when elements past the end of the LAZY-SEQ, passed in the first argument, are referenced.

The CONCATENATE-TO method returns a lazy sequence containing the concatenation of SEQUENCES. Like CONCATENATE and NCONCATENATE the concatenation is done lazily.

NCONCATENATE is identical to CONCATENATE, that is the LAZY-SEQ is not destructively modified.

MAP Methods

Method: MAP FUNCTION LAZY-SEQ &REST SEQUENCES
Method: NMAP FUNCTION LAZY-SEQ &REST SEQUENCES
Method: MAP-INTO LAZY-SEQ FUNCTION &REST SEQUENCES
Method: MAP-TO (EQL 'LAZY-SEQ) FUNCTION &REST SEQUENCES

Applies a function on each element of the LAZY-SEQ and of each sequence in SEQUENCES.

The result is a LAZY-SEQ with the function applied lazily to each element, that is it is only applied when that element is referenced.

The MAP-TO method returns the result, of lazily applying the function on each element of each sequence in SEQUENCES, in a LAZY-SEQ.

NMAP and MAP-INTO do not destructively modify the LAZY-SEQ but return a new sequence instead.

Utilities

RANGE

Function: RANGE START &OPTIONAL END STEP

Returns a LAZY-SEQ containing all numbers in the range [START, END).

If END is NIL, an infinite sequence, without an upper bound, is returned.

STEP, defaults to 1, is the delta by which each number is incremented to obtain the next successive number in the sequence.

Generic Hash-Tables

System and package name: GENERIC-CL.MAP

This interface provides a hash-table data structure with the generic function HASH as the hash function and the generic function GENERIC-CL:EQUALP as the key comparison function. This allows the hash-tables to utilize keys of user-defined types, whereas the keys of standard hash tables are limited to numbers, characters, lists and strings.

The generic hash-tables are implemented using CL-CUSTOM-HASH-TABLE. If the Common Lisp implementation supports creating hash-tables with user-defined hash and comparison functions, standard hash-tables are used. However if the implementation does not support user-defined hash and comparison functions, a fallback solution is used, which is a custom hash-table implementation on top of standard hash-tables. The HASH-MAP structure wraps the custom hash-table which allows methods methods to be specialized on a single type HASH-MAP regardless of whether standard or custom hash-tables are used.

The functions in this interface are specialized on the HASH-MAP type, thus this type, created with MAKE-HASH-MAP, should be used rather than built-in hash-tables. If a hash-table is obtained from an external source, use HASH-MAP or ENSURE-HASH-MAP to convert it to a HASH-MAP.

Table 1. Standard Hash-Table Counterparts
CL:HASH-TABLE HASH-MAP

GETHASH

GET

HASH-TABLE-COUNT

LENGTH

REMHASH

ERASE

CLRHASH

CLEAR

HASH-MAP

Structure: HASH-MAP

Slots
  • TABLE

Function: HASH-MAP TABLE

The HASH-MAP structure wraps a standard HASH-TABLE, or CUSTOM-HASH-TABLE, contained in the TABLE slot, which can be accessed accessed with HASH-MAP-TABLE.

The HASH-MAP function takes a single argument, a hash-table, and creates a HASH-MAP wrapping it.

Implemented Interfaces

The CLEARED, MAKE-SEQUENCE-OF-TYPE, LENGTH, EMPTYP, CLEAR, ELT, (SETF ELT) and ERASE methods of the Container interface are implemented.

The Iterator interface is implemented for HASH-MAP's. Each element returned by the iterator is a CONS with the key in the CAR and the corresponding value in the CDR. The order in which the entries are iterated over is unspecified. Likewise it is unspecified which entries will be iterated over if START is non-zero and/or END is non-NIL, the only guarantee being that END - START entries are iterated over. The reverse iterator iterates over the entries in the same order as the normal iterator due to the order of iteration being unspecified.

The (SETF AT) method for the HASH-MAP iterator sets the value corresponding to the key of the current entry, being iterated over, to the value passed as the argument to SETF.

The collector interface is implemented for HASH-MAP's. The ACCUMULATE method expects a CONS where the CAR is the key of the entry to create and the CDR is the corresponding value.

An EQUALP method is implemented for HASH-MAP's which returns true if both maps contain the same number of entries and each key in the first map is present in the second map, with the corresponding value in the first map equal (by EQUALP) to the corresponding value in the second map.

If the two maps have different test functions, the EQUALP method is not necessarily symmetric i.e. (EQUALP A B) does not imply (EQUALP B A).

A LIKEP method is implemented for HASH-MAP's, which is similar to the EQUALP method, however the values are compared using LIKEP.

A COPY method is implemented for HASH-MAP's which by default creates a new map with the same entries as the original map. If :DEEP T is provided the values (but not the keys as they should be immutable) are copied by (COPY VALUE :DEEP T).

MAKE-HASH-MAP

Function: MAKE-HASH-MAP &KEY TEST &ALLOW-OTHER-KEYS

Create a HASH-MAP wrapping a hash table with test function TEST, which defaults to #'GENERIC-CL:EQUALP.

TEST may be one of the following:

GENERIC-CL:EQUALP

A hash table with hash function HASH and comparison function GENERIC-CL:EQUALP is created.

LIKEP

A hash table with hash function LIKE-HASH and comparison function LIKEP is created.

TEST may also be a standard hash-table test specifier, in which case a native hash table is created, wrapped in a HASH-MAP.

The function accepts all additional arguments (including implementation specific arguments) accepted by CL:MAKE-HASH-TABLE.

ENSURE-HASH-MAP

Function: ENSURE-HASH-MAP THING

If MAP is a HASH-MAP returns it, otherwise if MAP is a HASH-TABLE or CUSTOM-HASH-TABLE returns a HASH-MAP which wraps it.

Signals an error if MAP is not of the aforementioned types.

HASH-MAP-TEST

Function: HASH-MAP-TEST MAP

Returns the test function, as a symbol, of the underlying hash table.

On some implementations the return value is not GENERIC-CL:EQUALP, even if the hash table has HASH and GENERIC-CL:EQUALP as its hash and comparison functions.

HASH

Generic Function: HASH OBJECT

Hash function for hash tables with the GENERIC-CL:EQUALP test specifier.

Return a hash code for OBJECT, which should be a non-negative fixnum.

If two objects are equal (under GENERIC-CL:EQUALP) then the hash codes, for the two objects, returned by HASH, should also be equal.

The default method calls CL:SXHASH which satisfies the constraint that (CL:EQUAL X Y) implies (= (CL:SXHASH X) (CL:SXHASH Y)).

Currently no specialized method is provided for container/sequence objects such as lists. The default method does not violate the constraint for lists (but does violate the constraints for non-string vectors) as keys, provided they only contain numbers, characters, symbols, strings and other lists as elements.

LIKE-HASH

Generic Function: LIKE-HASH OBJECT

Hash function for hash tables with the LIKEP test specifier.

Return a hash code for OBJECT, which should be a non-negative fixnum.

If two objects are equal (under LIKEP) then the hash codes, for the two objects, returned by LIKE-HASH, should also be equal.

Methods which satisfy these constraints are provided for strings, characters, lists, vectors and multi-dimensional arrays. The default method calls the HASH function.

GET

Generic Function: GET KEY MAP &OPTIONAL DEFAULT

Return the value of the entry corresponding to the key KEY in the map MAP.

If the MAP does not contain any entry with that key, DEFAULT is returned. The second return value is true if an entry with key KEY was found in the map, false otherwise.

Methods are provided for HASH-MAP's, standard HASH-TABLE's, association lists (ALISTS) and property lists (PLISTS). For ALISTS the EQUALP key comparison function is used. For PLISTS the EQ key comparison function is used.

(SETF GET)

Generic Function: (SETF GET) VALUE KEY MAP &OPTIONAL DEFAULT

Set the value of the entry corresponding to the key KEY in the map MAP.

DEFAULT is ignored.
Only a method for HASH-MAPS and HASH-TABLES is provided.

ENSURE-GET

Macro: ENSURE-GET KEY MAP &OPTIONAL DEFAULT

Like GET however if KEY is not found in MAP it is added, by (SETF GET) with the value DEFAULT.

The first return value is the value corresponding to the key KEY, or DEFAULT if KEY is not found in MAP. The second return value is true if KEY was found in MAP, false otherwise.

ELT Methods

The following ELT methods are provided:

  • (MAP HASH-MAP) (KEY T)

    Returns (GENERIC-CL:GET KEY MAP).

  • (MAP HASH-TABLE) (KEY T)

    Returns (GETHASH KEY MAP)

(SETF ELT) Methods

The following (SETF ELT) methods are provided:

  • (VALUE T) (MAP HASH-MAP) (KEY T)

    Calls (SETF (GENERIC-CL:GET KEY MAP) VALUE)

  • (VALUE T) (MAP HASH-TABLE) (KEY T)

    Calls (SETF (GETHASH KEY MAP) VALUE)

ERASE Method

Method: ERASE (MAP HASH-MAP) (KEY T)

Remove the entry with key KEY from MAP.

Returns true if the map contained an entry with key KEY.

HASH-MAP-ALIST

Function: HASH-MAP-ALIST MAP

Return an association list (ALIST) containing all the entries in the map MAP.

ALIST-HASH-MAP

Function: ALIST-HASH-MAP ALIST &REST ARGS

Return a HASH-MAP containing all entries in the association list ALIST.

ARGS are the additional arguments passed to MAKE-HASH-MAP.

MAP-KEYS

Generic Function: MAP-KEYS MAP

Return a sequence containing all the keys in the map MAP.

Specialized only on HASH-MAP's and CL:HASH-TABLE's.

MAP-VALUES

Generic Function: MAP-VALUES MAP

Return a sequence containing all the values in the map MAP.

Specialized only on HASH-MAP's and CL:HASH-TABLE's.

COERCE Methods

The following COERCE methods are provided for HASH-MAPS:

  • HASH-MAP (EQL 'ALIST)

    Returns an association list (ALIST) containing all the entries in the map. Equivalent to HASH-MAP-ALIST.

  • HASH-MAP (EQL 'PLIST)

    Returns a property list (PLIST) containing all the entries in the map.

MAKE-SEQUENCE-OF-TYPE Method

Method: MAKE-SEQUENCE-OF-TYPE (TYPE (EQL 'HASH-MAP)) (ARGS NULL)

Return a new empty HASH-MAP with test function GENERIC-CL:EQUALP.

Sets

System and package name GENERIC-CL.SET.

The set interface provides generic functions for performing set operations and implementations of those operations for a hash-set data structure.

Generic function wrappers are provided over the following Common Lisp set operation functions:

  • SUBSETP

  • ADJOIN

  • INTERSECTION

  • NINTERSECTION

  • SET-DIFFERENCE

  • NSET-DIFFERENCE

  • SET-EXCLUSIVE-OR

  • NSET-EXCLUSIVE-OR

  • UNION

  • NUNION

For each function, methods specializing on LISTS, which simply call the corresponding function in the CL package, and HASH-MAP's are implemented. Each function accepts all keyword arguments accepted by the corresponding CL functions however they are ignored by the HASH-MAP methods.

HASH-MAP's may be used as sets, in which case the set elements are stored in the keys. The values of the map’s entries are ignored by the set operations, thus the map values of the sets returned, by the set operation functions, are unspecified.

ADJOIN

Generic Function: ADJOIN ITEM SET &KEY &ALLOW-OTHER-KEYS

Return a new set containing the elements of SET, and of the same type, with ITEM added to it.

This function is non-destructive. A new set is always returned even if SET is a HASH-MAP / HASH-SET.
Accepts all keyword arguments accepted by CL:ADJOIN however they are ignored by the HASH-MAP method.

NADJOIN

Generic Function: ADJOIN ITEM SET &KEY &ALLOW-OTHER-KEYS

Same as ADJOIN however is permitted to destructively modify SET.

The set returned is EQ to SET in the case of SET being a HASH-MAP however this is not a requirement in the general case, and is not EQ if SET is a list. Thus this function should not be relied upon for its side effects.
Implemented for both lists and HASH-MAP's.

MEMBERP

Generic Function: MEMBERP ITEM SET &KEY &ALLOW-OTHER-KEYS

Return true if ITEM is an element of the set SET.

Implemented for both lists and HASH-MAP's. All keyword arguments accepted by CL:MEMBER are accepted, however are ignored by the HASH-MAP method.

HASH-SET

Structure: HASH-SET

A HASH-SET is a HASH-MAP however it is used to indicate that only the keys are important. This allows the EQUALP and COPY methods, specialized on `HASH-SET’s to be implemented more efficiently, than the methods specialized on HASH-MAP's, as the map values are not compared/copied.

The implementation of the Iterator interface for HASH-SETS differs from the implementation for HASH-MAPS in that only the set elements, i.e. the keys of the underlying hash table, are returned rather than the key-value pairs.

The set operations are implemented both for HASH-MAP's and HASH-SET's.

HASH-TABLE-SET

Function: HASH-TABLE-SET TABLE

Return a HASH-SET structure wrapping the standard HASH-TABLE or CUSTOM-HASH-TABLE.

HASH-SET

Function: HASH-SET &REST ELEMENTS

Return a HASH-SET with elements ELEMENTS.

MAKE-HASH-SET

Function: MAKE-HASH-SET &KEY &ALLOW-OTHER-KEYS

Return a new empty HASH-SET.

Accepts the same keyword arguments as MAKE-HASH-MAP. The default TEST function is GENERIC-CL:EQUALP.

COERCE Methods

The following COERCE Methods are provided:

  • LIST (EQL 'HASH-SET)

    Return a HASH-SET containing the elements in the list.

Math

System and package name GENERIC-CL.MATH.

This interface provides generic function wrappers over a number of math functions. Methods specialized on NUMBER are provided, which simply call the corresponding functions in the CL package. The purpose of this interface is to allow the mathematical functions to be extended to vectors and matrices.

This interface is not exported by the GENERIC-CL package, as it’s not as frequently used as the previous interfaces. The GENERIC-MATH-CL package exports all symbols exports by the GENERIC-CL package and the shadowed math functions in GENERIC-CL.MATH.

Generic function wrappers are provided for the following functions:

  • SIN

  • COS

  • TAN

  • ASIN

  • ACOS

  • ATAN

  • SINH

  • COSH

  • TANH

  • ASINH

  • ACOSH

  • ATANH

  • EXP

  • EXPT

  • LOG

  • SQRT

  • ISQRT

  • REALPART

  • IMAGPART

  • CIS

  • CONJUGATE

  • PHASE

  • NUMERATOR

  • DENOMINATOR

  • RATIONAL

  • RATIONALIZE

System GENERIC-CL.UTIL

The system GENERIC-CL.UTIL provides additional utilities implemented on top of GENERIC-CL. These utilities are contained in the package GENERIC-CL.UTIL.

Lazy Sequence Utilities

REPEAT

Function: REPEAT X &OPTIONAL N TYPE

Create a lazy sequence containing N elements with the value X.

If N is NIL or is not provided, an infinite sequence is returned.

If TYPE is non-NIL a sequence of type TYPE is returned. The sequence is created using the SEQUENCE-OF-TYPE function, and the elements are accumulated into the sequence using the Collector interface.

REPEATEDLY

Function: REPEATEDLY F &OPTIONAL N TYPE

Create a lazy sequence containing N elements, with each element being the result of an application of the function F with no arguments.

If N is NIL or not provided, an infinite sequence is returned.

If TYPE is non-NIL a sequence of type TYPE is returned. The sequence is created using the SEQUENCE-OF-TYPE function, and the elements are accumulated into the sequence using the Collector interface.

ITERATE

Function: ITERATE F X &KEY INITIAL

Return an infinite lazy sequence where each element is the result of applying the function F on the previous element.

IF the keyword argument INITIAL is true, the first element of the sequence is X, otherwise the first element is the result of applying F on X.

FITERATE

Function: FITERATE F X &KEY INIITIAL

Deprecated alias for ITERATE

CYCLE

Function: CYCLE SEQUENCE

Return a lazy sequence containing an infinite repetition of the elements in SEQUENCE.

The resulting sequence contains the elements of SEQUENCE in order, with the last element of SEQUENCE followed by the first, and remaining, elements.

Optimization

There is an overhead associated with generic functions. Code making use of the generic function interface will be slower than code which calls the CL functions directly, due to the cost of dynamic method dispatch. For most cases this will not result in a noticeable decrease in performance, however for those cases where it does there is an optimization.

This library is built on top of STATIC-DISPATCH, which is a library that allows generic-function dispatch to be performed statically, at compile-time, rather than dynamically, at runtime. The library allows a call to a generic function to be replaced with the body of the appropriate method, or a call to an ordinary function implementing the method, which is selected based on the type declarations of its arguments.

For a generic function call to be inlined an OPTIMIZE declaration with a SPEED level of 3 and with SAFETY and DEBUG levels less than 3 has to be in place, in the environment of the call. Additionally, it must also be possible to determine the types of the arguments at compile-time. This means in general that the types of variables and the return types of functions have to be declared. See STATIC-DISPATCH and CL-FORM-TYPES for information on how the types of the arguments are determined and how to make the type information available.

Example
(let ((x 1))
  (declare (optimize (speed 3) (safety 2))
           (type number x))

  (equalp x (the number (+ 3 4))))

This will result in the call to the EQUALP function being replaced with the body of the NUMBER NUMBER method.

The n-argument equality, comparison and arithmetic functions also have associated compiler-macros which replace the calls to the n-argument functions with multiple inline calls to the binary functions, e.g. (= 1 2 3) is replaced with (and (equalp 1 2) (equalp 1 3)).

Thus the following should also result in the EQUALP function calls being statically dispatched:

(let ((x 1))
  (declare (optimize (speed 3) (safety 2))
           (type number x))

  (= x (the number (+ 3 4))))
STATIC-DISPATCH requires the ability to extract TYPE and INLINE declarations from implementation specific environment objects. This is provided by the CL-ENVIRONMENTS library, which works in the general case however some workarounds are necessary in order for it to work on all implementations in all cases.