Implementing the Iterator Design Pattern in Lisp

Introduction

Here we implement, as a CLOS example, a common `design pattern'. Design patterns are an attempt to categorise and name solutions to commonly-occurring problems in object oriented (or general) software design.

Lisp has sometimes been criticised for its lack of support for such patterns. Partly this is because design patterns are less useful in a high level language with an advanced object system, and which allows syntactic extensions, such as Lisp. Partly it is because the implementation of these patterns is sufficiently easy in Lisp that people have often not formalised them. However there is a place for these ideas in Lisp, even if it is sometimes only to aid communication with people using other languages!

The classic book on design patterns is: Erich Gamma, Richard Helm, Ralph Johnson & John Vlissides, `Design Patterns, Elements of Reusable Object-Oriented Software', Addison-Wesley, 1995.

Collections

A collection is a group of objects; for example, the set of possible output devices for a particular program; or the various marks achieved in a particular examination by a group of students.

Iterators

The Iterator pattern is a solution to the problem of accessing the objects making up some collection without exposing the structure of the collection. There are two sorts of iterators:

An internal iterator is a function which maps another function over the elements of a collection. Internal iterators are very familiar in Lisp.
An external iterator, or cursor, provides a way of getting an object which will successively deliver the members of some collection.

Iterator protocol

In order to implement iterators, we need to define a protocol for internal and external iterators.

The internal iterator protocol is very simple, a generic function with a signature similar to mapc or mapcar will do: we've called it map-over, and it takes two arguments: f, a function, and collection, a collection.
For external iterators we can define a generic function which creates an appropriate cursor for a collection, and functions which get at the next element in a cursor and tell if a cursor is finished. We've called our cursor creation function make-cursor-for, which takes a collection as argument and returns a cursor for that collection, and defined cursor-next and cursor-finished-p, both of which take a cursor as argument. cursor-next returns two values: the next item from the collection, and a flag to indicate whether or not the collection is now empty.

Lisp has a well-known collection type, the list. We can define both internal an external iterators for lists:


USER(41): (defparameter mycollection '(a b c d e))
MYCOLLECTION
USER(42): mycollection
(A B C D E)
USER(43): (map-over #'(lambda (elt) (format t "~S~%" elt)) mycollection)
A
B
C
D
E
(A B C D E)
USER(44): (setf mycursor (make-cursor-for mycollection))
#<Closure (:INTERNAL (METHOD MAKE-CURSOR-FOR (LIST)) 0) @ #x203e1452>
USER(45): (cursor-finished-p mycursor)
NIL
USER(46): (cursor-next mycursor)
A
NIL
USER(47): (cursor-next mycursor)
B
NIL
USER(48): (cursor-finished-p mycursor)
NIL
USER(49): (cursor-next mycursor)
C
NIL
USER(50): (cursor-next mycursor)
D
NIL
USER(51): (cursor-next mycursor)
E
T
USER(52): (cursor-finished-p mycursor)
T
USER(53): (cursor-next mycursor)
NIL
T
USER(54):

Collection protocol

It is useful to define an abstract interface to `collections' while not specifying the implementation. Here we will deal with objects which have unordered collections of (unique) `children', and you should define a protocol for dealing with these objects.

We need to define generic functions to:

add a child to an object;
remove a child from an object (destructively);
remove all children matching some test from an object.

We've called these functions add-child, delete-child and delete-children-if respectively.

Childed collection class

We've defined a simple opaque collection class which has a list of children, and implemented the above protocol for it. We've called the class simple-childed-mixin. We've also defined iterator protocols for this class.

So, we can add new children to an object of this class and delete-children from an object of this class, and we can use our iterator protocols to look at the objects in the class:


USER(70): (defparameter mychildedthing (make-instance 'simple-childed-mixin))
MYCHILDEDTHING
USER(71): (add-child mychildedthing 'a)
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(72): (add-child mychildedthing 'b)
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(73): (add-child mychildedthing 'c)
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(74): (add-child mychildedthing 'd)
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(75): (map-over #'(lambda (elt) (format t "~S~%" elt)) mychildedthing)
D
C
B
A
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(76): (delete-child mychildedthing 'c)
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(77): (map-over #'(lambda (elt) (format t "~S~%" elt)) mychildedthing)
D
B
A
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(78): (setf mycursor (make-cursor-for mychildedthing))
#<Closure (:INTERNAL (METHOD MAKE-CURSOR-FOR (LIST)) 0) @ #x203e5f62>
USER(79): (cursor-next mycursor)
D
NIL
USER(80): (cursor-next mycursor)
B
NIL
USER(81): (cursor-next mycursor)
A
T
USER(82): (cursor-next mycursor)
NIL
T
USER(83): (delete-children-if mychildedthing #'(lambda (elt) (eql elt 'b)))
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(84): (map-over #'(lambda (elt) (format t "~S~%" elt)) mychildedthing)
D
A
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(85): (add-child mychildedthing 'a)
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(86): (map-over #'(lambda (elt) (format t "~S~%" elt)) mychildedthing)
D
A
#<SIMPLE-CHILDED-MIXIN @ #x203e51a2>
USER(87):