Trouble with unintended circular lists in common lisp

Question

Running sbcl 1.3.7 in linux, I have an object which has a slot which is intentionally a circular list, following Rainer Joswig's advice in Circular list in Common Lisp and a global variable which is intended to be a proper list (not intended to be circular).

(setf *print-circle* t)

(defun circular (items)
   (setf (cdr (last items)) items)
   items)

(defclass circular ()
  ((items :accessor items :initarg :items)))

(defmethod initialize-instance :after ((c circular) &rest initargs)
   (setf (slot-value c 'items)
         (circular (slot-value c 'items))))

(defmethod next-item ((c circular))
  (prog1 (first (slot-value c 'items))
    (setf (slot-value c 'items)
          (rest (slot-value c 'items)))))

(defparameter *notes* (make-instance 'circular :items '(A A# B C C# D D# E F F# G G#)))

(defparameter *stuff1* '(A A# B C C# D D# E F F# G G#))
(defparameter *stuff2* (list 'A 'A# 'B 'C 'C# 'D 'D# 'E 'F 'F# 'G 'G#))

My problem is the parameter *stuff1* which should be a simple list of symbols. Or so I thought. Compiling the above in sbcl, *stuff1* returns

> *stuff1*
#1=(A |A#| B C |C#| D |D#| E F |F#| G |G#| . #1#)

I definitely did not expect this non-circular list to turn into a Sharpsign Equal-Sign item. More to the point, even though I (setf *print-circle* t) the following hangs with no error from sbcl:

(member '|Bb| *stuff1*)

On the other hand, *stuff2* works as expected.

So, two questions, (1) why is the *stuff1* list turning into a circular cons, resulting in an improper list and *stuff2* stays a proper list and (2) how do I test membership in what *stuff1* has become?

Obviously I can use the *stuff2* version, but I am apparently misunderstanding something critical here. Any pointers are appreciated.

Rainer Joswig · Accepted Answer · 2016-09-04T10:15:30.747

Literal Lists

'(a b c) is a quoted literal list in your code. The Common Lisp standard says the effects of changing those is undefined.

Rule: Don't change literal lists. Treat them as constant data. See functions like list, copy-list and copy-tree for how to create fresh new lists at runtime.

Sharing literal objects in code

Two literal lists in the code like (a b c) and (a b c) can be detected by the compiler to be equal. Since they are constant data (see above), the compiler can generate code, such that it allocates only one list and this list is shared in more than one place. The SBCL file compiler does that.

Rule: a clever compiler may share equal literal lists.

Circular MEMBER

Common Lisp's member only supports proper lists. Not circular lists.

A mapc function for circular-lists is a good building block:

(defun circular-mapc (function list)
  (loop for fast = list then (cddr fast)
        for slow = list then (cdr slow)
        do
        (funcall function (car slow))
        (when (eq (cddr fast) (cdr slow))
          (return-from circular-mapc nil))))

(defun circular (items)
  (check-type items cons)
  (setf (cdr (last items)) items)
  items)

(defun circular-member-p (item list)
  (circular-mapc (lambda (e)
                   (when (eql item e)
                     (return-from circular-member-p t)))
                 list))

Example:

CL-USER 38 > (circular-member-p 'a (circular (list 'a 'b 'c 'd 'e)))
T

CL-USER 39 > (circular-member-p 'b (circular (list 'a 'b 'c 'd 'e)))
T

CL-USER 40 > (circular-member-p 'c (circular (list 'a 'b 'c 'd 'e)))
T

CL-USER 41 > (circular-member-p 'd (circular (list 'a 'b 'c 'd 'e)))
T

CL-USER 42 > (circular-member-p 'e (circular (list 'a 'b 'c 'd 'e)))
T

CL-USER 43 > (circular-member-p 'f (circular (list 'a 'b 'c 'd 'e)))
NIL

I had not realized that sbcl would reuse the literal list, re-creating the circularity. This solves the problem. — wolery123, Sep 04 '16 at 11:13
@wolery you may find [Unexpected persistence of data](http://stackoverflow.com/questions/18790192/unexpected-persistence-of-data) a helpful read. — Joshua Taylor, Sep 05 '16 at 12:59

Trouble with unintended circular lists in common lisp

1 Answers1