Re: Should the car be a stream?

["Phil Bewig" <pbewig@xxxxxxxxx>]

I think I am saying (eq? stream-type promise-type) is #t and Andre is saying (eqv? stream-type promise-type) is #f.  Both statements are correct.  Since both stream-type and promise-type are abstract, I can mix them up inside (streams primitive) without consequence, except that it causes some confusion.  I guess it is more precise to say that the type of the stream-car is a promise, not a stream, except that in the implementation they are the same thing.  Andre is correct in that I could have implemented the car of a stream as an ordinary promise instead of a stream-promise.

Types of the primitive functions aren't very interesting:

stream? :: alpha -> boolean
stream-pair? :: alpha -> boolean
stream-null? :: alpha -> boolean
stream-car :: alpha stream -> alpha
stream-cdr :: alpha stream -> alpha stream

Stream-null, stream-cons and stream-lambda are all syntax and have no type.  I guess you could say that the type of stream-null is alpha stream and the type of stream-cons is alpha * alpha-stream -> alpha stream.  I don't know how to writhe the type of stream-lambda.

On Nov 14, 2007 6:51 PM, David Van Horn <dvanhorn@xxxxxxxxxxxxxxx> wrote:

AndrevanTonder wrote:
> The following seems wrongly typed to me:
>
> (define-syntax stream-cons
>     (syntax-rules ()
>       ((stream-cons obj strm)
>         (stream-delay (make-stream-pare
>                           (stream-delay obj)   ;???
>                           (stream-lazy strm))))))
>
> Specifically, I don't think the car of a stream should be a stream.

I agree, from the types given, this doesn't seem right.

Why weren't there types given for the streams primitives library?  This
seems like a valuable part of the spec to me.

> But even I am wondering about the rationale for making the stream
> elements themselves promises.  It may be useful to leave the types of
> the elements (including whether they are promises or ordinary values)
> orthogonal to the backbone of the stream itself.
>
> I suspect that if the elements were not themselves delayed by default,
> you would see a huge difference in performance.

If the elements were not themselves delayed by default, computing the
nth element of a stream is proportional to computing each element
previous to it.  In the lazy version, it's simply proportional to n.
It's easy to imagine cases that perform infinitely worse using the first
model compared to the second.

To me at least, it's important that no element of a lazy list is
evaluated until it is needed.  This is what SRFI 40 specifies in prose
"no element of the stream is evaluated until it is accessed," but the
code does otherwise.  I'm glad to see SRFI 41 fix the problem.

David