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