Conor

Honestly, I don't want to offend our C listeners, but uh the best community uh is the array community. It's uh you know, they think the right way. You know you know, Phineas here he he swims in the land of folds and scans. You know, we we just like we spend a little bit of time there because we work at NVIDIA and it's important to us, but like C programmers, they're like a scan? What's that? It's like a partial sum, you know? Not everybody. The listeners of this podcast probably know. But most of the C devs out there, you know, uh it's uh they're still catching up on two potato tapes. Yeah, one bum potato, two potato. Welcome to ADSP the podcast, episode 176, recorded on March 6, 2024. My name is Connor, and today with my co-host Bryce, we chat about the algorithms from the Q language, prior, deltas, and more with Phineas Porter over dinner.

Bryce

I don't know. I don't have a plan, Connor, but I've had a revelation, and the people need to know about the revelation. Do you want to know that if there's anything else? You wanna you wanna you wanna do the introduction?

Conor

This is just like when we were doing the Slovenia 2023 road trip, and every time he'd start recording, he'd be like, alright, recording again. And I'd be like, no, Bryce, we have to do the intro. We are at Francia.

Bryce

What do they call it?

Conor

This isn't getting picked up. This isn't getting picked up. We got one mic now, and it's tiny. Uh we're at the Francia Vegan Cafe, a place that Ramona does not like. Bryce just said she's never even been here. She's not a big fan of vegan food. She's Polish, so she likes her meat and potatoes. And uh Bryce is not meat, but Bryce's uh cholesterol is too high, so he's not allowed meat. I myself did go to Shake Shack for lunch and got two double hamburgers with bacon. It I calculated the calories. It was 1,280 or something. It was worth every calorie. Anyways, uh, we're here at a cafe. It's not just me and Bryce. We're with uh never before guest on ADSP the podcast, and honestly, probably he should be on a ray cast, not ADSP the podcast.

Bryce

Uh without consent for him.

Conor

I mean, he hasn't said no at this point, so uh and honestly gotta keep your voice down.

Bryce

You gotta keep your voice down.

Conor

We had some noise complaints earlier.

Bryce

And uh I got uh I got PTSD from when that's just happened right now.

Conor

Um, anyways, no, we're gonna let Phineas uh introduce him.

Bryce

Connor doesn't seem to understand how consent works. You have to ask people. You can't just assume that a non-response means yes. Phineas, do you want to be on our podcast? Sounds good.

Conor

False, too. I mean, he hasn't, I don't have you you haven't been mentioned by name on ADSP the podcast. You've probably been mentioned uh, what do you call it?

Phineas Porter

Uh synonymously.

Conor

Like uh, yeah, without yeah, synonymously. And it'll be that was the same thing on a raycast, but then at some point you did get mentioned by name, because I think I asked you if it was okay. So I have subtly asked for consent. Anyways, I'm gonna hand it back to Bryce. We we're just finished dinner. There's some surprise event happening later, nobody knows what's happening. And uh Francio, it was pretty delicious. It was pretty delicious.

Bryce

I charged this response to the. So uh after we had our revelation earlier today that um that reduced by key is implemented in terms of scan in cub. In terms of scan by key in cub, which is even worse. Um, I we we've spent a lot of time in this podcast, I had a revelation in. We we've spent a lot of time in this podcast talking about how like everything's implemented in terms of you know, say a couple of primitive algorithms, but like more and more it's just everything is implemented in terms of scan. And I realized that all of the cub algorithms, I think, in some way, shape, and form use scan, other than just straight reduce and four. Histogram, I think, uses scan. The sorts definitely uses scan, um, scan uses scan. Uh the all the run length encoding, run length decoding uses scan. Um what other algorithms are in Cub? Um uh copy if uses scan. Like they're all they're all just fancy scams, is what I'm saying. Everything is just a fancy scan.

Conor

First of all, listeners, I'm disappointed. This is what we turned the mic on in the middle of dinner for. This is a little bit disappointing. Yes, thank you very much. It was delicious.

Bryce

Yeah, that's true. We did have ice cream last night. Uh can I get a box? Yes. Or if you can box it, that'd be great.

Conor

Anyways, disappointed that this is what we turned the mic on. We're not giving it back to you yet. I've got the power. But uh transforms? Transforms are not implemented in terms of a scan.

Bryce

But it's just a whole lot of things. Like, look at like I'm talking about.

Conor

Should we hand it over to Phineas? Also, Phineas, uh, in case we don't let him say anything, because I feel like Bryce is not gonna let him, we will make sure we put a link. That's cool. We will uh we will put a link to a talk he was featured in. Nick Saris gave a talk at KXCon 2023. It was fantastic. You also gave a talk. What am I even talking about? I was gonna say, uh I remember it from the the uh the cue gods. He's a cue god, but he also gave a fantastic talk himself. Both will be linked. Hopefully, Phineas will get to say something, but Bryce is throwing a tantrum across the table because I'm hoarding the mic.

Bryce

I don't even remember what I was gonna say. What was I gonna say? What were we talking about? Oh yeah, I'm just I'm talking about solely cub algorithms, which are like the underlying low-level primitives. And in in Cub's world, like a transform and a 4-H are both just four. Like Cub has a device for, and that's both are just forms of that. Anyways, I'll let other people talk now.

Conor

I don't know what you need to say. Should we interview Phineas? Let's interview Phineas.

Phineas Porter

Oh yeah.

Conor

Wait, you want to discuss that again?

Phineas Porter

No, you should just you should just point out this wasn't this already the claim? The claim. Oh yeah, yeah. We already uh scan is the scan is the old there. I think you actually said this. Yeah, I probably guessed just talk into this thing. Okay. I think Bryce said uh actually that on an earlier episode that scan was the the ultimate algorithm because you can implement everything as a scan. Or maybe it claims that it reduces a scan, because if you just keep enough state around, your reduce can can also work as a scan, technically. So it really reduces your is every algorithm.

Bryce

Yeah. Yeah, I believe that. So maybe it's almost reduces.

Conor

I mean that yeah, we already we will link to ADSP episode, what was it? I don't know, 120? That's a guess. We'll see how I'll look it up after. But uh Ben was on. Ben Ben Dean was on the episode, Tristan Brindles was on the episode. Alright, folks. As you might be able to tell, Bryce was in charge of the audio. He brought his own lapel road microphone. Questionable, questionable audio quality. And somehow he silenced it or muted the mic for a minute and a half here. So you're gonna miss a minute and a half of conversation. We apologize. I apologize on behalf of Bryce. Back to the conversation.

Phineas Porter

Yes. Yeah, pr I mean, I think obviously prior should keep the first element. You can reconstruct the original list that way, and it makes all the lanes the same, so you can it's like just very convenient for the shape. But you know, Connor here thinks that you should drop the first element because it's not really part of the reduction.

Conor

So, first of all, prior prior is the correct name for adjacent difference. And I I've actually adopted the name prior in my in my own. Sorry?

Bryce

Who wants to drop the first element?

Conor

So Bryce has asked who wants to drop the first element? The answer is me. And the answer is we did. Uh because we added in C23 a uh view called adjacent transform, which is the modern version of adjacent difference, and that does drop the first element.

Bryce

If you don't drop the first element, what do you do?

Phineas Porter

Keep the first element. You can reconstruct, so cumulative sums and deltas gives you the original list if you have the first element. Otherwise, you're missing a constant. It's like integrating in calculus. If you drop C, you don't have the C anymore. You're done.

Conor

And this is brilliant because deltas.

Bryce

You just want to keep it just on its own? You just want to keep the first element just on its own.

Phineas Porter

Return the length, the length, you have an iterate you have a container, it has n elements in it, and it the first element is the same element as it was in the original list.

Bryce

But what if the type changes?

Phineas Porter

This is the problem with type languages.

Conor

That's the pro That's the problem. So this is that's exactly it. So a JSON difference has a constraint, and because it copies that first element in order to maintain the circular round trip between uh partial sum, etc.

Phineas Porter

Or like or like ratios, ratios, and we'll give you back the original series. So if you take ratios between all the numbers, you know what the percent changes are, and then you can go back to the original list. This is like a very convenient feature to have around. When you do, a lot of times you're looking for like, I want to find all the cases where something big happened, and then I want the actual numbers. I don't have to keep around two two lists around with me the whole time. I just keep around the one element and then come back.

Conor

Price is ordering his dessert here.

Bryce

I will have the chocolate fudge cake.

Phineas Porter

I will have the tiramisu.

Bryce

Connor? Okay, Connor being boring. Where were we?

Conor

I mean I've had I've had uh the two Shake Shack burgers.

Bryce

I also did you have a shake shake shake something?

Conor

I did not I don't like shakes. Uh Bryce asked. You don't like shakes!

Bryce

What is wrong with you? I had two shake Hey, hey, this thing has auto gain. It's supposed to be idiot proof.

Conor

I had two burgers at Shake Shack, then I had lunch at a Thai place where I had uh a couple chicken wings and pad Thai.

Bryce

Yeah, yeah.

Conor

I told you I was meeting up with uh with an acquaintance, Ashley, if you're listening. And uh what? Ashley. He's another member from uh you know the KX uh you know Q community. Honestly, I don't want to offend our C listeners, but uh the best community uh is the array community. It's uh you know, they think the right way. You know? You know, Phineas here, he he swims in the land of folds and scans. You know, we we just like we spend a little bit of time there because we work at NVIDIA and it's important to us, but like C programmers, they're like a scan? What's that? It's like a partial sum, you know? Not everybody. The listeners of this podcast probably know. But most of the C devs out there, you know, uh it's uh they're still catching up on. Yeah, one bone potato, two potato.

Bryce

What's the resolution of the fire? How did you two resolve your differences? Oh, we didn't. Oh, Bryce. I asked, how did you two resolve your differences?

Conor

And uh the answer is uh I mean, did we I think we c we uh uh came to an agreement that uh I think for type languages it makes sense to be you have to have at least two types, right?

Phineas Porter

You need to be able to maintain the fact that like you're gonna dr if you change types, you can't keep this first element. But like I said, it's like much more memory efficient to like not keep around the original list if you can go back and forth between the two.

Conor

And in and Q and array languages, uh your first type can be different. You can end up with a heterogeneous list, right? So you can't do that in type languages, and I think so what we ended up agreeing on is that like prior and adjacent difference what I I don't see a reason that you couldn't have a list and an iterator in C where the well that has like nice properties.

Phineas Porter

What are you gonna wrap it in? Like what are you gonna wrap it in, like a std variant?

Conor

Absolutely not. Um so the point being is for convenience, adjacent difference and prior, especially in array languages that are dynamically typed, is very nice. However, if you want to design the perfect generic algorithm that you are able to implement all the different flavors of kind of deltas and adjacent difference or adjacent transform, it uh you want the one that doesn't bundle that first type there. And then from there you can kind of do everything you want.

Phineas Porter

Uh oh, there's there's there's another solution. So the other solution is that your your function that your the operator you're gonna apply between all the adjacent elements should have a um default like type for that that uh what's what do you like identity value. If you have that, then you do then you can then the identity value can push it into the other the first element into the correct identity type for the for the first element.

Bryce

Yeah.

Conor

So if you've if you've got like if you've got like if you want to do like a a prior transform where you're bundling your prior with a binary operation, which is typically what you're doing, right? Bri bin prior and adjacent transform, they're higher order functions that take a binary operation. If your binary operation and your type form, what is it, a monode or a semigroup or whatever it is from category theory, that comes with an identity uh value. And so if you've got integers with plus, that identity value is gonna be zero. And so you can just use that value as the uh the first element, and then instead of ending up with n minus one elements, you end up with n. And that's the other thing I haven't commented on is the convenience thing about the way prior works is that like in array languages, you like to end up with equally lengthed arrays because then your scalar operations work and you don't end up to you don't end up having to jump through hoops. We care about that less in like arranges like library, because it's it's a it's a sequence. Uh zip does zip have laziness built in? I don't actually don't know how our zip works. Of course. Or not sorry, not laziness, like uh short circuiting. Like if one length is uh different different.

Bryce

It goes to whichever the shortness.

Conor

Yeah, yeah. And then there's equivalent algorithms. Uh right, so we uh Phineas just asked, what about zip? I said something about laziness, but in my head I meant short circuiting because in functional languages like Haskell and whatnot, they usually have two different algorithms. Zip that short circuits to whatever the long the shorter length is, and then they also have one called like, you know, zip longest, which they have varying flavors. Sometimes you can give it like a uh a default value to put in there, sometimes it'll just fill it with like some some null or something like that. And uh we're gonna hand it back to Bryce because he's had a couple slices of his cake, and I'm guessing we're gonna get a review here.

Bryce

It's pretty good cake. I mean, it's hard to believe it's vegan.

Conor

Um what do you have against vegans, Bryce?

Bryce

Um I think I I literally brought us all listeners. I don't have any problem with vegans. I literally brought us all to a vegan restaurant, and I'm trying to convert my like meat-only girlfriend to at least sometimes enjoy uh a vegan meal. So I don't wanna I don't wanna alarm anyone, but my phone has 30% battery left, and we will need some percentage battery to navigate uh to various places and various things. So uh we gotta we gotta interview rapidly.

Conor

I mean, uh anything we've we talked about prior. I mean pri I I gotta say too prior. Uh I actually in my in my toy work project, which hopefully isn't a toy in the future, I did rain I I I use the name prior because it's a I think it's honestly better than a Jason Transform. It's shorter. I do love short names. I changed deltas to diffs to match uh NumPy a little bit more. Um which I actually think they're diffs is a little bit too close to one other thing. But uh things are matching quality matching. Yeah, yeah, so it's not uh alright, I'm gonna take a bite of uh this uh this cake. I'm not gonna identify it as a vegan cake. Cake is cake, folks. You know, we don't discriminate here over in Canada. I guess we're in America right now. Oh, that's not clear.

Bryce

But but we will but you should mention that I will be in Canada next week.

Conor

Yeah, it's pretty crazy. Well now I got a mouthful of cake. Oh, this cake is good. And uh I'm not a big Terramisu fan, you know. It's too complicated. It's got what do they call them? What are the what are the sticks? The the fingers, the lady fingers? Yeah, don't get me wrong, I'll eat a terramisu if uh terramisu. But but yeah, Diffs Deltas prior. Um we we I've no I mean this actually probably is gonna come out in like a month and a half from now, because we've got so much content once again. But uh I will link to the uh episode of a raycast we're gonna be having on someone from KX. We initially were hoping to get Andrew Wilson from the KX core team. Uh I think he said no because he doesn't like us. And uh not because he doesn't like us, I'm just joking around, obviously. And then I uh we're juggling a few people I don't know. Some people just I think he has to speak a KX con because he works for KX and they force him to. But um, you know, language people aren't necessarily the same people that want to get up in front of a crowd or get in front of a mic. Uh we're anomalies, you know? Uh especially you, you know? Although what what were you saying earlier is that Connor, stops stop referring to our podcast as a pod. And I was like, what are you talking about? You know, it's it's such a large part of our life now. I refer to our conversations as was that one on pod or off pod? Because I can't there's been so many conversations at this point. I can I can't keep track.

Bryce

I did serotypically uh record uh Connor earlier today when we were just talking about some problem because I'm like, this could be good podcast content. And there are times when I'll really want to talk about something with Connor, but I'll wait because I'm like, well, if we start talking about this, it might be really good, and then I would want to record it for the podcast.

Conor

That's what happened in Venice when when we were gonna go on that walk. I literally was like, aha, I have it. And you were like, stop talking. And I was like, I haven't even started talking. And you're like, you were about to, and then you wouldn't let me start explaining myself until we were recording.

Bryce

But you know what? For all the shit you give me about not contributing to the production values of this podcast, I do make sure we're recording the good content.

Conor

Honestly, this is gonna result in us at like 50. Like once our kids are or I guess actually we're already in our 30s, so when we're 60, once our kids are like off in university, university, we're gonna like get our own, you know. It won't even be Netflix at that point. Because GPTs will be so good, we won't even call them that anymore. Everyone will be able to go make their own reality TV show. All we need to do is we'll need to put a couple rings up in like the corners of our apartments and like feed it some footage, and we'll be able to like have our own the ADSP, the reality TV show, and uh it'll be fantastic, you know. We won't have to edit anything, it'll just know you know, when Bryce says certain topics, it'll automatically filter it up, and then that one time it'll mess up and then we'll get canceled.

Bryce

Connor. Anyways, we're we will definitely get cancelled before 30 years from now.

Conor

Yes, I was gonna say we'll link to whoever we do bring on from KX. Phineas will be on, I mean, he's already been on ADSP now. He'll be on ArrayCast at some point.

Bryce

And uh get into bur into array programming languages.

Conor

Oh yeah, great question. So Bryce just asked, how did you get into array programming? Uh, and specifically Actually, you don't actually use Q on your day job. You used to use Q. Last time I checked, you were using Scala. But anyways, yeah, give us a little story of how uh how you came to be uh Q god, because he is a Q god.

Phineas Porter

I don't know about a god, but I the way But uh the way I got into um Q is uh actually quite simple. I was working on uh a problem with which is a little bit related to uh the the the the classic programming problem, which is suppose I want to know the highest floor I can drop an egg off of, and I have two eggs. And so there's like a canonical solution to this problem. But I was thinking, what if what if the the cost of testing is not exactly like you don't have two eggs, but really like think about it as like the cost is proportional to your guesses. So like if you overshoot, you pay some cost proportional to the error. And the way this is the interesting case for this that's most interesting for is uh drug dosing. I want to find the right dosage of a particular drug, and I need to know how much you're how much titration. The way that doctors do this is really stupid. They go really slowly up from zero because they don't want to hurt you. But you're obviously getting harmed by not having the right drug the entire way through. So what you do what you should be doing is doing binary search, but obviously you can't just do binary search and like give the guy like a lethal dose of the drug and kill them, right? So the idea is you need to find like some optimal algorithm to skewed binary search. It's a skewed binary search. So I went to go and like create a grid search over this whole thing. And I started writing my code in Python. And I had heard that Q was this amazing, really fast programming language, and I learned enough Q to implement the language and have the solution finished before my Python code finished running, and I was like, okay, I'm hooked.

Conor

Oh wait, so it was running in Python. It was still running in Python. And then you learned enough and coded up, and then it was done while your Python solution was still running. Damn.

Phineas Porter

Also, Python was very slow back then. This is like Python 2.7. You know what?

Bryce

Python is still very slow.

Conor

I got the Shannon plan though. For those that know, they know. You know, if you know, you know.

Bryce

What is the uh what is the canonical solution to the two eggs?

Conor

Wait, you gotta have you gotta have the mic there.

Bryce

What is the canonical solution to the two eggs problem?

Phineas Porter

Uh you you you basically exponentially go up the floor, so you go start from start from the first floor, then go to two, go to four, go all the way up until the first egg drops, and then go back to the first floor that the egg didn't drop, and then just walk up one floor at a time until you're both eggs are gone. I mean the that you can see why that would not be very welcome to hospitals. You have like two patients are dead now. Start with one one one barely living patient.

Conor

Okay. And for the record, I I mean uh are the doctors worried about hurting patients or are they just worried about getting sued? You know, uh do we really know? We don't know.

Bryce

I don't I didn't understand the better solution to to this, like like to the dosing problem. Like, what's the better solution? I'm I I wasn't clear on that.

Phineas Porter

So so just the better solution is like depending on the cost of like overshooting, and it's gonna vary, but like you can think of it as proportional to the error that you overdose by. So like like by proportional, I mean like it, like it might be some function of the of the error between the true value, like suppose you're supposed to give the the the patient like 10 milligrams of something, and you give them 15, that five is like the error, and you some function of five is like the is the issue. And like it might be like some crazy function where it's like exponential, right? The idea is that cost is gonna be factored into your binary search so that instead of picking the the absolute median between the two ex the two values you're looking at, you're gonna pick like a quarter or or a ha like or a f and go to the twenty-five percent or ten percent and so on.

Bryce

But but it for something like like over somebody like isn't there like a step function to that cost? Because there's like the step function of like, oh, they're alive versus they're dead. Yeah.

Phineas Porter

So the the the the way that you could probably you approximate this is basically with some like with some exponential you can you can approximate it with some exponential cost function. So basically, like as the error grows larger, you just like it goes to your cost goes to effectively to infinity. But that's that's kind of how you model it.

Conor

Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day.

Bryce

Low quality, high quality, that is the tagline of our podcast.

Conor

That's not the tagline. Our tagline is chaos with sprinkles of information.