Algorithms + Data Structures = Programs - Episode 125: NanoRange with Tristan Brindle

Episode Date: April 14, 2023

In this episode, Conor and Bryce chat with Tristan Brindle about collection oriented programming and NanoRange.Link to Episode 125 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)TwitterADSP: The PodcastConor HoekstraBryce Adelstein LelbachAbout the GuestTristan Brindle a freelance programmer and trainer based in London, mostly focussing on C++. He is a member of the UK national body (BSI) and ISO WG21. Occasionally I can be found at C++ conferences. He is also a director of C++ London Uni, a not-for-profit organisation offering free beginner programming classes in London and online. He has a few fun projects on GitHub that you can find out about here.Show NotesDate Recorded: 2023-04-05Date Released: 2023-04-14C++ On Sea ConferenceACCU Conferencecpp.chat PodcastCppCast PodcastPhil Nash on TwitterCppCast Episode on C++ Uni (with Tristan Brindle)C++ London MeetupFluxFlowD RangesC++ RangesRust IteratorsCollection Oriented ProgrammingFunctional ProgrammingSmalltalkJava 8 StreamsSETLThrust LibrarycuCollectionsSwift SequencesSwift CollectionsRanges TSRange-v3 LibraryNanoRangeConquering C++20 Ranges - Tristan Brindle - CppCon 2021CppCon 2015: Eric Niebler “Ranges for the Standard Library”What a View! Building Your Own (Lazy) Range Adaptors (part 1 of 2) - Chris Di Bella - CppCon 2019What a View! Building Your Own (Lazy) Range Adaptors (part 2 of 2) - Chris Di Bella - CppCon 2019cmcstl2Intro Song InfoMiss You by Sarah Jansen

I was talking to him about this once and he was like, that is the definition of feature creep, right there. You started off wanting to call sort and you've ended up with 18,000 lines of code that implements the whole of the range of CS. Welcome to ADSP the podcast episode 125 recorded on April 5th 2023. My name is Connor and today with my co-host Bryce we interview Tristan Brindle about collection oriented programming, his nano range library and more. All right we will just hop straight into things um are you in london uh i am well actually a little town just just on the outskirts of london okay uh but are you and bryce are you going to c++ on c

yeah yeah i'm going to london three times in the next wait three three times in the next couple months i'll be in london for like a day before are you going to c++ on c2 tristan i am i am yeah we'll see we'll see each other there then so i was gonna say we should meet up in london you've this was dangerous information to give me because now i have another name of a person whose couch i can try to crash on every time i come through london um yeah you can try yeah i'm gonna be there for um on my way to core c++ um for cpp on c and then in two weeks for accu man why do you count why do you count your layovers that's not like in this case it's i'm actually there for a day. I fly in and I have to. No, that was cool.

So, yeah, this is the problem. I don't have any cool stories like Sean, obviously. I've never met Steve Jobs. And I was never in the army. So I just I don't know where my stories are going to come from. I feel like you probably everyone. I think that's the thing is everyone doesn't think their stories are like amazing or awesome. Yeah. But everybody has, and then they will just like incidentally tell some story and then you'll be

like, what the heck you, that, and that happened. And you'll be like, Oh yeah. I mean, I guess I seemed normal at the time,

but I guess from a third point party point of view, I think it's pretty rare to meet people who are actually boring. Like I, I re I really struggled to think of somebody that I know who does not have interesting facets. You've met me a couple of times. And I think you're an interesting person. I'm sure. I'm sure. You did invite me onto this for some reason. Yeah. Yeah, sure. You're under the spotlight. I know. I know. That's the problem.

Yeah, we are a, we are angrowing, we're the fastest growing, and we're now officially, oh, we never brought that up. So for the longest time, depending on what podcast app statistics you look at, we were behind CPP chat, which is now discontinued, I think forever discontinued. I actually don't know the status.

Phil Nash is always too busy skipping from podcast to podcast. And now that he's on CPP. Yeah, he's doing CPP cast now. He's like a pirate. He's like a podcast pirate, you know? He's on one podcast pirate ship and then he jumps to another podcast pirate ship

and then he saw this like slowly sinking CPP cast, you know, pirate ship. And then he was like, I'm going to take that back and bring it back to life. He and Tim were doing a really good job with CppCast. I think

I've really enjoyed their content since it's come back. Yeah, they've had some interesting guests. Okay, now I feel like we're done warming up. Whether or not, we'll see what makes it into the Go for it. Into the actual final cut. You have a topic in mind, Connor, right?

Yeah. Well, I'm not sure. Did you see it? Well, first of all, let's introduce Tristan Brindle as our guest today. This interview is kind of happening because let me bring up the email. I did link to both of them. So what's the date on this? It's February 9th 2023 uh tristan who i mean i assume most

listeners know that you know we know a lot of the people that we're bringing on but we've all met obviously at multiple conferences and committee meetings um actually yeah when was the first time we met tristan maybe it was cpp con 2019. Probably. That sounds about right. Yeah. I've never been to C++ now. I'd love to go, but yeah. So prolific speaker, many topics. We'll link a bunch of them in the show notes. I think ranges is primarily like the majority of the talks that I've seen by you. Yeah. Yeah. That's kind of the subject that I've given a few talks on. And actually, before we get back to the tweet that brought this interview slash conversation to you today, I think the very first time I came across your name was you were on CppCast as a one of three guests correct me if i'm wrong that was talking about

the cpp london university and i remember just being like in awe of the amount of work that it would take because you were saying that you basically were like marking assignments and like giving feedback and yeah conducting this kind of like online C++ course. And I was just, I don't even think at the time I had connected when I first met you that you were one of those three voices. I knew you had done the, your sort of nano, was it nano ranges? Is that what it was called? Nano range. Yeah. Yeah. And so I knew that you had implemented a bunch of ranges, like range like stuff in the range library that I think has been quite popular. And then at some point I remember that you had mentioned that you were doing this

cpp london university thing and then i was like i listened to that podcast and then i went and looked and i was like holy smokes you were one of those three voices yeah yeah so um that was uh i think that i i started with uh well uh it was started by a guy called Tom Brezza. It was an off show. There is a C++ meetup in London. It's called C++ London. It's run by Phil Nash. And it's roughly monthly.

And a guy called Tom, who was learning C++, started going along to these meetings, but, you know, they're for established programmers, you know, for people who use C++ all the time. And he was a learner, and he was like, it would be really cool if there was some sort of meetup for people who were learning C++. So Phil, like, emailed around everybody who was on the list for C++ London. He said, like, you know, Tom is trying to start this.

Would anybody fancy giving maybe a couple of classes? Maybe like five classes. Maybe we can do it in five. Maybe we can go through all of C++ in five hour-long sessions. I was like, well, I don't know about that but that that sounds that sounds like fun that sounds like something i could do so then i kind of signed up okay i'll do i'll do five sessions um and uh then very quickly another guy got involved uh called uh oliver din ollie and uh so then the three of us this just sort of this just sort of snowballed from there. And we ended up

giving these classes, weekly classes in C++ in London for a couple of years. And then it was all going pretty well. And then unfortunately, COVID hit and there was lockdown and we weren't able to meet up anymore. And we started doing them online, like right at the start of all the COVID shutdown. But at that point, like everyone had massive Zoom fatigue, you know, because we were all spending so long all day in these Zoom meetings. And it just, you know, it sort of tailed off because we all kind of lost enthusiasm for being on Zoom in a couple of hours in the evening. So, yeah, unfortunately, COVID sort of paid to that. It would be nice to get it going again. Tom and Ollie, if you're listening to this, get in contact because I'd quite like to get it going again.

Yeah, I remember listening to that thinking like that's such a cool thing. And also just like I've run virtual meetups before and virtual meetups are like a lot of work and just like preparing the content and the slides. And it's just a lot of work to run that. But on top of that, you were you were like doing marking and like I was just like, wow, that's like sounds like a Herac, Heraclion. That's the word Heraclion effort. And there we go. Thank you. That didn't sound right uh but yeah so you know if potentially connected some dots for some listeners that uh may know

of tristan's talks and have also listened to cppcast for a long time um and you also you did nano ranges you also were gonna this is gonna come up at some point um have a library i don't think you've really formally announced at any point called Flux, but it's, I've known about it for a while because you've, I follow you on Twitter and you've tweeted a couple of things. And then I've been like, what is this? And you were like, oh, you know, it's my unannounced library. So I feel like I'm saying it's unannounced and yet we have like several thousand people that listen to this podcast. So it's going to get a, this is the announcement. Here we are. Yes. Yes. All right. Let's, yeah, we can talk about that. So I've been working on this for a few months now,

working on a library called Flux. It's actually a follow-up, sort of a follow-up to another earlier library called Flow. But so Flux is a library for sequence- orientated programming i guess would be a good way to put it yeah yeah i don't mean in the in like the apl sense like don't get too excited connor because like i know nothing about apl or bqn or any of those uh array languages what i mean

is sequence orientated programming in the same way that you would get with C++ ranges or Python data tools or Rust iterators or, you know, D ranges or what have you. It's a library for doing that. It shares pretty much the same goals as C++ ranges. But it takes the things that I have learned from working on C++ ranges, from implementing C++ ranges, and it does some things slightly differently. And I think these are, you know, it's an experiment. I don't know that it's, you know, it's going to work. But I'm quite excited about it. And I think it's, I think it's, I think it's I think it's pretty good really all right I've got one comment and one question so the the name of the paradigm the reason why I went is because I think

I maybe mentioned it once or twice there's a paradigm called collection oriented programming which is literally what you just said like it is ranges in c++ iterators and rust and it's it's got some overlap with functional programming like i feel like spiritually functional programming and collection oriented programming are like cousins but it's the things that i actually like previously associated with functional programming like having functions that operate on sequences or you know even in small talk like small talk is not a functional language but it is a collection oriented programming language because it has all these different containers that just have operations aka what they call messages that you basically just like you build up this kind of like data flow where

you're just chaining a bunch of things together and you're never writing a for loop you're never worrying about like indexing and stuff like that you just sort of like build up this sequence of operations which is exactly what c++ 20 and 23, 26 ranges and all these types of like Java streams fits in this model. Anyways, there's going to be a talk at some point that I'll call collection-oriented programming, but it's like my favorite way to program, whether that's in Haskell or in C++ rangeland or in Smalltalk or even in like, I think there's a language called Settle, C-E-T-L, that I haven't looked at. But apparently, it's like specifically kind of like the APL, small talk kind of thing.

But it purely works on like sets and maps. I could be wrong about that. But anyways, collection-oriented programming. Fantastic. Yeah. Yeah, yeah. So I agree with you. So I previously used the term like functional style programming.

Like functional programming means a lot of things to different people you know referential transparency and yeah all that sort of stuff uh whereas i'm more focused on like you say the bits where you you have a sequence and you manipulate it in some way you build up a pipeline of operations and um yeah so we're not not kind of full-on haskell style functional programming but uh yeah we've got one of my goals over the next one or two years is to popularize this term collection oriented programming because it is like the perfect description of what you just like described and like it it like goes across like apl small talk functional languages like apl is kind of functional but like APL, small talk, functional languages, like APL is kind of functional, but like the thing that I love about it is this composing operations or like a pipeline of operations.

And then you just feed it your data and poof, you get your answer. Like, and that is my preferred way to program in general. Like in C++, that means like doing as much range like stuff as possible. But in other languages, it just means like using the language as it's designed. Yeah, yeah yeah definitely okay so i my my term was sequence orientated programming if collection orientated programming is the uh is the the proper term then i'll i'll start using that instead because i like the proper term nobody knows but, to me, collection suggests an unordered set of things, and sequence is a thing that has... How does collection mean unordered?

We literally... That's just what my... That's what I think in this field, when I think collection versus sequence, that's just what comes to mind to me. You're forgetting, I don't know how long ago this was, probably a year or two ago, you made me, or you made me, you nerd sniped me into doing an opposition analysis

of what language is called data structures because we were trying to figure out a name for the thrust equivalent of like a data structure library at NVIDIA. And we ended up coming across the terms basically containers, collections, data structures, and maybe there was one other less popular one. And we ended up going with collections. And that's why KUCO, KU Collections, is called collections because it's what many languages call their quote unquote data structures.

So I'm surprised that now your semantic attachment to collections is not just like data structures in general, but... I mean, I think that that's one of the semantic attachments that I have to it. But if I'm comparing the term with sequence, the important property that I get out of sequence is that it's a thing that I'm getting in where order is significant. That's true. So I'll add a data point on this, which is not something I know a huge amount about, but I know that in Swift, there are in the Swift standard library, there are both sequences and collections. They have sort of two iteration APIs and sequences are single sequences and collections they have sort of two iteration apis and sequences

are single pass and collections are multi-pass so this was um as far as i know uh dave abrahams came up with this i believe um so he knows he knows an awful lot about these sort of things so uh yes so what sequences and collections you have like an example of what it means to be a multi-pass on a collection like uh i think the sequence single pass thing it makes pretty it's pretty straightforward you're mapping over an operation you do it whatever left to right or in some sequential order what what does it mean to i think this is about capability about whether you can consume it multiple times yeah yeah so the equivalent of a forward range in C++ land. I see, I see.

That makes sense. Interesting. Well, yeah, that is another data point then. I'm not sure if Swift was a language we looked at of what they called their data structures. All right, so that was the comment. The question is, let's talk about the, the differences in everything you've learned. Uh, well, so we'll link for, uh, you know, the curious listeners, I'm pretty sure NanoRange still lives online. Um, even though it was kind of designed as like for people that are in previous versions that don't have access to C++20, you can use this in the interim. So I think if I recall it it it's usable in like c++ 14 uh 17 17 um nano range yeah so just to rewind a bit so back in the ranges ts days so before this was uh standardized there was um i don't think we do them anymore do we bryce but the uh like uh ts's were was this

idea that we would sort of try out some new libraries with the intention that they would eventually... We've stopped doing what I like to call grab bag TSs, which are TSs that are just a collection of things without really a specific purpose. And the reason for that is that there is a high overhead to publish in something in a TS versus an IS. And if we publish it in a TS and then want to put it into the IS, we basically have to pay the standardization costs twice. Because oftentimes we have to go through and do a re-review of it because things have changed or evolved since then. And so we'll still pursue TSs, but I think the general vibe on the committee, at least in library evolution, is that we only want to see focused TSs. TSs where we have a very clear goal for why we want to pay the additional cost of putting this out into a technical specification, what questions we're hoping that it's going to answer.

I mean, another reason that we've become more TS pessimistic is that we have found that we don't really get the usage experience in the deployment experience and the implementation experience that we had hoped with TSs, especially because we are now shipping on a three-year cycle pretty reliably. TSs were something we came up with when we were in this long, after this long decade that led to C++11, and we thought that it might be a while before we put out another standard revision. But now these days we reliably put them out every three years. And because of that, what often happens is we go through all the trouble

to publish a TS, and then almost immediately before it even really has any time in the wild, somebody advocates for us putting it into the IS. And so we don't end up getting any experience from it and we just pay a lot of extra effort. Makes sense. Yeah, so, well, Ranges was, I think Ranges was, it was a pretty focused TS. So Eric Niebuhr came up with range V3.

And then this went through the TS process to be standardized, eventually found its way into C++20. And back at the time when the ranges TS was published, I went and I wrote like a from scratch implementation of the ts for i started out with c++ 14 and then i moved to 17 later on because it had some uh really useful features like if constexpr and stuff um but yeah so i wrote basically my own implementation it was called nano range the idea was that you could, as you say, that you could get started with NanoRange and then whenever C++20 came along,

you could switch to that without having to use... You could use RangeV3, but RangeVC is kind of huge. And so if you wanted something that was smaller, like nano-sized, you could use NanoRange instead. So that, to be honest, it never quite got the usage that I was hoping for. I had a few people interested in it. And I believe I've seen somewhere that it's used in the Intel thread building blocks or parts of the bits of the nano-range code are used in there, which I thought, which I was, I was quite pleased about. Um, but, uh, perhaps that's not the case anymore. Uh, but, uh, yeah, so there was, there was nano range, uh, and I, I learned so much about, uh, ranges and, um, how

all these things were implemented, how all these parts fit together, uh, from doing that. Before we move on, uh, how,, when I think about implementing a TS, I don't know if it's my imposter syndrome, but to me that seems like a very impenetrable wall. And I've also seen a lot of the internal range V3 code. I've also watched your talks. I've watched Christabella's talks. Also too, we should mention,

Eric refers to Eric Niebler if you're, this is your first episode. I mean, Krista Bella's talks. Also too, we should mention, Eric refers to Eric Niebler. If, if you're, this is your, this is your first episode. I mean, we've had Eric on, so hopefully our listeners know when we say Eric, who Eric is, but like, so I've seen Eric's talks. I've seen your talks. I've seen Krista Bella's talks. Krista Bella has like a two-part CPPCon talk where he walks you through how to implement like a stride, a stride range adapter. And just like, you know, if I ever had the thought, I've had the thought of like, oh, it would be cool to implement my own like mini ranges, like similar to what you did, like only what the standard says,

not a bunch of action, extra stuff that's in range V3. And then immediately my brain is just like, yeah, probably not. Like that would be so much work. And like you would immediately hit some like language lawyer wall of like having to digest like the wordies of the standard. Anyway, so my question after that long, unnecessary monologue is like, what gave you the confidence or like, and how difficult did it end up being having to implement that, you know, taking it from a TS to basically having your own library okay so to start off with i did not uh by any means intend to start out and just like start off with an empty file and go i'm going to implement the range sts um what happened was that um i was using range v3 and i was like this is really cool but like i've got to be honest like the compile times at that time were a real drag um and i was like, what I really want is to be able to call STL algorithms,

but just pass the range. So I don't have to call dot begin and dot end, you know, just sort brackets back. And I was like, okay, what I'm going to do is I'm just going to write a single header. And all it's going to do is it's just going to have some overloads of, you know, all the, well, all the useful algorithms.

And you're just going to be able to pass in a vector as well or pass in a range directly as well as these.begins,.begin,.end. And I'll just forward those calls to the existing STL, right? And then the thing is, if you start doing that, it turns out that quite quickly, you'll find out that there will be ambiguous overloads. So if you think about the example of sort, you can pass a custom comparator, right? So if you have a call to sort that has two arguments, you've got to have some way of deciding, are these two things you've given it, are they a begin and an end iterator, or are they a range and a comparator? Right? Right. So in order to do that, you need to start using, well, nowadays you could use concepts, but we didn't have concepts yet then. So I was starting to do some metaprogramming, and it's like, how do I work out whether this object is an iterator? How do I work out whether this object is an iterator?

How do I work out whether this object looks like a range? I was like, you know what? Some very smart people have already worked this out, and it's all written down for me in this ranges TS document. So I started off using EnableIf and all that horrible stuff we had to do at the time, all this template programming to work out, okay, this looks like a valid range. This looks like a valid iterator. And, you know, it's really pretty useful as well because it allows you to reject calls when iterators don't meet requirements and all that. So I really didn't start out intending to do the whole TS. I was like, it was just going to start out being really simple,

just what I needed. And then I was like, okay, well, now I need to be able to differentiate between iterators and ranges and all that sort of stuff. So I'm going to take what it says in the ranges TS and do that. And I was like, you know what, this is really fun. I actually quite enjoy this. So I was like, you know what, this is really fun. I was, you know, I actually quite enjoy this. So I just ended up doing the whole thing. And the other thing that I really couldn't have done it without the help of Casey Carter, who is one of the two sort of godfathers, like the fathers, the fathers of ranges along with Eric Niebuhr. And Casey was, I was on Slack at the time,

the CPP Lang Slack, pretty much every day, just asking Casey the dumbest questions. And he was very, very patient with me, explaining stuff. We found a few bugs in the spec. And yeah, so Casey, for listening, thank you very much for your help at that time. I couldn't have done it. Yeah, he has his own version.

There's RangeV3, there's NanoRange, and then there's also his, which is like CMCSTL or something like that. CMCLSTL2, yeah. Which I think that was sort of the, so that used the GCC concepts TS implementation at the time. Yeah. I think that's online somewhere. So I'll link to that as well.

And what I was going to say is that this is, it's very inspiring to hear because as soon as you said, oh, I only just wanted to provide an overload for like existing algorithms. It's like that is- All I want to do is call sort bracket event. That sounds like my brain when I think of like,

oh, if I wanted to do that my brain goes oh yeah you can definitely provide just like an overload that dispatches to the existing thing and then from there you basically just was like oh well i just i need to know this one little thing you went to the the ts and then things snowballed from there and i could you i definitely know that like i've written things in the past where like the end thing that i ended up writing seems like a behemoth of like you know how would have i done this to begin with but like the end thing that I ended up writing seems like a behemoth of like, you know, how would I have done this to begin with? But like the initial thing that I wanted to do was just like build some small little stack machine for a small toy like calculator that ended

up being, you know, something way, way bigger. So I guess that, I guess the word of advice for the listener here is that if you're ever intimidated by some ultimate thing you want to achieve, just choose like a very small, easy part that your brain knows that you can do and go from there because that seems like it's exactly what you did and you ended up with a whole implementation of the of the ts yeah i'd say uh gashwell oaksman i think it's the same i was talking to about this once and he was like that is the definition of feature creep right there. You started off wanting to call sort and you've ended up with 18,000 lines of code that implements the whole of the ranges CS.

Yeah. Yeah. Not what I started out, you know, intending to do, but somehow. Yeah. Somehow ended up with that.

So, yeah, that, that was, but that was a few years ago now uh now we have uh ranges in um in the standard in the standard library as well it's uh you know and i and i i love ranges i love this collection orientated stuff um i you know like you it's um i really enjoy that style of programming.