Ben 0:00

You know, like in C, we say no raw loops. There's an idea that if you're writing a for loop, if you're writing a while loop, you should scrutinize it, you should figure out if there's a standard algorithm that does this. Don't write the raw loop, which has a tendency to gather craft. The difference in a way between Haskell and Lisp, similarly, a mantra in Haskell would be no raw recursions. In Lisp, you write the function and you're dealing with head and tail and you're recursing. Great. In Haskell, if you write a function where you're manually dealing with head and tail, it's kind of like in C when we're writing a raw loop. One of the things that languages like Haskell and BQN, one of the sort of next step up they've achieved over languages like C, Python, whatever, is exactly what you were just saying. You know, we keep making this mistake of when we write algorithms, we don't recognize that we can decouple the traversal of whatever data structure from the actual operation that we're doing on the locai.

Conor 1:16

My name is Connor, and today with my co-host Ben, we chat about programming paradigms, algorithms, and more.

Ben 1:25

So I my first job was programming C. C at that time, at least and probably still, was very procedural. Um, you know, you write functions, you do, you do one thing after another. You keep track of state, right? That is one paradigm. Now, and there are plenty of C programs that do that today. Most of them, in fact. Um, you know, object orientation was another paradigm that came along, really had a big heyday in the late 90s through the 2000s. Um functional has been taking over this past decade plus. Um array languages have always been like watching from the sidelines, if you like, you've really got into them. Um it seems like there are you know, each one of these things teaches you a different way to think, right? Like, like and uh with languages with with with languages like Lisp, Lisp family languages, um the big way it teaches you to think is recursion, right? You're always thinking about head and tail. Yeah, and you're you're coding up what to do for the head and then how to recurse on the tail. Um and I solved a couple of Avem code in in Lisp. Um and it was very nice to do that, right? Um, but then when you learn Haskell, you have the same things available, but you know, like in C we say no raw loops, right? So we've we've reached, we've there's an idea that if you're writing a for loop, if you're writing a while loop, you should scrutinize it, you should figure out if there's a standard algorithm that does this. If there's not the standard algorithm, maybe there's a boost algorithm, maybe there's some kind of algorithm. It is unlikely that we are every day in our day in our regular jobs inventing algorithms that are new to science. And so there's a recognition that we should call the thing by its right name, form an abstraction, don't write the raw loop, which has a tendency to gather craft. The difference in a way between Haskell and Lisp in their fun one of the things about their functional styles, they're both sort of functional languages at the core. But I might say that similarly, a mantra in Haskell would be no raw recursions, right? In Lisp, you write the function and you're dealing with head and tail and you're recursing. Great. In Haskell, if you write a function where you're manually dealing with head and tail, it's kind of like in C when we're writing a raw loop.

Conor 3:59

Yeah.

Ben 3:59

Right? There's the idea that really I should be able to express this better using built-in recursion schemes in the language. And I think, you know, array languages maybe have that, but they take it to a different place. They, you know, mask-based programming is about you know, in the Lisp, in the Lisp way of thinking, uh it's very much minimizing data and data layout, and it's bringing to the fore the idea of the evolution of the program, right? To the point where you can you can model famously in like lecture five of the SICP lectures, um Hal Abelson, I think, shows shows how to model like pairs and therefore lists and all the underlying data, like that's not actually you you thought that was an array under the hood? No, that's that's not any kind of data at all. That just functions, right? And in BQN, it seems like that sort of turns around, gets put in its head. It's like directly composing data, right? You have a data structure, you make another data structure that mirrors it like a mask, and use it to select out. So you're you're sort of bringing the data to the to the forefront and using transformations on data. All of which is to say, you know, I think there are lots of different tools here, and uh and all of them are very useful in their own way. Um but I don't know if you have ideas about that, those observations.

Conor 5:30

No, no, I I completely agree with almost everything you said. Uh I mean, I think it was this is goes back to like the very first time we met, actually, which I believe was at C now 2019. Right. I was super, super early on my we'll call it algorithmic ascension journey.

Ben 5:51

And you were I remember you being super excited just to meet other people who could talk at the level that you were already talking at about algorithm, who could who could talk, exchange these ideas of like this algorithm and this algorithm go together this way.

Conor 6:08

Well, it's I mean it's funny that you you say that because I think at the time I don't I I didn't even realize really like what what I was on to. And in fact, when I first gave the meetup version of that talk in the same year in January, my goal was to try and give it uh at CPPCon. And I had been listening to CPP Cast and knew C now was like the expert conference, and I I was not interested, like I did not consider myself an expert. And I remember when I was talking to Bryce, he was like, You got to submit this to C Now. And I was like, no, no, no, no way. Like I'm not I'm not going there. Like I I don't have anything to contribute. He convinced me. And then when I uh I showed up, I was like pretty nervous, but like my advantage was that I had almost met like half the people virtually, in a way, from watching everyone's talks. So like I had watched your talks, I had watched uh a bunch of folks' talks. So whenever I'd bump into someone, I'd be like, oh, my favorite talk of this was is yours, uh, which is a a a good like ice uh breaker if you know if that's your style. Anyways, um, and I remember talking to you and just like I remember one of the things you told me, because I was just learning, I was at the phase of like transitioning to C algorithms are awesome, but like man, Haskell makes it so much easier. And I think you were the one that mentioned, like, oh, have you heard of uh like Bartaj Meluski? Um and I was like, no. And and uh you were like, oh yeah, like he has been giving talks for years at this conference, uh basically implementing Haskell stuff at compile time and C. And uh that was just like one of like several. You we we you also like led to uh at least one slide directly in the um 2019 edition of that talk where you pointed out that Fibonacci numbers could be uh calculated with adjacent difference, which like I think that that was like a a stone that you pushed off a mountain that like rolled into like a whole thesis of mine.

Ben 8:14

An algorithmic intuition lighting a fire. That was part of that.

Conor 8:19

Yeah, like I I remember I remember not believing you. Um and I think I went and like got my laptop and whipped out gobbled because I I could not believe that s that that was what adjacent difference did. And I think that that led to the insight of like, holy smokes, like anytime you encode the default binary operation or operation in the name, it's it's so it's it's it's kind of limited.

Ben 8:43

Just putting a fence around the way you think about it.

Conor 8:45

Yeah, and uh like an intellectual box around what something can do. And I was like, how could you like Fibonacci is adding? How could you possibly use an algorithm that's about subtracting? And then you realize, oh my goodness, it's not about subtracting at all. It's about combining adjacent elements together with a binary operation, and they've accidentally and I I think in is it um uh Stepanov's defense, or I'm not sure if he was the one that named it, it was to it was uh adjacent difference and partial sum were specifically named to I think elicit the fact that these were two round-tripping functions. To be kind of inverses, yeah. Yeah, which is a mistake. Uh even if if that's your goal, you succeeded in the goal, but you've you've made the mistake of obfuscating what you can do with this. Anyways, the point being is that uh all the stuff that you're talking about, it's like uh i like I c I completely agree with. And Haskell, I rarely ever write recursion. In the same way in C I rarely ever write raw loops, and that's not because no one ever said uh no raw recursion. It's because I don't think of Haskell as a recursion language language. I think of it as every algorithm's already been written. It's in it's in a library somewhere, data.list, data.list dot ht, data.split. I'm not gonna go write it because I don't like writing recursion. I just like using the dot composition operator or the b1 composition operator in between things that other people wrote. Anyways, you were gonna mention something a couple times and uh I was gonna agree.

Ben 10:04

I was just gonna I was gonna say one of the things that languages like Haskell and BQN, one of the the sort of next step up they've achieved over languages like C, Python, whatever, is exactly what you were just saying. You know, we keep making this mistake of when we write algorithms, we don't recognize that we can decouple the traversal of whatever data structure from the actual operation that we're doing on the loci. Right? We uh in C we it looks like we do that less because we have this large library of algorithms, but in fact, it's a small library of algorithms. Those algorithms pretty much only work to a first approximation, they work on linear sequences, right? As soon as you go into something that's a tree or a graph or something else, you are back to rolling your own algorithm. And like as not, if you are used to programming in C and Python, you are not thinking in the way of let me separate the recursion from the operation or the the the traversal from the operation, right? Which in languages like Haskell, BQN, anything like that, sort of the the way they the the way they lead you to write the code is naturally to do that, I think.

Conor 11:19

Yeah, no, it's uh and I've heard Adam make this argument, he's one of the panelists on uh ArrayCast that that's one of the nice things about APL and BQN in these languages is because they're symbolic, you don't actually need to name the symbols. Which like he's I think taken issue with the fact that in a lot of the documentation we have to try and find ways to name these things so we can speak about them, but the naming of them you can fall into that trap again. Whereas like without the name at first, it is conceptually and like intellectually free. Like uh until you put the name indices on the uh symbol that you know pulls out the corresponding index name, without that there, you might be more likely to see that there's a generalization of this where it's really more of a copying thing than it is a a taking the index of thing. And and yeah, you know, speaking of which, adjacent difference in in Haskell, they named correctly, uh adjacent map, which we then got a version of in C23 with adjacent transform. Anyway, so yeah, there's uh I don't I don't know what the BQN version of no raw recursion and no raw loops is. I'll have to think about that.

Ben 12:29

I'll get back to you and think if there's but I think uh maybe there isn't one, but maybe there is something that you can identify.

Conor 12:36

Yeah. I think I think yeah, and this is getting back to your very original question is you know, what is BQN and these languages, you know, if and and that was the thing. At the beginning of I keep on not answering this question because I can just have thoughts that pop into my head. Is what was it, problem three that you did with the command line and grep? At the beginning of my video uh and regex, uh, I think I said, you know, really, I want regx for this, but BQN doesn't have a regex library. APL does, but I was doing this at BQN. And that's what I would have done if I if I had that DSL available to me.

Ben 13:06

Yeah. Well, you know, regardless of what languages that that you know, I would highly recommend, not not you personally, but that that one knows. I would highly recommend getting familiar with the command line. You know, just just string together like grep, cut, tr, exarch, find, yeah. And when you need them said an orc, tons and tons of problems become become trivial. You know, I I I've I've had situations where uh where I've been on a team and and um you know the day after this happened, someone another program team came to me and uh you know we were chatting about what we did yesterday and and he said, Oh, I wrote this I wrote this Python script to um find all the find all these files and zip them up right for localization or whatever. And and and I and I you know I spent half a day on it. And I and I'm confused at this point. I'm like why why would you spend half a day writing Python to do that when it's literally like 10 seconds on the command line? Yeah. But I didn't make him feel bad over it. I just, you know, you're one of today's lucky 10,000 sort of thing.

Conor 14:22

Yeah, and it it makes me uh think of like the times when I've learned a new like you've got your toolbox of command line tools. I think yours is definitely larger than mine. I did some said slash I don't actually think I've ever done any AUK, um, but I've done some said stuff in the past. But like definitely Do learn a bit of orc.

Ben 14:42

Do learn a bit of orc. It's a fantastic Swiss Army knife.

Conor 14:46

It's come up before multiple times when when we've been chatting. Um But like one of the things that I learned was the the back ticks for evaluation. Like that that is probably like a a small insight in the way that my brain works because when I learn that small trick, because you there's two ways to spell it. Exactly. Dollar parens, and I think even there's like an avow thing, but like the backtix was like a couple characters less. And it then I was just it made me so happy because it's a more elegant way. It's like it's back to the whole uh partial application. Like when there's a simpler, more elegant way to do things and you're able to leverage like a whole tool belt of these things, it's the it meant it makes it painful to go back to the way you had to do it before.

Ben 15:30

And it's very much like programming in like when you're on the command line, you're not like it's like programming in a REPL, right? Yeah, you're not writing out this 100, 200 characters code. You you're building it up piecemeal, you're playing with it, you're you're you know, it's real easy to do.

Conor 15:47

Yeah, it's uh and so yeah, to circle back for the tenth time to your you know, what is it great for? It's best for things where reduction scans, these kinds of things you need to reach for. But my follow-up to that is that's like 98% of like if it I plan to dual day job? Uh well, just of all of my programming. Like even when you're going to um read from some JSON file or do some kind of, you know, I do some geospatial stuff every once in a while. The code that I end up writing in Python or whatever, it's just like the kind of code that I would be writing in BQN, but it's just m it's just more painful, and I'm reaching to a third-party library here, oh, a built-in function, oh, whatever. And it's like BQN, as I learn more about it and these are array languages in general, it's like it does the common stuff so much better than every other language I know, like reductions, scans, etc. And then it has the ability to do, you know, all the other stuff, maybe not as elegantly, but like it does the common path so much better. And that's the thing, is people think of it as like, oh, you need arbitrarily ranked arrays and blah blah blah. No, you don't. Think what what if I just restrict like you we said earlier that uh algorithms basically they just work on 1D sequences. It's like that's a subset of what APL does. I think of like APL is just like a superset of the programming I was doing in C algorithm land. And then it turns out not only do you get 1D sequences, you get all the dimensions. And then on top of that, you're discovering like four or five different paradigms, this mask programming. Under programming is just it's mind-blowing like this like perform an operation and then do the do something and do the reverse of it.

Ben 17:29

Like it's oh, I see what you mean. Under. Yeah, yeah, yeah. I get you now. I was wondering what you meant by that.

Conor 17:35

It's such a useful tool.

Ben 17:36

Like So let's make that a little clearer for the listener.

Conor 17:39

Oh, okay, yeah.

Ben 17:40

When you say under programming, you are talking about transforming your data into some form where you run an algorithm and then transforming back. So the algorithm is performed under some reversible transformation. Yeah. That's one way we can see.

Conor 17:55

And this uh this ties into a uh quote that I heard once that um what is that uh the book of the Gang of Four book that's um patterns? Pattern matching.

Ben 18:05

Uh no, sorry, pattern design patterns, not pattern matching.

Conor 18:08

Uh design patterns, and and I can't remember who said the quote, but it was uh something to the effect of design patterns are just like missing. Do you know what I'm talking about?

Ben 18:17

Yes. I think it was Peter Norvik.

Conor 18:20

Okay.

Ben 18:20

Does that sound right to you?

Conor 18:22

Yeah. And but it's this idea that design patterns are merely there to address flaws or like missing things in a certain language. Which like you go from language to language, sometimes you have some language facility or library thing, and now you no longer have a need for like, for instance, the visitor pattern. Like, we need that until we have something like pattern matching, you know? Then you no longer need the visitor pattern. Is that correct?

Ben 18:46

Well, okay. The visitor patterns I'm gonna take issue with that. The visitor patterns are probably a poor pattern to pattern.

Conor 18:53

A bad example of what I'm reaching for.

Ben 18:56

Because the visitor pattern is not really about visiting things. The visitor pattern is a solution to the expression problem, right?

Conor 19:05

Right.

Ben 19:05

It's turning, you know, in an object in your in your standard object-oriented languages, it it's and I'm including C, even though I wouldn't really say C is an object-oriented language. But it's that in that model of object orientation, it's easy to create new types. It's easy to subclass things, it's easy to, you know, d uh derive and uh and extend. Um but it's hard to create new functionality. If you have a type if you have a class hierarchy and you want to add a function, add a member function, you need to thread it through every part of that class hierarchy, right? Um and in functional languages, to a certain extent, it's the opposite other way around. It's very easy to add new functionality, but because you have because uh because they have pattern matching, right? If you have pattern matching, you have functions. Every function you write matches the patterns of your classes, and so you've turned the problem on its head. It's hard to, it's easy to add functions, but it's hard to add new types because you would need to go and change all of the pattern matching places to build the new type. Right. So that's a fundamental dichotomy, and it's known as the expression problem. And the visitor pattern changes the one form into the other form. So for classes, for languages that have object orientation and it's easy to add classes, types, what the visitor pattern does, it makes it easy to add functions.

Conor 20:26

Yeah, I think um Gashper Asman has a really good talk um about the expression problem. Uh I'll find a link and throw it in the show notes. I think that was him. I'll fix it in post if it wasn't, but I'm pretty sure it was.

Ben 20:40

So anyway, I'm I'm a I agree with you, but I just think the visit pattern is.

Conor 20:44

That was a bad example, yeah.

Ben 20:45

It's a can of worms when we open the visit pattern.

Conor 20:48

Well, the so the the reason I brought it up though was because uh under obfuscates or makes um a couple things in both C and Haskell, as those are the languages we've been mentioning, unnecessary. Or not unnecessary, but there's a different way for solving it. So one of my kind of irritations uh is that in Haskell you have two different types of scans. You've got scan L and scan R. One's for the left, one's for the right. But in BQN, you only need one because a right scan is just a left scan under reverse, which modulo performance concerns because obviously if you're gonna be actually doing a copy, uh, and I'm actually not sure how uh under reverse, I know a lot of them have like idiom recognition, so you're not actually completely doing copies, you're just once again doing some kind of view-like thing. But it's a very nice way to conceptualize like I can do things, and it's like and some people might be thinking, well, now I like R scam better. What about all the other operations though that don't have the right equivalents that you'd need to go and roll yourself? It's like, well, now we have a generic higher order thing that I can just apply. This operation under this. And it's what about under transpose? What about under some sort? What about actually I don't know if sort works? Because it has to be something that is reversible in a sense or invertible. Yeah, yeah.

Ben 22:12

I think it again, I'm gonna kind of say that Haskell L and R scan was maybe not the best example because uh it's not just performance concerns of putting a reverse in, it's laziness as well, right? Um and so there are real reasons talking uh thinking about laziness, why like like the canonical example is like in Hask, Haskell has um uh what do they call reduce in Haskell? Fold fold right. So Haskell has fold L and fold L prime, yeah. The prime meaning it evaluates strictly, not lazily, and and and fold R, right? Which is right to left. Um and the rule of thumb is basically never use fold L to a first approximation, right? Because if you're doing a left fold, you probably strict you probably want strictness, or you probably it is it is performance-wise, much better to be strict in the first argument. Conversely, if you're doing a right fold, the performance of right fold comes from the laziness.

Conor 23:21

Yeah. These are things that uh I skate over a lot of the time, because in Haskell Well, in Haskell, I've never checked in any production Haskell code in my life. So uh I play fast and loosed with fast and loose with my folds.

Ben 23:35

Yeah, I mean, and that's fine. But now I'm gonna hit you with the killer question.

Conor 23:39

Like so there's been a killer question in the wings this whole time.

Ben 23:43

No, just one more question. Um so I've known professional but professional programmers who programmed in functional languages. And um, to a large extent, you know, they don't spend their days carefully crafting algorithms, they spend their days wondering about how to interface library A with library B and wrangling the build process. Um so you know using BQN in a professional sense, which I I'm pretty sure you don't currently do, but maybe you know people who do you certainly talk to people on the raycast who do, probably. Um, what happens there? How do you put like one of the great things about programming in, let's say, a mainstream language like Python or C is there are there are off-the-shelf solutions for just doing the same thing in CI as you do at your command line, right? What does CI look like in in BQN or one of these array languages?

Conor 24:37

CI. I think across the board, CI is non-existent. I know that like because so there's BQN, which is a language in its infancy, in that probably my biggest complaint right now is that there's no any form of like a package manager. And even even the idea of libraries and packages in the array community is controversial because some folks don't believe in dependencies, which the more and more I use these like languages, the more and more I disagree with that, because at a certain point, you do not want to be writing the world, which is what some people advocate for.

Ben 25:14

Right. A similar thing happens in Lisp, right? The more things change, the more they stay the same, right? Um, if we look at Lisp, the the ease of writing things in Lisp to a certain extent for a long time meant that yeah, the package ecosystem was very poor.

Conor 25:31

Yeah.

Ben 25:32

Because Lisp is a language where you want to write something while you you build the language up to make a DSL in which you can easily express your problem. That is the Lisp way, if I could say that, not being a professional Lisp player, Lisp uh writer. But then I don't think it's that way anymore. Like you have folks like Zach Bean, who who wrote uh quick Lisp, I think, or um uh yeah, and and and package managers, um well, I forget what it's called. It's got ASDF, is it called? But yeah, Lisp has a package ecosystem these days, thanks to efforts of people like that. And uh anyway, so where do you think this is going with with array languages?

Conor 26:10

I can't predict, but I can hope. And what I hope for is that a language like BQN comes up with a pan package management uh and kind of like ecosystem solution for this stuff. And on top of that, uh a part of writing array code is that everyone has a different style, not dissimilar from Lisp and you know Racket where you can very quickly there's a proliferation of DSLs. And I want, I don't necessarily need to be the dictator that this decides the style, but like something closer to Rust and Rust format, and like even something I think that's configurable, where we do get some, you know, we don't want all BQN code looking uh different. But like so something towards package management, standardized linting formatting tools, and testing frameworks, and then from there you get to CI. Um this is for BQN, we'll see what happens there. I know that at uh Dialog, the company that makes uh the APL interpreter, they're also working on a bunch of tooling. So I know they have like a package manager called, I'm gonna mess this up, I think it's Tartan or TATAN, something like that. And they're all Apple-based things. So I think one of those is like a Tart. And um I know that there's like a testing framework. So they're starting to build this stuff, but you have to remember or know if you if you didn't know, if the listener didn't know from before, APL is is um shares a similarity with Smalltalk in that it's a workspace-based language, which is completely different than how a lot of CI systems you're not starting from this like workspace environment. You're typically starting from code that's either compiled and then executed, or already you've got some binary or executable thing. So to do something where you're loading a workspace and loading like the act of running something from a script in dialogue involves with this kind of it you have to use something called dialog link, which I think in the background is running this workspace kind of box. Right.

Ben 28:13

It's like loading a default workspace image.

Conor 28:15

Exactly.

Ben 28:15

Exactly.

Conor 28:17

I could be wrong. Uh because it would it would seem like, well, why not just write an interpreter that executes it and it's like, well, they've got, I think, hundreds of thousands of lines of this interpreter code that works this way. It's not it's not a small thing to um have it be like a scripting language like Python. Um and so uh it's a sad answer to your question. Is that yeah, a lot of this stuff doesn't exist at all. And my hope is that like if we get a language, whether that's BQN or WeWa or some version of APL that comes with this stuff, I think the interest in the language would skyrocket because right now I love BQN so much that like I'm willing to go and write like the uh simple versions of this tooling for myself because like it's like you know, you there's some quote that I heard someone saying is that like, you know, a language has to inspire people to a certain extent that they're willing to suffer in its infancy. And like I am I am that person right now. Like I am willing to not only suffer, but like write this stuff myself just because it it enables me to write more of this code on my free time. Like if I I can make BQN the entirety of my command line scripting, so I instead of going to grep and whatnot, I just I hop down into a BQN like session.

Ben 29:33

Right, right.

Conor 29:34

I can do that there. You know, it's got a super easy way to load files and whatnot in the command line. 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 Bryce. Um