Algorithms + Data Structures = Programs - Episode 215: C++ vs BQN (AoC Part 2)

Episode Date: January 3, 2025

In this episode, Conor and Ben chat about solving advent of code problems in C++ and BQN.Link to Episode 215 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)SocialsADSP: The Podcast: TwitterConor Hoekstra: Twitter | BlueSky | MastodonBen Deane: Twitter | BlueSkyShow NotesDate Generated: 2024-12-16Date Released: 2025-01-03Advent of Code 2024AoC 2024 Day 5Ben's C++ SolutionConor's BQN SolutionConor's AoC Video PlaylistBQNC++ std::multimapC++20 std::ranges::is_sortedC++20 std::ranges::sortAlgorithms as a Tool of Thought // Conor Hoekstra // APL Seeds '21C++23 std::views::enumeratePython enumerateScala zipWithIndexComposition Intuition II - Conor Hoekstra - CppNorth 2024Intro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

You make a multi-map that is your sort function, and then you call isSorted, and then you call sort, right? There are only three ideas there. And the number of ideas in the problem is how I measure the triviality in a sense. It feels like the things that I love about C++ and Haskell are just everything is there in BQn like and more welcome to adsp the podcast episode 215 recorded on december 16th 2024 my name is connor and today with my co-host Ben we continue part two of our chat comparing different approaches to solving Avent of Code problems. In today's discussion we talk about C++, BQN and more. So the question behind this observation is like what is BQN for in your opinion? What is it good at? What does it solve well?

And what is its typical application? I mean, I think BQN is amazing for everything. I understand you love array languages, but I hope you can see where I'm coming from. It's not great for memoization it's not great for when you have to put a big for loop and handle state in your code it doesn't seem naturally suited those things it seems great for reducing data structures summing them up you know scanning them doing all that stuff it seems algorithmically you can put all those things together really easily um but when it comes to some of this other stuff it it seems clunky i don't know i mean i the more i will say that

over the last year like one of my goals this year was to one of my criticisms on my youtube channel is that i just do one-liners which that's valid that's valid if you look at the corpus of code that i've written the majority of it is leet code, these small challenges, because that's fun. And with a limited set of knowledge, you can actually just go pretty far. actual language for writing substantial pieces of applications of software and now i've written you know all of these programs are you know 100 lines of code or less but that's still a dense amount of bqn code and so i've written a linter a formatter a unit tester all in bqn and the language definitely has its limitations there's no metaprogramming capabilities and so i do some hacky things to get like a pi test kind of unit testing framework i'm doing some things that are you know don't feel great coming from languages that have these

these meta programming capabilities that being said it is it feels like the things that i love about c++ and haskell are just everything is there in bqN, like and more. And the way that I feel writing BQN code, it's just like, it's painful almost to go to any language now. In general, there are definitely things that other programming languages have that BQN doesn't, but I don't think it is a limitation of the array paradigm. It's just that bqn is not a language that has a metaprogramming facility you could design an array language that has one right it doesn't exist right now and it's in the back of your head thinking you know what are the small things that are missing that are made so much easier and i think metaprogramming is probably like the biggest one

which is what led to your ability to do the decorator thing and memoizing functions in Python. Right, right. I mean, understand, I am not trying to level particular criticism at BQN. I'm not trying to do down BQN or APL or any other array language. I think I am coming, have come to recognize, like 40, 50 years ago, like if we wind the clock back, if we think about programming in the early 70s, mid 70s, even late 60s, in those days, there were hundreds of programming languages around, right? And they were, many of them were not what we would think of today as general purpose. They were designed for certain application scenarios. You know, you wouldn't use a numerical language for string processing and vice versa, for instance. Right. You had things like Fortran.

You had Snowball. You had, you know, literally hundreds of languages back um that many of which are now not in our consciousness anymore um you know we could name the half a dozen that have really survived but you know it's the same actually true today we don't tend to think that way today but but you know watching the things you do in bqn thinking about what's easy to do in python what's easy in haskell what's easy in C++. It seems to me like that might still be true today. Languages have

a particular fit for application domains. Okay, yeah. So I get closer to... I mean, I still maintain that... I think I can't remember when or where on some recording somewhere, I said that BQN has been my favorite language for a while

but the the gap that it is putting on other languages is like ever increasing and a part of the reason uh paradoxically is because my discovery of like i always knew that there was a system while um loop or like while higher order function technically is what it is it's not really a loop um or i guess it's both. But I never used to use that. And that meant that like for certain tasks, it becomes difficult to do it in BQN without that kind of thing. But now that it's there. Right. And I know I can reach for it.

Like there was a, I think one of the most recent problem that I did day 14. Part B is like find a Christmas tree in your input. And I'm like, what? What do you mean find a Christmas tree? It's just like it's like a grid. They give you no description of what it looks like or how to find it. And I made an educated guess and my educated guess. But basically, you just need to iterate on these little things moving around on your grid for this rules of like how these things move.

And that at a certain point, it just materializes a little picture of a tree. And that is like it's exactly what you need a while loop for like you don't need a reduction or a scan you need something that iterates conditionally that's a while loop like and uh and now that it's there i find myself reaching for it probably more than i should because that's one of the criticisms a couple folks have made of the videos is that sometimes there is an array solution that I ignore because the more intuitive thing to do, or at least for my brain is to reach for this kind of conditional exit. I mean, it sounds like, it sounds like what we're agreeing on is that, you know, when you start out learning a language, particularly one like BQN or like Haskell,

the language and the paradigm are very closely knit, right? And what you just said to me indicates that, you know, you're now sort of discovering, well, of course you knew, but, you know, you're doing different paradigms in BQN other than the array paradigm, right? Because the paradigm fits the problem better. Yeah. And I think that's what i'm discovering is that there was this set of things that bqn is just lights out better than any other language and i think that's

probably what you're asking more but what i'm realizing is that like not only is it amazing at that stuff but it can still do the other stuff let's talk about day five the the print ordering ordering the pages for print day five I think it was day five. Yes. Day five gives you page ordering rules, which are ordered pairs. You get a bunch of pairs of pages where, and the rule is that the first one must come before the second one. And so that's part one of the input. And then the second part is a bunch of lists of page numbers. And for the part A, you just have to say, are these numbers correctly ordered according to the rules?

Mm-hmm. Right? So I look at this puzzle. So I say, I haven't solved this puzzle. I have not coded up the solution. But the way I would do it in C++ is to recognize that the first part of the input defines your sort function, right? And then you just say, is sorted according to that function. The first part of the input is basically you would make a multi-map or something. And from that multi-map, you'd be able to answer the question, given any two numbers, are those numbers ordered? Is A less than B? And then you

would just call is sorted. And I think part two watched your video i've learned that part two you would call sort right according to the definition of the ordering which is given by the first part of the input so which is all to say that i think this problem in c++ is trivial or close to trivial it's like it's like you make a multi-map that is your sort function and then you call is sorted and then you call sort right there are only three ideas there and and the the the number of ideas in the problem is how i measure the triviality in the sentence i would well do i want to say disagree go ahead disagree with me my guess is that whatever the c++ code ends up looking like is is nothing compared to the elegance of what bqn gives you and bqn actually uh has a like i ended up once again looking at i think i solved it initially but then i ended up looking at other solutions like i always will try and

solve it myself and then i go and do like a code review because i think that's one of the best ways to learn is like sure you you might have solved it your way but seeing five or six other solutions from people that are experts in this language can lead you to some really nice things that you end up learning so i i do not doubt that the bqn solution is fewer characters by maybe one or two orders of magnitude right i'll give you two orders of magnitude on that one but i'm questioning like the the especially in a world perhaps where with an AI assistant in your editor, you can... My question to you is, is this changing things at all? If I could say to my editor, if the solution is...

To me, I haven't coded up the problem, but we've just talked through a solution. And to code it up would be just a matter of hitting the keys in my head. And so, in a sense, it's as trivial to write that in C++ as it is in BQM, unless you can convince me otherwise. Well, actually, so let's take a step back, because I'm not sure I fully have comprehended, because I probably haven't actually, I've been too BQM-brained. When you say your multimap is your comparator, what do you actually mean by that? Do you have to, I assume you mean, you do not mean I can pass my multimap as a binary operation.

Like, do I have to wrap this in a lambda to some extent, correct? I need to write a less than function, right? I need to answer the question, is A less than B? That's what will power the sort or is sorted absolutely to answer is a less than b i can look up a in my multi-map and see if see if b is one of its values right that or vice versa right because, the way the input is structured. So I checked this. In the sample, seven numbers occur in the list of pages, right? 21 pairs are given.

Yeah, it's complete. So seven choose two is 42, right? Seven ways to pick the first number, six ways to pick the remaining number. Half of 42 is 21 which is the number of rules we're given that is sufficient to determine because if you're given obviously a rule one way around it also applies the other way around for greater than so this was the question i had when i read through this is the input defining an order that we can use to power sort. And in fact, I believe it is. Yes. Because... Yeah.

So if I make that multi-map and I make it... Let's say I make it sort of both ways around, or my sort comparator looks both ways around, then that sort comparator is easy to write, right? I can answer the question, is A less than B, just by looking them up in the map. Okay. I fully understand now.

Yes. So there's several different ways you could do this. One of them, which would probably be the one that I would lean towards, is just, yeah, hand-rolling a lambda after populating this multi-map and then doing a call into that and you're done. Which is, I agree, quite simple. I mean, I don't want to get into the rich hickey complex versus complex etc etc but it's it's not a if you if you have in your tool

belt the multi-map uh is sorted the algorithms the data structures and the mechanisms that are how to spell a lambda it's a pretty trivial thing you said, you don't actually need to go. The fact that we've just explained this in a couple of minutes, talking at the level of like, here's the algorithms, here's the structure, here's how you write the sort comparator done. That indicates to me that this is simple, as you say.

Yeah. So I still would, I still think that the BQN solution, not the one that I initially coded up, but the one that I ended up with, it is like a superpower level above the C++ one. And I also think that, and this is more of like a philosophical territory of like the elegance and the number of keystrokes to spell like that solution in C++ affects what does it affect obviously the elegance of the solution but i think it also affects my ability to go and play with the solution it's like i said like i i coded this up one way and then went and looked at other solutions and then immediately

started like playing with my solution and modifying it the experience of doing that and this isn't to pick on c++ this is to pick on lots of languages it is sure it's almost like the it's it's that ability to play around with different solutions is non-existent like in a in a practical kind of like oh i'm doing this with an is sorted or assorted and now i gotta switch switch this out. I am just, maybe I'm not a good enough C++ developer, but I constantly am like spending time just trying to get the thing to compile versus like the malleability. And I think that's what's like,

there's other people that do a way better job of articulating like the, like it's like the freedom, it's similar to if you've read SICP and then you get up to chapter five and you're building the circular evaluator interpreter or whatever the thing is called. Metacircular evaluator.

Metacircular. Yes. Thank you. Uh, it's like you, at that point you're like, wow, I just kind of wrote the whole language. Like you feel like empowered. You can write lisp in lisp in like 25 lines or something. And it gives you a sense of like, you know else can i do like i can now bend the i wrote the language i can do whatever i want with it i can go add my own constructs and i feel like c++

fights you when you try to do this versus like array languages and in these simpler languages like lisp and haskell i shouldn't call them simpler but just like the the fact that there's so much stuff that comes in the prelude with Haskell and there's not namespace and the text of double colons. And it's just like you can't that that one talk that I gave algorithms as a tool of thought, not notation as a tool of thought. Was that like I can go and write 11 solutions in a grand total of like 30 characters to this one problem all equal. And I can't even. Right. It's going to take me a couple minutes just to get something compiling. And it's probably not going to compile on the first time. Is to say that like, I think the C++ solution is elegant for what C++ can do.

But like, it falls short of the power that you get with BQN. And the BQN solution, we haven't even talked about it. It uses this thing called like a table grade that when I saw it i was like oh my god that is that's like mind-blowing it's like these it's these things where you get the the uh uh inversion of uh indexes to get your histogram or you get these table grades it's like it's things that i don't i can't even begin to think like you would just you'd be hand rolling some bespoke thing in c++ anyways this is uh i feel like i'm picking on c++ is that it's fine i can i will defend it if you like i mean there's something in what you say i i accept that the there's something there which is the terseness of bqn uh does help your ability to very quickly play around with it right and like you say build a dozen solutions two dozen solutions in five ten

minutes and and try them all out um the question i have which i am unable to answer at the moment is like does having an llm assistant in your editor help with that in a language like c++ or python does does it narrow the playing field there i Python. Does it narrow the playing field there? I don't know. Does it narrow the playing field? That's a mixed metaphor. Does it narrow the gap? Does it level the playing field at all? I definitely think it does because whenever I program in Rust,

that is essentially what I'm doing. I'm asking an LLM, use iter tools. I want to fold a map, destructure this tuple. I can explain to it and it goes bum, bum, bum, bum, bum. And where I typically would hit a,

you need an unsigned I32 here, so you need an as, and you need a into iter instead of an iter here. All of those little bumps in the road, the LLM is going to nail because it's studied a corpus of correct Rust code out there. And me programming in Rust with an llm is like at least an order of magnitude if not more more productive right but the code that i still end up

with i am still like it doesn't doesn't touch doesn't touch the the nicety yeah the express the expressivity the terseness the just pure expression of the algorithmic ideas, I think. Yeah. And it's just like never in any language other than BQN, maybe Haskell a little bit. I'll run into like I wrote enumerate for all intents and purposes, which is, you know, just zipping with your corresponding index. Yeah. Yeah. It's called zip with index and

scala and it's called enumerate and python and i think it's in c++ 23 now yes fuse enumerate yeah yeah it's like four or five characters in bqn and i'm at the point where like i i saw it and i immediately read it understood it and was like wow this and it's tacit. It's a beautiful example of a tacit expression. Right. And it's half the length of the word. And like enumerate, maybe you can guess what that means if you've never seen it before. But like, it's not a bad name, but is it a name that like, I think zip with index, perfect name. You can, if you know what zip is, you can get your way to what zip with index is. But enumerate.

I mean, if you know what enumerate is, same argument. But what you're saying, I think, is that you have cultivated algorithmic intuition, right? That is a big part of, you know, in the process of learning APL and BQN and the real languages in general, I think your ability to translate word problems into algorithms has grown tenfold. Right. And at some level, the problem of C++ is just that its affordances are so bad for that kind of thing. Yeah. Right. Everything in the standard is named after what it literally does, pretty much, not what you would typically want to use it for

yeah yeah right like last time we talked to when we talked to sean like the prosichal for me is always like rotate right you look at rotate and yeah it rotates blocks of things but you totally don't come away with the idea that the most common thing you're going to want to do 99% of the time is rotate a block of one thing and reposition one element in your sequence. And that's a rotate. Like it's named for the general thing it does and not for the common use cases. And that's bridging that gap is cultivating algorithmic intuition. Yeah.

And that gap doesn't really exist in BQN or applicative language where you just, you know, put these things together. Yeah, I think that's what you're nailing the nail on the head. That doesn't sound like it's right. But anyway, it's hitting the nail on the head. Hitting the nail. I was right. I was using both the nail as the verb and the noun.

Hitting the nail on the head in that. I don't know what the analogy is, it's like you know colored belts in in uh you know jujitsu or it's some religious like ascension up the ranks but like i started in like c++ algorithm land then like elevated to haskell where things were like cleaner and simpler but like you know this intuition you can build you know the exact same there and then i discovered apl and i feel like it's like the highest form of like if if you're on this like algorithm ascension path right you fall in love with this symbolic because and one of the talks that i'm planning on giving in 2025 is going to be called something like paradigms within paradigms and it's this realization

that like inside of apl and bqn and these array languages is the out you can so beautifully develop the algorithm intuition but there are a number of other paradigms the array programming which is the rank polymorphism like the elision of having to spell map everything, map everywhere. But then there's also the combinator paradigm, which enables you to write this just absolutely beautiful tacit code, which it's so painful being in other languages, and not just like, you know, tacit expressions, like I want to use the S or the sigma combinator, but like things like partial application. I was just looking at some... Oh, that is, yeah, that's a game changer.

Yeah. Someone that liked a tweet that I had tweeted from a year or two ago in 2022. And I was, it was me highlighting like, oh, if we got, if we got both destructuring in Lambda parameter lists and something else, We could have code that looked like this and the code still inside the body of the lambda was just doing return x equals equals one semicolon and I'm like, how am I advocating for like this is where we want to end up? Like that's just

that's a partial application of a binary operation. It's equals one. Like in Haskell four characters. in most functional languages not four characters but it's still pretty short like and it's so fundamental it's so fundamental and so painful to do in a language like it's two characters whatever it's just they've got a just a partial application operator that on any binary operation, you just sit that in between whatever and the value you want to partially apply and stuff like that. Like, so it's what I think, you know, I get too excited about combinatory logic and like, you know, the D2 combinator that's like, or I see the delta combinator.

I was rewatching the CPP North. You spot a rare bird in the wild. Yeah. And I go nuts. It's exciting. People think it's like this esoteric thing that is like okay how useful is that what's really the useful stuff is the stuff that bores me because it's it's just happens all the time but that's the stuff that's super super useful um but then anyways back to

the paradigms on top of paradigms is that there's two other ones mask programming and then also under programming where it's like these things that you don't even have access to in other languages yeah mask programming is something i've noticed you talk about a lot of your solutions come down to that kind of thing where you make a mask you mentioned that a lot in your in your code report videos that is that is not a way that i typically think yet we might say yeah um it is very much on the on the level of whole meal programming transforming data structures by by by making masks and using them to select out whatever and then you know reducing and re-expanding and all that sort of thing and the the real moment when i

realized that this is something that was like latent and i i wasn't acknowledging as like a whole way of programming was when i was building the the formatter and i was not making use of a use of a mask to split some stuff and so i was kind of using like a filter thing i was filtering out some unnecessary stuff. And for the simple case, that worked. But then when I wanted to do something more advanced that kind of relied on a couple criteria, that criteria depended on the structure of where things showed up. And after a single filter, you lose that structure.

And so I needed a way to basically apply like multiple filter operations, but like structure preserving filters. And that's what a mask is. It's just booleans, ones and zeros. And so as soon as I switched from splitting using like filtering, like in functional languages to splitting using masks, I can just stack those masks on top of each other, do a column wise reduction. And then poof, now I have my final mask that I want. And like how to solve that in a kind of functional style where you're just making use of the filter. It's like it kind of falls apart because now instead of filtering, I'm doing something with a scan and multiple scans and a scan is not really what I want. I just want to do this kind of mask based splitting or mask based filtering.

And and yeah, anyways, I it's having more tools in the toolbox right? And sometimes having an entirely new toolbox you didn't know existed 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-brace Um