Conor

I had no idea that it was rotates all the way down.

Sean Parent

And so if you think about it, how do you get a stable sort in place? Well, that's a quick sort with a stable partition. How do you do stable partition? That's just rotate called recursively. How do you do a rotate? That's just three reverses. How do you do reverses? That's just swap. And so we just built like some of the most complex algorithms in 20 seconds, right?

Ben

It's really beautiful. People should in general think about and there's multiple algorithms in that kind of sort hierarchy, right? So stable sort is at the top, then sort, then partition, and then element, yeah, there's a or partial sort might be in there, but there's a there's a range of power there, right? And we should be picking the least powerful thing to solve the problem in general. Yes.

Sean Parent

The fastest algorithm is usually the one with the with the fewest guarantees. People tend to use a shotgun where a scalpel would suffice.

Conor

Interesting. So we've got Std Rotate and GCD. They have an intertwined history. Although uh a good friend of mine on top of you has also, I think he tried to read EOP and was a C dev for a while, but now is mostly using Python. And uh he transitioned very quickly to mathematics, from mathematics to generic programming and said that it was a much easier read, but also like more thoroughly enjoyable because of the way that the content is uh given to the reader. Does that book cover the three different implementations of Rotate, or I'll have to just, you know, I I it should be, I don't know if I can make it a 2024 goal, but 2025 goal will be to get through all these videos, read EOP, and read from Mathematics to Generic Programming. Otherwise, you know, it's I can't have you know this happening again where I, at the end of an episode, um, and I'm apologizing for probably only, you know, 80% of what we should have been apologizing for. We didn't know how little we knew. I mean, Bryce has less of an excuse because he's purportedly read EOP. So I don't know, I don't know, he dropped the ball there. Uh I can I can admit more ignorance and say, ashamedly that I haven't actually even finished it, so at least I didn't fail to recall it. Yeah. I'm not sure which is worse.

Ben

I mean, there was a time. There was a time when if you went to C now, the the first thing you would hear would be read elements of programming. That was the the first year I went to C now was 2014. That was where I first heard about Elements of Programming. The next year when I went back, I had read Elements of Programming, so I was ready for C ⁇ now. In a sense. Yep.

Sean Parent

I yeah, I think, well, I mean, since you guys talk a lot about STL algorithms, uh uh not always, but if you're if you're trying to to research one of the STL algorithms where where it's it's one of the the ones that came out of the Stepanov library, right? Stepanov and Lee. Check EOP first. If it isn't there, go to Stepanov Papers, and there's uh, oh I can find the exact links for you. There's a a couple of near books, I think. One of them is called Notes on Programming, and one is called Programming as Mathematics. Uh those were drafts of what eventually became EOP. They're in some ways more approachable, they're more algorithmic-centered, uh uh less less math, uh, even a little less philosophical.

Conor

When you say notes on programming, are you because I'm pretty sure, uh, at least when you you say that, I think of the 88-page PDF uh that is uh written or the language used in it. I'm not sure if there's multiple, but one of them for sure is Scheme. Is this the same thing you're thinking of? Because there's a chance then, if that was a starting point for EOP, maybe EOP all this time, and I it's my fault for not having fully read it, maybe it mentions APL because famously the notes on programming that I'm thinking of implements Reduce and I think all the other algorithms in Scheme, and it mentions that was the first time I had heard a reference to the fact that uh Stepanov borrowed the name Reduce from APL and basically said that's where he first um saw that algorithm.

Sean Parent

Yeah, let me see.

Conor

Links, of course, dear listener, will be in the show notes. I also sadly, even though I have referenced in both podcasts and talks the notes on programming, uh have not fully read that 88-page PDF. Uh I have read through some of it.

Sean Parent

Right. So if you go to stepanoffpapers.com, and then uh the the two things I'm referring to are under class notes and videos, there's a section that says incomplete notes for the foundation of programming course taught at Adobe, May 2004. Um, and there's a PDF for that. And if you open that PDF, it's uh uh the title of it is Foundations of Programming, I think volume one, linear structures. And so that was the start of what was going to become EOP. And then Alex was having uh a difficult time kind of completing that that work, partially because he just is somebody who goes off on a lot of tangents. And so Matt Marcus jumped in to help. And so if you look, the next thing on the page is uh Stepanov and Matt Marcus, Notes for the Foundations of Programming Course 2004-2005, and it's split into three sections: mathematical preliminaries, generic programming, and the partition algorithm. And those three sections uh form the complete draft of a book. Okay, so so we we had had finished the draft of the book. And there were a number of things that Alex wasn't happy about. Alex and Matt got into uh a bit of an argument over the direction and how things should be shaken out, and Alex actually pulled out of the effort and said he was gonna go do it himself. And and so he started again, page one, uh rewrite. And soon after he started, Paul McJones joined him, and so it was that effort that led to EOP. But the the notes for the foundations of programming and Alex's notes before that uh cover most of the algorithms that are in in the classic STL in in a fair amount of detail with all the proper references, right? It's not like you know Alex invented this stuff. There's there's very little in STL that's that's that's new. It's it's collecting other people's work and putting it into a generic form. It's the generic aspect that's the new aspect of it.

Ben

Well, uh so I actually I want I want to ask you is so uh stable sort is uh new, right? Stable sort uh in Knuth edition two was uh listed as a research problem, I believe. Yeah. At least the problem that took uh yeah, in-place stable sort.

Sean Parent

Yeah, in in in situ stable sort is is Alex's big algorithmic contribution there. And that's um in older versions of the art of computer programming, which is Knuth's book, uh uh it was listed as an exercise, and the exercises have a difficulty problem. And I forget what the scale is, it's like like five or something is is basically it's a Knuth scale.

Ben

Uh M50 is ringing a bell for some reason. I think that's like the take a grad student and give them a couple of years to solve it.

Sean Parent

Yes. So it's basically an exercise with no known solution. And um stable partition in in STL is uh is an in-place solution and depends on rotate. So it's really quite amazingly trivial once you understand, which is uh, you know, if you want to do a stable partition for the reader, what that means is you've got some predicate uh that's gonna return true or false, and you want to reorder your sequence so that all the true guys are first and then all the false guys are follow. But the relative order of everything in the true bucket and everything in the false bucket uh uh doesn't change. And you want to do that in place uh with some reasonable complexity. And so the algorithm is is well, if you imagine somehow magically, uh what if our sequence was stable partitioned on half and the other half was stable partitioned just somehow magically, and I wanted to combine those so that the whole was stable partitioned. Well, what you want to do is you want to take the two adjoining parts in the middle and rotate them. And now the whole is stable partitioned. And so then you can just keep recursively dividing each half until you get down to just one element. Uh in which case, how do you how do you stable partition one element? Well, you need to you're just returning the partition point, which is you're just gonna return whether or not it satisfies the predicate plus its place.

Ben

Yeah.

Sean Parent

Effectively. Right, right, plus its address. So so that's trivial. Once you recurse all the way down, now you can build it back up by just rotating. Okay, and that gives you a uh an n log n uh uh complexity algorithm for doing an in-situ stable partition. And so, you know, an in-situ stable partition gives you an in-situ stable sort. And so if you think about it, how do you get a stable sort in place? Well, that's a quick sort with a stable partition. How do you do stable partition? That's just rotate called recursively. How do you do a rotate? That's just three reverses. How do you do reverses? That's just swap. And so so we just built like some of the most complex algorithms in 20 seconds, right?

Ben

It's really beautiful. And people say that the STL algorithms are not composable. Yeah, they're incredibly composable.

Sean Parent

So so, in fact, like almost every algorithm that's in the original STL, the reason why it's there is because it was a building block for s for stable sort. So that's it.

Conor

Uh that's that's the beauty. I had no idea that it was rotates all the way down. In the back of my head now, I've been thinking where it's almost unfathomable that I've made such a big deal. At one point, I actually wanted to get a the APL rotate symbol uh as a tattoo. And then I had this whole plan to like reveal it during a talk. Anyways, I have a a very, very soft place in my heart for the rotate algorithm because I feel like it that was like watching that talk however many years ago, you know, almost it's like you have these inflection points in your career, and uh that was like a big one. And now here we are, four years later, episode you know, 202 of this podcast where rotate has come up this many times. And I feel like we only on this podcast have touched like the tip of the rotate iceberg, but not only just on this podcast, like also in the conference like circuits. Like there is this beautiful talk that I may give in the future, and maybe someone else will beat me to it, that is just titled Stood colon colon rotate, that like talks about like these implementations and talks about elements of programming. Unless if maybe in the hundred hours of content of the four algorithmic journeys, these algorithms are talked about. Because like similar to your C seasoning talk, Sean, where you have those beautiful animations uh building up to what you ended up calling gather, you could show basically the exact same kind of animations talking about the rotate algorithm, but I have in the thousand plus talks I've watched in the last N years, I've never seen that in any not not just C, but there's also some Swift talks out there by Dave Abrahams and uh Doug Greger and other talks in different languages, I've never seen anything touches on this. So, yeah, what's going on? How come this talk doesn't exist? Or maybe it doesn't, it just hasn't come across my radar.

Sean Parent

I don't know one quite like that that exists, but yeah, I think if you did like title a talk stood rotate, and you can get into kind of the algorithmic beauty and then the uses, both the uses inside of STL and things like uh slide and then gather.

Conor

Ben's example of picking up one element and putting it somewhere else. Actually, when you said when you said that, I was like, that's not a rotate, and I was like, oh no, that is a one rotate just on you know some.

Ben

This is overwhelmingly the the most common use case I've ever seen for rotate. Yeah. People do this all the time. Yeah. Arbitrarily rotating blocks of uh or ranges, that's a useful building block. But but in application code, 90% of the time you want to take this element and put it somewhere else.

Conor

Yeah. I'm not sure that a rotate lies behind that animation, but any time I can think in like a multiple um apps on my phone where you'll have a basically some form of a playlist or some form of a list, and then you have like a hamburger thing that you can touch and like drag the UI thing, even if there's no rotate in the code behind the scenes, because you're actually doing a little bit more, right? As soon as you touch it, uh I guess technically you're just doing repeated one rotates on two elements, but you can drag it up and down, and that is effectively at the end of the day, if if you're not showing that animation. That's uh that's a one rotate on on that sequence whenever you're doing that kind of and I think that's simple. I mean, that's that's not that far removed from the gather example that Sean shows, where I think you kind of talk about what if you're in like an email inbox or something like that, and you you select two things, and or I can't remember if that was your exact example, but it is something to do with that.

Sean Parent

Well, my exact example, I was working on Chrome OS and and and I was doing my very first code review at Google, and uh somebody made a change so that you could Chrome OS has a view where you could could like see all of your windows as kind of these little slices on your screen, and you could reorder your windows. And you could only drag one, right? You could drag one and put it in. And that's the code that I was reviewing. And the code, I I show all the code in my talk. Um uh it's this morass of loops, right? It's it's like this 1800-line function or something like that that's doing all of these loops. And you know, a bunch of them are conditionalized, like, oh well, in this case we do this loop, in that case we do this loop, in this other case we do this other loop. And I was like, whenever I do code review, the first thing I look at is what are the loops? What in the world are these things doing? Right? And I tear through it, and they're doing a one-rotate, and they're doing it by erasing the one element and then erasing the next element and and reinserting it into the new slot. So it's like this quadratic erase and assert mess. Okay. And so it's it's really slow. And and the only other piece of it was you needed to find the position, right? You user clicks somewhere, you need to find the position. And and so I went went and said, okay, like the start of this is a find if followed by rotate. And if you read all of the rest of it, it's it's basically just another rotate, which is which is what gather is, because you're rotating, depending on which way you're moving, you're rotating one one direction or the other, right? It's the same three arguments, just a different permutation of the same three arguments. So I'm like, I'm like, this is just you know, find if rotate. That's all that's happening here. And and that had led to a big argument, and I finally convinced the uh uh uh the author of the code that that yes, that's what his code was actually doing. I mean, the first thing was he's like, no, that's not at all. You don't understand my code, right? My code is doing way more than that. And I'm like, it's doing that, right? It's doing a lot more work to do that, but right, right. So I finally convinced the author, but then it was still rejected from the code review because my mentor, who was overseeing the since it was my first code review, uh uh uh said that it was too tricky and nobody knew what rotate did. And because of that, that code landed in the Chromium open sourced effort, because Chrome OS is open sourced under under Chromium, and that's why I was able to put the code in my slides. Okay? Nice. So that's kind of the the the the whole arc. And my point there is that once you realize once you realize that that's a one rotate, then if you want to do multiple selection and select a range, that's still just a rotate. And if you want to do a disjoint selection, it's stable partition. But stable partition is just recursive rotate. Right? So once you realize what you're doing is a rotate, you can now do multiple selections in your UI. Okay? Trivially.

Ben

Yeah, because it's all built from the same stuff.

Sean Parent

Because it's all built from the same stuff. If your code though is is looking like like, well, if it's at this position, then I'm gonna erase this guy and insert these guys, and and otherwise I'm gonna erase this guy and insert those guys. If that's how your code's written, first you're gonna go horribly quadratic as you try to extend it to more to more elements, uh, but you're also never gonna figure it out. The complexity gets too high to think about it in those terms. So my pet peeve right now is is applications that don't support multiple select. Or if they do support multiple select, don't let me drag the selection around. Right? Drives me insane. Uh uh and it's ubiquitous.

Conor

So Alright, I know we only have a couple minutes left because we we have a hard stop and we have to let you go, Sean. But maybe in the last couple minutes, a final question, and it might be hard to answer now, so if there's no answer, maybe we can all just think about it and uh see if we can come up for answers next time. I just in the last 60 minutes, just during this recording, realized that the one rotate is actually like the the most common use case of a rotate that's like lying in plain sight, but before but until you someone says it or you notice it, I do kind of like, you know, I have a soft spot in my heart, like I said, for for rotate, but you do kind of think of this like, oh, whoever you needs like a four rotate, it doesn't come up that often. But a one rotate, when you think about it from like what's what is that doing, that comes up all the time. Are there other either STL algorithms or algorithms outside of the STL that have these obvious like in plain sight use cases that you know might I might be missing or folks might be missing? Because like I think std sort, you know, algorithms like that, it's obvious what you use those for. But uh potential I'm guessing that there are these other kind of uses in plain sight that until you see it, you might miss. Do you have any of those off the top of your head?

Sean Parent

Or yeah, I think you know, my my other favorite algorithm that gets missed a lot is nth element. I was gonna say the same thing. Least appreciated, the most underappreciated algorithm ever. Yes. So nth element, I mean, it it will give you a median, it will give you, you know, so it's very useful if you're trying to gather statistics on things.

Ben

It'll give you unsorted top n elements.

Sean Parent

Yeah, if you need the top n elements out of something, uh uh, or not just the top n, if you need a window of things. You need things. Right. You need elements 30 to 50 out of a sequence of a million. How do you get that without sorting the whole sequence? So, nth element is gonna is gonna be a piece of that, of that answer. It it also partitions, it leaves your sequence partitioned. And and so that's a very useful property that can be exploited. And so if you're trying to gather a range of statistics, like if you're in graphics and you want the, you don't just want the median, you want like like what's at the the the 10% mark, the the 40% mark, the 50%, the 90%, right? Right, you want to sample a set across of ranges, you can do that by by starting at the nth element for whatever element is roughly in the middle, and then recursively partitioning, yeah, with nth elements. And you can gather a uh a set of statistics uh very quickly from uh from a large sequence of numbers. So it it it comes up a lot. It's it's one of the the most underutilized, and a lot of times where I see people sort, it's like, uh, you didn't need to sort, you know. You you you just needed to end that right.

Ben

Yeah, people should in general think about and there's multiple algorithms in that kind of sort hierarchy, right? So stable sort is at the top, then sort and partition, then element, you know, there's a or partial sort might be in there, but there's a there's a range of power there, right? And we should be picking the least powerful thing to solve the problem in general.

Sean Parent

Yes. The fastest algorithm is usually the one with the with the fewest guarantees. And so so think about what problem you actually need solved and then select accordingly. And uh, you know, it's just like the number of times I see people reach for a map when sort and lower bound would have been the obvious better choice. People tend to use a shotgun where a scalpel would suffice.

Conor

Wow, this has been absolutely phenomenal. We'll do this again at some point, because this was amazing. Uh, links for everything we mentioned in the show notes, and I know, Sean, we have to let you run. So we'll say thank you and until next time, and to my new co-host as well, Ben.

Ben

Yeah.

Conor

Thank you, Sean. Hey, thank you both. 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. I am the anti price. Um