[R6RS] cyclic list exceptions

dyb at cs.indiana.edu dyb at cs.indiana.edu
Wed May 10 14:35:51 EDT 2006


On the subject of requiring map, reverse, append, etc., to check for
cyclic lists, Mike claims that the programmer usually gets feedback in the
form of nontermination when one of these procedures is passed a cyclic
list.  I initially bought claim, thinking only of an implementation that
doesn't check for cycles, but what if an implementation does check for
cycles but chooses do do something other than raise an exception?
For example, when given a cyclic list, an implementation of map might
reasonably return a cyclic list, e.g.:

  (map add1 '#1=(1 2 3 . #1#)) => #1=(2 3 4 . #1#)

An implementation of append might reasonably ignore all arguments after
the first cyclic list:

  (append '(a) '#1=(b . #1#) '(c)) => (a . #1=(b . #1#))

An implementation of reverse might reasonably return a copy of its input
for the degenerate case where each element of the list is the same:

  (reverse '#1=(1 1 1 . #1#)) => #1=(1 1 1 . #1#)

of course it might as reasonably return #1=(1 . #1#) for the same input.

These rather cool alternatives to nontermination are all legitimate, along
with other, possibly less reasonable, alternatives, if we don't require an
exception to be raised for cyclic inputs.

Bottom line: I think we should require these procedures to raise an
exception when they receive a cyclic list.  If an implementor wants to
do something more cool, they can do so with versions exported from
an implementation-specific library.

On the other hand, it would be okay with me to require that memq, assq,
etc., return #f if the element or key isn't found in a cyclic input list,
e.g.:

  (memq 'a '#1=(b c d . #1#)) => #f

and I think we *should* require that list-ref and list-tail to do the
"obvious" thing for cyclic lists.

  (list-ref '#1=(a b c . #1#) 5) => c
  (list-tail '#1=(a b c . #1#) 5) => #1=(c a b . #1#)

Kent



More information about the R6RS mailing list