[Scheme-reports] R7RS-large library proposal: Pure Delayed Evaluation

[Alan Manuel Gloria <almkglor@x>]

I have no idea what the proper procedure is for proposing a library in
R7RS-large (there's no procedure in the Trac website, and searching
for "r7rs large proposal procedure" seems to suggest that proposal are
just put on the mailinglist, so well.

--

Title: Pure Delayed Evaluation

==Rationale==

Scheme provides delayed evaluation by the (delay ...) and (force ...)
forms.  However, the small language specifications do not mention the
interaction between delayed evaluation and threads.

In addition, the small language specifications (by virtue of an
example for delayed evaluation) require that promises should be
re-entrant, such that promises may also, while being forced, cause
themselves to be directly or indirectly forced.  However, it is not
clear (as of R7RS draft 9) which of the values returned by a
re-entrant delayed expression will be returned by which invocations of
force, especially if this re-entrance is not in tail position.

The interaction between the re-entrancy requirement and threads
generally implies the following:

1.  Since promise re-entrancy is a requirement of R7RS-small, but
threads are not, then the re-entrancy requirement is more important
and will be more likely to be implemented.

2.  This can mean that, in a multithreaded Scheme implementation, if
multiple threads force the same promise, the delayed expression may be
executed in parallel by multiple threads.  This is because a naive
implementation of delayed evaluation simply uses a flag that is
toggled only when the delayed expression calls its
continuation/returns a value; multiple threads may enter the force
code with the flag in the "not yet forced" state, and thus multiple
threads might execute the delayed expression.

3.  A multithreaded Scheme implementation could set a flag that is
toggled at the start of forcing instead, and to suspend other threads
that attempt to force the promise when that flag is in the "started
forcing" state; it can support direct re-entrancy by associating the
flag with a thread, so that the same thread that re-enters a promise
will not be suspended.  This enforces that even with multiple threads,
the delayed expression will only be executed exactly once.  However,
such a flag would have to be global to all promises; otherwise,
consider this case: two promises p and q are re-entrant to each other
(unless the specification specifically disallows mutual re-entrancy,
but to require support for self-re-entrance but disallow mutual
re-entrance does not seem to fit Scheme's spirit).  Thread A starts
forcing p, while thread B starts forcing q.  p's flag is set to
"started forcing" and then associated with thread A, while q's flag is
set to "started forcing" and then associated with thread B.
Eventually, A forces q, which is in "started forcing" state but
associated with thread B, and so suspends; thread B encounters the
mirror situation.  Both threads are suspended, and the mutual
re-entrance does not follow the implications of the spec.

Finally, the small language specifications require that promises may
be used in iterative lazy algorithms, and requires the (delay-force
...) form to support iterative lazy algorithms.  This, together with
the re-entrancy requirement, constrains the possible implementations
to be practically just the implementation shown in SRFI-45.

This proposed library seeks to do the following:

1.  It specifies a particular interaction between delayed evaluation
and threads, which users of this library must observe.

2.  It removes the re-entrancy requirement, to allow implementations
other than the SRFI-45 one.

== Specification ==

(pure-delay <expr>)
Creates a promise whose value can be forced by (pure-force ...).  The
expression is not executed immediately.

(pure-force <promise>)
Forces the delayed expression.

Conceptually, the user of this library can consider the promise to be
in one of three states:

not-forced
being-forced
already-forced

The pure-force procedure attempts to move the state into
already-forced.  If the promise is already in that state, then the
promise's value is returned directly.

If the promise is in the not-forced state, then pure-force puts it
into the being-forced state, and executes the delayed expression using
the current dynamic environment.  If the expression returns normally
(i.e. it invokes its continuation) then its return value (which must
be a single value) is cached as the promise's value, and the promise
is put into the already-forced state.  If the expression does not
return normally (i.e. it invokes a continuation that is parent to the
(pure-force ...) form) then the promise is put into the not-forced
state (this tends to exclude implementations that implement threads
using Scheme-level continuations, however).

If the promise is in the being-forced state, then (pure-force ...)
shall suspend the current thread (to be revived later when the promise
leaves the being-forced state) if the promise was put into the
being-forced state by a different thread; the behavior is otherwise
unspecified if the promise was put into that state by the current
thread (i.e. re-entrance, direct or indirect, is not allowed).  This
allows single-threaded Scheme implementations considerable leeway in
implementing pure promises (i.e. such implementations can just use
their normal r7rs-small promises), while constraining multithreaded
implementations to behavior that users can rely on.

If the delayed expression returns multiple times (i.e. it saves its
continuation and somehow causes it to be invoked multiple times) then
the behavior is unspecified.

(pure-delay-force <expr>)
This shall be similar to (pure-delay (pure-force <expr>)) except that
additional space should not be retained; if called iteratively, then
average constant space should be consumed by (pure-delay-force ...)

== Sample Implementation ==

(define-library (blah pure-delay)
  (export pure-delay pure-force pure-delay-force)
  (import (scheme base))
  (import (srfi 18))
  (begin

(define-record-type :promise
  (promise mtx state data)
  promise?
  (mtx mtx)
  (state state state-set!)
  (data data data-set!))

(define (delay-force:f f)
  (promise (make-mutex) 'not-forced f))
(define (delay:f f)
  (delay-force:f (lambda () (promise (make-mutex) 'already-forced (f)))))
(define-syntax pure-delay
  (syntax-rules ()
    ((pure-delay x) (delay:f (lambda () x)))))
(define-syntax pure-delay-force
  (syntax-rules ()
    ((pure-delay-force x) (delay-force:f (lambda () x)))))
(define (pure-force p)
  (define (dispatch sub-p)
    (let ((exec
             (begin
               (mutex-lock! (mtx sub-p))
               (let ((d (data sub-p)))
                 (case (state sub-p)
                   ((already-forced)
                     (lambda ()
                       (mutex-lock! (mtx p))
                       (type-set! p 'already-forced)
                       (data-set! p d)
                       (mutex-unlock! (mtx p))
                       d))
                   ((being-forced) (lambda () (thread-sleep! 0)
(dispatch sub-p)))
                   ((not-forced)
                     (type-set! sub-p 'shared)
                     (data-set! sub-p p)
                     (lambda () (dispatch (d))))
                   ((shared)
                     (lambda () (dispatch d))))))))
      (mutex-unlock! (mtx sub-p))
      (exec)))
  (let ((exec
           (begin
             (mutex-lock! (mtx p))
             (let ((d (data p)))
               (case (state p)
                 ((already-forced) (lambda () d))
                 ((being-forced) (lambda () (thread-sleep! 0) (pure-force p)))
                 ((not-forced)
                   (type-set! p 'being-forced)
                   (data-set! p #f)
                   (lambda () (dispatch (d))))
                 ((shared) (lambda () (pure-force d))))))))
    (mutex-unlock! (mtx p))
    (exec)))

))

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports