• Home
• All tickets
• All wiki pages

Source for wiki PureDelayedGloria version 1

author

cowan

comment

ipnr

70.44.231.3

name

PureDelayedGloria

readonly

0

text

= 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-entrancy 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-entrancy 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-entrancy, 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)))
 
))
}}}

time

2013-02-17 12:55:59

version

1