Streams library 2.0 development, part 1

[qw23]

@toontalk

Then creating a stream of the positive rational numbers (including the negative ones isn't hard) to make the point that the rational numbers are countable.

That was an interesting exercise, as It made me discover an opportunity for improving the interleave streams block. This rational number generator:

… gets stuck in an infinite loop. I suppose this is because both of interleave’s inputs are ‘evaluated’ - let’s see what happens if the second one is made “unevaluated” (like interleave-delayed in SICP):

(with BIGNUMS engaged)

Much better! (It has been changed now) - Makes me wonder if merge streams needs to be changed, too … I don’t think so, or at least it wouldn’t have any impact, as both streams’ heads will be compared anyway.

BTW i created a Toontalk sprite within the project.

@toontalk

Finally create a stream whose input is a stream claimed to include all the real numbers and show that a stream of numbers not included in the input stream can be computed. Each real number can be represented by a stream of digits.

I wouldn’t know how to do that. Could you give a hint?

[toontalk]

The idea is to implement Cantor's diagonalization argument (I would avoid binary representations of numbers - see footnote 3 in the Wikipedia article).

I see it as a adversary game - someone says that they have a stream of all real numbers between 0 and 1 (not hard to generalize if desired) and you create a number that can't be in the stream. One example would be a stream of streams where each inner stream is a stream of random numbers between 0 and 9. Perhaps the inner streams begin with "." just to be clear.

[qw23]

I made two changes to the proposed library blocks:

• terminate stream : will now optionally include the item for which the halt condition holds TRUE;
• log stream : will now optionally include a label a/o index with each logged item (value).

[qw23]

@toontalk

The idea is to implement Cantor's diagonalization argument (I would avoid binary representations of numbers - see footnote 3 in the Wikipedia article).

I see it as a adversary game [...]

A simple demonstration game might indeed be a nice addition to the Streams library ... Perhaps you would be willing to write some code? using the blocks in the proposed library update (be careful not to mix them with any blocks from the current Streams library, as the underlying data structures vary). Thank you in advance!

[toontalk]

Sorry but glad to provide some help.

The diagonal argument when applied to a stream of streams of digits need only create a number (i.e. a stream of digits) that can't be in the stream. So it reports a stream whose first element is the first element of the first stream plus one (or any integer less than 10) mod 10, and then does the same with the second element of the second element, and so on.

[qw23]

I'll try to envision it with lists first:

Round 1:

• "player 1" will create a set of 1 list of 1 item;
• "player 2" will disprove the completeness of the set by creating a list of 1 item that's not in player 1's set.

Round 2:

• player 1 will expand the set to a 2x2 by adding player 2's list to the set, and then append a random digit to each list in the set;
• player 2 will disprove the completeness off the expanded set by creating a list of 2 items that's not in it.

Round 3: ... (ad infinitum)

And the stream mechanism may be used to move from round to round.

Is that like what you had in mind?

[bh]

@cymplecy

Aah- that one is Brian's fault then!

Not really. I would have been happy with just a MAP block and a KEEP block. But qw23 wanted to make it more efficient by combining HOFs. Having been poisoned by Python, he built MAP OVER KEEP FROM, which is a piece of syntax there. I objected that KEEP FROM MAP OVER is just as useful, and in fact they can be nested arbitrarily, MAP OVER KEEP FROM MAP OVER MAP OVER and so on. So we spent a while talking about how to design a block that would efficiently do an arbitrary sequence (as in PIPE) of HOFs, but in the end I suggested that MAP OVER KEEP FROM MAP OVER would handle most of the interesting cases. The rightmost MAP OVER transforms the input stream; the KEEP FROM selects part of the result, and the leftmost MAP OVER transforms the selection. But all that grew out of qw23's desire to optimize nested HOFs.

@toontalk

You might consider reimplementing this in your stream library:

Young students exploring cardinality by constructing infinite processes - ORA - Oxford University Research Archive

Hey, I know those people! :~) Long paper, no time to read it this morning. I'll have to come back to it. I'll be interested to see how you turn a proof by contradiction into a programming exercise. We teach the halting theorem in BJC, and we can program the case that fails, but we have to say "suppose we have a HALTS? predicate..." but we can't (clearly) show code for it.

@toontalk

not robots and birds

Before looking at the paper, I thought you were making a really narrow in-joke! But I see you weren't joking at all.

@qw23

(It has been changed now)

So, you're saying that the INTERLEAVE in the library will always delay its second input? I guess that's okay... But I don't like the List shape for the first input and Any for the second. I know IN FRONT OF STREAM has the same problem, but it doesn't beat you over the head about it because there's only one stream involved. Lemme see what Jens will say about List(unevaluated), or rather, turning Unevaluated into a checkbox that can be applied to any type.

@qw23

• terminate stream : will now optionally include the item for which the halt condition holds TRUE;
• log stream : will now optionally include a label a/o index with each logged item (value).

Oy, these are getting complicated. (I know, LOG is my fault.)

I'm going to have to take a pass over these looking at their help screens and stuff like that. But we're almost there! (Modulo Jens.)

[qw23]

@bh

Not really. I would have been happy with just a MAP block and a KEEP block. But qw23 wanted to make it more efficient by combining HOFs. Having been poisoned by Python [ they’re constrictors BTW] he built MAP OVER KEEP FROM […] in the end I suggested that MAP OVER KEEP FROM MAP OVER would handle most of the interesting cases. […] But all that grew out of qw23's desire to optimize nested HOFs.

Though quirky, you made a great suggestion IMO.

@bh

So, you're saying that the INTERLEAVE in the library will always delay its second input?

Yes. It’s exactly what SICP’s interleave-delayed does BTW, from the section on logic programming, of course . I agree its looks are somewhat peculiar., but interleaving streams is an advanced concept anyway, so who cares?

@bh

Lemme see what Jens will say about List (unevaluated), or rather, turning Unevaluated into a checkbox that can be applied to any type.

We don’t have to wait for something like that having been implemented in vanilla Snap!, do we? (It could be changed in a later update of the library)

@bh

Oy, these are getting complicated.

These options have defaults, so the user may ignore them.
As for terminate stream (it’s really a variant of keep, avoiding infinite search, in applicable circumstances): I can both think of cases where you’d want to see the pivotal item in the result, and where you don’t - and if there’s going to be further processing done within the streams domain, inserting an operation just for filtering out a single item is disproportionately “expensive”.

@bh

But we're almost there!

Do you have any news on upvars a/o ring parameters?

[bh]

@qw23

Do you have any news on upvars a/o ring parameters?

Nope, I spent today in surgery. (Nothing serious, an elective, ambulatory surgery. But it kept me off the computer all day.)

[qw23]

@qw23

Yes. It’s exactly what SICP’s interleave-delayed does BTW, from the section on logic programming, of course . I agree its looks are somewhat peculiar., but interleaving streams is an advanced concept anyway, so who cares?

Actually, the second output looking different from the first may be an advantage - as it could alert the user that there is a difference between the two input slots, and that this is relevant in some cases.
Would it be preferable to explicitly call the block interleave (delayed) instead of just interleave?

[bh]

@qw23

Would it be preferable to explicitly call the block interleave (delayed) instead of just interleave?

No, they do that in SICP because they don't make INTERLEAVE (DELAYED) a special form to delay that input, so the caller has to use an explicit DELAY in the second input slot. We make it easier than Scheme does to get an unevaluated input slot, so your user doesn't have to call DELAY explicitly. I think in SICP they are emphasizing that delaying the second input to CONS is all you need to make streams work; things like MAP then just automatically work streamily. So they don't want to say "well, CONS and INTERLEAVE." And in fact plain old interleave works almost all the time.

[qw23]

@bh

And in fact plain old interleave works almost all the time.

I agree. However, not in some deeply recursive cases. And I can’t think of a case where plain interleave works while “delayed” interleave doesn’t. So as a library block the latter is preferable anyway, IMO.

[bh]

@qw23

And I can’t think of a case where plain interleave works while “delayed” interleave doesn’t. So as a library block the latter is preferable anyway, IMO.

Oh, yeah, if the first sentence is right, so is the second sentence. :~) And I can't think of one either, certainly not if the stream is used functionally (so the order of evaluation doesn't matter).

[bh]

Okay, down to really tiny details:

What would you say to THE EMPTY STREAM to match SICP? When I (wearing my naive user hat) see EMPTY STREAM, I try to parse the "empty" as a verb.

The RATIONALS stream is meant to be a stream of (unique) numbers, not a stream of pairs of integers. So I rewrote

and added the helper GCD function. You might consider whether this complexity is worth it, compared with writing a POSITIVE RATIONALS helper and then at top level just interleaving its result with the negatives of its result. Also, I had to display 200 items to convince myself that it would eventually get around to numbers whose numerator and denominator are both big enough to be interesting. I think it's okay to display a list that you have to scroll through. Alternatively, leave out the negative ones altogether. (We don't show negative integers!) But still show 100 items.

I also edited the comments to remove "(theoretically)" from the descriptions. You have to believe in abstractions! Every single integer (prime, rational) is in there, if you go far enough down.

I also edited the initial comment, because seeing ︎ by itself made me think you wanted me to click on the arrowhead of some block, and seeing "and now, to continue" brought to mind the common use of "and now, the stars of the show, the Beatles!"

Something I didn't do, but want to suggest, is making ONES, INTS, etc., global variables (which I think is doable in v10 without using the variables library?) so that after running the demo, the user can use those, especially ONES and INTS, to create additional streams. ("Okay, class, now make the stream of all the integers, positive and negative included." Or "the even integers," and so on.)

Maybe add a demo of getting the first five items of a huge list after sorting?

...with the comment saying the rest of the sorting isn't computed.

Speaking of v10, I'm happy with your ordering of blocks in the palette, except that I think UNIQUES should move down two (or three, your choice) places. The HOFs are super important!

I still want to do more editing of help screens and demos in the block editor. Do you want to read my changes as I do them?

[qw23]

@bh

What would you say to THE EMPTY STREAM to match SICP? When I (wearing my naive user hat) see EMPTY STREAM, I try to parse the "empty" as a verb.

I considered that ... and I, too, tend to associate empty stream with, like, "Empty your plate !" . Really the one reason why I decided against "the ..." is I thought the following would be confusing:

(and I didn't want the user to have to initialize a unique "empty stream" pointer)

I also considered: , which to me sounds like a title for a sentimental memoir though.

However that may be, you're the editor-in-chief, so if you have a strong preference, please follow that.

@bh

The RATIONALS stream is meant to be a stream of (unique) numbers, not a stream of pairs of integers. So I rewrote [...]

For simplicity of demonstration I would prefer to use: uniques of stream (BTW to keep it usable I used the fast version of the latter) (and positive rationals only):

with:

and:

(it's to be found in the Toontalk sprite, final script).

I'm having second thoughts about this. GCD is probably better, because it requires more or less O(n) runtime, whereas uniques requires O(n²). If anyone wanted to try a very much larger selection, this might become an issue.

@bh

Something I didn't do, but want to suggest, is making ONES, INTS, etc., global variables

Sure.

@bh

Maybe add a demo of getting the first five items of a huge list after sorting?

Nice.

@bh

Speaking of v10, I'm happy with your ordering of blocks in the palette, except that I think UNIQUES should move down two (or three, your choice) places. The HOFs are super important!

I initially put uniques before the HOFs because I tried to adhere to the order used in the Lists palette, where [uniques] of is in the 6th position (combined with several other functions), well before map etc. But I do agree on the HOFs being more important, so I'm happy to rearrange it.

@bh

I still want to do more editing of help screens and demos in the block editor. Do you want to read my changes as I do them?

I understand you're now doing the final editing yourself. That's totally OK with me. If you would like to leave the link to your version in this forum, I (and perhaps others) may take a look every once in a while. I promise: no kicking and screaming

Final remark: Do you think it would be useful to add flatmap (function) over stream ?
Added that to my library version, plus stream versions of some more list HOFs ... for what it's worth.

[bh]

@qw23

Really the one reason why I decided against "the ..." is I thought the following would be confusing:

Yeah, in Lisp tradition, there's only one empty list. (That is, all empty lists are EQ, not just EQUAL.) But I think only hackers are even going to try that, so I'm okay with THE.

@qw23

I'm having second thoughts about this. GCD is probably better, because it requires more or less O(n) runtime, whereas uniques requires O(n2). If anyone wanted to try a very much larger selection, this might become an issue.

Yeah, plus, it's educational, teaching GCD. :~)

I don't think the streams library should drag the bignums library in with it. So, either we do (JOIN numer / denom) or we make a list of two integers. I think doing floating point division is a nonstarter in this context! What do you think?

@qw23

I initially put uniques before the HOFs because I tried to adhere to the order used in the Lists palette, where [uniques] of is in the 6th position (combined with several other functions), well before map etc. But I do agree on the HOFs being more important, so I'm happy to rearrange it.

Oh pooh, it's LENGTH that merits its place high in the palette!

@qw23

Final remark: Do you think it would be useful to add flatmap (function) over stream ?

Yeah we should have that for lists too. It's unfortunate that we use FLATTEN to mean flatten all the way down to atoms, rather than flatten one level.

[qw23]

@bh

Yeah, in Lisp tradition, there's only one empty list. (That is, all empty lists are EQ, not just EQUAL.) But I think only hackers are even going to try that, so I'm okay with THE.

OK, let's call it the empty stream then, add a comment about the implementation (implemented in my version of the library now), and make sure it's made truly unique as soon as Snap! allows such without initialisation hassle.

@bh

I don't think the streams library should drag the bignums library in with it. So, either we do (JOIN numer / denom) or we make a list of two integers. I think doing floating point division is a nonstarter in this context! What do you think?

Agreed. I think join (numerator) / (denominator) would be best. I considered , as it will actually yield a number when call-ed, but that may require too much explanation.

Flatmap: there is such block in my version.

[bh]

Radical proposal: I hate -1 for no limit. That's so 1950s. So, give those inputs a dropdown that has Infinity as its only item, and make that the default. ∞−1=∞, so it has the behavior you want (never reaching zero). What do you think?

[sonic123cdmania]

I think it's -1 because you can use something set to -1 infinite times, it will never reach 0.

[bluebaritone21]

That's why they used -1 for no limit in the 50s.