[r6rs-discuss] Plausible list problems

From: Andre van Tonder <andre>
Date: Tue Oct 3 13:52:51 2006

On Tue, 3 Oct 2006, Andre van Tonder wrote:

> To muddy the waters even further, let me point out that detecting cycles is
> not a correct way to test if the list is plausible according to the
> formal definitions. In particular, there might be a cycle at time t_1
> during the traversal that is not a cycle when we complete the circle later
> in the traversal. Such a list could still be a perfectly fine plausible
> list according to the definition, but would wrongly be rejected by an
> implementation that detects cycles.

Here is an example that illustrates this problem:

(let ((ones (list 1)))
   (set-cdr! ones ones)
   (map (let ((time 0))
          (lambda (x)
            (set! time (+ 1 time))
            (when (= time 4)
              (set-cdr! ones '()))
            x))
        ones)) ;==> (1 1 1 1)

According to the definition, ones is a plausible list of length 4 between entry
and exit of MAP. An implementation that does not detect cycles will give the
above output. An implementation that does detect cycles (e.g., MzScheme and
Chez) will (wrongly according to the draft) reject it.

Andre
Received on Tue Oct 03 2006 - 13:52:12 UTC