Streams library 2.0 development part 2

  (lambda (one)
      (lambda (two)
          (lambda (three) (list one two three))
          (numbers-from (+ two 1))))
      (numbers-from one)))
  (numbers-from 1))

My Scheme version of my original Snap! algorithm, running in Lisppad Go on an iPad Pro (2017) found 5 Pythagorean triples. Lookimg for the 6th it went on for a long time without reporting.


Okay, so, I guess I propose that we forge ahead with the original plan and reject Pythagorean triples as too hard, at least unless we make the stream of all triples ordered by largest value:

If there were a FINITE-FLATMAP that used APPEND instead of INTERLEAVE, then the tuples would come out in exactly the order you'd expect.

I'm cheating a little by using a<b<c instead of a≤b<c as you did, but it doesn't matter because there aren't any isosceles Pythagorean triples. It was just easier to code this way.

How lists with infinitely many items? You haven't been following the (long) discussion... Briefly, a nonempty stream is stored as a list containing the first item of the stream and a promise to compute the rest of the stream later. (A promise is a function of no inputs, i.e., a ringed expression with no empty slots to be filled.) But "the rest of the stream" is itself a stream, so when you cash in the promise, you get just one more item, along with a new promise.

The precise sense in which, say, the stream of primes contains all the primes is that any particular prime will turn up after cashing in only a finite number of promises. So, for example, it matters in what order the items are generated. If I make the stream of all positive integers:

and then I try to make the stream of all positive and negative integers this way:

even if I listed 100 items, or a million, they'd still all be positive numbers. The negative numbers aren't reachable in this stream, so (by definition) they're not in the stream at all. But I can get all the integers this way:

And of course this works only for countable sets. There's no way to make the stream of all the real numbers no matter how you reorder them.

thats sick. i just dont see how this is so useful

I'm not sure how to take that.

Well, you don't have to use it, if you don't have a use for it. I think it's a thing of beauty: an abstraction that allows me to have all the prime numbers in my computer!

It's also sometimes useful for efficiency reasons to reorder a computation by lazy evaluation, but I don't want to explain that yet again -- go read the earlier threads on streams.

:smirk: I wasn’t aware of any “plan” behind Pythagorean triples.

The reason I mentioned them in this topic was that - out of curiosity, whether I would be able to tackle the problem easily - I had done exercise 3.69 from SICP, and found my code crashed somewhere along the road from the 2nd to the 3rd solution. This prompted you to discuss the issue with jens, who told us that Snap!, as a block-based IDE, carries a larger environment than (text-based) Scheme, and suggested we try a non-SICP approach. I consider the Pythagorean triples algorithm a benchmark for memory use (and speed) in comparing streams management systems, and perhaps also in comparing application strategies.

I built a flatmap finite (function) over stream (stream) in both library versions BTW.

Or, perhaps you mean: “the original plan” = SICP-based streams library v2?
Yeah, that’s fine with me.
Then I’ll continue developing the alternative system “in the background”, i.e. with low priority.

Yeah. That, and logic programming. :~)

I would like to implement a few changes, inspired by the effort on non-SICP streams and recent performance / stabillity tests. I'll summarize them later below for discussion:

  • stream with numbers from () to ()stream with numbers from () to () step () (= off-palette variety of stream with numbers from ()); ( :white_check_mark: done)
  • copy stream: integrating skip, copy and keep features (while keep is kept simple); :white_check_mark:
  • add a comparator function to the advanced (off-palette) variety of uniques;
  • add a uniques option to merge streams (makes sense & runs efficiently);
  • add a flatmap (off-palette) variety for finite mapped streams, using append, not interleave; :white_check_mark:
  • add a list () items of stream () (off-palette) variety with a continuation upvar. :white_check_mark:

Definitely - that's what it was all about in the first place.

is that what you're doing? I think you should just calculate b from c and a, honestly. might save a bit of memory.
thats what i do in my pinned repl on replit.

We've been using it as a benchmark for streams mechanisms.

I wish there were an intermediate between on-palette and off-palette. It seems silly to have features we withhold from users, but as you know I don't want the complexity to get in their way. Maybe if we put them down at the bottom of the palette?

I’ve been thinking about that, too. Perhaps a demo script featuring varieties?

I guess. A block called "Others..." that when run just says "edit me."

MIT Scheme (a/k/a GNU Scheme) does the same as the others: works for five triples, runs out of memory for seven. So, I declare Snap! okay. :~)

It'd be nice if we responded to running out of memory in some more graceful way, but I wouldn't care were it not for this Chrome misfeature of killing all the s.b.e tabs if one of them crashes.

Here’s my latest version. I moved most of the advanced stuff, with extra options and all that, to block: Streams library v2 wip script pic 41.

i’m struggling with merge, though. The reason being a sorting quirk I found in Snap!.

Thanks; I'll look it over this weekend. If you hurry you can submit a talk to Snap!Con. :~) (Deadline today, but it might be extended because our system wasn't letting people submit earlier today.)

I prefer to remain anonymous for now.
The latest version of the proposed library is here now.

Ah, okay. IIRC we did once have a Snap!Con talk whose presenter was listed by username, but whatever.

First thoughts:

How about renaming to
FIRST ITEM+INDEX <pred> FROM [stream]
The existing name looks as if it means "first item whose index appears in the stream..."

Also I still think it should be right under KEEP in the palette, as for lists.

COPY STREAM is so complicated! I think to make it understandable it needs a longer title, something like
COPY STREAM [stream]
Partly this is because I don't understand what "strictly" means in this context. Actually I think it might be even better to change the third line to CONTINUING UNTIL and changing the sense of the predicate.

Or maybe even
At one point in the discussion it was important to you that this made a partial copy of the stream, but we're doing functional programming here, so it's all about values, not pointer identity. This block makes much more sense to me as a sort of variant of KEEP that keeps one segment of the stream.

Is there a reason FLATMAP isn't OVER STREAM(S) with variadic input? And it belongs right under MAP. You have it down with INTERLEAVE because you're thinking about how you implemented it, but that's not what we want users to think about. (I'm grinning as I type this because it's an argument I frequently have with Jens!)

In the "mix streams" category, each block has a hidden advanced version that, among other things, is variadic. I'm not sure the variadicness should be viewed as advanced; the APPEND block for lists, for example, is variadic. I realize the delayedness question is complicated for the implementation, but is it complicated for the user? The two-input versions already raise the delayedness issue. So then it's only MERGE that needs a hidden advanced version, because of the comparison function. And I think that input should be a predicate, so in your example it'd be

so that you could use > instead of < if you want descending order, or I guess maybe you could use ≤ or ≥ to affect the stability of the merging. But I could be talked out of this.

STREAM DEMO above SIEVE, I think. The latter is a helper for the former.

Speaking of STREAM DEMO, an actual bug: The computation of the Hanoi stream should be

(One of many cool ways to compute it!)

Let me make these changes and send it back... and also rewrite some of the help text. (Speaking of help text, some of the MORE BLOCKS blocks don't have any, the ones whose purpose I don't understand. :~/ )