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

From: William D Clinger <will>
Date: Wed Oct 4 15:21:24 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:
> However, I do not understand how an implementation of this
> type, that does not do up-front checking, can guarantee that
> an error will be raised in Shiro's example (given likely
> implementations of call/cc continuations).

Nothing in the draft R6RS requires the for-each
procedure to be implemented in portable R6RS
Scheme. Indeed, one would expect the slower
implementations to implement for-each in some
other language.

When I describe an implementation of for-each,
therefore, I can postulate any convenient and
realistic semantics for concurrent threads.
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. This code usually performs
the exception check twice; that can be fixed,
but I leave it as an exercise for the reader.
I will also allow the reader to repair SRFI-18
so as to handle multiple values correctly.

; 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)))

Will
Received on Wed Oct 04 2006 - 15:21:19 UTC