Simpler implementations incorrect!

[AndrevanTonder <andre@xxxxxxxxxxxxx>]

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