Why aren't cyclic lists considered lists in Scheme?

Question

I haven't found any questions regarding this for the Scheme programming language, so I hope this isn't a duplicate.

While doing some dabbling in the interpreter I encountered a peculiar occurrence:

(define li (list 'a 'b 'c 'd 'e))

(list? li)
;; -> #t

(set-cdr! (cddddr li) li) ;; list is now circular

(list? li)
;; -> #f

Apparently, upon changing the list object to now be cyclic, list? will return #f.

How come Scheme doesn't consider a cyclic list to be a list? I guess it has something to do with the formal definition of list, but how does Scheme formulate such definition? Also, how is list? even implemented in terms of possessing the property of detecting a cyclic list?

Answer 1

I think that a natural definition of a list is that a list is either:

• the empty list, ();
• or a pair whose car is any object and whose cdr is a list.

Note that a circular list does not meet this criteria, and neither does something like (x . y) or (x y . z).

I believe that this is the definition of 'list' used by RⁿRS for at least some values of n (in particular it's the definition used by R5RS). R5RS is clear, again, that list? must return false for a circular list (so in particular it must have an occurs check or something like it).

Other Lisps have historically been much more lax about this: Common Lisp for instance defines it's listp simply checks if an object is either () or a cons, and defines lists as being elements of that type. What Scheme calls 'lists' Common Lisp calls 'proper lists'.

Here is a version of list? which uses an a tortoise-and-hare algorithm to check for circularity (this may not be correct and I think is overcomplex even if it is, but it's late):

(define (lyst? l)
  (cond
    [(null? l)
     #t]
    [(not (cons? l))
     #f]
    [else
     (let lyst-loop? ([tortoise l]
                      [hare (cdr l)])
       (cond [(eq? hare tortoise)
              #f]
             [(null? hare)
              #t]
             [(cons? hare)
              (cond [(null? (cdr hare))
                     #t]
                    [(not (cons? (cdr hare)))
                     #f]
                    [else
                     (lyst-loop? (cdr tortoise)
                                 (cdr (cdr hare)))])]
             [else
              #f]))]))