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 [email protected] http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
