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

From: AndrevanTonder <andre>
Date: Wed Oct 4 21:27:22 2006

On Wed, 4 Oct 2006, William D Clinger wrote:

> For example, I could postulate the SRFI-18
> semantics for threads, and also postulate fair
> scheduling (in the form of non-starvation for
> threads that aren't blocked).
>
> I will also assume that concurrency is available
> only within the implementation language, so the

> procedure argument to for-each can perform only
> a single-threaded computation.
>
> Then something like the following (untested)
> code should work.

> ...

> ; To avoid irrelevant complexity, this is just
> ; a two-argument version of for-each.
>
> (define (for-each2 proc list)
> (define (loop list)
> (cond ((null? list)
> (unspecified))
> ((null? (cdr list))
> (proc (car list)))
> (else
> (proc (car list))
> (loop (cdr list)))))
> (define (exception-check)
> (if (not (list? list))
> (contract-violation "for-each"
> "Argument may not be a plausible list"
> list)))
> (let ((thread
> (make-thread
> (lambda ()
> (dynamic-wind
> unspecified
> (lambda () (loop list))
> exception-check)))))
> (thread-start! thread)
> (exception-check)
> (thread-join! thread)))

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.

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.

Andre
Received on Wed Oct 04 2006 - 21:24:32 UTC