Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
overview of the protocol, sequence, iterator, and iterate+ packages.
#|
UPDATE: this file no longer works with the changes
pushed to github today (2012-09-17) will fix it
soon.
A working overview of the protocol, sequence,
iterator, and iterate+ packages.
These packages are each quite small and are
intended to be used ala carte.
the projects are all here on github:
https://github.com/jaeschliman/
|#
(defpackage #:demo
(:use #:cl #:alexandria
; this package provides the protocol
; abstraction, only needed if you wish
; to create a new protocol or implement
; an existing one on your own data structures.
; protocols are integrated with the type system.
#:com.clearly-useful.protocols
; this package provides a generic sequence
; protocol with the methods head and tail,
; a macro doseq similar to dolist,
; and a function count-seq similar to
; list-length.
#:com.clearly-useful.sequence-protocol
; this package provides a generic stateful
; iteration protocol, and a macro do-iterator
; similar to dolist. iterators are not intended
; to be used directly, but created behind the
; scenes and consumed immediately. they should
; be thought of as having dynamic extent.
#:com.clearly-useful.iterator-protocol
#:iterate
; this package provides drivers for
; iterate to consume seqs and iterators.
; since iterate uses symbol equality,
; you must :use it or it will have
; no effect. it exports only the symbols
; 'per' and 'of'.
#:com.clearly-useful.iterate+))
(in-package #:demo)
(defun show (it)
"spell out seqs to stdout for demonstration purposes."
(etypecase it
(seq (write (class-of it))
(write-string ": (")
(show (head it))
(doseq (item (tail it))
(write-char #\Space)
(show item))
(write-string ")")
(terpri))
(t (write it))))
(defvar *a-cons* '(a b c d))
(defvar *a-vector* #(a b c d))
(defvar *a-string* "abcd")
(defvar *an-array* #2A((a b) (c d)))
(defvar *a-hash-table* (alist-hash-table '((a . b) (c . d))))
(show (list *a-cons*
*a-vector*
*a-string*
*an-array*
*a-hash-table*))
;; =>
;; #<BUILT-IN-CLASS CONS>: (#<BUILT-IN-CLASS CONS>: (A B C D)
;; #<BUILT-IN-CLASS SIMPLE-VECTOR>: (A B C D)
;; #<BUILT-IN-CLASS SIMPLE-BASE-STRING>: (#\a #\b #\c #\d)
;; #<BUILT-IN-CLASS SIMPLE-ARRAY>: (A B C D)
;; #<HASH-TABLE :TEST EQL size 2/60 #x302000F7A9BD>)
;;; wait, why wasn't the hash-table spelled out?
;;; since hash-tables are unordered, they can't
;;; conform to the seq protocol directly.
;;; however, a generic function 'seq' is provided
;;; which converts arbitrary objects to seq's if
;;; needed. an implementation is provided for
;;; hash-table (returning a list of proper lists)
(show (seq *a-hash-table*))
;; =>
;; #<BUILT-IN-CLASS CONS>: (#<BUILT-IN-CLASS CONS>: (A B)
;; #<BUILT-IN-CLASS CONS>: (C D)
;; )
(head *a-hash-table*) ;;seq is called internally
;; => either (A B) or (B C)
;;; seq acts as the identity function for objects
;;; implementing the seq protocol
(eq *a-cons* (seq *a-cons*)) ; => t
;;; an example of integrating a custom data structure
(defstruct range
"an immutable integer range from
low to high, exclusive."
low high)
(defvar *a-range* (make-range :low 0 :high 10))
(defun %range-size (range)
"the number of elements in a range"
(- (range-high range)
(range-low range)))
(defun %next-range (range)
"return the next range by incrementing
the lower bound of range, or nil"
(if (<= (%range-size range) 1)
nil
(make-range :low (1+ (range-low range))
:high (range-high range))))
(extend-type range
seq
(head (range) (range-low range))
(tail (range) (%next-range range)))
;;; range is now a seq:
(assert (typep *a-range* 'seq))
(assert (seq-p *a-range*))
(assert (= 0 (head *a-range*)))
(show *a-range*)
;; #<STRUCTURE-CLASS RANGE>: (0 1 2 3 4 5 6 7 8 9)
;;; a default implementation is provided
;;; for count-seq for any object implementing
;;; the seq protocol:
(assert (= 10 (count-seq *a-range*)))
;;; but it may be overidden for efficiency
;;; if desired:
(defmethod count-seq ((range range)) (%range-size range))
;;; still true:
(assert (= 10 (count-seq *a-range*)))
;;; doseq now works on our object:
(doseq (x *a-range*) (write x))
;; 0123456789
;; => NIL
;;; and the iterator protocol provides
;;; a default for objects implementing seq:
(do-iterator (x *a-range*) (write x))
;; 0123456789
;; => NIL
;; the iterator protocol
;;; unlike seqs, iterators are updated destructively,
;;; and not intended to be hold onto or passed around.
;;; the facilities provided for consuming iterators
;;; first call the generic function 'iterator' on their
;;; argument, and destructively operate on its return
;;; value.
;;; since our range objects are intended to be immutable,
;;; and iterator acts as the identity function for objects
;;; implementing the iterator protocol, we need to provide
;;; a wrapper class or struct to be destructively modified.
;;; implementing iterators is more complex than seqs,
;;; as it requires juggling state. the code below is
;;; commented accordingly.
(defstruct (%mutable-range (:include range)))
(extend-type %mutable-range
iterator
;; iterator defines two methods:
;; this method is the 'driver':
(iterator-next! (r)
(if (plusp (%range-size r))
;; there are still elements left
;; so get the current element:
(let ((v (range-low r)))
;; destructively update the iterator:
(incf (range-low r))
;; return the value and t to indicate
;; a value was found:
(values v t))
;; otherwise return an ignored value,
;; and nil to indicate the iterator
;; is finished.
(values nil nil)))
;; and this method performs clean-up.
(iterator-finish! (r)
;; in our case, just a noop
(declare (ignore r))))
;; a quick test:
(let ((m (make-%mutable-range :low 0 :high 10)))
;;%mutable-range is now an iterator:
(assert (typep m 'iterator)))
;;; now we define a method on 'iterator' to
;;; return our custom supremely efficient
;;; mutable range object:
(defmethod iterator ((range range))
(make-%mutable-range :low (range-low range)
:high (range-high range)))
;;; and everything still works:
(do-iterator (x *a-range*) (write x))
;; 0123456789
;; => NIL
;;; if you're still not sure:
(iterator *a-range*)
;; => #S(%MUTABLE-RANGE :LOW 0 :HIGH 10)
;;; iter integration.
;;; iterate provides a facility for user extension,
;;; the package com.clearly-useful.iterate+ provides
;;; three extensions, all keying of the symbol 'per',
;;; as opposed to 'for' :
;;; iter per ... in
;;; similar to for ... in,
;;; calls 'seq' on its argument:
(iter (per x in *a-range*)
(collect x))
;; => (0 1 2 3 4 5 6 7 8 9)
(iter (per x in *a-hash-table*)
(collect x))
;; => ((A B) (C D))
;;; iter per ... on
;;; similar to loop for ... on
;;; calls 'seq' on its argument:
(iter (per x on *a-range*)
(show x)
(collect x))
;; prints:
;; #<STRUCTURE-CLASS RANGE>: (0 1 2 3 4 5 6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (1 2 3 4 5 6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (2 3 4 5 6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (3 4 5 6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (4 5 6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (5 6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (6 7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (7 8 9)
;; #<STRUCTURE-CLASS RANGE>: (8 9)
;; #<STRUCTURE-CLASS RANGE>: (9)
;; => (#S(RANGE :LOW 0 :HIGH 10) ..snip.. #S(RANGE :LOW 9 :HIGH 10))
;;; iter per ... of
;;; similar to per ... in,
;;; but calls 'iterator' on its
;;; argument:
(iter (per x of *a-range*)
(collect x))
;; => (0 1 2 3 4 5 6 7 8 9)
;;; a method for 'iterator' is
;;; provided on hash-tables:
(iter (per x of *a-hash-table*)
(collect x))
;; => ((A B) (C D))
;;; the projects are all here on github:
;;; https://github.com/jaeschliman/
;;; and contain fairly good readme's
;;; (perhaps best viewed raw, as they're in org files)
;;; as well as basic tests, and the source
;;; of each is quite small, though sparsely
;;; commented at the moment.
;; Cheers!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.