Generic collections and the printing of streams
82 views
Skip to first unread message
Alexis King
Dec 21, 2015, 6:22:19 PM12/21/15
to dev
As anyone familiar with my collections library is aware, my library makes very
heavy use of streams. So far, they seem to have served it well, but there is one
obvious problem that has to do with how streams are printed. Having the ability
to inspect values in the REPL is obviously useful, but Racket streams always
print out as the opaque value #<stream>, which is effectively useless. The
programmer is required to force the stream in some way, usually by converting it
to a list. Of course, if the stream is infinite, this has some pretty major
problems, too.
Jack Firth and I have been discussing this problem a little bit[1], and I’d like
to try and come up with a solution, even if it is imperfect. The obvious other
languages I’ve looked at so far[2] don’t solve this in any elegant way, they
mostly just accept subpar behavior for infinite streams. I think it might be
worth attempting to come up with superior behavior for Racket streams.
One thing we have discussed is that gen:countable has a notion of finiteness:
specifically, any collection may report whether or not it is `known-finite?`. If
it returns #f, no information is gained, but if it returns `#t`, it’s at least
known to be finite. This certainly seems like useful information for printing
purposes, but it also isn’t necessarily strong enough: it would be very
difficult to automatically track, for example, that `map`ping over a finite
stream would still be finite. Still, certain operations, such as `take`, could
make very strong guarantees about the length of their results, which could be
useful information when printing.
At an absolute bare minimum, elements of a stream that have already been forced
could be safely printed, but this would potentially cause confusion over where
streams arbitrary stop printing. It also probably wouldn’t come up very often,
given that most of the time streams are the results of various filtering,
mapping, or other such operations, and values won’t have been forced yet,
anyway.
With all this in mind, does anyone have any strong feelings about printing
streams? Is the current scheme adequate? Is it feasible to try and create some
kind of “best-effort” algorithm, or are the optimistic algorithms of Haskell and
Clojure valid compromises? Is this a change that should be implemented within
the collections package, or is it something that belongs in racket/stream?
Alexis
P.S. This problem can likely be more or less solved in DrRacket through some
sort of interactive snips in the REPL. This is a great idea, and it’s something
I’ve considered already, but it does not eliminate all the valid use-cases when
one might want better textual output.
[1]: https://github.com/lexi-lambda/racket-collections/issues/4
[2]: https://gist.github.com/lexi-lambda/6985d77048f458960468
heavy use of streams. So far, they seem to have served it well, but there is one
obvious problem that has to do with how streams are printed. Having the ability
to inspect values in the REPL is obviously useful, but Racket streams always
print out as the opaque value #<stream>, which is effectively useless. The
programmer is required to force the stream in some way, usually by converting it
to a list. Of course, if the stream is infinite, this has some pretty major
problems, too.
Jack Firth and I have been discussing this problem a little bit[1], and I’d like
to try and come up with a solution, even if it is imperfect. The obvious other
languages I’ve looked at so far[2] don’t solve this in any elegant way, they
mostly just accept subpar behavior for infinite streams. I think it might be
worth attempting to come up with superior behavior for Racket streams.
One thing we have discussed is that gen:countable has a notion of finiteness:
specifically, any collection may report whether or not it is `known-finite?`. If
it returns #f, no information is gained, but if it returns `#t`, it’s at least
known to be finite. This certainly seems like useful information for printing
purposes, but it also isn’t necessarily strong enough: it would be very
difficult to automatically track, for example, that `map`ping over a finite
stream would still be finite. Still, certain operations, such as `take`, could
make very strong guarantees about the length of their results, which could be
useful information when printing.
At an absolute bare minimum, elements of a stream that have already been forced
could be safely printed, but this would potentially cause confusion over where
streams arbitrary stop printing. It also probably wouldn’t come up very often,
given that most of the time streams are the results of various filtering,
mapping, or other such operations, and values won’t have been forced yet,
anyway.
With all this in mind, does anyone have any strong feelings about printing
streams? Is the current scheme adequate? Is it feasible to try and create some
kind of “best-effort” algorithm, or are the optimistic algorithms of Haskell and
Clojure valid compromises? Is this a change that should be implemented within
the collections package, or is it something that belongs in racket/stream?
Alexis
P.S. This problem can likely be more or less solved in DrRacket through some
sort of interactive snips in the REPL. This is a great idea, and it’s something
I’ve considered already, but it does not eliminate all the valid use-cases when
one might want better textual output.
[1]: https://github.com/lexi-lambda/racket-collections/issues/4
[2]: https://gist.github.com/lexi-lambda/6985d77048f458960468
Marc Burns
Dec 21, 2015, 6:57:25 PM12/21/15
to Alexis King, dev
I use sequences often in the context of database query results. I don't
get as much mileage from streams, but I really like the idea of printing
stream elements. Something like current-stream-display-count that
defaults to a small number would be nice in non-interactive mode, and a
widget to navigate the stream contents in DrRacket would be perfect.
Having something similar for sequences would be convenient but a bit
invasive (a bug involving displayln prematurely consuming a sequence
could be terrible).
get as much mileage from streams, but I really like the idea of printing
stream elements. Something like current-stream-display-count that
defaults to a small number would be nice in non-interactive mode, and a
widget to navigate the stream contents in DrRacket would be perfect.
Having something similar for sequences would be convenient but a bit
invasive (a bug involving displayln prematurely consuming a sequence
could be terrible).
Alex Knauth
Dec 22, 2015, 1:58:25 PM12/22/15
to dev, Alexis King
I was curious about how stream printing could work, so I inserted a prop:custom-write property that printed the `promise` field.
But then I was a bit surprised to find it was not a promise, but a mutable pair containing the symbol 'eager and a #<stream-pare> struct. The 'eager is confusing because it shows up even when it is an unforced lazy stream, and the mcons is confusing because streams are supposed to be immutable.
I also looked more closely at stream-cons, and it looks like `(stream-cons x y)` is equivalent to this:
(make-stream
(mcons
'eager
(make-stream-pare
(make-stream (mcons 'lazy (lambda () (make-stream
(mcons 'eager x)))))
(make-stream (mcons 'lazy (lambda () y))))))
Where the `x` is wrapped in not just one `(make-stream (mcons ...))`, but two `(make-stream (mcons ...))`s. I would think only the lambda would be necessary. What are all these extra `make-streams` and `mcons`s around all the elements of the stream, even when they are not streams themselves?
Also is there a reason why streams use this instead of promises?
Alex Knauth
But then I was a bit surprised to find it was not a promise, but a mutable pair containing the symbol 'eager and a #<stream-pare> struct. The 'eager is confusing because it shows up even when it is an unforced lazy stream, and the mcons is confusing because streams are supposed to be immutable.
I also looked more closely at stream-cons, and it looks like `(stream-cons x y)` is equivalent to this:
(make-stream
(mcons
'eager
(make-stream-pare
(make-stream (mcons 'lazy (lambda () (make-stream
(mcons 'eager x)))))
(make-stream (mcons 'lazy (lambda () y))))))
Where the `x` is wrapped in not just one `(make-stream (mcons ...))`, but two `(make-stream (mcons ...))`s. I would think only the lambda would be necessary. What are all these extra `make-streams` and `mcons`s around all the elements of the stream, even when they are not streams themselves?
Also is there a reason why streams use this instead of promises?
Alex Knauth
Alexis King
Dec 22, 2015, 2:51:09 PM12/22/15
to Alex Knauth, dev
I’ve looked into the internals of streams before, and my understanding is that
they are, in large part, ported from a different Scheme implementation. Hence
the use of mutable pairs and lack of promises, as well as some degree of
compatibility with SRFI 41.
I cannot comment on individual implementation decisions, nor would I expect many
people to be able to. A lot of things can be explained by the caching, though:
streams need to cache their results, and while promises get this for free, an
implementation that does not have access to promises does not get such a luxury.
This is why mutable pairs are necessary, along with the layers of indirection.
Is this a good implementation? It’s certainly not very Racket-y. I think
rewriting it would be warranted iff we can maintain compatibility, maintain or
improve performance, and help to address some of the issues with printing and
the API. Rewriting it for the sake of making it more idiomatic would be good,
too, but it seems like wasted effort if we aren’t fixing anything from a user’s
perspective but could potentially break compatibility in subtle ways. On the
other hand, reducing code complexity is always a win.
Alexis
they are, in large part, ported from a different Scheme implementation. Hence
the use of mutable pairs and lack of promises, as well as some degree of
compatibility with SRFI 41.
I cannot comment on individual implementation decisions, nor would I expect many
people to be able to. A lot of things can be explained by the caching, though:
streams need to cache their results, and while promises get this for free, an
implementation that does not have access to promises does not get such a luxury.
This is why mutable pairs are necessary, along with the layers of indirection.
Is this a good implementation? It’s certainly not very Racket-y. I think
rewriting it would be warranted iff we can maintain compatibility, maintain or
improve performance, and help to address some of the issues with printing and
the API. Rewriting it for the sake of making it more idiomatic would be good,
too, but it seems like wasted effort if we aren’t fixing anything from a user’s
perspective but could potentially break compatibility in subtle ways. On the
other hand, reducing code complexity is always a win.
Alexis
Matthias Felleisen
Jan 4, 2016, 11:56:53 AM1/4/16
to Alexis King, dev
Please consider a more general way of specifying "strictness" patterns
for streams so that people can easily deal with finite and infinite
streams uniformly.
I think the first step would be to develop some basic combinators for
taking/printing pieces of streams and combining those. The second one
might introduce a very small DSL so that plain users don't need the
combinators unless they have a very special need.
-- Matthias
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/0FB7FA46-5D42-4F75-8B2E-804E74EEF9BF%40gmail.com.
> For more options, visit https://groups.google.com/d/optout.
Alexis King
Jan 5, 2016, 12:06:08 AM1/5/16
to Matthias Felleisen, dev
Yes, this precisely the sort of thing I envisioned when considering how
to create smarter generalizations of `known-finite?`. A good approach,
however, is not yet clear to me; I need to spend more time
experimenting. I’ve tried to find prior art in this area, but I haven’t
been particular successful (though I’m not very experienced in looking
for these kinds of things).
Certain bits are obvious: `take` always produces a finite stream, and
`drop` and `map`/`filter` always preserve finiteness. Figuring out how
to handle more flexible constructs like `fold` is less clear. It seems
likely that a richer understanding of strictness and finiteness would be
necessary to adequately describe all of the traditional primitives, but
I’m not sure how clever such a system could really get. I’ll keep
thinking about if there are better ways to encode this kind of behavior,
but it seems impossible to solve the problem in general without losing
significant expressiveness (a truly perfect solution to finiteness
tracking would need to solve the halting problem).
Alexis
to create smarter generalizations of `known-finite?`. A good approach,
however, is not yet clear to me; I need to spend more time
experimenting. I’ve tried to find prior art in this area, but I haven’t
been particular successful (though I’m not very experienced in looking
for these kinds of things).
Certain bits are obvious: `take` always produces a finite stream, and
`drop` and `map`/`filter` always preserve finiteness. Figuring out how
to handle more flexible constructs like `fold` is less clear. It seems
likely that a richer understanding of strictness and finiteness would be
necessary to adequately describe all of the traditional primitives, but
I’m not sure how clever such a system could really get. I’ll keep
thinking about if there are better ways to encode this kind of behavior,
but it seems impossible to solve the problem in general without losing
significant expressiveness (a truly perfect solution to finiteness
tracking would need to solve the halting problem).
Alexis
Reply all
Reply to author
Forward
0 new messages