Algorithms + Data Structures = Programs - Episode 76: C++ Algorithms & Point Free Programming with Ben Deane (Part 2)

Episode Date: May 6, 2022

In this episode, Bryce and Conor continue their conversation with Ben Deane about C++ Algorithms!About the Guest:For Ben Deane, C++ wasn’t even among the first 10 languages that he learned on his programming journey, but it’s been the one that has paid the bills for the last 20-odd years. He spent most of that time in the games industry; many of the games he worked on used to be fondly remembered but now he’s accepted that they are probably mostly forgotten. These days he works in the finance industry writing high-frequency trading platforms in the most modern C++ that compilers can support.In his spare time he watches a lot of YouTube’s educational sector, practices the Japanese art of tsundoku, reads about the history of programming, avoids doing DIY, and surprises his wife by waking in the middle of the night yelling, “of course, it’s a monad!” before going back to sleep and dreaming of algorithms.Date Recorded: 2022-04-19Date Released: 2022-05-06ADSP Episode 72: C++ Algorithm Family Feud!ADSP Episode 75: C++ Algorithms with Ben Deane (Part 1)Felipe TweetC++Now 2017: Ben Deane & Jason Turner “constexpr ALL the things!”C++ std::accumulateC++ std::reduceC++ std::transform reduceTyler Weaver TweetC++ std::sortC++ std::partial_sortC++ std::nth_elementC++ std::partition_copyC++ std::minmax_elementDouglas McIlroyLambdaConf 2015 - Haskell Nuggets Power Series Brought to Life Doug McIlroyA Killer Adversary for Quicksort by Doug McIlroyProgramming Languages Virtual MeetupSeven Languages in Seven Weeks by Bruce TatePointfree.ioScala Programming LanguageHaskell allHaskell anyHaskell .C++ std::all_ofTo Mock a Mockingbird“Point-Free or Die: Tacit Programming in Haskell and Beyond” by Amar ShahHaskell Curry

Point free. Should we? I mean, I didn't delete it. We'll actually take before we get to the profiling. Let's take this. We're going to take a small interlude here. Welcome to ADSP, the podcast episode, recorded on April 19th, 2022. My name is Connor, and today with my co-host Bryce, we continue Part 2 of our four-part interview with Ben Dean on C++ algorithms.

One of the things, too, that in going over both the blog that I still have not gone back to find that individual's name, but if you're listening, your name will come up in either this episode or part two of this episode. What blog is this? Actually, we can just go find it right now. Because that's great podcasting, serving the internet live. Here we go. Felipe, I wrote the solutions you guys discussed in this episode.

I'd appreciate it if you could have a look at the reduce slash transform, reduce. And let me know if this is what you had in mind. Love the episode. So thank you, Felipe. I responded. And yeah, it looked good. I only perused it quickly. He was missing one of the function objects or lambdas called max two underscore accumulating. But other than that, it looked good. This podcast is now so big that people write commentary on the podcast. It's not that big uh i was talking to jason the other day at the denver c++ meetup and ours is uh not an order of magnitude smaller but we got a long way to go uh to call it big as being generous swag i need swag for c++ now do we have stickers do we have a logo no we put and here's the thing uh we one time got a request for uh transcripts um but we have to understand is we will get transcripts as soon

as some company offers uh to pay but it's not cheap to because like i do not have the bandwidth to uh go and you know have them automatically generated and then clean it up um and so the alternative is and i know bryce doesn't have the bandwidth either and then clean it up. And so the alternative is, and I know Bryce doesn't have the bandwidth either, and neither does Ben, and neither would he be interested in doing that. But so you have to- I did that once. I think it was the Conspect for All the Things talk

that Jason and I did. And I think that year there was a push to get transcripts. And Google, YouTube does automatic transcription and just gets it horrendously wrong when it comes to C++ keywords. Constexpr, you know, that's not a word that Google transcription software has heard of, at least not in 2017.

So that was an interesting fix-up. And so that's the thing. Bryce and I, we do really care a ton about accessibility. It's just that it is not, it's like they charge by the minute for transcribing that stuff. And, uh, so if there's some company out here that's listening, that's like, Hey, I want to support that. And they want to pay for that to get done. Boom. We're going to have transcripts, but I've already got like 16 things on the go. So it's, it's not that we don't care. It's that, uh, It's prohibitive to do.

Don't have the resources. Yeah. And also, too, like if I had the bandwidth, I definitely would. I just currently don't. But back to my question. At this point, we might be on part two of this podcast. Is that one of the things that really led me to prefer the reduced version or the accumulate version and something we didn't really touch on in the previous uh version is that uh or maybe i'll ask it i'll ask it in the form of a question an interview question i was trying to think of what game show i could do but i don't have the

energy to think of a game show and put it in the right format um sort partial sort nth element all have something in common that transform reduce and reduce and accumulate do not which makes me prefer those well sort at least requires random access iterators is that true the others uh not what i'm thinking of even if it is true it is i believe it is true of all of them that's a bold requirement to place upon so to repeat the repeat the question to the listener partial sort sort and nth element all are in one category reduce accumulate and transform reducer all in another category what's the difference that i'm thinking of there might be multiple yeah i am correct is it the header they're in algorithm versus numeric that actually while i was saying it that popped into my head and i think you're definitely correct

about that um also not what i'm thinking of this is a fundamental property of what the algorithm is something like they're not allowed to oh it's uh uh it's it's in place it modifies correct they're permuting algorithms right and that's actually something that i noticed when i was watching the tyler weaver video is the first thing he does is create a temporary because he's passing in by cons ref and he creates a temporary and just copies it for a lot of them. And for an algorithm where you're just pulling out the top two elements, that's kind of irritating that I'm going to have to permute my input vector or input range, if you will, because this is like one of the really nice things I like about reductions and transform reduces is that they're very functional in the sense that they're not modifying the input range.

And a lot of other algorithms, like anytime you reach for nth element, and there's not actually an equivalent nth element copy, which a lot of the times you wouldn't actually want this, at least in this case, you wouldn't want that second, as you always point out, Ben, that is it partition copy is one of the only algorithms that has two output iterators? It's the only algorithm in the standard that has two. And actually, we should talk more about that in a minute because I think it's overlooked. Yeah. And so if you had an nth element copy, which if there's a partition copy, seems like there should be an nth element copy. But there's a lot of those missing sort of prefix suffix algorithms. You could use nth element copy to not modify the input sequence, but then you're going to end up with a range of n minus two elements in, you know, that one of your iterators

pointing to that you don't need. And I think that's actually, I can screen share here in a bit if you want to look at the profiling that Tyler did is nth element is actually quite a bit slower than, so like I ended up writing my own, and transform, reduce, and accumulate were definitely the fastest. But nth element was slower than the max element, and then erasing a single value, and then doing another max element. And I think that probably has to do with the fact that you're permuting your input range. Anyways, thoughts? Well, one of the nice things about the non-destructive algorithms, in particular in the parallel case, is you can do multiple different things in parallel on the same dataset. Multiple things in parallel. If you have a read-only dataset, yeah.

That is true, yeah. I guess I don't really think... I always think like sort of data flow pipeline-y, but if you don't think that way and you just use it as sort of like an immutable source, then yeah, you can definitely... I mean, pipelines are just boring graphs, Connor. Just very boring graphs. You just need to think about more interesting graphs. Not when you introduce the phi combinator, Bryce.

Somebody has just completed their thesis. There was one more thought that as I was listening to your last, to this podcast about the algorithms and Bryce mentioned, I had the thought and Bryce mentioned it that

it's interesting to think about a kind of tricksy way to solve this with min-max element. Is that possible? You had the same and bryce mentioned it that um it's interesting to think about a kind of tricksy way to solve this with min max element is that possible you had the same thought damn man i'm being left out reminded me so i haven't worked through it i don't it is definitely tricky to do because it's it has to be adaptive in the comparator or something yeah um but it reminded me wait does min max element have an overload you can possibly compare it to it yeah really keep talking Ben

how would it be useful if you couldn't this is great I love learning stuff live on ADSP have you read the paper A Killer Adversary for Quicksort it's a paper by Doug McElroy he's who is the bashy unix guy he's often cited as the inventor of bash pipelining oh he is one of my heroes then because i love bash

yeah yeah he's he's a great guy um i was lucky enough to attend one of his talks at LambdaConf, I think it was 2015. He talked about... Oh, wow. He presented 12 lines of Haskell that were a complete framework for manipulating polynomials, including infinite sequences. And that was just beautiful. Anyway, highly recommended that that talk uh we'll link it in the show notes so definitely um he has this paper a killer adversary for quicksort which the the the tenet of the paper is um you know we all know that quicksort performs poorly on certain inputs it can go quadratic, right?

If the pivot selection is poor. And so he constructs a deliberately bad input for Quicksort that is constructed adaptively on the fly to bamboozle Quicksort's pivot selection. Okay. And it's that kind of adaptive nature that, I mean, that's what it made me think of that when I thought about this potential min-max element solution to top two. Because again, it would have to be adaptive in the comparator somehow.

Yeah, and I brought up the min-max element page. It definitely, not that I doubt you, I just had to confirm, because I think I said actually on that episode that min-max element didn't have an overload version that takes a custom comparator, which I apologize to both Bryce and the listener, that is entirely incorrect.

I will consider accepting your apology but i appreciate that that's a true friendship right there considering accepting yeah well i mean that's actually that's pretty big uh for a big step from bryce he's from he's a he's a new yorker you know uh he's lucky he didn't just right then and there say you you know what, I'm done with this podcast. I am an aggressive megalomaniac, so that is pretty big of me. I appreciate Bryce's self-awareness. It's just that if he wasn't self-aware, I'd just say, this guy is a little bit, but he acknowledges it, so it's all good. It is important to own one's bullshit.

So, yeah, maybe I'm sort of curious. I won't be surprised at this point because we've basically had a blog slash one blog and one YouTube video. So maybe there's a listener that's going to go and create another blog. Can we look at the benchmarks live in large part because I suspect I will find reasons to object to them. Yeah, let's do it. And this will be an instructive episode in how to produce good benchmarks, or at the very least, benchmarks that pass muster with me. Yeah, so maybe this will, I'm not actually sure if this is the start of part three or

part two, but definitely this is a great, we're talking about profiling now. Let me share my screen. And the listener is actually able to go, we'll link this in the show notes and check out. Oh, man. Actually, you guys are seeing Twitter? At the top of whatever part. We're seeing Audacity. What the heck?

Stop sharing. Audacity is the name of the software that we use to record the episodes. Why does it keep on giving you... We're seeing more Audacity. Oh, yeah. That makes sense. Connor, just share your full screen. I've got two monitors. You have nothing to hide from us.

I am sharing my full screen, but I just can't share both monitors. Wait, that means we've got to look for anything embarrassing in the tabs. No, that's not going to happen. Point free. I mean, I didn't delete it. We'll actually take, before we get to the profiling let's take us we're going to take a small interlude here ben i was going to suggest

also put on the stack the algorithm you talked about from the meetup last night forget it was the uh oh yeah yeah the um yeah what's closest to zero and choose the largest of the two. All right. So we've got three things on the stack at the, what we're going to talk about for a second here is point free.io and a future YouTube video. Cause I got, I got so excited last night and then derailed my meetup for like a good, I said I wasn't going to talk about it for 20 minutes.

And then I proceeded to talk about it for 15 minutes and had to like literally cut myself off because i was i was so excited about it this is what makes the meetup great i mean i felt it i was it was a little too i really sort of i felt like it derailed a little bit too quickly because i'm not sure how many people were following along but i was so i was so excited about it people don't always follow where you're going, but they're excited to be on the journey because of how excited you are. Yeah. So, all right. On the stack, point free is next. Then we're going to look at some profiling from Tyler, and then we're going to talk about an algorithm we discussed last night.

So, I'm confused about your stack because you seem to have inserted it at both ends of the stack. This is true. All right, Q, whatever. It's a stack because we're going to pop off in one direction. That's not what makes a stack. It's a heap. It's a heap. Things have been pushed on by priority and they're going to be popped off in another way.

Exactly. So for context, I have a programming virtual meetup um ben attends from time to time and i think you've been there for most of the uh seven languages in seven weeks and we were covering chapter five and programming language four of seven last night which was scala and one of the problems in the chapter was to write a little tic-tac-toe status function that, given a board that is partially filled out, determine if there's a winner and if it's an X or an O or if there's no winner. And without going into too many details, at one point, there's a function that I used

in my solution for both a Scala solution and a Haskell solution of a function called all equal to that takes a solution and a Haskell solution of a function called all equal to that takes a character and a string. And it basically just determines is the string, are all the characters in that string equal to the character that you specified? So if you're given all equal to the character x and xxx, it'll return true. And if it's xox or x.x it'll return false and in haskell i had programmed that by basically all equal to uh with a single parameter e for the character and then equals and dot map parentheses equal equal e and parentheses should we be spelling this out for the listener great This is great radio.

Yeah, great radio. And you don't really need to follow it or like be spelling it out in your head. But we went to this site, pointfree.io, because I was like, I said just sort of off the cuff during the meetup, you could make this point free, but it probably wouldn't be as readable. Because basically what you're doing

is you're mapping a unary function over your string and converting that to a string of booleans that's true if it's equal to your specified character and false if not. And then once you have that list of booleans, you just do a logical and reduction. And if they're all equal to true, you get a true back. If any one of them is equal to false, you get false back. And so that's basically, you could do this with a transform reduce in C++ where you're transforming your characters and your string to Booleans and then doing a logical and reduction. So we plug this into pointfree.io and what we get back, it changes the and, which is our logical and reduction to all, which is is the equivalent of stood all of in C++, and basically takes a list of Booleans.

All takes a list of anything and a unary predicate that's going to evaluate that list of things and turn it into a list of Booleans. And so it turns and into all, keeps the dot, which is the B combinator, the bluebird. Everybody loves the blue bird. And then drops the map and it turns the unary operation into a binary operation. And I'm not even going to really try to begin to explain what happened there. But basically, the B combinator, it's, I mean, do I even attempt, Ben? Do you want to try? It's just, I'll make a YouTube video and maybe

people will understand but I was so excited Jean-Michel who's an attendee he pointed out I was like oh I think I understand what's going on I didn't even notice at first that the and changed to an all this website is pure magic uh Ben do you have anything to add uh I would just say for listen the point of the website is it's called point three because it it changes functions to the point of the function is the argument of the function or the parameter to the function right and so it removes function parameters in favor of plain function composition hence point three so and instead like the c++ analogy instead of having a you know sequence of calls to algorithms where the inputs are explicitly named, having a pipeline of range adapters that can be applied to any input

where the input sequence is an implicit impasse between all of them. Or the other analogy is like, you know, a bash pipeline, where you don't explicitly name, you know, stood in, it's just implicitly passed from thing to thing. Yeah, Eric Niebler was the first one that point because I think at some point, I remarked in a meeting or in a conversation, he was a part of that I said, Oh, C++ doesn't have support for point free. And he said, Oh said that's not actually true if you are building up a custom range adapter that is the composition of you know a transform and a filter and something else um that's technically point free because you never mention your arguments um which i was like oh yeah that's a good point um or at the

very least you you never mention your primary argument in a lot of cases there you might have an argument of a functor or some other parameter to one of those functions but but not the actual input sequence yeah not not the argument that will be required for basically the the callable that is returned um yeah and yeah and maybe well we're probably not going to have time to to get into all these things but yeah i've been thinking a lot about higher order functions these days. Well, I was going to say, you made the observation here, Conor. So the dot operator is the bluebird combinator, right?

Function composition. Yep. And you come at this code very much in a combinator mindset, where, at least you said last night, you think about combinators. And the way you think about combinators and the way you think about combinators, you know, you can tell me I'm wrong, but you think of them as functions of one argument. Well, in particular, I guess the Bluebird Combinator

combines together two functions of one argument, right? And looking at this Haskell 0.3 version is not obvious from that mindset because, of course, the equality operator is a binary operator. It's not a function of one argument. It's a function of two arguments. And indeed, all is a function of two arguments as well. And so at first glance, in that mindset,

it looks like how is dot working to combine these two functions because they're not functions of one argument? Except, of course, that in Haskellkell every function is a function of one argument which can then return a function as opposed to returning the eventual results because of partial application being built into the language yep that's and that's that's like a very even to this day i have to like when i start thinking about this stuff like I have to sit down and start. I think like at some point I'm going to have to go and implement a mini, it doesn't have to be Haskell, but basically a language that has currying built in because it is, it's a very different model. Like you said, right in this code, all dot, you know, paren, equal, equal paren. That's the B combinator, which composes two unary functions sitting between. So

it's an infix operator. It sits between two binary functions. So two functions that take two arguments. Right. And somehow it works. And somehow it works. It's very, even like the Blackbird, the B1 combinator, one of my favorite combinators. We talked about it in a previous episode where that combines a unary function and a binary function there's a definition of that where basically three beat combinators in a row three bluebirds in a row equals the blackbird and like i have no idea like i have not sit down to like work through the eta reduction or whatever you whatever technique you use but like i've seen that in a talk and a couple other blogs and like i'm just'm just like, I don't even like BBB. I do not understand how that equals B1.

But like, that's the whole, I mean, Haskell Curry's very first paper on the topic in 1929 was entitled An Analysis of Logical Substitution. And before he had named it combinatory logic, like that's how he approached it. Like programming languages weren't even a thing back then pre, you know, 30s or 40s. And it was, it was substituting it was substituting one expression for another expression based on these sort of relationships. And yeah, you are definitely correct that I come at it from a very specific mindset.

That's primarily of how they're used in APL. And then I've been sort of reverse engineering my way into these other sets or know or contexts of haskell and i came to haskell first before combinators so i think about this just in terms of how the types unify and check pretty much interesting and it's interesting because technically i i landed at haskell first but didn't really appreciate what the dot did or really what the dollar sign did. I just sort of knew that if I stuck them in different places, then it would work. And so, yeah, even though I saw them first in Haskell, I didn't really appreciate what they were until coming back from Array Languages.

Well, it's spring. It's a good time to study combinators. I would say I currently have two combinators living outside my front door. I have two finches made a nest in my wreath. And for the last month, I have not been using my front door as a result. They laid, she laid five eggs, of which four hatched. And there are currently at least two baby birds that are still surviving oh you know it's it's sad that some die but that's nature for you that's why that's why she had that number i suppose but yes they're they're surviving and thriving as far as i can tell and the for the

f combinator is definitely a combinator. Ben, we're going to need some pictures. Yeah. To add to our show notes. I do have a picture. We don't disturb them very much, but I do have one picture. I assume that you had some pictures. And for the listener that hasn't heard the lore of raymond smullion's

tamaka mockingbird and why so a mathematician famous mathematician that um i think i probably heard about it from you ben um or maybe if i first heard about the book from that point free or die talk that was given by amar shah back in like strange loop 2016. But then you mentioned Raymond Smolian and had told me that he was a very well-known and prolific writer of sort of logic puzzle books and math puzzle books. And he wrote this book in 1985 called Tamaka Mockingbird, where he nicknamed all the combinators. And the reason he gave them bird nicknames is because very famously or not so famously, because I only learned this from reading, um, Tamaka Mockingbird is that Haskell Curry, who was, you know, basically did all of the research that led to the, the field of combinatory logic. He was a huge avid birdwatcher and that's why it was

basically an homage to him. And, and the funny thing is, is I was at lunch the other day and I'm pretty sure I saw a warbler because i actually through like investigating combinators and spending so much time researching them and tweeting out photos i actually am starting to recognize types of birds and i like i fell off my chair and like ran outside the restaurant to try and get a photo of this warbler because i was like a warbler in the wild that's the w combinators one of the best connor's gonna become a bird watcher connor's gonna become like a bird man he's gonna have like a collection of birds that he cares for this week what may be useful i just heard about this app that's out of um cornell merlin mer? Merlin bird ID? Yeah.

Yeah, it's like you just record some audio and then it tells you what it is. But apparently they're doing amazing things identifying birds. About 10 years ago, my dad, who's a bird watcher, had that idea for an app. And he was like, can this be made? And I'm like, like I'm sure it can be but I'm not the person to make it alright moving on to unless do we have anything we want to say about point free tacit programming before we move on to the profiling because Bryce is

I'm fading fast it's approaching my bedtime I don't know how you're still alive given that you exercised more than me today. I'm wired. I'm wired. We mean, we're talking about birds, combinators. The crash hasn't happened yet.

It's coming. It's coming. I mean, you also have a way earlier bedtime than me. I typically go to sleep at midnight. No, my bedtime has been disrupted the entire winter. Not entirely because of winter, but because of my very active social life. Bring up the profiling. Make Bryce nice and angry so he stays awake.

There are things wrong here, Bryce. Thanks for listening. We hope you enjoyed and have a great day.