[r6rs-discuss] Plausible list problems

From: Andre van Tonder <andre>
Date: Tue Oct 3 11:57:17 2006

Another remark: The document states

"in other words, an exception must be raised if list is not a plausible list".

This seems like an impossible requirement, since whether or not list is
plausible is undecidable, isn't it (the test may not terminate, since
the list may be infinite without being circular, by being modified
faster than the test can catch up with it)?

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.

Andre
Received on Tue Oct 03 2006 - 11:56:37 UTC