Bill Clementson's Blog

Using Circular Structures in CL

Wednesday, December 28, 2005

I often bookmark interesting c.l.l. threads in order to come back to them later on. One thread that I bookmarked a while ago was a discussion about "circular structures". Chris Perkins kicked off the discussion:

"Ok, I'll bite. I know what a circular structure is and how to go about creating one, but it's definitely not in my toolkit. I've never run across one in Lisp code I've read nor have I used one.

When would be a good time to use one? To what types of problems do they map well? Where do they give good leverage?"

"Funny you should mention mapping, since that's a place that circularity can be fun AS LONG AS at least one mapped element terminates. Consider:

(setq *print-circle* t) ;You'll be unhappy if you don't do this.


(defun circular-list (&rest elements)
  (let ((backbone (copy-list elements)))
    (nconc backbone backbone)))


(circular-list 'foo 'bar)
=> #1=(FOO BAR . #1#)


(let ((*print-length* 5) (*print-circle* nil))
  (circular-list 'foo 'bar))
(FOO BAR FOO BAR FOO ...)
=> #1=(FOO BAR . #1#)


(mapcar #'list (circular-list 'wrapper) '(a b c))
=> ((WRAPPER A) (WRAPPER B) (WRAPPER C))

But circularity is also useful in other cases that are more subtle.

(defstruct simple-person
  name
  parent ;just one, for simplicity
  (kids '()))


(let ((cain  (make-simple-person :name "Cain"))
      (enoch (make-simple-person :name "Enoch")))
  (setf (simple-person-parent enoch) cain)
  (setf (simple-person-kids cain) (list enoch))
  cain)


=> #1=#S(SIMPLE-PERSON :NAME "Cain"
                       :KIDS (#S(SIMPLE-PERSON :NAME "Enoch"
                                               :PARENT #1#)))

This is classically described as circular in that there are forward and backward pointers between parents and kids. In the database world, this would be replaced by using a unique key to each person that was opaque. In effect, one would put (list "Enoch") not (list enoch) in Cain's kids slot, hiding the circularity. In early Lisp, this was done by using symbols (usually called atoms). Lots of early knowledge systems did:

(putprop 'cain "Cain" 'name)
(putprop 'enoch "Enoch" 'name)
(putprop 'enoch 'cain 'parent)
(putprop 'cain '(enoch) 'kids)

so that

(get 'cain 'kids) => (ENOCH)

and

(get 'enoch 'parent) => CAIN

with no hint of circularity in sight because the name was opaque."

"Well, I don't normally use them, so I'm not sure about good leverage, but I do have at least a cute example of their usefulness. I suppose the serious answer is when you have naturally circular data structures such as recurring sequences, cyclic graph structures, doubly linked lists, etc."

(setq *print-circle* t)    ;; Otherwise this gets a bit messy.


(defvar *days* '#1=(monday tuesday wednesday thursday friday
                    saturday sunday . #1#))


;; Now you can do some fun things with this:


(member 'friday *days*)


;; And use it to build another cute little function:


(defun days-of-month (n-days starting-day)
  ;; Print out the date and day of the week for a
  ;; month of N-DAYS starting on STARTING-DAY
  (loop for d from 1 to n-days
        as day in (member starting-day *days*)
        do (format t "The ~:R is a ~:(~A~).~%" d day)))


;; Then try calling, i.e. for June & July 2003:


(days-of-month 30 'sunday)


(days-of-month 31 'tuesday) 

Any wimp can use circular structure, but real programmers know how to use circular code. Every once in a while there is discussion on c.l.l about the tradeoffs between recursion and iteration. Some say that recursion can be hard to read, and has execution efficiency issues on real hardware. Others say that iteration is hard to read, uses implied goto's, and is generally unlispy:"

<1> (defun recurse-n (n)
       (when (> n 0)
        (format t "~a~%" n)
        (recurse-n (1- n))))
recurse-n
<2> (defun iterate-n (n)
       (loop
        (when (= n 0)
          (return nil))
        (format t "~a~%" n)
        (decf n)))
iterate-n
<3> (recurse-n 5)
5
4
3
2
1
nil
<4> (iterate-n 5)
5
4
3
2
1
nil

But real programmers know how to avoid both! No silly repeating function calls, no implied goto's, just do it:

<5> (defun nike-n (n) . #1=((when (> n 0) (format t "~a~%" n) (decf n) . #1#)))
nike-n
<6> (nike-n 5)
5
4
3
2
1
nil
<7>

"[Warning: This is a tongue-in-cheek response. The suggested code at end is not legal CL code, although it will run interpreted in some implementations and the transcript is an honest copy of a real session.]"