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