Simpler implementations incorrect! AndrevanTonder 14 Nov 2007 19:33 UTC
Resending (hopefully this time the phase of the moon is favorable for the dang message to be archived). On Wed, 14 Nov 2007, Phil Bewig wrote: > With this version of promises, (unit-test) passed, and so did the bounds > tests, but computing the 50th element of the stream of pythagorean triples > seemed to fail: > > (stream-ref > (stream-of (list a b c) > (n in (stream-from 1)) > (a in (stream-range 1 n)) > (b in (stream-range a n)) > (c is (- n a b)) > (= (+ (* a a) (* b b)) (* c c))) > 50) > > In fact, it did not fail, but merely ran very slowly. Jos ran (unit-test) > with profiling enabled, and found that with the previous version of promises > stream-force was called 392874 times but with the new (attached) version of > promises stream-force was called 7065035 times. I have found the problem. First, let me just reassure you that I believe the implementation in the finalized SRFI-45 is correct. However, both mine and Eli's supposedly simpler implementations, starting in message http://srfi.schemers.org/srfi-45/post-mail-archive/msg00010.html in the post-finalization list, are incorrect. Just printing out the argument to FORCE in the above example shows ever growing chains of "shared" promises like this: #3(#0=(record-marker) #1=#4(#0# #2=#4(#0# #2# :record-type (name field-tags)) stream-type (box)) (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared . #3(#0# #1# (shared The reference implementation in the finalized SRFI document avoids this issue by a more careful treatment of indirections. > For my SRFI-41, I have reverted to the original version of promises in the > base SRFI-41 document (not any of the post-finalization versions). But I > would still like to know what happened, and if possible replace the promises > of SRFI-41 with a more efficient version that avoids one level of boxing. I think that is as good as can get. It is exactly the extra level of boxing that avoids the above problem. Andre