Reducing a circular list in Common Lisp

Question

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.

Note that if you use CCL then (reduce #'+ *foo* :end 3) produces 3, while (reduce #'+ *foo*) signal a [Condition of type CCL::IMPROPER-LIST]. — Renzo
So, it should be interesting to know how the different systems check for an “improper list”. Do they examine the whole list before processing it? Do they have this information in the type of the list? What it is the correct semantics? (even if today it seems that nobody cares any more for formal semantics of programming languages). — Renzo
Maybe the SBCL maintainers would accept a patch which would enable SBCL to report such an error? — Rainer Joswig

sds sds · Accepted Answer · 2015-08-14T14:44:05

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.

Reducing a circular list in Common Lisp

1 Answers