On Sun, Jun 10, 2018 at 12:38 PM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:

Your comment about the O(1) space behavior strikes a nerve. Correct me if I am wrong, but in the following modified example, (x+ (srfi-155-integers) N) has O(1) space behavior with R7RS-small's (scheme lazy), but O(N) space behavior with any currently discussed implementation of (srfi 155). (Here, I am assuming a "correctly" implemented parameterize as in SRFI 157.)(define dummy (make-parameter #f))(define (srfi-155-integers)(let next ((n 0))(parameterize ((dummy 1))(delay (cons n (next (+ n 1)))))))(define (x+ stream n)(let loop ((s stream) (r 0) (n n))(if (= n 0)r(loop (cdr (force s))(+ (car (force s)) r)(- n 1)))))So (srfi 155) would be regression to (scheme lazy) in this regard.

I had to massage the x+ function slightly for my weak compiler -- it captures the whole lexical environment on lambda, not just the variables actually referenced -- so the original stream passed to x+ stays alive, and since each force call memoizes successive values, I was getting O(N) behavior even with (scheme lazy). So, a simple **(set! stream #f)** form inside the loop worked around that, and I get O(1) behavior with (scheme lazy) and O(N) behavior with (srfi 155).

We expect there to be a cost when delay captures the extent, and force resurrects it -- am I mistaken in that respect? The expression "(cons n (next (+ n 1)))" is the delayed expression and is evaluated in a context where the current marks have been "grown" by one notch each time - so the marks are growing at every step.

Now I'm realizing it's obvious -- I CAN fix this by filtering the parameter-related mark association to just the most-recent ones -- only for the continuation about to be invoked by with-dynamic-extent. The beauty of (srfi 157)'s API is that it does not expose the client to keys the client doesn't know about - so no code could get broken by this. Ie. nobody can complain that I'm screwing with their marks, because the marks for parameters are not *their* marks.

So, then can we acknowledge that if (srfi-155-integers) were written differently:

(define (srfi-155-integers)

(let next ((n 0))

(with-continuation-mark 'dummy 1

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

...then we could **not** prevent the O(N) behavior without breaking (srfi 157)'s api -- (because I have assumed that (srfi 157)'s api are a valid aspect of "dynamic extent" to be correctly supported by 154/155).

Thanks for your clearly-written example. I'll confirm when I have more bounded-space tests passing with the proposed fix.

-jim