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

overview.lisp

#|

  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!