CODEWITHSUNDEEP
listcommon-lispreducesbclcircular-list
jobach
jobach

Reputation: 115

Reducing a circular list in Common Lisp

I've been playing around with circular list in Common-lisp (SBCL) and encountered the following problem when trying to call REDUCE on such a list.

First, we create a list:

CL-USER> (defvar *foo* (list 1 1 1 1))
*foo*

Of course, now we can do

CL-USER> (reduce #'+ *foo*)
4

or 

CL-USER> (reduce #'+ *foo* :end 3)
3

However, if we create a circular list:

CL-USER> (setf *print-circle* t)
CL-USER> (setf (cdr (last *foo*)) *foo*)
CL-USER> *foo*
#1=(1 1 1 1 . #1#)

Obviously (reduce #'+ *foo*) now never returns.

But when I tried

 CL-USER> (reduce #'+ *foo* :end 3)
 ...

I also got an infinite loop.

Why is that so? Is there any way to work around this without explicitly using loop construct such as LOOP or DO? I'm working with SBCL, but tried this with other implementations (CLISP, ECL), they all have the same problem.

Upvotes: 3

Views: 291

Answers (1)

sds
sds

Reputation: 60014

I agree that the behavior you observe can give one a start - after all, why not process the first 3 elements of the circular list?

Let us read the ANSI Common Lisp standard:

reduce:

  • Exceptional Situations: Should be prepared to signal an error of type type-error if sequence is not a proper sequence.

proper sequence:

  • a sequence which is not an improper list; that is, a vector or a proper list.

improper list:

  • a list which is not a proper list: a circular list or a dotted list.

Should be prepared to signal an error:

  • An implementation is always permitted to signal an error, but even in safe code, it is only required to signal the error when failing to signal it might lead to incorrect results. In unsafe code, the consequences are undefined.

So,

  • signaling an error is conforming
  • returning 3 is conforming as well
  • your code is not conforming - since its outcome cannot be determined by reading the standard
  • if we consider the interactive (REPL) code safe, then the infinite loop is not conforming
  • if we consider the REPL code unsafe, then infinite loop is conforming

Personally, I think that interactive code should be viewed as safe, so this is a bug. YMMV.

Upvotes: 5

Related Questions