Stream problem redux
Joe Marshall
relying on the underlying implementation.
(define (integers-from n)
(cons n (delay (integers-from (+ n 1)))))
(define jrm-stream-ref
(letrec ((loop (lambda (stream index)
(cond ((not (pair? stream)) (error 'stream-ref 0))
((zero? index) (car stream))
(else (loop (force (cdr stream)) (- index 1)))))))
loop))
(define jrm-stream-filter
(letrec ((loop (lambda (predicate stream)
(cond ((not (pair? stream))
(if (null? stream)
'()
(error stream 'stream-filter 1)))
((predicate (car stream))
(cons (car stream)
(delay (loop predicate (force (cdr stream))))))
(else (loop predicate (force (cdr stream))))))))
loop))
(define (demo-stream-problem n)
(jrm-stream-ref
(jrm-stream-filter
(lambda (x) (zero? (modulo x n)))
(integers-from 0))
3))
(demo-stream-problem n) consumes O(n) memory rather than constant
memory. I believe that it ought not do so (though I understand
the mechanism through which it does), but that `fixing' the problem
is very difficult (though I believe it *can* be done, albiet with
considerable work). The reason that I believe that it ought not
run in O(n) time is because computing element n+1 of the integers
stream requires only the single prior element and filtering a
stream requires none of the prior elements.
I have actually run and tested this code on multiple scheme
implementations with the same results. (The prior posting I
just tested on one implementation. Mea culpa.)
Stephen McCracken
confirm or refute it.
In the R5RS "possible implementation" of force/delay, delay creates
two closures: a promise and a proc. The promise calls the proc, but
*not* in a tail position. With that in mind, consider the promise
created here:
(define jrm-stream-filter ...
...
(cond
...
((predicate (car stream))
(cons (car stream)
(delay (loop predicate (force (cdr stream))))))
The promise refers to the proc, which refers to the original stream.
Because the promise does not call the proc in a tail position, the
proc will be retained even after it finishes (in this case by calling
loop tail-recursively). Only after the promise finishes can the proc
be garbage collected. When the promise is forced, it may need to
expand a very long stream before it can return with another element
satisfying the predicate. However, none of the long intermediate list
can be garbage collected because the promise still holds a reference
to the head of the stream through the proc.
I confirmed that the example fails in my version of scheme48.
Interestingly, when I replaced delay with simple (lambda () ...)
thunks, it ran without a problem.
(define (integers-from n)
(cons n (lambda () (integers-from (+ n 1)))))
(define (jrm-stream-ref stream index)
(cond ((not (pair? stream)) (error 'stream-ref 0))
((zero? index) (car stream))
(else (jrm-stream-ref ((cdr stream)) (- index 1)))))
(define (jrm-stream-filter predicate stream)
(cond ((not (pair? stream))
(if (null? stream)
'()
(error stream 'stream-filter 1)))
((predicate (car stream))
(cons (car stream)
(lambda () (jrm-stream-filter predicate ((cdr stream))))))
(else (jrm-stream-filter predicate ((cdr stream))))))
(define (demo-stream-problem n)
(jrm-stream-ref
(jrm-stream-filter
(lambda (x) (zero? (modulo x n)))
(integers-from 0))
3))
"Joe Marshall" <prunes...@attbi.com> wrote in message news:<PW6T8.351531$cQ3.22120@sccrnsc01>...
Joe Marshall
"Stephen McCracken" <sam...@yahoo.com> wrote in message
news:18fbf543.02062...@posting.google.com...
> Here's my analysis of the problem. I'd appreciate it if a guru would
> confirm or refute it.
You're close.
> In the R5RS "possible implementation" of force/delay, delay creates
> two closures: a promise and a proc.
A promise contains a way to finish the computation that was
promised, thus it has an expression and environment. Some versions
of scheme implement this by simply capturing a thunk, others
capture the expression and environment separately.
In addition to the thunk, there is a place to memoize the return
value(s). Again, the details don't matter, so let us use this
model:
(define make-promise cons)
(define promise-flag car)
(define promise-thunk-or-value cdr)
(delay <form>) => (make-promise nil (lambda () <form>))
(define (force promise)
;; if it isn't forced, force it now
;; and memoize
(if (not (promise-flag promise))
(let ((value ((promise-thunk-or-value promise))))
(set-promise-flag! promise #t)
(set-promise-thunk-or-value! promise value)))
;; return the memoized value
(promise-thunk-or-value promise))
> The promise calls the proc, but *not* in a tail position.
This is correct. In order to memoize the values, we need to
interpose the memoization between the evaluation and returning
the values to the caller.
>
> The promise refers to the proc, which refers to the original stream.
> Because the promise does not call the proc in a tail position, the
> proc will be retained even after it finishes (in this case by calling
> loop tail-recursively). Only after the promise finishes can the proc
> be garbage collected. When the promise is forced, it may need to
> expand a very long stream before it can return with another element
> satisfying the predicate. However, none of the long intermediate list
> can be garbage collected because the promise still holds a reference
> to the head of the stream through the proc.
Yes. But there is some subtlety here. When we force the promise:
(let ((value ((promise-thunk-or-value promise))))
(set-promise-flag! promise #t)
(set-promise-thunk-or-value! promise value))
we have retained the original procedure in the `thunk-or-value' slot,
and since this contains an environment that refers to the original
stream, none of the intervening stream elements can be collected
until we get rid of the promise.
*But we don't need to retain the procedure!*
Once we have extracted it from the promise in order to invoke it,
we don't refer to the slot again except to overwrite the value.
This suggests the obvious improvement of zapping the thunk-or-value
slot to #f prior to invoking the thunk. Unfortunately, this is tricky
because you would have to retain the value of the slot in a local
variable (in order to invoke it) while you zap the slot and there
is no guarantee that the compiler will delete it until the function
returns. A hack that does work is to make the thunk delete itself:
(delay <form>) => (make-promise nil (lambda (promise)
(set-promise-thunk-or-value! promise #f)
<form>))
(define (force promise)
(if (not (promise-flag promise))
(promise-force-and-memoize promise))
(promise-thunk-or-value promise))
(define (promise-force-and-memoize promise)
(set-promise-thunk-or-value! promise
((promise-thunk-or-value promise) promise))
(set-promise-flag! promise #t))
This solves the GC problem, but it causes a different problem:
While we are forcing the promise, the promise itself is in an
invalid state. It isn't forced, but there is no longer enough
information in the promise to force it. This is ok *provided*
that the process of forcing *completes*. If the body of the
promise performs a non-local exit, the promise will be `broken'.
Normally, this wouldn't be much of an issue, but when the
*user* causes an asynchronous non-local exit (by hitting the
`break' button, or its equivalent), and we're in the middle
of evaluating a stream, a broken promise will end up in the
stream. Users frequently cause asynchronous non-local exits
in stream programming because it is the only way to get the
interpreter to stop evaluating an infinite stream.
Now it *is* possible, but very hard, to get this to work.
While we are forcing a promise, the end result is being
computed by the current state of the machine. Instead of
simply tossing this state when a non-local exit is performed,
we could capture it and stuff it back into the promise.
In effect, we would have partially forced promises. Trying
to force a partially forced promise continues where we left off.
> I confirmed that the example fails in my version of scheme48.
> Interestingly, when I replaced delay with simple (lambda () ...)
> thunks, it ran without a problem.
Yes. This is because forcing the `promise' can now happen in tail
position and thus the `promise' itself isn't being retained.
Al Petrofsky
> While we are forcing the promise, the promise itself is in an
> invalid state. It isn't forced, but there is no longer enough
> information in the promise to force it. This is ok *provided*
> that the process of forcing *completes*. If the body of the
> promise performs a non-local exit, the promise will be `broken'.
> Normally, this wouldn't be much of an issue, but when the
> *user* causes an asynchronous non-local exit (by hitting the
> `break' button, or its equivalent), and we're in the middle
> of evaluating a stream, a broken promise will end up in the
> stream.
Asynchronous non-local exits are a difficult concept to assign exact
meaning to, and the standard doesn't even try to do so. However, even
if you ignore non-local exits, both asynchronous and synchronous, you
still have the same problem because promises are required to handle
reentry, e.g.:
(letrec ((x #f)
(promise (delay (or x (begin (set! x #t) (force promise))))))
(force promise))
=> #t
So when stream-filter forces a promise that scans a stream for the
next matching element, there's no avoiding keeping all the stream
elements in memory until it finishes, because at any time before it
finishes, it might reenter itself and need access again to all the
elements of the stream that it passed.
I suppose one fix is "only use memoization when there's something
worth memoizing", and have things like integers-from-n use
non-memoizing promises. You could mix memoizing and non-memoizing
promises like so:
(define-syntax stream-cons
(syntax-rules ()
((_ a b) (cons a (lambda () b)))))
(define-syntax stream-cons-memoizing
(syntax-rules ()
((_ a b) (cons a (let ((memo (delay b))) (lambda () (force memo)))))))
(define (stream-car s) (car s))
(define (stream-cdr s) ((cdr s)))
Should all the stream-constructing procedures in a streams library
have memoizing and nonmemoizing variants?
-al
Joe Marshall
"Al Petrofsky" <a...@petrofsky.org> wrote in message news:87k7oh8...@radish.petrofsky.org...
I did gloss over re-entrancy (yet another problem) but that isn't an
issue in this situation because there is no reference to the head of
the stream kept anywhere else. (We could use weak-pointers etc. etc.)
By the way, *are* promises required to be re-entrant? Consider
this:
(letrec ((x #f)
(promise (delay (or x
(begin (set! x #t)
(not (force promise)))))))
(force promise))
returns what?
> I suppose one fix is "only use memoization when there's something
> worth memoizing", and have things like integers-from-n use
> non-memoizing promises.
Ugh. Are side-effects `worth memoizing'?
Al Petrofsky
> By the way, *are* promises required to be re-entrant? Consider
> this:
>
> (letrec ((x #f)
> (promise (delay (or x
> (begin (set! x #t)
> (not (force promise)))))))
> (force promise))
>
> returns what?
#t. R5rs explicitly covers this.
> > I suppose one fix is "only use memoization when there's something
> > worth memoizing", and have things like integers-from-n use
> > non-memoizing promises.
>
> Ugh. Are side-effects `worth memoizing'?
That's entirely up to you, and it may depend on the nature of the side
effects. For any <foo>, <foo> is "worth memoizing" if you prefer the
semantics and performance of memoizing <foo> to the semantics and
performance of not memoizing <foo>.
-al
David Rush
> Ugh. Are side-effects `worth memoizing'?
Well if you're side-effecting (aside from memoizing) in lazy code,
then shame on you ;)
david rush
--
Scheme's motto is there are two ways to do it...Actually the motto is
twofold too. Some prefer to say: There is more than one but less than
three ways to do it (TIMTOBLTWTDI, pronounced Tim-too-bloody).
-- Dorai Sitaram (on comp.lang.scheme)
Stephen McCracken
that all forces of promises and all calls to delayed thunks occur in
tail position. The example now runs without heap overflow in scheme48
and mzscheme. Unfortunately, it bears little resemblance to the
original example. In fact, I think it would probably be clearer if it
were just rewritten in terms of coroutines.
Anyway, what I'm wondering is:
* Can anyone see a useful way to generalize this approach? I don't
think macros would be much help. Writing an entire stream library in
this style would be nasty, but it might be worth it to avoid the
memory retention caused by standard force/delay.
* Would promises written in this style have the same memoizing and
reentrancy-safe behavior as R5RS promises? I think these promises do
the same checks in the same order as the R5RS force/delay example
implementation, so they should behave the same...
* Any suggestions for a cleaner approach to force/delay for a streams
library? We'd want:
- portable R5RS
- no unnecessary memory retention
- memoization works
- reentrance is safe (though it may cause memory retention)
;;======================================================================
(define (error . args) (apply write (cons 'ERROR args)))
(define (my-force promise k) (promise k))
;; memoizations are stored in a pair.
(define result-ready? car)
(define result cdr)
;; make-memoizer makes a function that takes a value, memoizes it, and
;; returns it to a continuation.
(define (make-memoizer memo-pair k)
(lambda (x)
(if (result-ready? memo-pair)
(k (result memo-pair))
(begin
(set-car! memo-pair #t)
(set-cdr! memo-pair x)
(k (result memo-pair))))))
(define (my-make-promise memo-pair thunk-cps)
(lambda (promise-k)
(if (result-ready? memo-pair)
(result memo-pair)
(thunk-cps (make-memoizer memo-pair promise-k)))))
;;======================================================================
(define (integers-from n)
(cons n (my-make-promise
(cons #f #f)
(lambda (k) (k (integers-from (+ n 1)))))))
(define (make-stream-ref index)
(lambda (s) (stream-ref s index)))
(define (stream-ref s index)
(cond ((not (pair? s)) (error 'stream-ref 0))
((zero? index) (car s))
(else (my-force (cdr s) (make-stream-ref (- index 1))))))
(define (make-stream-filter p? k)
(lambda (s) (stream-filter p? s k)))
(define (stream-filter p? s k)
(cond ((not (pair? s))
(if (null? s)
(k '())
(error 'stream-filter 1)))
((p? (car s))
(k (cons (car s)
(my-make-promise
(cons #f #f)
(lambda (thunk-k)
(my-force (cdr s) (make-stream-filter p? thunk-k)))))))
(else (my-force (cdr s) (make-stream-filter p? k)))))
(define (demo-stream-problem n)
(stream-filter
(lambda (x) (zero? (modulo x n)))
(integers-from 0)
(lambda (s) (stream-ref s 3))))
Phil Bewig
> memory. I believe that it ought not do so (though I understand
> the mechanism through which it does), but that `fixing' the problem
> is very difficult (though I believe it *can* be done, albiet with
> considerable work). The reason that I believe that it ought not
> run in O(n) time is because computing element n+1 of the integers
> stream requires only the single prior element and filtering a
> stream requires none of the prior elements.
I appreciate your effort in bringing this problem to the attention
of the group. I have been following this discussion closely, and
will address it in the SRFI I am writing. I have some questions:
1) Is there a clean way to solve the problem in the reference
implementation? I suspect the answer might be "no," that
any solution would be messy. In that case, there is a
secondary question: Is it okay to leave the reference
implementation as is, so that users can experiment with
streams while waiting for a proper implementation, with a
warning that it fails to comply with the specification?
And there is a third question: If I have to fix the
reference implementation, how do I do it? At the moment
I haven't a clue.
2) Is there any way for implementors to solve the problem. I
suspect the answer is "yes," because Haskell compilers are
able to solve the problem. My secondary question is what
advantage do implementors have that allows them to solve
the problem in a way the reference implementation cannot,
or do they just have to get dirty in the details?
3) What do I need to say in the SRFI specification to require
implementors to solve this problem? Does the statement
Any implementation of this SRFI is required to release
a stream element to the garbage collector as soon as
it has been used and is no longer needed to compute a
later element in the stream, unless it has been bound
to a variable outside the scope of the stream.
specify accurately what an implementor must do in a proper
stream implementation? Is there any loophole that would
allow an implmentation to claim compliance with the SRFI
but still have the memory leak?
Many thanks,
Phil
Joe Marshall
"Phil Bewig" <pbe...@swbell.net> wrote in message news:455f7154.02070...@posting.google.com...
>
> I appreciate your effort in bringing this problem to the attention
> of the group. I have been following this discussion closely, and
> will address it in the SRFI I am writing. I have some questions:
>
> 1) Is there a clean way to solve the problem in the reference
> implementation?
I don't know. I was hoping someone might come up with something
clever, but I guess there isn't something obvious. The problem
*seems* tied to stream-filter (when calling stream-ref on a stream
without a filter clause, the amount of memory used seems constant).
So I'm wondering if there isn't a hack that could be done there.
(something along the lines of a `trampoline' see below)
In any case, if there isn't something simple that could be done
I wouldn't worry about it, just put a note in the SFRI that
releasing the storage is desirable but non-trivial.
Trampoline hack.
Part of the problem seems to be that when filtering a stream
we're holding on to an environment that stores the head of the
stream while we're trying to get to the next element. This
suggests a hack similar to the one used to mimic tail recursion
in a non-tail recursive language: Instead of having stream-filter
return the filtered stream directly, have it do one step on the
underlying stream and return a special thunk that makes it loop
again. When FORCE gets as a value this special thunk, it replaces
the current promise with the special thunk and re-forces it.
Thus we get the iteration step at a time, but we're constantly
replacing the thunk pointer in the promise with a new pointer that
contains less information than the old.
I haven't fully thought this out, but it'd be neat if it worked.
![Michael Sperber [Mr. Preprocessor]'s profile photo](http://lh3.googleusercontent.com/a-/ALV-UjW1Ug-7D5rvPAe0Dy8QWlBwdoMp8sHWFACGdNTzwJ9mF7CkTQ=s40-c)
Michael Sperber [Mr. Preprocessor]
Joe> Ok, this time I tested it more thoroughly and I am not
Joe> relying on the underlying implementation.
Joe> (define (integers-from n)
Joe> (cons n (delay (integers-from (+ n 1)))))
Joe> (define jrm-stream-ref
Joe> (letrec ((loop (lambda (stream index)
Joe> (cond ((not (pair? stream)) (error 'stream-ref 0))
Joe> ((zero? index) (car stream))
Joe> (else (loop (force (cdr stream)) (- index 1)))))))
Joe> loop))
Joe> (define jrm-stream-filter
Joe> (letrec ((loop (lambda (predicate stream)
Joe> (cond ((not (pair? stream))
Joe> (if (null? stream)
Joe> '()
Joe> (error stream 'stream-filter 1)))
Joe> ((predicate (car stream))
Joe> (cons (car stream)
Joe> (delay (loop predicate (force (cdr stream))))))
Joe> (else (loop predicate (force (cdr stream))))))))
Joe> loop))
Joe> (define (demo-stream-problem n)
Joe> (jrm-stream-ref
Joe> (jrm-stream-filter
Joe> (lambda (x) (zero? (modulo x n)))
Joe> (integers-from 0))
Joe> 3))
Joe> (demo-stream-problem n) consumes O(n) memory rather than constant
Joe> memory. I believe that it ought not do so (though I understand
Joe> the mechanism through which it does), but that `fixing' the problem
Joe> is very difficult (though I believe it *can* be done, albiet with
Joe> considerable work). The reason that I believe that it ought not
Joe> run in O(n) time is because computing element n+1 of the integers
Joe> stream requires only the single prior element and filtering a
Joe> stream requires none of the prior elements.
It seems to me the explanation is quite simple: The loop in
JRM-STREAM-FILTER calls itself strictly in the ELSE clause of the
cont. Since the particular filter test you're applying runs into that
clause for all initial elements of the stream, that part of the stream
is completely generated before anything is returned. The FORCE in
that branch is an implicit, non-tail-recursive call.
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
Michael Sperber [Mr. Preprocessor]
Phil> "Joe Marshall" <prunes...@attbi.com> wrote in message
Phil> news:<PW6T8.351531$cQ3.22120@sccrnsc01>...
>> (demo-stream-problem n) consumes O(n) memory rather than constant
>> memory. I believe that it ought not do so (though I understand
>> the mechanism through which it does), but that `fixing' the problem
>> is very difficult (though I believe it *can* be done, albiet with
>> considerable work). The reason that I believe that it ought not
>> run in O(n) time is because computing element n+1 of the integers
>> stream requires only the single prior element and filtering a
>> stream requires none of the prior elements.
Phil> I appreciate your effort in bringing this problem to the attention
Phil> of the group. I have been following this discussion closely, and
Phil> will address it in the SRFI I am writing. I have some questions:
Phil> 1) Is there a clean way to solve the problem in the reference
Phil> implementation? I suspect the answer might be "no," that
Phil> any solution would be messy. In that case, there is a
Phil> secondary question: Is it okay to leave the reference
Phil> implementation as is, so that users can experiment with
Phil> streams while waiting for a proper implementation, with a
Phil> warning that it fails to comply with the specification?
Phil> And there is a third question: If I have to fix the
Phil> reference implementation, how do I do it? At the moment
Phil> I haven't a clue.
Phil> 2) Is there any way for implementors to solve the problem. I
Phil> suspect the answer is "yes," because Haskell compilers are
Phil> able to solve the problem.
I think there's some confusion here: In Haskell, everything is a
suspension, whereas in Joe's SICP-style example, only the cdr of pair
representing the stream is one. If you follow Haskell with this, you
get the same run-time behavior as in Haskell.
If you're writing a SRFI, you need to take into account that the
various uses of streams have differing strictness requirements, and a
lot of them are not satisfied by SICP-style streams. I strongly
recommend at least reading
@InProceedings{WadlerTahaMacQueen1998,
author = {Philip Wadler and Walid Taha and David MacQueen},
title = {How to Add Laziness to a Strict Language without Even Being Odd},
booktitle = {1998 {ACM-SIGPLAN} Workshop on {ML}},
crossref = {ML1998},
pages = {24--30},
year = 1998
}
@Proceedings{ML1998,
title = "1998 {{ACM}-SIGPLAN} Workshop on {ML}",
booktitle = "1998 {{ACM}-SIGPLAN} Workshop on {ML}",
year = "1998",
month = sep,
address = "Baltimore, Maryland"
}
It's available electronically at the top of
http://www.research.avayalabs.com/user/wadler/topics/language-design.html
George Caswell
> It's available electronically at the top of
>
> http://www.research.avayalabs.com/user/wadler/topics/language-design.html
>
Hrm, enlightening. I'd sort of wondered whether delay/force streams should
have their first value delayed, now I guess I know.
But I was confused at first, I tried their example:
(stream-eval (take 5 (stream-map sqrt (countdown 4))))
And was pleased to see that it didn't generate a numeric exception with the
simple ("odd") stream style... Then I remembered that (sqrt -1) is legal in
Scheme. :)
(stream-eval (take 4 (stream-map (lambda (x) (/ 1 x)) (countdown 4)))) does
indeed fail.
---GEC
New projects page: http://home.attbi.com/~sieg_haro/
(M-x depeche-mode)
"Must... Finish... Zaku..."
Joe Marshall
"Michael Sperber [Mr. Preprocessor]" <spe...@informatik.uni-tuebingen.de> wrote in message
news:y9l8z4t...@sams.informatik.uni-tuebingen.de...
It sure *seems* that simple, but the same argument applies to the
else clause in JRM-STREAM-REF, yet *that* function does not use up
storage.
Phil Bewig
> It seems to me the explanation is quite simple: The loop in
> JRM-STREAM-FILTER calls itself strictly in the ELSE clause of the
> cont. Since the particular filter test you're applying runs into that
> clause for all initial elements of the stream, that part of the stream
> is completely generated before anything is returned. The FORCE in
> that branch is an implicit, non-tail-recursive call.
I finally got it. The definition of force in R5RS (section 6.4,
page 31) is:
(force promise) forces the value of promise. If no value
has been computed for the promise, then a value is computed
and returned. The value of the promise is cached (or "memo-
ized") so that if it is forced a second time, the previously
computed value is returned.
The problem is the memoization, which saves each element of the
stream. The solution is to use a definition of streams that
doesn't use force:
(define-syntax stream-cons
(syntax-rules ()
((stream-cons obj strm)
(cons (lambda () obj) (lambda () strm)))))
(define (stream-car strm) ((car strm)))
(define (stream-cdr strm) ((cdr strm)))
Changing Joe's example to use these definitions solves the problem.
Thanks to Joe and Michael for a challenging problem and useful hint.
Phil
Stephen McCracken
> > 1) Is there a clean way to solve the problem in the reference
> > implementation?
>
> I don't know. I was hoping someone might come up with something
> clever, but I guess there isn't something obvious.
Here's another fully-lazy implementation that may be clever. Delayed
streams are represented as pairs that mutate themselves into lists
when they are forced. Lists are streams, and streams can easily be
mutated into lists by replacing the-empty-stream with '().
To address the memory-retention problem, I provided a CPS-style
stream-force! instead of stream-car and stream-cdr. This prevents you
from accidentally capturing a reference to a whole stream inside your
thunk when you really only need its parts -- I thought that was the
crux of the problem with jrm-stream-filter. The new stream-filter is
a little clumsy, but someone good with macros could probably pretty it
up.
The only problem :-( is that I didn't see the memory behavior I
expected. In mzscheme, maximum usage increased with the n in
demo-stream-problem, though not obviously linearly. mzscheme's
conservative collector makes the figures suspect, though. In
scheme48, it ran with larger n than before, but it still eventually
ran into memory problems. I'd appreciate it if someone else would
help me understand the memory behavior.
(define-syntax stream-cons
(syntax-rules ()
((_ x s)
(letrec ((delayed-pair
(cons 'delayed (lambda ()
(set-car! delayed-pair x)
(set-cdr! delayed-pair s)))))
delayed-pair))))
(define the-empty-stream (cons 'the-empty-stream 'the-empty-stream))
(define (stream-delayed? s) (and (pair? s) (procedure? (cdr s))))
(define (stream-force! s k-null k-pair)
(if (stream-delayed? s) ((cdr s)))
(if (or (null? s) (equal? s the-empty-stream))
(k-null s)
(k-pair (car s) (cdr s))))
;; These are superfluous, and they may lead to memory retention!
;(define (stream-null? s)
; (stream-force! s (lambda (s) #t) (lambda (a s) #f)))
;(define (stream-car s)
; (stream-force! s
; (lambda (s) (error "attempt to take car of null stream"))
; (lambda (a s) a)))
;(define (stream-cdr s)
; (stream-force! s
; (lambda (s) (error "attempt to take cdr of null stream"))
; (lambda (a s) s)))
(define (error . args) (apply write (cons 'ERROR args)))
(define (integers-from n)
(stream-cons n (integers-from (+ n 1))))
(define (stream-ref s index)
(stream-force! s
(lambda (s) (error "index beyond length of stream"))
(lambda (a s)
(if (zero? index) a
(stream-ref s (- index 1))))))
(define stream-filter
(letrec ((test (lambda (p?)
(lambda (a s)
(if (p? a) (stream-cons a (expand p? s))
(expand p? s)))))
(expand (lambda (p? s)
(stream-force! s
(lambda (s) the-empty-stream)
(test p?)))))
expand))
(define (demo-stream-problem n)
(stream-ref
(stream-filter
Stephen McCracken
Sorry if this is a dup. Having trouble with Google
again, and I'm anxious to correct myself.
The fully-implementation using CPS-style stream-force!
that I posted has the same old problem. The promise
holds a reference to the thunk, which holds a
reference to the head of a long intermediate stream.
It could be fixed by deleting the reference to the
thunk and putting the cdr-computing expression in tail
position, as Joe Marshall suggested. It would have
asynchronous exit and reentrace problems, though.
Furthermore, it seems that the CPS-style stream-force!
is unnecessary.
__________________________________________________
Do You Yahoo!?
Sign up for SBC Yahoo! Dial - First Month Free
http://sbc.yahoo.com
Phil Bewig
> I finally got it.
I went back and re-read all the messages in this thread and in Joe's prior
thread. All the messages that didn't make sense before do now. Thanks to
all who responded, and all who put up with my slow learning.
Phil
Joe Marshall
"Stephen McCracken" <sam...@yahoo.com> wrote in message
news:18fbf543.02070...@posting.google.com...
> I reorganized parts of the example using continuation parameters so
> that all forces of promises and all calls to delayed thunks occur in
> tail position. The example now runs without heap overflow in scheme48
> and mzscheme.
And in MIT-Scheme, too. This is great!
> Unfortunately, it bears little resemblance to the
> original example. In fact, I think it would probably be clearer if it
> were just rewritten in terms of coroutines.
I'm pretty comfortable with CPS, so I don't find it that confusing.
> Anyway, what I'm wondering is:
>
> * Can anyone see a useful way to generalize this approach? I don't
> think macros would be much help. Writing an entire stream library in
> this style would be nasty, but it might be worth it to avoid the
> memory retention caused by standard force/delay.
I haven't given it all that much thought. I suppose one *could* write
the library this way, but have the exported functions use CWCC so as
to look `normal'.
> * Would promises written in this style have the same memoizing and
> reentrancy-safe behavior as R5RS promises? I think these promises do
> the same checks in the same order as the R5RS force/delay example
> implementation, so they should behave the same...
It appears to be, but I haven't thoroughly tested it.
Joe Marshall
"Stephen McCracken" <sam...@yahoo.com> wrote in message
news:18fbf543.02070...@posting.google.com...
>
> streams are represented as pairs that mutate themselves into lists
> when they are forced. Lists are streams, and streams can easily be
> mutated into lists by replacing the-empty-stream with '().
>
> To address the memory-retention problem, I provided a CPS-style
> stream-force! instead of stream-car and stream-cdr. This prevents you
> from accidentally capturing a reference to a whole stream inside your
> thunk when you really only need its parts -- I thought that was the
> crux of the problem with jrm-stream-filter. The new stream-filter is
> a little clumsy, but someone good with macros could probably pretty it
> up.
>
> The only problem :-( is that I didn't see the memory behavior I
> expected. In mzscheme, maximum usage increased with the n in
> demo-stream-problem, though not obviously linearly. mzscheme's
> conservative collector makes the figures suspect, though. In
> scheme48, it ran with larger n than before, but it still eventually
> ran into memory problems. I'd appreciate it if someone else would
> help me understand the memory behavior.
The problem is that the retention is caused by the promise captured
at the call site to stream-filter. In the CPS version, that promise
isn't held on to because the value of stream-filter is passed to a
thunk that doesn't need the promise. In the non-CPS version the
promise is being held on the stack.
Richard Kelsey
> Part of the problem seems to be that when filtering a stream
> we're holding on to an environment that stores the head of the
> stream while we're trying to get to the next element. This
> suggests a hack similar to the one used to mimic tail recursion
> in a non-tail recursive language: Instead of having stream-filter
> return the filtered stream directly, have it do one step on the
> underlying stream and return a special thunk that makes it loop
> again. When FORCE gets as a value this special thunk, it replaces
> the current promise with the special thunk and re-forces it.
A quick hack shows that this works. The version of JRM-STREAM-FILTER
below updates its own delayed computation as it skips unwanted elements
in the stream being filtered. This makes DEMO-STREAM-PROBLEM run in
0(1) memory.
(define (jrm-stream-filter predicate stream)
(let loop ((stream stream)
(promise #f))
(cond ((not (pair? stream))
(if (null? stream)
'()
(error stream 'stream-filter 1)))
((predicate (car stream))
(cons (car stream)
(let ((next (cdr stream)))
(letrec ((promise (list (lambda ()
(loop (force next)
promise)))))
(delay ((car promise)))))))
(else
(let* ((next (force (cdr stream)))
(do-it (lambda ()
(loop next promise))))
(if promise
(set-car! promise do-it))
(do-it))))))
Negative results are also of value.
-Richard Kelsey
Stephen McCracken
> "Stephen McCracken" <sam...@yahoo.com> wrote in message
> news:18fbf543.02070...@posting.google.com...
> >
> > expected. In mzscheme, maximum usage increased with the n in
> > demo-stream-problem, though not obviously linearly. mzscheme's
> > conservative collector makes the figures suspect, though. In
> > scheme48, it ran with larger n than before, but it still eventually
> > ran into memory problems. I'd appreciate it if someone else would
> > help me understand the memory behavior.
>
> The problem is that the retention is caused by the promise captured
> at the call site to stream-filter. In the CPS version, that promise
> isn't held on to because the value of stream-filter is passed to a
> thunk that doesn't need the promise. In the non-CPS version the
> promise is being held on the stack.
Thanks for the succinct explanation. I created a version using
CPS-style stream-force! that does not have memory retention problems.
Since I have it, I'm going to post it. I don't think it adds much to
the discussion, though, because the promises aren't reentrant.
(define-syntax stream-cons
(syntax-rules ()
((_ car-expr cdr-expr)
(letrec ((car-thunk
(lambda ()
(set! car-thunk (lambda ()
(error "car-thunk in progress")))
car-expr))
(cdr-thunk
(lambda ()
(set! cdr-thunk (lambda ()
(error "cdr-thunk in progress")))
cdr-expr)))
(letrec ((delayed-pair
(cons 'delayed
(lambda ()
(set-car! delayed-pair (car-thunk))
(set-cdr! delayed-pair (cdr-thunk))))))
delayed-pair)))))
(define the-empty-stream '())
(define (stream-delayed? s) (and (pair? s) (procedure? (cdr s))))
(define (stream-force! s k-null k-pair)
(if (stream-delayed? s) ((cdr s)))
(if (null? s)
(k-null)
(k-pair (car s) (cdr s))))
(define (error . args) (apply write (cons 'ERROR args)))
(define (integers-from n)
(stream-cons n (integers-from (+ n 1))))
(define (stream-ref s index)
(stream-force! s
(lambda () (error "index beyond length of stream"))
(lambda (a s)
(if (zero? index) a
(stream-ref s (- index 1))))))
(define stream-filter
(letrec ((test (lambda (p?)
(lambda (a s)
(if (p? a) (stream-cons a (expand p? s))
(expand p? s)))))
(expand (lambda (p? s)
(stream-force! s
(lambda () the-empty-stream)
Joe Marshall
"Richard Kelsey" <kel...@s48.org> wrote in message news:1383b6a.02070...@posting.google.com...
> "Joe Marshall" <prunes...@attbi.com> wrote in message news:<f3sU8.66571$Uu2.10963@sccrnsc03>...
> > Part of the problem seems to be that when filtering a stream
> > we're holding on to an environment that stores the head of the
> > stream while we're trying to get to the next element. This
> > suggests a hack similar to the one used to mimic tail recursion
> > in a non-tail recursive language: Instead of having stream-filter
> > return the filtered stream directly, have it do one step on the
> > underlying stream and return a special thunk that makes it loop
> > again. When FORCE gets as a value this special thunk, it replaces
> > the current promise with the special thunk and re-forces it.
>
> A quick hack shows that this works.
It doesn't work for me. Which Scheme compiler are you using?
Joe Marshall
"Stephen McCracken" <sam...@yahoo.com> wrote in message
news:18fbf543.02070...@posting.google.com...
> "Joe Marshall" <prunes...@attbi.com> wrote in message
news:<MUZV8.313140$6m5.2...@rwcrnsc51.ops.asp.att.net>...
> > "Stephen McCracken" <sam...@yahoo.com> wrote in message
> > news:18fbf543.02070...@posting.google.com...
> > >
> > > The only problem :-( is that I didn't see the memory behavior I
> > > expected. In mzscheme, maximum usage increased with the n in
> > > demo-stream-problem, though not obviously linearly. mzscheme's
> > > conservative collector makes the figures suspect, though. In
> > > scheme48, it ran with larger n than before, but it still eventually
> > > ran into memory problems. I'd appreciate it if someone else would
> > > help me understand the memory behavior.
> >
> > The problem is that the retention is caused by the promise captured
> > at the call site to stream-filter. In the CPS version, that promise
> > isn't held on to because the value of stream-filter is passed to a
> > thunk that doesn't need the promise. In the non-CPS version the
> > promise is being held on the stack.
>
> Thanks for the succinct explanation. I created a version using
> CPS-style stream-force! that does not have memory retention problems.
> Since I have it, I'm going to post it. I don't think it adds much to
> the discussion, though, because the promises aren't reentrant.
I'm not sure re-entrancy is such a big deal. Yes, I know that R5RS specifies
that promises are re-entrant, but that doesn't mean that *streams* have
to be re-entrant.
Richard Kelsey
> "Richard Kelsey" <kel...@s48.org> wrote in message news:1383b6a.02070...@posting.google.com...
> > "Joe Marshall" <prunes...@attbi.com> wrote in message news:<f3sU8.66571$Uu2.10963@sccrnsc03>...
> > > return the filtered stream directly, have it do one step on the
> > > underlying stream and return a special thunk that makes it loop
> > > again. When FORCE gets as a value this special thunk, it replaces
> > > the current promise with the special thunk and re-forces it.
> >
> > A quick hack shows that this works.
>
> It doesn't work for me. Which Scheme compiler are you using?
Scheme 48 version 0.57. We are in somewhat murky water here
because the RnRS say very little about what kind of garbage
collection is required. I know that the code I posted would
not have worked in some earlier versions of Scheme 48, and
slight changes might make it not work in the current one.
-Richard Kelsey
Joe Marshall
"Richard Kelsey" <kel...@s48.org> wrote in message news:1383b6a.02070...@posting.google.com...
> "Joe Marshall" <prunes...@attbi.com> wrote in message
news:<WS4W8.316378$6m5.3...@rwcrnsc51.ops.asp.att.net>...
> > "Richard Kelsey" <kel...@s48.org> wrote in message news:1383b6a.02070...@posting.google.com...
> > > "Joe Marshall" <prunes...@attbi.com> wrote in message news:<f3sU8.66571$Uu2.10963@sccrnsc03>...
> > > > Instead of having stream-filter
> > > > return the filtered stream directly, have it do one step on the
> > > > underlying stream and return a special thunk that makes it loop
> > > > again. When FORCE gets as a value this special thunk, it replaces
> > > > the current promise with the special thunk and re-forces it.
> > >
> > > A quick hack shows that this works.
> >
> > It doesn't work for me. Which Scheme compiler are you using?
>
> Scheme 48 version 0.57. We are in somewhat murky water here
> because the RnRS say very little about what kind of garbage
> collection is required. I know that the code I posted would
> not have worked in some earlier versions of Scheme 48, and
> slight changes might make it not work in the current one.
So it's probably because the compiler I'm using is retaining
a bit more storage in an environment frame than it needs to?
If that's the case, it ought to be possible to rewrite the code
to make it less dependent upon what the compiler does.
Joe Marshall
>
> So it's probably because the compiler I'm using is retaining
> a bit more storage in an environment frame than it needs to?
> If that's the case, it ought to be possible to rewrite the code
> to make it less dependent upon what the compiler does.
>
And in fact that turns out to be the case.
This version works when compiled under MIT-Scheme:
(define (rk-stream-filter predicate stream)
(rk-stream-filter-aux predicate stream #f))
(define (rk-stream-filter-aux predicate stream promise)
(cond ((not (pair? stream))
(if (null? stream)
'()
(error stream 'stream-filter 1)))
((predicate (car stream))
(cons (car stream)
(let ((promise (cons #f #f)))
(rk-stream-filter-aux-1 predicate (cdr stream) promise)
(delay ((car promise))))))
(else
(let* ((next (force (cdr stream)))
(do-it (lambda () (rk-stream-filter-aux predicate next promise))))
(if promise
(set-car! promise do-it))
(do-it)))))
(define (rk-stream-filter-aux-1 predicate next promise)
(set-car! promise
(lambda () (rk-stream-filter-aux predicate (force next) promise))))
Unfortunately, I haven't gotten it to work under MIT-Scheme in the interpreter.
(Not sure how much effort I want to invest in this, but I see no reason in
principle that it wouldn't work.)
Now that we have a `working' version of stream-filter, it seems to me that the
SRFI ought to require that implementations do not retain extra storage in
this manner and make sure that the reference implementation exhibits the
correct behavior. The version above isn't quite correct (it should work
interpreted, be modified to be head-strict, if that is what is desired,
and it should be tested on other platforms.)
Phil Bewig
> Now that we have a `working' version of stream-filter, it seems to me that the
> SRFI ought to require that implementations do not retain extra storage in
> this manner and make sure that the reference implementation exhibits the
> correct behavior. The version above isn't quite correct (it should work
> interpreted, be modified to be head-strict, if that is what is desired,
> and it should be tested on other platforms.)
I think it's a little bit optimistic to claim we now have a working stream-
filter, even with quotes around working.
Question: Why should stream-filter be an exception to the rule that streams
are cached? Just because I filter a stream doesn't mean I'm not going to use
the stream again. For example, the simple-minded quicksort shown below filters
the same stream twice. Shouldn't the stream be cached from the first access to
the second?
!!! WARNING -- CODE TYPED DIRECTLY INTO THIS MESSAGE WITHOUT TESTING !!!
;; QSORT lt? stream -- sort stream according to lt? less-than predicate
(define (qsort lt? strm)
(if (stream-null? strm)
stream-null
(stream-append
(qsort lt?
(stream-filter
(lambda (x) (lt? x (stream-car strm)))
(stream-cdr strm)))
(stream (stream-car strm))
(qsort lt?
(stream-filter
(lambda (x) (not (lt? x (stream-car strm))))
(stream-cdr strm))))))
Second question: I am not a "language lawyer," and I have been struggling
for a week to write a rule in my SRFI that would clearly explain what a
conforming implementation of streams would have to do with regard to caching.
Just saying that "implementations should not retain extra storage in this
manner" isn't clear enough. If anybody would like to propose some lawyerly
language it would be appreciated.
Phil
Joe Marshall
news:<C2hW8.327510$6m5.3...@rwcrnsc51.ops.asp.att.net>...
>
> > Now that we have a `working' version of stream-filter, it seems to me that the
> > SRFI ought to require that implementations do not retain extra storage in
> > this manner and make sure that the reference implementation exhibits the
> > correct behavior. The version above isn't quite correct (it should work
> > interpreted, be modified to be head-strict, if that is what is desired,
> > and it should be tested on other platforms.)
>
> I think it's a little bit optimistic to claim we now have a working stream-
> filter, even with quotes around working.
>
> Question: Why should stream-filter be an exception to the rule that streams
> are cached?
It isn't. The problem was that stream-filter was holding on to the head
of the stream after it didn't need it anymore. I suggested that incrementally
replacing the promise at each iteration would preserve the semantics yet
still allow GC of the elements that were not strictly needed. Richard Kelsey
offered an implementation that works under Scheme 48, I tweaked it for MIT Scheme,
and I think that a little more tweaking will make it portable.
But it doesn't change the semantics of stream-filter, it just makes it less
space hungry.
Phil Bewig
> > are cached?
>
> It isn't. The problem was that stream-filter was holding on to the head
> of the stream after it didn't need it anymore. I suggested that incrementally
> replacing the promise at each iteration would preserve the semantics yet
> still allow GC of the elements that were not strictly needed. Richard Kelsey
> offered an implementation that works under Scheme 48, I tweaked it for MIT Scheme,
> and I think that a little more tweaking will make it portable.
>
> But it doesn't change the semantics of stream-filter, it just makes it less
> space hungry.
I respectfully disagree.
Let's start with the underlying representation of streams that you used in your
initial posting that started this thread. It is the old definition of "odd"
streams, but that doesn't matter for this discussion.
(define-syntax stream-cons
(syntax-rules ()
((stream-cons obj strm)
(cons obj (delay strm)))))
(define (stream-car strm)
(car strm))
(define (stream-cdr strm)
(force (cdr strm)))
(define stream-null
(vector 'the 'null 'stream))
(define (stream-null? strm)
(eq? strm stream-null))
And here are your derived stream functions, rewritten slightly to call the
underlying stream primitives, but essentially unchanged.
(define (integers-from n)
(stream-cons n (integers-from (+ n 1))))
(define (jrm-stream-ref strm index)
(let loop ((strm strm) (index index))
(cond ((stream-null? strm) (error "out of bounds"))
((zero? index) (stream-car strm))
(else (loop (stream-cdr strm) (- index 1))))))
(define (jrm-stream-filter pred? strm)
(let loop ((strm strm))
(cond ((stream-null? strm) stream-null)
((pred? (stream-car strm))
(stream-cons (stream-car strm) (loop (stream-cdr strm))))
(else (loop (stream-cdr strm))))))
As you pointed out, the function shown below uses O(n) memory and thus fails for
large n.
(define (demo-stream-problem n)
(jrm-stream-ref
(jrm-stream-filter
(lambda (x) (zero? (modulo x n)))
(integers-from 0))
3))
Demo-stream-problem uses linear memory because the (integers-from 0) stream is
called 3n+1 times as demo-stream-problem counts from 0 to n and each of the 3n+1
values 0, 1, 2, ... 3n+1 is cached by the delay/force mechanism that underlies
the representation of streams, consuming memory at a linear rate.
You have proposed a new version of stream-filter that bypasses the underlying
stream implementation and consumes only a constant amount of memory, claiming
they have the same semantics:
(define (rk-stream-filter predicate stream)
(rk-stream-filter-aux predicate stream #f))
(define (rk-stream-filter-aux predicate stream promise)
(cond ((not (pair? stream))
(if (null? stream)
'()
(error stream 'stream-filter 1)))
((predicate (car stream))
(cons (car stream)
(let ((promise (cons #f #f)))
(rk-stream-filter-aux-1 predicate (cdr stream) promise)
(delay ((car promise))))))
(else
(let* ((next (force (cdr stream)))
(do-it (lambda () (rk-stream-filter-aux predicate next promise))))
(if promise
(set-car! promise do-it))
(do-it)))))
(define (rk-stream-filter-aux-1 predicate next promise)
(set-car! promise
(lambda () (rk-stream-filter-aux predicate (force next) promise))))
However, the semantics of jrm-stream-filter and rk-stream-filter are different,
as jrm-stream-filter caches the values it computes and rk-stream-filter forces
the values into a let-bound variable that is discarded once the stream element
is passed. It is easy to see that the semantics are different. Consider the
streams ones, for which (stream-ref n) returns n, and millions, for which
(stream-ref n) returns 1000000n.
(define ones (integers-from 0))
(define millions
(XXX-stream-filter
(lambda (x) (zero? (modulo x 1000000))) ones)))
[ Although it is not pertinent to this discussion, this is a good example of the
difference between odd and even streams. The streams here are odd, so
(jrm-stream-ref millions 1) will count to TWO million, which is one million more
than it needs to. With even streams, the counting would stop at one million. ]
Stream millions is just the inner portion of demo-stream-problem with the call
to (integers-from 0) replaced by the stream ones. With jrm-stream-filter, the
millions stream consumes linear memory and fails with large n. With rk-stream-
filter, the millions stream consumes constant memory and works for all n.
The difference between the two stream-filter functions is what happens to the
ones stream. With jrm-stream-filter, the ones stream is cached; assuming there
is enough memory to compute (jrm-stream-ref millions 1), a subsequent call to
(jrm-stream-ref ones 1000000) will operate in constant time. With rk-stream-
filter, the ones stream is not cached, as the underlying stream-cdr is bypassed,
the stream element is forced into a local variable that is immediately discarded,
and a subsequent call to (jrm-stream-ref ones 1000000) will operate in linear
time. Thus my claim that the semantics of jrm-stream-filter and rk-stream-filter
are different, as they leave the environment of bound variables in two different
states.
You said that "stream-filter was holding on to the head of the stream after it
didn't need it anymore." My question is how does stream-filter know it doesn't
need the head of the stream any more. It's true that the stream (integers-from 0)
in your demo-stream-problem isn't bound outside stream-filter, but stream-filter
has no way of knowing that. Stream-filter can't just throw away cached elements
of the stream, because that violates the definition of streams, but for it to run
in constant space, that is exactly what it must do.
The data structure that I call streams has the characteristic that stream elements
are cached. I claim that this is a necessary characteristic of streams. Michael
Sperber said in a message posted on 7/7 to the "Memoization in streams" thread:
"I'd say users of something called "streams" expect something using promises in
the Scheme world." SICP (second edition, top of page 324) calls caching "an
important optimization." Chris Okasaki, in his book Purely Functional Data
Structures, uses caching, and presents a bibliography at the end of Chapter 4
quoting two 1976 papers by Friedman and Wise and by Henderson and Morris to the
effect that stream elements must be cached. The data structure that you are
talking about is interesting and may be useful in some situations, but it isn't
a stream.
Speaking with my best "language lawyer" voice, I propose the following definition
of a stream:
A stream is either nil (a single object distinguishable from all
other objects) or it consists of a car containing an object (the
stream element) and a cdr containing a stream. Streams are fully-
lazy, so no stream element is ever evaluated until it is needed. All
stream elements, once evaluated, must be cached so that they won't
be re-evaluated if accessed a second time. Stream elements may be
discarded from the cache if an implementation can prove the cached
element cannot possibly matter to any future computation, as provided
in R5RS section 1.1 fourth paragraph, and of course once a stream is
no longer bound both the stream itself and any cached elements may be
discarded.
It might also be useful to consider the following extension to the definition:
If desired, an implementation may discard cached stream elements, to be
re-evaluated when needed, if failing to do so would cause a program to
abort due to lack of memory.
I have personally concluded that the extension should not be allowed, since it
means a programmer is never sure what an implementation will do and will lead
programmers to distrust streams and thus not use them, although of course I am
willing to listen to discussion on this matter.
Questions, comments and suggestions are welcome.
Phil
Joe Marshall
"Phil Bewig" <pbe...@swbell.net> wrote in message news:455f7154.02071...@posting.google.com...
>
> The difference between the two stream-filter functions is what happens to the
> ones stream. With jrm-stream-filter, the ones stream is cached; assuming there
> is enough memory to compute (jrm-stream-ref millions 1), a subsequent call to
> (jrm-stream-ref ones 1000000) will operate in constant time. With rk-stream-
> filter, the ones stream is not cached, as the underlying stream-cdr is bypassed,
> the stream element is forced into a local variable that is immediately discarded,
> and a subsequent call to (jrm-stream-ref ones 1000000) will operate in linear
> time. Thus my claim that the semantics of jrm-stream-filter and rk-stream-filter
> are different, as they leave the environment of bound variables in two different
> states.
(define (jrm-stream-map f stream)
(if (null? stream)
'()
(cons (f (car stream))
(delay (jrm-stream-map f (force (cdr stream)))))))
(define by-ones (jrm-stream-map (lambda (i) (newline) (display i) i) (integers-from 0)))
(define by-tens (rk-stream-filter (lambda (x) (zero? (modulo x 10))) by-ones))
(jrm-stream-ref by-tens 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
;Value: 20
(jrm-stream-ref by-ones 10)
;Value: 10
(promise-forced? (cdr by-ones))
;Value: #t
The fact that the numbers weren't printed shows that the stream *is* cached.
Feuer
Phil Bewig wrote:
> A stream is either nil (a single object distinguishable from all
> other objects) or it consists of a car containing an object (the
> stream element) and a cdr containing a stream. Streams are fully-
So streams are odd by definition??
> I have personally concluded that the extension should not be allowed, since it
> means a programmer is never sure what an implementation will do and will lead
> programmers to distrust streams and thus not use them, although of course I am
> willing to listen to discussion on this matter.
The best would be to allow the programmer to override the default.
David
Phil Bewig
> The fact that the numbers weren't printed shows that the stream *is* cached.
Hmph. I note that with rk-stream-filter calculating (stream-ref ones
1000000) took the same amount of time before and after calculating
(stream-ref millions 1), and also that there was no disk activity
during rk-stream-filter but furious disk activity during
jrm-stream-filter.
I'm leaving in a few hours to go out of town for several days. I'll
study this further when I return.
Phil
Phil Bewig
> Phil Bewig wrote:
> > A stream is either nil (a single object distinguishable from all
>
> > other objects) or it consists of a car containing an object (the
> > stream element) and a cdr containing a stream. Streams are fully-
>
> So streams are odd by definition??
Streams are even. I'm not a very good language lawyer. What I'm trying
to say is that there is a function stream-car that returns an object and
another function stream-cdr that returns a stream. Maybe I should say
... or it consists of an object (the stream element) and a stream.
but then the "definition" becomes so simple it's almost meaningless.
Phil
Michael Sperber [Mr. Preprocessor]
Phil> Feuer <fe...@his.com> wrote in message news:<3D2EE1CE...@his.com>...
>> Phil Bewig wrote:
>> > A stream is either nil (a single object distinguishable from all
>>
>> > other objects) or it consists of a car containing an object (the
>> > stream element) and a cdr containing a stream. Streams are fully-
>>
>> So streams are odd by definition??
Phil> Streams are even. I'm not a very good language lawyer. What I'm trying
Phil> to say is that there is a function stream-car that returns an object and
Phil> another function stream-cdr that returns a stream.
This doesn't specify even-/oddness at all. The earlier definition
ties you down to odd streams: "A stream is either nil [...]" does the
trick. You really need to look at the definition of even-/oddness
again.
Phil> Maybe I should say
Phil> ... or it consists of an object (the stream element) and a stream.
This isn't any better.