Continuing from part 4, it’s time to start beefing up the macro a bit.  Now, we might want our loop to start somewhere other than the beginning of the list, and end somewhere other than the end of the list.  And, a few articles back, I mentioned that these lists might sometimes be circular, so we’d like to be able to start at the fifth element of the list, loop forward to the end, continue at the beginning, and then loop up to, say, the second element of the list.

At this point, we come across another very helpful feature of Lisp, one that I frequently miss when programming in C++.  Named parameters.  A function that takes four or five parameters can be awkward to read where it appears in source code, because it might not be clear which parameters represent what behaviour.  It interferes with readability.  In Lisp, you can require certain parameters to be named, which helps to understand what is happening.  A nice consequence of this is that you can set defaults for any of the named parameters, in any order, whereas in C++ you are fairly tightly restricted in what default parameter values you may omit (you cannot choose to omit the second, fourth, and seventh parameters of the invocation, you must omit a contiguous set of trailing parameters with defaults).

So, now we’re going to set up our macro.  Once again, I use (gensym) to build capture variables to avoid multiple evaluations of the arguments.  I also define named parameters :start and :end, which take iterator values as arguments, and :circular, which is either nil or non-nil.  I’ve also created here two lambda functions.  These allow me to create a tiny function on the spot, where the programmer can see it because it’s in the screen with the implementation of its use.  One lambda function is the alternative iterator increment function, to be used when the :circular argument is non-nil, to force the iterator to loop back once it reaches the end of the list.  The other is an exit test that checks to see if the iterator matches the :end condition, if one was supplied.  If so, the (do…) loop is exited at that point.  Note that this condition is tested after the user-supplied body of the loop, before the iterator increment operation, so that the :end iterator is included in the loop.

Here is the next version of this macro:
macros.lisp  

(defmacro iter-loop ((dl-list iter &key start end circular) &body body)
  (let ((dl-cap (gensym))
        (start-cap (gensym))
        (end-cap (gensym))
        (circ-cap (gensym))
        (inc-fcn (gensym))
        (early-exit (gensym)))
    `(let((,dl-cap ,dl-list)
          (,start-cap ,start)
          (,end-cap ,end)
          (,circ-cap ,circular)
          (,inc-fcn 'iter-next)
          ,early-exit)
       (when ,circ-cap
         (setf ,inc-fcn #'(lambda (dl it) 
                            (let ((rv (iter-next dl it))) 
                              (or rv (iter-front dl))))))
       (unless ,start-cap
         (setf ,start-cap (iter-front ,dl-cap)))
       (when ,end-cap
         (setf ,early-exit #'(lambda (x) (eq x ,end-cap))))
       (do ((,iter ,start-cap (funcall ,inc-fcn ,dl-list ,iter)))
           ((not ,iter))
         ,@body
         (when (and ,early-exit
                    (funcall ,early-exit ,iter))
           (return))))))

Now, referring back to the code we showed in part 3, it’s time to step off into macros.  Macros have a bad reputation in C/C++.  Their limitations are significant, and their use is often discouraged except in fairly narrow cases where they are used only in a trivial fashion.

Multi-instruction macros in C/C++ can be made safely, as long as the programmer takes the time to learn how to do it.  The common construct is do { … } while (false), with no trailing semicolon.  That allows it to be used safely in things like the clause of an ‘if’ statement without parenthesis delimiters.  Designing a macro that creates its own named variables is dangerous because they may collide with names already in use in the context where the macro is applied, but not using temporary variables can be dangerous if the arguments are reused, because their side-effects are invoked every time the arguments appear.  Having a complex macro return a value is awkward, and variadic macro arguments are complicated.  The C-preprocessor macro language is very handy, but it does not give the macros the full power of the language.

Because of this, a C/C++ programmer coming to Lisp may hear “macro”, and think that this is a feature to be avoided, clunky and dangerous.  Lisp macros, however, are quite strongly different.  Lisp macros have access to the language features at compile-time, and emit Lisp code at expansion time.  They can implement new language structures, such as new looping constructs.  Often, they seem quite mundane at first, but there eventually comes an “aha!” moment, after which the power and utility becomes clear.  So, we’ve defined out doubly-linked lists and our iterators.  One common activity is to loop the iterator over all elements in the list.  In C++, you would typically do this with a for(;;) loop, or sometimes a while() loop if the conditions are a bit more unusual.  However, your C++ code is full of these for(;;) loops.  Looping over integers, looping over iterators of one kind or another, they’re expressed the same way, so interpreting them requires reading the context of the loop to understand what the variables are and what they represent.  It would be nice to have a loop construct whose name indicates immediately that it is looping an iterator over a doubly-linked list.With that introduction, here is our first (wrong) implementation of an iterator looping macro:

(defmacro iter-loop ((dl-list iter) &body body)
  `(do ((,iter (iter-front ,dl-list) (iter-next ,dl-list ,iter)))
       ((not ,iter))
     ,@body))))

This is wrong because of the danger of argument re-evaluation.  If one were to use it in a loop like this:
macros.lisp  

(dl-list:iter-loop ((expensive-dl-list-creation-function) my-iter)
  (perform-my-operation-on-iterator my-iter))

then the expensive-dl-list-creation-function would be called many times, each time creating a new object that would cause difficulties because of the way iterator incrementation is implemented.  Just as in C/C++ macros, the side-effects of the parameters can manifest too many times, in ways the programmer doesn’t expect.  In Lisp, however, there is a way to capture the argument exactly once, using a temporary variable that is guaranteed not to collide with variables in the program where the macro is expanded.

The (gensym) function, invoked at compile time during macro expansion, returns a variable guaranteed not to exist.  We use this to expand and capture the value of the dl-list, whatever it might be, and use it in the macro.

(defmacro iter-loop ((dl-list iter) &body body)
  (let ((dl-cap (gensym)))
    `(let ((,dl-cap ,dl-list))
       (do ((,iter (iter-front ,dl-cap) (iter-next ,dl-cap ,iter)))
           ((not ,iter))
         ,@body))))

Why didn’t I do the same thing for ‘iter’?  Well, as we see from the use case, ‘iter’ is a variable name that the user supplies, and which they can then operate on in the body of the macro expansion.  I don’t see a way the user could supply anything other than a bare name here and expect it to work.  If the user supplies a name for ‘iter’ that is the name of an existing variable, then this macro shadows that variable.

So, that’s the very basic, single iterator looping over the entire list from beginning to end, example.  But we can build on this, making it significantly more powerful.  That’s for later posts.

Here we are continuing from part 2.

The reader might be remaking by now that we’re cluttering up the namespace with these functions, and it’s a bit inelegant to make all the function names start with dl-list-.  Also, some of the functions there are for internal use, while others are parts of the interface.  A modern language should address these problems.

So, enter the package.  Think of this as a C++ namespace, not a class name.  The exported names, i.e. the external API, are listed in the declaration of the package.  At a glance, the user can tell which functions are expected to be used outside the package.  Now, we can drop the dl-list- prefix on our functions, and that becomes the namespace.  Functions would now be invoked as (dl-list:make-dl-list).  If the user absolutely needs access to the internal functions, though, it is possible to call them, by using a double-colon separator between the namespace and the function name.  This is different from the C++ convention of private and public methods, and allows the programmer to make use of the “private” functions without having to modify the source code of the package.  In C++, the programmer would have to add a friend declaration to the class definition, which requires modifying the class.

We’ve also modified the automatically-generated functions in the definition of the dl-list structure.  Having the structure interface functions be prefixed dl-list is now a bit confusing given the namespace behaviour, so we use the :conc-name parameter to modify the way those functions are defined.

We’re almost ready to start in on the more interesting features.  Those will come in part 4.

 

;; We started with a fairly basic version.  It worked, but was clunky.
;; Now, we start making changes.

(defpackage :DL-LIST
  (:use :COMMON-LISP)
  (:export :EMPTY-P :DL-LENGTH :ITER-FRONT :ITER-BACK :ITER-NEXT :ITER-PREV
           :PUSH-FRONT :PUSH-BACK :POP-FRONT :POP-BACK :ITER-CONTENTS
           :INSERT-AFTER-ITER :MAKE-DL-LIST))

(in-package :DL-LIST)

(declaim (optimize (debug 3) (safety 3)))

;; Define the node.  They're opaque types to the user, but they double
;; as iterators (also opaque).
(defstruct (dl-node)
  (value        nil)
  (next-node    nil)
  (prev-node    nil))

;; Define the doubly-linked list.
(defstruct (dl-list (:conc-name dlst-))
  (first-node   nil)
  (last-node    nil))

(defun empty-p (dl-list)
  "Returns non-nil if the list is empty."
  (not (dlst-first-node dl-list)))

(defun iter-front (dl-list)
  "An iterator to the first element in the list."
  (dlst-first-node dl-list))

(defun iter-back (dl-list)
  "An iterator to the last element in the list."
  (dlst-last-node dl-list))

(defun iter-next (dl-list iter)
  "The next iterator, or nil if we're at the end of the list."
  (declare (ignore dl-list))
  (dl-node-next-node iter))

(defun iter-prev (dl-list iter)
  "The previous iterator, or nil if we're at the beginning of the list."
  (declare (ignore dl-list))
  (dl-node-prev-node iter))

(defun dl-length (dl-list)
  (let ((rv 0))
    (do ((iter (iter-front dl-list) (iter-next dl-list iter)))
        ((not iter) rv)
      (incf rv))))

(defun dl-list-insert-after-worker (dl-list iter val)
  "Insert a value in the dl-list after the iterator.  As a special case, 
if 'iter' is nil, inserts at the front of the list."

  (let* ((next-node (if iter (dl-node-next-node iter) (dlst-first-node dl-list)))
         (prev-node iter)
         (new-node (make-dl-node :value val
                                 :next-node next-node
                                 :prev-node prev-node)))
    (cond
      (next-node
       (setf (dl-node-prev-node next-node) new-node))
      (t
       (setf (dlst-last-node dl-list) new-node)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) new-node))
      (t
       (setf (dlst-first-node dl-list) new-node)))

    new-node))

(defun dl-list-delete-at-worker (dl-list iter)
  "Deletes the value under the iterator."
  (assert iter)
  (let ((prev-node (dl-node-prev-node iter))
        (next-node (dl-node-next-node iter)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) next-node))
      (t
       (setf (dlst-first-node dl-list) next-node)))

    (cond
      (next-node
       (setf (dl-node-prev-node next-node) prev-node))
      (t
       (setf (dlst-last-node dl-list) prev-node))))

  (dl-node-value iter))

(defun push-front (dl-list val)
  "Push a value onto the front of the list."
  (dl-list-insert-after-worker dl-list nil val))

(defun push-back (dl-list val)
  "Push a value onto the back of the list."
  (dl-list-insert-after-worker dl-list (dlst-last-node dl-list) val))

(defun pop-front (dl-list)
  "Remove the first value from the list and return it.  Returns nil if the list is empty."
  (let ((first-iter (iter-front dl-list)))
    (when first-iter
      (dl-list-delete-at-worker dl-list first-iter))))

(defun pop-back (dl-list)
  "Remove the last value from the list and return it.  Returns nil if the list is empty."
  (let ((last-iter (iter-back dl-list)))
    (when last-iter
      (dl-list-delete-at-worker dl-list last-iter))))

(defun iter-contents (dl-list iter)
  "The value of the list element pointed to by the iterator."
  (declare (ignore dl-list))
  (dl-node-value iter))

(defun insert-after-iter (dl-list iter val)
  "Insert a value into the list after the position of the iterator."
  (assert iter)
  (dl-list-insert-after-worker dl-list iter val))

(defun insert-before-iter (dl-list iter val)
  "Insert a value into the list before the position of the iterator."
  (assert iter)
  (dl-list-insert-after-worker dl-list (iter-prev dl-list iter) val))

(defun verify-dl-list-contents (dl-list &rest contents)
  (assert (= (dl-length dl-list) (length contents)))
  (assert (or (and contents (not (empty-p dl-list)))
              (and (not contents) (empty-p dl-list))))
  (let ((iter (iter-front dl-list)))
    (dolist (entry contents)
      (assert (eq entry (iter-contents dl-list iter)))
      (setf iter (iter-next dl-list iter)))))

(defun unit-test ()
  (let ((test-list (make-dl-list)))

    (verify-dl-list-contents test-list)

    (push-front test-list 10)
    (verify-dl-list-contents test-list 10)

    (push-front test-list 5)
    (verify-dl-list-contents test-list 5 10)

    (push-back test-list 20)
    (verify-dl-list-contents test-list 5 10 20)

    (let ((iter (iter-front test-list)))
      (assert (= (iter-contents test-list iter) 5))
      (insert-after-iter test-list iter 7)

      (verify-dl-list-contents test-list 5 7 10 20)

      (setf iter (iter-next test-list iter))
      (assert (= (iter-contents test-list iter) 7))

      (insert-before-iter test-list iter 6)

      (verify-dl-list-contents test-list 5 6 7 10 20)

      (setf iter (iter-prev test-list iter))
      (assert (= (iter-contents test-list iter) 6))

      (setf iter (iter-next test-list iter))
      (assert iter)
      (assert (= (iter-contents test-list iter) 7))

      (setf iter (iter-next test-list iter))
      (assert iter)
      (assert (= (iter-contents test-list iter) 10))

      (setf iter (iter-next test-list iter))
      (assert iter)
      (assert (= (iter-contents test-list iter) 20))

      (setf iter (iter-next test-list iter))
      (assert (not iter)))

    (assert (= (iter-contents test-list (iter-front test-list)) 5))
    (assert (= (iter-contents test-list (iter-back test-list)) 20))

    (assert (= (pop-front test-list) 5))
    (assert (= (dl-length test-list) 4))
    (assert (= (iter-contents test-list (iter-front test-list)) 6))

    (assert (= (pop-back test-list) 20))
    (assert (= (dl-length test-list) 3))
    (assert (= (iter-contents test-list (iter-back test-list)) 10)))
  t)

(defmethod print-object ((node dl-node) stream)
  "Allow pretty-printing of the a node."
  (let ((prev-node (dl-node-prev-node node))
        (next-node (dl-node-next-node node)))
    (format stream "{ ~A <- ~A -> ~A }" 
            (and prev-node (dl-node-value prev-node))
            (dl-node-value node)
            (and next-node (dl-node-value next-node)))))

Having written a somewhat basic and brute-force version of the doubly-linked list code in the previous post, I’m going to start cleaning it up.  This first change is fairly small.  Collection of common code, and an improved unit test.

One helpful shortcut in lisp is the ability to build lists at function invocation time, with the &rest keyword.  That’s just a bit of syntactic convenience, it can easily be implemented with the (list) function, but it’s worth pointing out.  In C/C++, I’d have to use some repetitive boilerplate for this, either building up C arrays, or filling in C++ vectors.  Not really a big deal, though.  The real magic will come later.  Continued in part 3.

;; We started with a fairly basic version.  It worked, but was clunky.
;; Now, we start making changes.

(declaim (optimize (debug 3) (safety 3)))

;; Define the node.  They're opaque types to the user, but they double
;; as iterators (also opaque).
(defstruct (dl-node)
  (value        nil)
  (next-node    nil)
  (prev-node    nil))

;; Define the doubly-linked list.
(defstruct (dl-list)
  (first-node   nil)
  (last-node    nil))

(defun dl-list-empty-p (dl-list)
  "Returns non-nil if the list is empty."
  (not (dl-list-first-node dl-list)))

(defun dl-list-length (dl-list)
  (let ((rv 0))
    (do ((iter (dl-list-iter-front dl-list) (dl-list-iter-next dl-list iter)))
        ((not iter) rv)
      (incf rv))))

(defun dl-list-iter-front (dl-list)
  "An iterator to the first element in the list."
  (dl-list-first-node dl-list))

(defun dl-list-iter-back (dl-list)
  "An iterator to the last element in the list."
  (dl-list-last-node dl-list))

(defun dl-list-iter-next (dl-list iter)
  "The next iterator, or nil if we're at the end of the list."
  (declare (ignore dl-list))
  (dl-node-next-node iter))

(defun dl-list-iter-prev (dl-list iter)
  "The previous iterator, or nil if we're at the beginning of the list."
  (declare (ignore dl-list))
  (dl-node-prev-node iter))

(defun dl-list-insert-after-worker (dl-list iter val)
  "Insert a value in the dl-list after the iterator.  As a special case, 
if 'iter' is nil, inserts at the front of the list."

  (let* ((next-node (if iter (dl-node-next-node iter) (dl-list-first-node dl-list)))
         (prev-node iter)
         (new-node (make-dl-node :value val
                                 :next-node next-node
                                 :prev-node prev-node)))
    (cond
      (next-node
       (setf (dl-node-prev-node next-node) new-node))
      (t
       (setf (dl-list-last-node dl-list) new-node)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) new-node))
      (t
       (setf (dl-list-first-node dl-list) new-node)))

    new-node))

(defun dl-list-delete-at-worker (dl-list iter)
  "Deletes the value under the iterator."
  (assert iter)
  (let ((prev-node (dl-node-prev-node iter))
        (next-node (dl-node-next-node iter)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) next-node))
      (t
       (setf (dl-list-first-node dl-list) next-node)))

    (cond
      (next-node
       (setf (dl-node-prev-node next-node) prev-node))
      (t
       (setf (dl-list-last-node dl-list) prev-node))))

  (dl-node-value iter))

(defun dl-list-push-front (dl-list val)
  "Push a value onto the front of the list."
  (dl-list-insert-after-worker dl-list nil val))

(defun dl-list-push-back (dl-list val)
  "Push a value onto the back of the list."
  (dl-list-insert-after-worker dl-list (dl-list-last-node dl-list) val))

(defun dl-list-pop-front (dl-list)
  "Remove the first value from the list and return it.  Returns nil if the list is empty."
  (let ((first-iter (dl-list-iter-front dl-list)))
    (when first-iter
      (dl-list-delete-at-worker dl-list first-iter))))

(defun dl-list-pop-back (dl-list)
  "Remove the last value from the list and return it.  Returns nil if the list is empty."
  (let ((last-iter (dl-list-iter-back dl-list)))
    (when last-iter
      (dl-list-delete-at-worker dl-list last-iter))))

(defun dl-list-iter-contents (dl-list iter)
  "The value of the list element pointed to by the iterator."
  (declare (ignore dl-list))
  (dl-node-value iter))

(defun dl-list-insert-after-iter (dl-list iter val)
  "Insert a value into the list after the position of the iterator."
  (assert iter)
  (dl-list-insert-after-worker dl-list iter val))

(defun dl-list-insert-before-iter (dl-list iter val)
  "Insert a value into the list before the position of the iterator."
  (assert iter)
  (dl-list-insert-after-worker dl-list (dl-list-iter-prev dl-list iter) val))

(defun verify-dl-list-contents (dl-list &rest contents)
  (assert (= (dl-list-length dl-list) (length contents)))
  (assert (or (and contents (not (dl-list-empty-p dl-list)))
              (and (not contents) (dl-list-empty-p dl-list))))
  (let ((iter (dl-list-iter-front dl-list)))
    (dolist (entry contents)
      (assert (eq entry (dl-list-iter-contents dl-list iter)))
      (setf iter (dl-list-iter-next dl-list iter)))))

(defun unit-test ()
  (let ((test-list (make-dl-list)))

    (verify-dl-list-contents test-list)

    (dl-list-push-front test-list 10)
    (verify-dl-list-contents test-list 10)

    (dl-list-push-front test-list 5)
    (verify-dl-list-contents test-list 5 10)

    (dl-list-push-back test-list 20)
    (verify-dl-list-contents test-list 5 10 20)

    (let ((iter (dl-list-iter-front test-list)))
      (assert (= (dl-list-iter-contents test-list iter) 5))
      (dl-list-insert-after-iter test-list iter 7)

      (verify-dl-list-contents test-list 5 7 10 20)

      (setf iter (dl-list-iter-next test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (dl-list-insert-before-iter test-list iter 6)

      (verify-dl-list-contents test-list 5 6 7 10 20)

      (setf iter (dl-list-iter-prev test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 6))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 10))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 20))

      (setf iter (dl-list-iter-next test-list iter))
      (assert (not iter)))

    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 5))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 20))

    (assert (= (dl-list-pop-front test-list) 5))
    (assert (= (dl-list-length test-list) 4))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 6))

    (assert (= (dl-list-pop-back test-list) 20))
    (assert (= (dl-list-length test-list) 3))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 10)))
  t)

(defmethod print-object ((node dl-node) stream)
  "Allow pretty-printing of the a node."
  (let ((prev-node (dl-node-prev-node node))
        (next-node (dl-node-next-node node)))
    (format stream "{ ~A <- ~A -> ~A }" 
            (and prev-node (dl-node-value prev-node))
            (dl-node-value node)
            (and next-node (dl-node-value next-node)))))

 

There are several features of Lisp that I find very useful, and miss when I’m working in, for example, C++. One in particular is the ability to create new flow-control syntaxes.

To draw from a real example from my work, let’s say I have an arbitrary closed polygon, defined as an ordered sequence of points, and I’m interested in performing operations on these points, either individually, pairwise, or in triplets. I also might want to go in forward or reverse directions.

I’ll represent my polygons as doubly-linked lists. Not circular, it will be up to the user of the data structure to wrap around, if necessary, upon reaching the end of the list.

I’m going to be developing and refining this code, starting simply, but moving on to doing things better. Here’s our first iteration of a doubly-linked list, with a few helper functions.

Work will continue in a later post.

;; Define the node.  They're opaque types to the user, but they double
;; as iterators (also opaque).
(defstruct (dl-node)
  (value        nil)
  (next-node    nil)
  (prev-node    nil))

;; Define the doubly-linked list.
(defstruct (dl-list)
  (first-node   nil)
  (last-node    nil))

(defun dl-list-empty-p (dl-list)
  "Returns non-nil if the list is empty."
  (not (dl-list-first-node dl-list)))

(defun dl-list-length (dl-list)
  (let ((rv 0))
    (do ((iter (dl-list-iter-front dl-list) (dl-list-iter-next dl-list iter)))
        ((not iter) rv)
      (incf rv))))

(defun dl-list-push-front (dl-list val)
  "Push a value onto the front of the list."
  (let* ((first-node (dl-list-first-node dl-list))
         (new-node (make-dl-node :value val
                                :next-node first-node
                                :prev-node nil)))
    (when first-node
      (setf (dl-node-prev-node first-node) new-node))

    (setf (dl-list-first-node dl-list) new-node)
    (unless (dl-list-last-node dl-list)
      (setf (dl-list-last-node dl-list) new-node))
    new-node))

(defun dl-list-push-back (dl-list val)
  "Push a value onto the back of the list."
  (let* ((last-node (dl-list-last-node dl-list))
         (new-node (make-dl-node :value val
                                :next-node nil
                                :prev-node last-node)))
    (when last-node
      (setf (dl-node-next-node last-node) new-node))

    (setf (dl-list-last-node dl-list) new-node)
    (unless (dl-list-first-node dl-list)
      (setf (dl-list-first-node dl-list) new-node))
    new-node))

(defun dl-list-pop-front (dl-list)
  "Remove the first value from the list and return it.  Returns nil if the list is empty."
  (when (dl-list-first-node dl-list)
    (let* ((first-node (dl-list-first-node dl-list))
           (second-node (dl-node-next-node first-node))
           (rv (dl-node-value first-node)))
      (cond
        (second-node
         (setf (dl-node-prev-node second-node) nil)
         (setf (dl-list-first-node dl-list) second-node))
        (t
         (setf (dl-list-first-node dl-list) nil
               (dl-list-last-node dl-list) nil)))
      rv)))

(defun dl-list-pop-back (dl-list)
  "Remove the last value from the list and return it.  Returns nil if the list is empty."
  (when (dl-list-last-node dl-list)
    (let* ((last-node (dl-list-last-node dl-list))
           (penultimate-node (dl-node-prev-node last-node))
           (rv (dl-node-value last-node)))
      (cond
        (penultimate-node
         (setf (dl-node-next-node penultimate-node) nil)
         (setf (dl-list-last-node dl-list) penultimate-node))
        (t
         (setf (dl-list-first-node dl-list) nil
               (dl-list-last-node dl-list) nil)))
      rv)))

(defun dl-list-iter-front (dl-list)
  "An iterator to the first element in the list."
  (dl-list-first-node dl-list))

(defun dl-list-iter-back (dl-list)
  "An iterator to the last element in the list."
  (dl-list-last-node dl-list))

(defun dl-list-iter-next (dl-list iter)
  "The next iterator, or nil if we're at the end of the list."
  (declare (ignore dl-list))
  (dl-node-next-node iter))

(defun dl-list-iter-prev (dl-list iter)
  "The previous iterator, or nil if we're at the beginning of the list."
  (declare (ignore dl-list))
  (dl-node-prev-node iter))

(defun dl-list-iter-contents (dl-list iter)
  "The value of the list element pointed to by the iterator."
  (declare (ignore dl-list))
  (dl-node-value iter))

(defun dl-list-insert-after-iter (dl-list iter val)
  "Insert a value into the list after the position of the iterator."
  (let* ((next-node (dl-node-next-node iter))
         (new-node (make-dl-node :value val 
                                 :next-node next-node
                                 :prev-node iter)))
    (cond
      (next-node
       (setf (dl-node-prev-node next-node) new-node))
      (t
       (setf (dl-list-last-node dl-list) new-node)))
    (setf (dl-node-next-node iter) new-node)
    new-node))

(defun dl-list-insert-before-iter (dl-list iter val)
  "Insert a value into the list before the position of the iterator."
  (let* ((prev-node (dl-node-prev-node iter))
         (new-node (make-dl-node :value val 
                                 :next-node iter
                                 :prev-node prev-node)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) new-node))
      (t
       (setf (dl-list-first-node dl-list) new-node)))
    (setf (dl-node-prev-node iter) new-node)
    new-node))

(defun unit-test ()
  (let ((test-list (make-dl-list)))
    (assert (dl-list-empty-p test-list))
    (dl-list-push-front test-list 10)
    (assert (not (dl-list-empty-p test-list)))
    (assert (= (dl-list-length test-list) 1))
    (dl-list-push-front test-list 5)
    (assert (not (dl-list-empty-p test-list)))
    (assert (= (dl-list-length test-list) 2))
    (dl-list-push-back test-list 20)
    (assert (not (dl-list-empty-p test-list)))
    (assert (= (dl-list-length test-list) 3))
    (let ((iter (dl-list-iter-front test-list)))
      (assert (= (dl-list-iter-contents test-list iter) 5))
      (dl-list-insert-after-iter test-list iter 7)
      (assert (not (dl-list-empty-p test-list)))
      (assert (= (dl-list-length test-list) 4))

      (setf iter (dl-list-iter-next test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (dl-list-insert-before-iter test-list iter 6)
      (setf iter (dl-list-iter-prev test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 6))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 10))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 20))

      (setf iter (dl-list-iter-next test-list iter))
      (assert (not iter)))

    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 5))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 20))

    (assert (= (dl-list-pop-front test-list) 5))
    (assert (= (dl-list-length test-list) 4))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 6))

    (assert (= (dl-list-pop-back test-list) 20))
    (assert (= (dl-list-length test-list) 3))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 10)))
  t)

(defmethod print-object ((node dl-node) stream)
  "Allow pretty-printing of the a node."
  (let ((prev-node (dl-node-prev-node node))
        (next-node (dl-node-next-node node)))
    (format stream "{ ~A <- ~A -> ~A }" 
            (and prev-node (dl-node-value prev-node))
            (dl-node-value node)
            (and next-node (dl-node-value next-node)))))