Conor

I'm down in Florida this week. I've been in Costa Rica. Welcome to ADSP the podcast episode 167, recorded in between January 30th and February 2nd of 2024. My name is Connor, and today with my co-host Bryce, we play Phone Tag because he was down in Florida and I just got back from Costa Rica. In today's episode, we chat about control structures in array programming and array languages as well as two algorithms scatter and gather.

Bryce

Hey Connor, it's Bryce. I was just trying to reach you, but uh seems like you're busy right now, so I figured I would leave you a message. I'm down in Florida this week uh visiting my mom and uh my stepdad. And we've had some not so great weather thus far. Um but this morning I woke up and it's nice and sunny and warm, and so I'm out on my mom's patio by her pool, uh just doing a little bit of work, um, taking some meetings, and uh I keep thinking about this uh this conversation and question that I was asked yesterday that uh I think you'd find quite interesting. So I was talking to somebody about array programming languages, and they asked me, well, how do you express conditional logic in an array programming language? And this is somebody who came from an imperative programming background. And so I think they were thinking of, well, okay, like how do I write, you know, if and else? And more so I think they were in their head sort of imagining, like, okay, I can see how I could, you know, chain together some transforms and some reductions and and scans, uh, but it wasn't as straightforward for them to see how they might uh you know introduce an if-else that maybe uh would appear in the inner body of a of a for loop. Now, my my first reaction uh was that you would use something like a filter. Now, this is something from C ranges. Filter is uh an operation that takes a range and a predicate and it returns you a range that has all of the elements uh for which the filter returns true. And so then you can use this to select which elements are going to uh participate in the rest of the operations that you're gonna apply to this range. Now, this pattern is very common in parallel programming, where uh traditional conditional logic uh can be quite a challenge. In particular, in the world of vector or SIMD programming, uh conditional logic can be very hard, and for a long time it was uh not possible to express in many cases. The way that you often express it is through masked operations. So a masked operation is an operation that takes a bit mask that tells you which elements of the vector are going to participate in this operation. And you can construct those bit masks through other operations that might apply a predicate, etc. This is a very common thing in SIMD programming models, especially today. Uh so like the uh the ARM SVE instruction set uh essentially has all of the operations have a masked form. And this is also a common pattern in uh GPU programming. Uh this is how we do um selection and grouping in libraries like Cub. Uh we we build up some mask, and uh in some cases we have to propagate uh information about this mask forward using scans. Um, for example, uh Cubs Selective has to do this because it is a uh a stream compacting operation. So it decides, okay, well, these elements in this uh uh sequence, you know, match this predicate, and then I need to move all the ones that matched to the front and move all the ones that didn't match to the back. And so I need to know as I'm going uh, you know, where is the cursor of like where's the next spot where I need to put things into? And that requires information from earlier in the sequence, and thus it's a scan. But I think there was a deeper question underneath this question that I was asked, which is that I think this person was really expressing to me that they felt like array programming languages couldn't express everything that you might need to write a full-fledged application. I think that they were telling me, well, okay, array programming languages might be a great thing to use in one part of my application to uh write a particular uh compute operation, but I can't do everything with them, that I can only use an array programming language uh within a broader project that is primarily written in some more general purpose programming language. Um and I think maybe what they were getting at is that um you know there may be cases where you need to write some scalar uh sort of control logic, you know, like uh some just single-threaded some non-array operation that you know does I/O or does some initialization or something like that. And and they felt like, well, I can't really express that in an array programming language. And so I was uh I was sort of interested in your thoughts about this, um, both about this question of uh can you write full applications in an array programming language? Can you express the sort of imperative uh uh logic for setup and I/O and uh you know stitching together all the various behind-the-scenes things that an application does aside from just compute. Um but also I I was wondering whether I'm missing some ways in which conditional logic can be done in array programming languages. You know, the filter is the one that came to my mind, but maybe there's some others that you know you know of uh that I hadn't thought of. Uh anyways, um I'm gonna be pretty busy this week. You know, um I'm working a full work week and I'm got my family uh to spend time with. So I may be a little bit hard to reach, but uh you give me a call back and uh leave a message if you can't reach me.

Conor

Hey Bryce, sorry I missed your call. I've been in Costa Rica for the last not week, but just under a week for a wedding. Congratulations to the bride and groom. One of the best weddings I've been to. We had a lot of fun. Wedding was on Saturday, we ended up doing a catamaran on Tuesday. Anyways, we are back in Toronto, Canada now. Just got your call and thought I would reply. So, the question overall was what do you reach for in an array programming language when you want to do something like a conditional branch, or you didn't mention this, but another common thing that people reach for in array languages that isn't necessarily obvious how to do is something like a while loop where you have a condition that you're trying to converge to, and it's different than a for loop in that a for loop you know the length of the number of iterations you want to complete. Where a while loop might have some condition like, you know, you're trying to converge to some, you know, threshold, and you don't know the number of iterations you're gonna need to do. So you need to basically check you have some kind of condition. And the short answer to this is that almost all array languages have control structures. And we actually did an episode on my other podcast, ArrayCast. It was episode 32, and the title of it was Control Structures in Array Languages, where we answer this question basically, which is how do you do this? And like I said before, the answer is that most languages like APL and J actually have control structures in them. They're not primitives per se because they're built into the language as keywords, so you don't get these little ASCII digraphs. In J, I will leave links in the show notes for folks that want they represent their control structures with lowercase letters followed by a period. So a couple of them are for dot, if dot, else if dot, and dot, etc. And in APL we have similar control structures, which are I think it's Pascal case, so like if you want a while loop, it's colon, capital W, and then lowercase H-I-L-E, and then there's and while if and if, etc. But for the rest of this, you know, return message, I will read to you from the APL wiki the history section on control structures in array languages, because it is rather interesting. So here we go. Relative to other programming languages, which began to adapt structured programming in the late 1950s and almost all supported it by the end of the 1980s, APL was slow to adopt the paradigm. Adoption by mainstream array languages began in the 1990s, and some dialects such as APL2 and GNU APL have never added support for control structures. Many dialects developed in the 2010s and later also do not include control structures, favoring Lite DFund that stands for defined function syntax in combination with operators such as Each, that is the explicit mapping operator. Edgar Dijkstra's letter GoToConsidered Harmful, published in 1968, is widely considered a turning point in the push for structured programming. At the time, APL programs were written as defined functions using branch for control flow, but programmers began to publish responses considering alternatives in the mid-1970s. Several programmers showed how to use structured programming in current APL systems or modify these systems to better support it. Others proposed more radical changes that would allow the user to define control structures. Experiments to extend APL with algal style control structures also began in the 1970s. This led to APL Goal, first described in 1972, which used names beginning with underlined characters and was supported by a compiler implemented in and targeting APL 360. A similar project was called SAPL for structured APL, and that used reserved words for control structures and was published in 1978. Control structures using reserved words were included in A Plus by 1989. And A Plus, for those of you that don't know, is one of the very first programming languages that Arthur Whitney created, who is famously the creator of the K languages. In 1994, they were both added to J, aka APL 2.0, with a dotted syntax such as while dot and to APL Star Plus 3 using the colon prefixed syntax, aka capital W H I L E, that has since been widely adopted in APL. Dialogue introduced similar structures in version 8.0 in 1996. They also appear in SACS, APLX, and NARS 2000. Newer APL dialects such as NGN APL, APL4, and Zima APL often discard control structures as well as branch on the grounds that DFunds, along with operators like H and Reduce or Recursion, allow similar functionality. Such a possibility was not available in the 1970s because APLs at the time did not allow arbitrary functions to be operands and was not generally considered before the rise of DFunds and tacit programming in the 1990s. APL, which is a APL implemented in Common Lisp, does not support control structures on the grounds that April code should be embedded in Common Lisp, which can handle control flow better. BQN also does not include predefined control structures, but its first class functions and list literals allow a similar syntax to be achieved without extending the language. So that is the end of the history section. In general, the state of the art in languages like BQN, it is a more functional language and allows you to do things like building up list of functions and then using your mask that you described earlier to then basically execute conditional logic and functions based on the mask that you build up. So a common thing you can do is just build up a list of two functions and then a mask that's either going to be a 1-0 or a 0-1, and then you can execute one of those functions depending on which of the masks you build up. And then PQN also has support for recursion and things like that. And it's also an interesting comment that they made about April, which is something I guess a little bit more akin to what you might be doing in the GPU programming world with libraries like Thrust and Cub. You're gonna execute your kernels by invoking functions that are provided via these libraries. But if you need to do sort of these conditional logic things, you still have access to everything that comes with C because these are just CUDA C libraries. That being said, within this history, it is clear that certain APLs along the way never added any support for any of these structured programming control flow statements. So it is definitely possible. And one of the operators that wasn't really mentioned here is the power operator, and that gives you the ability to basically do the equivalent of the while statement with a pattern called repeat match or power match, which basically a power or repeat operator, you can basically put a function to the power of a number. So if you want to repeat something ten times, like multiplying by 10 or squaring something, you can do that with the power operator and then the literal number 10. And that kind of mimics a for loop. However, if you want to mimic a while loop, you can use the power match pattern where you include basically a conditional statement along with your power operator, and now you're gonna repeat whatever function you've paired your higher order function power with until it converges and this uh predicate or condition is satisfied. So recursion, the power operator, and masks basically give you the ability to replicate everything that you would want to do in a typical imperative programming language. Hope that answers your question. Interested to hear your thoughts on the history section and everything that I just mentioned, and hope you're having a good time in Florida. Hear from you soon, buddy.

Bryce

Hey, just got your message, so I thought I'd try to reach you. Sounds like you had a fun time in Costa Rica. I hope you didn't get sunburned. Did you get too much swimming? We're uh about to leave to go play some mini golf, and I have a feeling it's not gonna end well for me because I am quite clumsy. So it was really interesting to hear uh uh about all of the history of uh control flow in array programming languages. I I hadn't even thought about um like while loops um when uh when I was originally asked this question. Um you know there's another uh example from the world of C, which is um in the world of senders, um there is this sender adapter called repeat, where you give it a sender chain and then a count, and it performs that sender chain um in times where n is the count. Um and presumably you could also make a uh a while form of that too, um, where instead of taking a uh uh an a count, it takes a predicate for when it should stop, and that predicate gets sent the uh the value from the underlying sender change chain every uh iteration. Um I it was really interesting to hear that remark about April, um, where the creator sort of said, well, we don't need to have this in April because it's meant to be embedded in Lisp. Um I wonder how many uh array programming languages were designed to be embedded in other languages. If you think about it, uh ranges and like the range adapters and the senders and the sender adapters, that whole like little piping syntax. That's sort of like an array programming language that was designed to be embedded in C. So I had another question for you. Are you familiar with the thrust gather and scatter algorithms? I was looking through a couple of the thrust examples the other day, trying to find some uh examples that I could use in a paper that I'm writing about C asynchronous parallel algorithms. And I noticed that a lot of the um thrust example algorithms use gather and scatter. Um and it's I don't think they're algorithms that we've talked about in great detail uh on the podcast before or that we've used. So ThrustGather, it takes um as an input a range of uh uh a map, um, they call it, and then an input range, which uh has to be a random axis iterator, and then an output um iterator. And you take that map range, and for each element of that map range, you uh take the course, you you use it as an index to the input range, and then you copy that element to the uh to the output iterator. Um and then scatter, scatter it does sort of the opposite, where it takes um a range and then it takes a random access output iterator and also a map. And then for uh uh for every element in the input range, it uh it copies it to the output element corresponding to the the index in the map that um is associated with that input element. Um so they they kind of remind me of of the by-key algorithms in uh in thrust. They're almost sort of like a copy by key, maybe. Um and so one of the places where these is are used in one of the examples is in the thrust lexigraphical sort example, um where it does a uh you know a lexographical sort, like you want to sort like some tuple of like three elements where you want to sort it by the first by the middle element and then by the first element and then by the the third element. And the way that this thirst example does it is it creates this permutation vector, and then it uh it does this update permutation step where it does um uh a gather um with of the current reordering um uh using the the permutation uh vector as the uh as the map, and then the the keys of your original input as the input to the gather, and then um it uh it outputs to some temporary storage. And then it does a stable sort by key of the temporary key storage, and it the output of that stable sort is this permutation vector. Um and then you do this update permutation step um in times where n is the number of uh You know, columns that you want to sort by. Uh if you think about this in like Excel terms. And then at the end of the result of that, you have this permutation vector of the indices. I that I need to apply to the thing that you're storing. Um and there's a couple other examples that use this gathering algorithm. And I just thought it was quite interesting that this is never something that's come up uh in our chat. Um you can imagine that uh gather scatter are used for things like um stream compactations to implement something like copy if. Uh but maybe we never have talked about it because we we just have the the optimized copy if available, and so we just always use that copy if and we never really talked about how it's implemented. Anyways, I was just uh wondering if you'd have any thoughts about that. You ever used the Rust scatter or scanner? Anyways, hope to hear from you soon. Talk to you later, buddy.

Conor

Good to hear back from you, Bryce. Hope you had fun playing mini golf. We'll have to revisit how that went in the next episode, as I believe this will probably be the last message. So interesting that you bring up the scatter and gather algorithms. I can't actually recall if I covered them in my Thrust versus standard C algorithms talk from I believe it was GTC 2021. But if I didn't cover them, I at least briefly mention them. And I am familiar with these algorithms. I don't reach for them very often, the same way that I don't reach for their equivalents in APL very often, but they I'm not sure if they come from APL, but they have exact equivalents in APL. And the sort in uh example that you came up with is actually interesting because when you are trying to sort something in APL, you actually don't have a sort primitive. You have two different primitives that you compose together in order to get that sort. There's a couple different ways to do this, but the way that I'm going to explain uses bracket indexing and a primitive called grade, grade up and grade down. And what grade up and grade down give you, if applied to a rank one vector, is a permutation of indices that if you index into an array to resort them by that sort of indexation, if you will, you end up with a sorted rank one vector. So the way that you spell this in APL is if you have an array which we'll call X, the way you spell this is X open bracket grade up x close bracket. And what this does is the set of brackets is what's called bracket indexing, and it is the equivalent of a gather in thrust. So it's basically given a permutation of indices, bracket indexing is going to permute your rank one vector, aka X in this example, based on the permutation indices. And scatter has also a equivalent in APL, and that is indexed assignment. So in the sort example where you have x bracket grade up or grade down x n bracket, that's just an expression that's gonna return you a rank one vector. But you can also do indexed assignment where assignment in APL is a left arrow. And so if you once again have a vector X, you can go X bracket and then a set of indices. We'll call it, you know, two, three, four, which is gonna be the second, third, and fourth indexes or indices of that vector, end bracket, then you have your left arrow, and then whenever you're doing indexed assignment, you have to have an array on the right that matches the length of the number of indexes that you are trying to assign to. So this is basically what scatter does. You want to kind of do the opposite of a gather. A gather is similar to a copy if if you want to think that like copy if is a compaction where you go linearly across your vector and then you're doing a compaction. It's like a filter. You're just getting rid of elements, but they always stay stable, like the the order always stays the same. Whereas in a gather, it's like a copy if where you can rearrange, it's no longer going to be stable. You can end up with you know elements towards the end that are at the beginning, and that's the whole point of a gather. It's kind of like an unstable copy if, if you will. But a scatter is completely different. You're basically trying to send off values to certain locations in a rank one vector or some kind of arbitrarily ranked array. And this is what you can do in APL with indexed assignment. You have your basically left arrow, on the left of that left arrow, you're gonna have an array with bracket indexing and some indices, and then on the right of the arrow, you're gonna have a rank one vector that is equal in length to the number of indices, and then whatever values correspond. So in the example we had x bracket, two, three, four, n bracket arrow, and then if I had the values 10, 20, 30 in an array, which is just space delimited in APL, those values will be will be sent to the second, third, and fourth index of your vector. So hopefully that makes sense. Uh as I mentioned before, I barely reach for these because even when I'm coding coding an APL, I don't like to use bracket indexed, bracket indexing for the gather. Uh there are other ways to basically index into rank one of rank one arrays. One of them is using the squad operator. I don't actually know the actual name of it. But these are there's typically alternative ways to spell these algorithms that I find more preferable. And it's kind of considered I don't want to call it like old school APL, but like for instance, in BQN and in another array language cap, there are just sort primitives. So you don't need to reach for two different sort of language features or primitives, one being the grade up and grade down, and the other being uh bracket indexing. You can just use the sort primitive and it does what you want. Similar to how you could build up a sort if you wanted, I'm sure, with either thrust or cub primitives, uh, like you spelled out in that lexica graphical. Although at the end of the day, you still passed it a stable sort, I believe. But I would prefer not to have to use two different things if I can use one. There are certain cases where you need both, but in most of the common cases, or at least the use of cases that I've come across, you can get away with just using the basic sort primitive. Anyways, I think that's where we'll leave it. That'll wrap episode, I think this is 167, and we will chat in episode 168, hopefully both in person. Be sure to check your 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.

Bryce

Low quality, high quality, that is the tagline of our podcast.

Conor

That's not the tagline. Our tagline is chaos with sprinkles of information.