The problem is the naive implementation of (srfi 154). The naive implementation has no way to find out whether two dynamic extents are effectively the same. In other words it cannot guarantee that an expression like

(with-dynamic-extent (current-dynamic-extent) (lambda () <expression>))

does not yield nested dynamic contexts.

On the other hand, the native Chibi implementation is in principle capable of simplifying the above expression and others. I have implemented this and removed the O(n^2)-behaviour.

In principle, the Chibi implementation could be made portable, but not without redefining call/cc, dynamic-wind, parameterize, and things dependent on parameterize (current-input-port, for example). So any implementor wishing to include SRFI 154/155 should use the portable reference implementation only for demonstration purposes. To make it usable, the Scheme system should adapt the provided sample implementations to its own implementation of dynamic-wind and parameter objects.


P.S.: I am soon pushing revised versions of SRFI 154 and SRFI 155 (with the above changes) to the repos.

Marc Nieper-Wißkirchen <> schrieb am Fr., 6. Okt. 2017 um 15:24 Uhr:
I was able to reproduce the O(n^2)-behavior here. For the general implementation, the O(n^2) behavior persists even when I remove support for "forcing-extent", i.e. when I remove the parameterization of "current-forcing-extent".


Marc Nieper-Wißkirchen <> schrieb am Fr., 6. Okt. 2017 um 14:36 Uhr:

thank you very much for your helpful comment. I think you analysis is correct. The current implementation (of the optional procedure "forcing-extent") yields a blow-up of the dynamic extents involved, which is not acceptable.

I am currently investigating how the sample implementation can be repaired. This should be resolved before SRFI 154 and SRFI 155 are finalized.


Shiro Kawai <> schrieb am So., 1. Okt. 2017 um 16:20 Uhr:
I've ported srfi-154 and srfi-155 reference implementations to Gauche and played with it to see performance implications, and noticed a peculiar behavior.  It might be something I'm doing wrong.

I use these infinite stream of integers and taking first n elements from it:

(define srfi-155-integers
  (let next ((n 0))
    (delay (cons n (next (+ n 1))))))

(define (xtake stream n)
  (let loop ((s stream) (r '()) (n n))
    (if (= n 0)
      (reverse r)
      (loop (cdr (force s))
            (cons (car (force s)) r)
            (- n 1)))))

While running with various n with fresh streams, I noticed it was taking O(n^2) time.

After some digging, I see the cause.

(delay (cons n (next (+ n 1))))

is expanded to:

(let ((dynamic-extent (current-dynamic-extent)))
     (let ((forcing-extent (current-dynamic-extent)))
       (with-dynamic-extent dynamic-extent
          (lambda ()
             (parameterize ((current-forcing-extent forcing-extent))
                 (cons n (next (+ n 1)))))))))

When it is forced, the inner expression (cons n (next (+ n 1))) is evaluated with the dynamic extent
which is the extent 'delay' is evaluated *plus* the extent added by parameterizing current-forcing-extent.  The call to next calls delay again, which captures this enhanced dynamic extent.

When the new promise is evaluated, the dynamic extent is further extended by yet another parameterization of current-forcing-extent, and so on.

Since the calls of force in xtake happens outside of those extended dynamic extent, every force executes before and after thunks of parameterization of current-forcing-extent, which gets longer as the stream unfolded.

To unsubscribe from this list please go to