[Scheme-reports] Promises that force themselves

[Alan Manuel Gloria <almkglor@x>]

Hello,

R7RS draft 9 has the following example:

>  1: (define count 0)
>  2: (define p
>  3:   (delay (begin (set! count (+ count 1))
>  4:                 (if (> count x)
>  5:                     count
>  6:                     (force p)))))
>  7: (define x 5)
>  8: p
>  9: (force p)

force has the following description:

> If no value has been computed for the promise,
> then a value is computed and returned.  The value
> of the promise must be cached (or "memoized") so
> that if it is forced a second time, the previously
> computed value is returned.

Arguably, the "first time" the promise is forced is at line 9 in the
example, and the "second time" is at line 6.  However, at that time
line 6 gets executed, no value has been computed *yet*, so presumably
this example follows the spirit of the law.

However, this example, I think, limits implementation options.

1.  The G-Machine technique for laziness, which black-holes unforced
promises at time of forcing, cannot be used, because it would have to
raise a "black hole encountered!" exception at line 6.

2.  We have to be more careful of implementing promises in a
multithreaded environment.  It could be desirable that, if two threads
force the same promise, one runs the delayed expression and the other
waits for the value (for example the delayed expression requires
taking external resources, such as a trip to a database or whatnot).

For #2 above:

This can be implemented using some sort of very simple lock on each
promise; a thread forcing the promise retains the promise locked, and
only unlocks when execution exits the promise code (via continuation
call or normal return).  But if promises are required to be able to
safely force themselves *and safely force another promises that also
force the first promise*, we need to use a global lock on all promises
- a recursive thread-owned lock will not suffice!

Consider the case of two promises p and q, and two threads A and B.

p will cause q to be forced, unless some external variable (analogous
to count in the R7RS draft example) has some condition.

q will cause p to be forced, unless (again) some external variable has
some condition.

In the case where only one thread forces p or q, the looping ends when
the external variable of one of the promises reaches the desired
condition (this matches the behavior of the R7RS draft 9 example).

But consider instead:

A forces p, and B forces q.  If p and q have their own recursive
locks, then eventually B reaches the part where it has to force p -
whose lock is owned by A.  And eventually A reaches the part where it
has t force q - whose lock is owned by q.  Deadlock occurs, so even if
the external variables reach the condition, both A and B have
deadlocked.

Thus, to implement this safely on a multithreaded system requires a
single global lock for all promises.

--

I think it's better to change the example to the following:

> (define x 5)
> (define p (delay x))
> p  => a promise
> (force p) => 5
> p => a promise, still
> (begin (set! x 42)
>        (force p)) => 42

And then, add the following to force:

> A delayed expression which, directly or indirectly, causes
> itself to be forced (including forcing another promise that
> forces itself) will result in unspecified behavior.  For
> example:
>
>  (define count 0)
>  (define p
>    (delay (begin (set! count (+ count 1))
>                  (if (> count 5)
>                     count
>                      (force p)))))
>  p => a promise
>  (force p)  => unspecified

--

I've done a cursory search through the archives, and it seems most
discussions about promises involve auto-forcing, so I'm not sure if
this was discussed before.


Sincerely,
AmkG

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