[r6rs-discuss] [Formal] Requirement to detect circular lists

From: William D Clinger <will>
Date: Thu Oct 5 14:02:33 2006

I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors, and
this message should not be confused with the editors'
eventual formal response.

Andre van Tonder wrote:
> Thank you - I think I understand what you are getting at.
> One possible problem I see with this implementation, though,
> assuming the circular case where an exception must be raised,
> is that whatever the relative sizes of the time quanta
> assigned to the threads, one can exhibit a "proc" that uses
> set-cdr! to grow the circular list in the thread "thread"
> faster than the "exception-check" thread can catch up with it.

Right. I should have said it works only when pairs are not
mutable.

> One solution I see is to build in some threshold which would
> trigger "thread" to be put to sleep indefinitely until
> "exception-check" completes its work.

For example, it suffices to arrange for the thread to block
if it attempts to use set-cdr!, and then to unblock it after
the call to exception-check has returned.

It might be possible to implement the above using the condition
objects of SRFI-18 to communicate with set-cdr!, but I decided
I didn't really want to understand SRFI-18 all that well.

Fun and games aside, let's review the situation:

The draft R6RS requires procedures to raise an exception if
a list argument is not a plausible list, or in some cases a
plausible list up to k, or something else like that.

This is no big deal for first order or nearly first order
procedures like append, apply, assoc, assq, assv, datum->syntax,
length, list->string, list->vector, list-ref, list-tail,
make-enumeration, member, memq, memv, remove, remq, remv,
and reverse.

It is a much bigger deal for higher procedures like assp,
exists, filter, find, fold-left, fold-right, for-each,
forall, map, memp, partition, and remp. Although it is
possible to imagine many different ways to satisfy the
requirements of the draft R6RS, the simplest and most
obvious way to satisfy the draft R6RS requirements is to
check the list argument(s) before making any calls to the
procedure argument.

That has adverse consequences for performance.

It complicates the specification of these procedures, and
complicates their specification greatly when pairs are
mutable.

It implies that exceptions will sometimes be raised even
for arguments that are plausible lists, since it is
infeasible to prove that a mutable pair is not a plausible
list when there are multiple calls to unknown procedures,
and impossible to prove that a mutable pair is not a
plausible list in the presence of concurrency.

Furthermore it provides only the illusion of safety.

When pairs are mutable, the list arguments may be lists of
the same length at the beginning, when the check is made,
but have different lengths or not be lists at all after
the first call to a procedural argument. The draft R6RS
does not even attempt to specify the behavior of higher
order procedures whose list arguments are mutated during
calls to their procedure argument. It seems to me that
all bets must be off, aside from the general property of
weak safety guaranteed by section 4.4 (and that general
safety property would continue to hold even if all of the
other "an exception is raised" requirements were dropped
from the report).

I do not believe an illusion of safety can justify the
inefficiency, complexity, and indeterminate exceptions
that result from requiring implementations to raise an
exception whenever the list arguments of a higher order
procedure are not lists, or do not have the same length.

Indeed, I believe an illusion of safety is worse than an
honest acknowledgement of danger.

In my view, this is a fairly pervasive problem with the
draft R6RS. We will have several more conversations of
this sort before the six months are up.

It should be evident that I am not speaking for the R6RS
editors.

Will
Received on Thu Oct 05 2006 - 14:02:22 UTC