Dear Jim,

thank you a lot for your shared thoughts and your experiments with SRFI 154, 155 and 157.

I have a question about the behavior of your code in the absence of current-forcing-extent. Shiro Kawai gave the following example code:

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

He observed an O(n^2) behavior with the naive implementation of SRFI 155. Neglecting current-forcing-extent (which is just a bonus), the expression H[n] given by

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

is expanded to:

(let ((dynamic-extent (current-dynamic-extent)))

(scheme-delay

(with-dynamic-extent dynamic-extent

(lambda ()

(cons n H[n + 1]))))))

(Here, scheme-delay is imported from (scheme lazy).)

The continuation of the expression H[n + 1] is strictly larger than the continuation of the expression H[n]. Therefore, the dynamic extent (which includes, in principle, the current continuation) captured in the evaluation of H[n + 1] is strictly larger than the dynamic extent captured in the evaluation of H[n]. This causes an O(n^2)-behavior.

How does your implementation circumvent this problem?

-- Marc

Jim Rees <xxxxxx@gmail.com> schrieb am Fr., 1. Juni 2018 um 06:14 Uhr:

I've spent a ton of time in the past week on the 157/154/155 triumvirate in my private scheme implementation. As of tonight, I've had the last of my eurekas to solve all the space blow-up problems, and have clean interfaces which pass all tests now.

For reference, I copied all the bounded space tests from the (srfi 45) document and run those automatically.

Maybe you already have this all sorted out, but I thought I'd chime rather than wait for your "final" code updates and then raise more issues.

Referencing the "srfi 157 version" of the (srfi 155) sample code...

Using a parameter for current-forcing-extent is not ideal. It's clear as you already know, that if parameters are based on, say, dynamic-wind, the bounded space tests will fail. So, presumably, you're depending on parameters being based on continuation marks. In that case, what you effectively have are two marks getting set in succession -- never otherwise apart. For my own code, I simplified this by simply cons'ing c and forcing-extent together into one object and one mark setting. By doing this, I eliminated any dependency on how parameterize works.

Next up -- setting that continuation mark still blows up the space tests -- because delay captures the current extent, which includes this mark, so each pass of, say, (delay-force (loop)) as the simplest example -- keeps capturing a deeper and deeper list of marks.

I realized that when delay captures the current extent, and when force captures the current extent (for forcing-extent), any values associated with key in those captured extents will never be used, nor can they be observed outside (srfi 155) since all the (srfi 157) interfaces requires that you know the keys you're interested in looking at. So, I added another API function to (srfi 154) extent-remove-marks which filters a given extent to remove all marks associated with a given key, and used this in those two places where (current-dynamic-extent) was called.

Boom. All tests pass now, including bounded space tests.

-jim

To unsubscribe from this list please go to http://www.simplelists.com/confirm.php?u=3gmIi49Ouh6YpCluDZXWeokz7NgY9f9r