Writing GNU Emacs Extensions

Circular Lists?!

Because we can destructively modify lists after they're created, we're not limited to building lists only out of pre-existing parts. A list can be made to refer to part of itself! Consider:

(setq x '(a b c))
(nthcdr 2 x) ⇒ (c)
(setcdr (nthcdr 2 x) x)      ;don't try this yet!

What's happening in this example? First we create a three-element list and place it in x. Next, we find the last cons cell with nthcdr . Finally, we replace that cell's cdr with x—which is the first cons cell in the list. The list is now circular: the former end of the list now points back to the beginning.

What does this list look like? Well, it starts out like this:

(a b c a b c a b c a b c a b c a b c a b c a b c ...

and it never stops. The reason I wrote don't try this yet! above is that if you executed the setcdr in the *scratch* buffer, Emacs would try to display the result—and would never finish. It would get caught in an infinite loop, albeit one that you can interrupt with C-g. Go ahead and try it now, but press C-g as soon as Emacs locks up. The longer you wait, the more it fills up the *scratch* buffer with repetitions of a b c.

Obviously, printing isn't the only thing you can do to a circular data structure that can make Emacs loop forever. Any operation that iterates over all the elements in a list will never terminate. Here's an important illustration:

(eq x (nthcdr 3 x)) ⇒ t       ;3rd cdr is same object as x
(equal x (nthcdr 3 x)) ⇒ never terminates!

If circular lists throw Emacs for a loop (pun ...