[r6rs-discuss] Re: Plausible list problems

From: William D Clinger <will>
Date: Tue Oct 3 13:53:12 2006

I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors.

Andre van Tonder wrote:
> 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

Although it is undecidable whether a list is
plausible, the draft R6RS requirement can be
implemented because it *requires* an exception
to be raised if list is not a plausible list,
while *allowing* an exception to be raised even
if list is a plausible list.

To implement that, the procedure attempts to
prove that list is a plausible list. If a
good-faith attempt fails, then the procedure
is either required or is allowed to raise an
exception, so it raises an exception. See
the note in section 23.3.1 for the length
procedure, whose specification you quoted.

I agree that section 23.3.1 can and should be
more careful about this. In particular, the
fact that implementations are allowed to raise
an exception just because their attempt to
prove that the argument is a plausible list
fails, when an attempted proof with different
timing might have succeeded, is explained only
in the notes.

This is an example of a more widespread problem,
to which I will soon allude in a long note, and
for which I intend to submit a formal comment.

> (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)?

For the length procedure, whose specification
you quoted, that can happen only in systems
that allow concurrent execution. See the note
referenced above.

> 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.

Once again, implementations are allowed to raise
exceptions whenever their good-faith attempt to
prove that the list is a plausible list fails.

It is the programmers' responsibility to make sure
that the list is not just a plausible list, but an
actual list, throughout the dynamic extent of the
call to the procedure. The specification of these
procedures in the draft R6RS does not describe the
programmers' responsibility for avoiding the
exception; it describes instead the implementors'
responsibility for detecting the exception. That
is an example of the problem on which I will comment
formally at some later date.

Will
Received on Tue Oct 03 2006 - 13:52:53 UTC