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)
      (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.