public
Created

overview of the protocol, sequence, iterator, and iterate+ packages.

  • Download Gist
overview.lisp
Common Lisp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
#|
 
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!

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.