trivial extensible sequences

1.0.0

Portability library for the extensible sequences protocol.

About

This package provides a portability layer for the extensible sequences standard extension to Common Lisp. Extensible sequences allow you to create your own sequence types that integrate with the rest of the functions and operations that interact with sequences.

The extensible sequences protocol is defined in 'User-extensible sequences in Common Lisp' by Christophe Rhodes[1]. Also see the SBCL manual. Please refer to the above documents as well as the sequence operations in the hyperspec for documentation.

How To

The basic operation is rather simple. All the functionality is defined in the org.shirakumo.trivial-extensible-sequences package – you may want to use a package-local-nickname to alias it to sequences.

First, create a subclass of sequence. This will be your new sequence type. For this how-to, we'll define a sequence type that can represent any value as a sequence of length 1.

(defclass value-as-sequence (sequences:sequence)
  ((value :initarg :value :initform (error "VALUE required.") :accessor value)))

Then you should add methods on length, elt, (setf elt), adjust-sequence and make-sequence-like.

(defmethod sequences:length ((sequence value-as-sequence))
  1)

(defmethod sequences:elt ((sequence value-as-sequence) index)
  (check-type index (integer 0 0))
  (value sequence))

(defmethod (setf sequences:elt) (value (sequence value-as-sequence) index)
  (check-type index (integer 0 0))
  (setf (value sequence) value))

(defmethod sequences:adjust-sequence ((sequence value-as-sequence) length &key initial-contents initial-element)
  (check-type length (integer 1 1))
  (when initial-contents
    (setf (value sequence) (elt initial-contents 0)))
  sequence)

(defmethod sequences:make-sequence-like ((sequence value-as-sequence) length &key initial-contents initial-element)
  (check-type length (integer 1 1))
  (make-instance 'value-as-sequence
                 :value (or (elt initial-contents 0) initial-element (value sequence))))

If you leave out any of these functions, some of the sequence operators will not work and will instead signal a protocol-unimplemented error on use. If you do provide a method on each, then all the sequence operators should work out of the box using generic implementations. If you would like to speed up a particular operation for your sequence type, you can also define a specific implementation by adding a method to that function.

Also useful is to explicitly support the iterator protocol, which should allow most default operations to be performed much faster. To do so you only need to define a method on make-sequence-iterator. This method should return 9 values:

  1. An iteration state value.

  2. A value describing the limit of iteration, if any.

  3. The from-end value.

  4. A step function of three arguments: the sequence, the state value, the from-end value. The function should return the new state value.

  5. An end predicate of four arguments: the sequence, the state value, the limit value, the from-end value. The function should return a generalised boolean describing whether the iteration has reached the end of the sequence.

  6. An element read function of two arguments: the sequence, the state value.

  7. An element write function of three arguments: the new value to store, the sequence, the state value.

  8. An index function of two arguments: the sequence, the state value. The function should return the current iteration index, starting from zero.

  9. An iterator copy function of two arguments: the sequence, the state value. The function should return a "fresh" iteration value.

Here's what it might look like for our relatively useless example sequence type:

(defmethod sequences:make-sequence-iterator ((sequence value-as-sequence) &key start end from-end)
  (values 0 1 from-end
          (lambda (seq state from-end) (1+ state))
          (lambda (seq state limit from-end) (< state limit))
          (lambda (seq state) (value seq))
          (lambda (value seq state) (setf (value seq) value))
          (lambda (seq state) state)
          (lambda (seq state) state)))

Obviously for more complicated sequences the functions and state could be more interesting than this. Note that you can use iterators more easily using with-sequence-iterator, with-sequence-iterator-funcntions, and dosequence.

Implementation Support

The following implementations have native support for extensible sequences. On those implementations, this package will merely be an alias for the implementation's sequences package.

  • ABCL

  • SBCL

On any other implementation, this package provides a fallback implementation of the protocol. The protocol should work completely with the following caveats:

  • You must use the functions provided by this package to handle your sequences, rather than the ones from the cl package.

  • Custom sequences defined with a subclass will not actually be a subtype of cl:sequence.

  • The fallback protocol will be slower than what the implementation could provide.

Meaning you can still make things work most of the time, but with some heavy caveats. For this reason, please contact your implementation maintainers and request for the protocol to be implemented natively. The source code of the fallback implementation, as well as SBCL's own implementation are licensed liberally and should serve as a good basis.

System Information

1.0.0
Nicolas Hafner
zlib
https://shinmera.github.io/trivial-extensible-sequences/

Definition Index