Transcript
Thanks to Rodrigo Girão Serrão for producing this transcript.
Adám Brudzewsky [AB] 00:00:00
I'm sure it's simpler to use a normal knife, but you take an array language and you've got a Swiss army knife.
[Music theme] 00:00:08
Conor Hoekstra [CH] 00:00:17
Welcome to the 4th episode of Array Cast. I'm your host Conor and we are going to quickly go around and do brief introductions before we hop into our topic for today. So we'll start with Bob, then hop to Adám and then go to Nick.
Bob Therriault [BT] 00:00:31
I'm Bob Therriault and I'm a J enthusiast. I've been programming in J for about 19 years, coming up on 20, but I'm not a developer. I'm not a professional programmer.
[AB] 00:00:42
I'm Adám Brudzewsky. I work full time for Dyalog Ltd., doing APL. I've been doing APL all my life, but professionally for about 7-8 years.
Nick Psaris [NP] 00:00:55
I'm Nick Psaris. I've been coding in q since 2006. It's my favorite language to to develop in, but these days I've been migrating to Python as well.
[CH] 00:01:09
And as mentioned before, my name is Conor Hoekstra. I'm your host and I'm your resident non array program language developer.
I develop in C++ professionally, but I'm a huge fan of APL and J and I know a little bit about k and q. But as this podcast goes on, I'm sure I'll learn more and more and more so our topic for today I believe is going to be talking about what an array is, and more broadly, what is array oriented programming or the array paradigm.
Because this podcast is all about the array programming paradigm. Yet we haven't actually talked about that too much.
We've talked about why we love APL. Some things that you know have might have been holding back that paradigm, or some of the languages.
And also you know what is looping sort of versus iteration, but we haven't talked about what is an array so.
It's an open ended question. Maybe we'll kick it to to Adám and then from there everyone can share their thoughts and we'll just see where this topic takes us.
[AB] 00:02:09
Well, I'd like to quote the late John Scholes who was a great and innovative APLer who was there from the beginning at Dyalog in creating the Dyalog interpreter.
And and I asked him not long time before he passed away, what I should say when people ask me what's an array?
And he said an array is a rectangular collection of numbers, characters and arrays arranged along zero or more axes.
And I guess we'll we can get back to the details of that, but that's how you put it.
[CH] 00:02:47
Bob, Nick, do you have thoughts you want to add from the J or K or Q perspective?
[BT] 00:02:52
Well, I think that's a great definition and the only thing I kind of add to it is.
Why? What does an array give us? And I think one of the things I was thinking about is just being able to put values into specific positions, gains you a whole lot of information if you even think about things like ordered pairs for coordinates, having one position as opposed to another. Well, those two positions can be represented as an array and as soon as you have that constraint of meaning according to position, you have a lot of power that anybody else would have to sort of carry through their program. Well, it becomes. Once you've defined that.
And with it comes a lot of mathematical advantages to that you can do with arrays because there's properties that go with that kind of a structure as soon as you define it, as soon as you constrain it.
[NP] 00:03:48
I'd say that that from my experience, the definition array doesn't have such a strict, strict notation. You know, I think of a difference between an array and a vector, where in an array would just be a a list of items and a vector would be a list of the same types of items. And in q everything is a vector. Everything is a 1-dimensional vector and you can just make a collection of vectors. But the the term array doesn't have special meaning in in the q community.
[CH] 00:04:21
It's interesting, yeah we. There's probably going to be a bunch of listeners 'cause I know. I know there's some C++ devs listening and array and vector are both vocabulary types in C++ and they have specific meanings. An array is a compile time fixed length list. Like an array, so you have to specify the length of that array at compile time, whereas a vector is like a dynamically sized array that ends up on the heap.
So if you need to add items to it or you know erase items from it, you can. So I guess we should clarify. Like depending on the language you're coming for from, definitely set aside whatever your notion of array and vector are here, because I think in the array languages all we have is array. I guess I I just learned that K has this idea of a vector. Does that translate?
Is there a mapping of the difference between array and vector in k or q to APL and J? Or are those just both arrays Adám?
[AB] 00:05:18
We we sometimes qualify our arrays. It's from the programming perspective, there is not really any difference but in APL's we'll sometimes sometimes talk about homogeneous arrays or heterogeneous arrays and where homogeneous means that every item in the array and every element of the array is of the same, not just type but structure as well, since elements themselves can be erased.
[CH] 00:05:51
Is it the same in J bob? So we just we call them arrays and it's either homogeneous or heterogeneous.
[BT] 00:05:58
Yeah, I think in arrays I think I'm guessing from what I heard Adám say, is the, I think it feels to me more in J that everything is homogeneous because once you have an element of an array, everything is that element that you you can't have ragged array, so you can have different lengths of dimensions, but you also everything, everything in an array will be that type, and once once you've defined a. In fact, if you do make a change to an array and you do some operation that changes the type. It changes the type on the entire array.
[CH] 00:06:34
So is it worth pointing out? I know that the the the names of these things are different depending on whether it's like the IBM APL 2 or the sharp APL plus, but the the rank array. So if you have zero rank one rank, two rank, these sort of map to different names.
That can also sort of be confusing. Do we want to walk through those, or should we skip over that and not confuse our listeners? Bob?
[BT] 00:06:56
Well I was. I was looking at some of this and it was really interesting. It was an essay I read by Roger Hui.
And through the whole essay he does. The people that think that what we call atoms or scalars scalars often commonly used, are they arrays, or aren't they?
And and like a single number with no dimension would be an atom or a scalar. Then the question is, is a scalar an array?
And he had the people pro which is just about everybody. And then there was one instance he could find of somebody saying actually an atom isn't an array, and then it turned out that that person felt that kind of misspoke and they didn't think that way anymore.
The interesting part was an addendum to it was Henry Rich put in in terms of NuVoc, which is the J dictionary.
He's allowed that for definition purposes, just to be able to be more clear, he'll separate atoms from arrays, in other words.
If he wants to say atoms.
It gives him a specific non dimensional value if he wants to say a raise he excludes atoms even though he admits that they are arrays.
But in terms of teaching, it's easier to explain to a person a single value as a scalar or an atom, and then the multiple elements or multiple scalars is an array, but that's actually just an educational device that he's put in. It makes sense. It's easier for beginners to understand, but when you dig underneath like the covers, scalars are arrays.
[CH] 00:08:34
Adám, Nick, do you want to comment?
[NP] 00:08:36
I think in in q in in the underlying implementation every every every variable has a type and you can ask for the type and you will return a numeric value.
Uh, if it's a negative number. That means it's an atom. What's stored in that variable is in at.
If it's a positive value below a certain number, it would be a list, so it's either an atom or a list.
Of course, as you go up higher, there's the type for tables and the type for dictionaries. But the first, the first 10:15 integers, positive numbers indicate that it's a list, and if it's exactly 0, it means it's a mixed list, so you have a list where every element of that list can be a different type itself.
So within that list, the first element could be a type of an atom, and the next element in that list can be a vector so there is. There's no strictness on what's in a mixed list, it's it's. It can be anything.
Uhm, so there's a distinction between lists, atoms and a mixed lists.
[CH] 00:09:41
Adám?
[AB] 00:09:41
I think it's important to understand why we look at, and we can call them atoms or or units of data. This the smallest unbreakable units of data like a single number or single character. Why do we look at them as arrays?
And I think it's it's it goes both ways, the the languages and I should probably single out APL and J and related languages and they have these built-in functionalities, but whatever name we can call them algorithms and they apply in an identical manner to arrays.
And it doesn't matter then whether the array is an atomic number or a collection of numbers of some shape.
But my understanding and Nick, you should correct me if I'm wrong. Is that very often the builtins in in k and q have a radically different meaning if the argument is an atom, or at least some. Yeah, you can't. You can't even have a a larger collection of data that has been packaged up as and as there's no such thing in k and q, but you can have that in in J and APL.
So I think I would conclude that in k and q there is a difference and maybe atoms are not arrays whereas in, J and APL they most definitely are.
[NP] 00:11:10
If you take a string, for example, there's operators that apply to a string that you know the like operator, and you know you can. You can consider a string as a vector of characters.
But because some operators can't work on, uh, they work on that vector. That string as an atom if it treated as an atom, there's a lot of code that you would write where you try to make sure that the function works on both atoms and vectors, but when it comes to a string you can't, strings are not atomic there is no such thing as a string. A symbol is an atomic string, but a string is just a character, a vector of characters, and So what? You end up having to do in in your code is the very first line.
As you have to check the type of what's being passed in and if it happens to be a string, for example, uh, then you need to.
If it's a list of strings, then you can't run a uniform function over it. You would have to then recursively call yourself for each of the elements of that string list and that adds a little bit of a mess in into the implementation of functions that you would hope could treat all types, whether atoms or vectors the same when it comes to strings, they you have to special case them.
[CH] 00:12:24
Bob?
[BT] 00:12:24
Yeah, I think one of the advantages of having the atoms consistent with the arrays is that as you're saying Nick, you have to treat strings and things like that differently with with J, and as far as I know, APL. Once you're working with atoms you don't have to make any. I mean they fall right down to their shape and their ranks and all other thing they fall right into the way the operators work on them.
There's there's nothing extra you have to do, although it's useful when you're trying to work with them because they have what feels like a slightly different property.
For instance, if I take an array and I multiply it by an atom, I don't have to worry about having the dimensions fit properly because an atom fits with anything.
So if I have an array of four by four matrix and they're all five's and I multiply by 4, the item four, I'm going to get 20 in every position, just bang, that's it.
If I make that first 4 a list, so I make it a 1 dimensional list, so it's a 1 atom list.
Now it's a list and now I can get length mismatches because as soon as I put a dimension in there now I have to start making sure dimensions fit, but when even then it's all consistent with the way the operators work together, and that's a real the single value list is something that often trips people up starting in J anyway, because it doesn't look any different. It's just got a dimension, whereas a scalar just has an empty.
It has an empty shape. There's no shape to it. It has no dimension.
[CH] 00:14:13
So are there any any array languages that treat “scalars” as 1-length arrays?
Or like 1 length rank 1 arrays like I don't think I've run into that. So like the example that I'm thinking of is like to extend Bob's example, you've got a four by four matrix of fives.
You multiply it by 4. Say you have a list of two fours. If you do first on the 2 fours, you're going to get back a scalar 4.
And then you can multiply that by your 4 by 4 matrix, no braino.
And if you do drop one, though, you're going to get back a list of length 1, correct? It's going to be.
It's going to be a rank one, so it's either referred to like earlier. We were calling 0 rank arrays, scalars or atoms.
The other names for rank one arrays or lists or vectors so you can get back a list of length one. And if you try and multiply.
Not by your 4 by 4 matrix. It it's not going to work, but from what I know almost every single time I've played around with J, APL or k or q or, I think even Julia or sort of those languages they treat scalars as scalars like they're not actually treated as one rank arrays with just a single element so and it sounds like there at some point was an implementation that did it that way. Adám?
[AB] 00:15:40
No, there aren't any that I know of either. I it happens quite often when I teach new people API that they come and say you know, why make a difference between a one element list and a scanner, but they it has huge implications if you actually try to to draw the conclusions that come out of it.
Results of various things. It just won't hold.
Uh, I think though that Matlab, which you could call an array language, at least in some senses of that word and that term, it treats everything by default as a matrix as a 2 dimensional thing, and even a single number will be treated as a one by one matrix, and then it makes concessions to various things.
Because of that, but then necessarily they'll have interesting drawbacks.
And there is a concept in in APL historic thing called Singleton extension. So what you described before about taking a single number and add them together and multiplying, say, with a matrix that's called scalar extension. We take the single scalar and we extend it to the full shape and structure of the matrix and then we can multiply elementwise.
Uh, for various historic reasons, APL's have tended to have also Singleton extension, where they said if there is a mismatch between the shapes but one side is a one element vector, or even if one side is a one element, any array. We'll treat it as a scalar, but it's considered by modern scholars of array theory as quite an abomination, and not something you should rely on, and there are definitely plenty of cases in in all implementations that do this where it's they're not the same.
[NP] 00:17:30
The term array these days I think everyone is that familiar now with tensor flow and so then the question is what is it?
And I think that the way the array languages use the term array now in machine learning, everyone referring to as a tensor.
What's the the rank of the tensor? And I think if you map that in your brain you you can kind of get the concept of what an array is.
[CH] 00:17:51
Yeah, I if Nathan from Amazon. We worked together. Nathan, if you're listening to this one time he tried to explain tensor to me for like 30 minutes and I was so confused.
I was just like wait what and then at some point someone just said oh a tensor is just a multidimensional array and I was like what how did that? How did I not get that? After 30 minutes? We just. I guess they the data scientists were like saying multidimensional array is too many syllables.
We're going to shorten that to tensor and and so yeah, anytime you hear about someone talking about a tensor library, they're just talking about some APL derivative basically.
So we have we have atom and scalar for zero rank list and vector for one rank and then matrix and table are the two that I've heard for two rank you mentioned table earlier, Nick, is that the same thing or is that different? Is table repurposed to mean something else in q/k?
[NP] 00:18:44
Well, I mean in under the hood, under the hood a table, all it is is a matrix with a key tacked onto the front of it.
So you have the the columns on the top. Those columns is a vector of symbols, so you can think of as a dictionary right the the column names are symbols and the value of the dictionary is a bunch of vectors of columns and so everything is a list, whether it's the symbol, the column names or symbols, but it's a list of symbols. The matrix itself is that the matrix itself is a list of vectors of data datums.
Uh, and then the the concept is that a table in q is a flipped dictionary of lists. So you can build it from the ground up. You can first create your lists of lists. Then you create a dictionary from that by appending the keys to it.
And then you “flip it”, and flipping. It doesn't actually transpose the data underneath it just tags it. To say that this is no longer a dictionary of lists it is a table so that I can index into it by column or by row and it would treat it differently.
[CH] 00:19:51
And does that have the same length? So it's like a regular matrix and that each of.
[NP] 00:19:55
Yes, if you've tried to flip it and the lists of the each column has a different length, you will get into trouble. It won't allow you to do it.
[CH] 00:20:03
Interesting, so that actually sounds very very similar and do each of the elements in the lists have the same type?
[NP] 00:20:09
Everything is a list. When ah and as I define it can be a mixed list or it can be a uniform list, so it doesn't matter. It doesn't matter, it can be anything.
[CH] 00:20:16
OK, interesting, Adám?
[AB] 00:20:17
Well, it's actually interesting the the way I look at that is kind of like syntactic sugar.
As Nick said, it's all arrays under the hood, right? And and we at Dyalog at least we call this concept an inverted table so you can have just a plain matrix and it could be mixed data types. But there are performance benefits.
And possibly some logic benefits in considering a traditional table where you look up things, records on the go across and columns of, of matching data type or vertical in and if you instead store that and and look at it as a list of lists but column lists, that's important. Then you can. You can have some benefits and we have some some things in the interpreter that take care of running that super fast, and that's basically what's built in in k and q is just syntax to do that, and a dedicated data type, but underneath the hood that's exactly what's happening, and it's basically just column store databases.
Where if you know that a column has a consistent data type, then there are lots of optimizations you can do.
[BT] 00:21:35
Well, one of the things when I was when I was looking into this one of the sort of the fundamental things of the way J certainly looks at language of the arrays is that it's in what's called row major order, so that if you took all your values and you strung them back out, you'd do a row at a time, and so the first row would go first, and then you'd follow the 2nd row.
Now my sense and I'm sort of throwing this up as a question 'cause I've I've heard about and I've used the inverted tables a lot, or the inverted arrays a lot I'm guessing, are we actually at that point? Flipping it to go to column major order? Is that actually what's happening? Is that where we gain our advantage?
[AB] 00:22:11
But it's not, it's not only that, because the important thing is that if you had a homogeneous array of say numbers or characters, then for best performance you want to store them in contiguous memory in the computer, and you can't do that if you, even if you were to transpose the table and then you flatten it out, you ravel it, you can call it.
Then if the columns don't have the same data type, you still can't do that, and if the first column has, say, a character and 2nd column has numbers, then if you want to transpose it, you end up with the first row being characters and the 2nd row being numbers, and then when you flatten it out you now have a one long list which would be stored in memory, but there's a break in the middle where you switch type and that means that you cannot keep an efficient storage where you just in memory.
You remember what the shape is at this particular address, and then what the data type is, and then the raw data. You would have to mark or indicate every piece of data with its type, and that's very expensive.
[NP] 00:23:22
You know you unwrap, unravel it the data structure into one long list. Does that actually happen? Is that how it's stored in memory?
Because in q it is not. Each vector is just a vector and a matrix is just a list of vectors.
So when you want to parallelize your code, you can each a function across every row and it will take every vector by itself and apply the function.
But it sounds to me that what you're saying is in, in APL, things are stored maybe in like a Fortran style or something where where everything is just on end up to itself, is that right?
[AB] 00:23:57
Fortran or C for that sake, yes, uh, if the array is homogeneous and just consisting of raw atomic data, then as as far as I know, all implementations of, or at least all serious implementations of APL and J related languages, they have contiguous raw memory.
Like that which makes super efficient. Both storage and access. You can even go vertically just with a stride, but it also makes a real difference.
It's not just under the hood, it makes a real difference in how we use their arrays. So if you make what you would call a matrix in k or q.
And and then you apply something. Some function transformation function, something within within each, which is like a map you looping over it.
Then it would apply this function once on on each row, because it's just a list of lists, whereas in APL and J it would go in and apply it directly to every element in both dimensions of this matrix. And this goes to further in all dimensions as many as you have.
[NP] 00:25:05
But I think I think this this might come down to a performance issue and you say yes on small matrices, but once you start getting relatively large.
Uh, the fact that you might not be able to allocate a matrix that is that big in the free memory of your process, you run into problems.
Meanwhile, in a q process, if each vector the amount of memory you need to allocate when you're modifying it is a lot smaller because it's just the first vector.
You can find some, you know a chunk of memory that hasn't been reused hasn't been used, and you can allocate it.
It seems to me much more flexible to have a bunch of smaller lists than one massive matrix of data, and then.
If you want to copy it or modify it, you know you know you have to allocate a huge huge chunk of data, uhm, to to continue.
I think that's one of the performance problems with pandas. Is that the matrix is similarly organized is if it's the same type it tries to allocate a massive block of data under the hood instead of a bunch of smaller vectors.
[BT] 00:26:03
And I guess in some ways the way J gets around that or or simplifies its storage issues is when Adám was talking about having multiple types within an array that doesn't happen in J, so you don't have that.
You can't, you can't create that as soon as you've changed one value in the array, the whole array stays that same type, so you don't have that particular issue, but you do have that constraint.
[AB] 00:26:27
But it's you can also say it's conversely, yes it's true. And though today memory constraints are usually not what the problem is, the the problem is usually memory throughput speed. In fact there can be. It cannot pay off to implement a faster algorithm because the computer's memory cannot feed enough data to the processor to keep the process of busy.
So so memory constraint and efficient storage and transfer of memory is actually really important and you can. But you're right, yes, if you cannot.
If you cannot allocate enough contiguous memory, then that's a problem. We could also turn that problem on its head. Imagine that we have a very narrow but tall matrix.
Then if it was stored as a list of lists like in k or q, then you would use a disproportionate amount of memory just for pointers and you'll have a long list of pointers and every pointer is say 64 bit these days and it just goes to somewhere else where you store maybe only a couple of bytes of data and that means if you then wanted to say flatten that or do some transformation on every element or loop over it the the computer will be very busy doing pointer chasing, whereas with the contiguous format it can literally just read the memory contiguous memory, feed it to the processor and get it back into a different place in memory.
[NP] 00:27:52
I think that the benefit for at least the use with q is that because columns in it, because everything is a vector by themselves, each column of the database can be mapped into memory as its own.
It is a pointer, but in this case it's a pointer to memory on disk and it doesn't have to copy it all from disk into a continuous list of memory into memory, and I think that's that's in some sense where an advantage occurs when when you have an in memory table and it's conceptually the same as an on disk table, each of the vectors are are distinct. One just happens to be in memory and one is physically mapped on disk.
[AB] 00:28:29
Well, that's where we have the option to use inverted tables.
Whereas you cannot do a contiguous multidimensional array in k or q because the the array model simply doesn't support this concept.
[CH] 00:28:41
I guess we've been talking about, you know what what arrays are from, like you know, the definitions of atoms and scalars up to you know two rank matrices and tables.
And also you know how does this map to implementation. You know whether things are stored on the heap with pointers or on the stack.
Let's let's step back and and answer the question so so we have this. You know different flavors, but at the end of the day, it's sort of all arrays.
I guess q it sounds like and k, have a couple of different flavors and you even mentioned dictionary at one point Nick, but maybe we'll we'll pause on those for a second. Just ask what do what does an APL or or a J programmer or a k or q programmer get by only having this sort of one data structure?
Because any developer coming from any other language has, you know from C++ you've got, you've got your queues, your stacks, your deques, you've got your node based containers, your your hash maps.
You know, if you go outside of the standard library, there's even, you know, flat maps, which is a hash map, but it's implemented with a vector under the hood. A ton of different data structures that you can choos to solve the problem of your choice, what are you know, array programmers? What's the advantage that they're getting by only having like this single data structure?
[NP] 00:30:09
I, I mean, the fact that everything is in array means that the operators that are defined in the language can work on everything that you've got.
So if I, if you know I take first or last, you know operators or reverse or all those things you don't need extra functions to manipulate a special kind of dictionary.
Special functions on a table. Special functions on the list all the same primitives work on all the all the data structures.
Now we mentioned dictionary and you might think OK, well, the dictionary might be a, you know, a binary tree or something, but no. Again it's just a list, it's a list of keys and a list of values bound together. So then the question is how do you get performance if you can't change the data structure? The reason why you mentioned you know linked lists or or q is in some sense because you want the performance to be better for a particular use case. With you know there's a hash map or or a flat map.
In in q you create a dictionary and as I indicated, the keys and the values are both lists, but under the hood you can say you know what these keys are unique, and then if you put this attribute on it, they will store that hashed the hash look up for you as an added, uh, data structure along with the dictionary you don't have access to it, but the minute you apply that attribute, you're telling q that this in fact is a list of unique keys and I should use a hashing algorithm to find the row that I need.
So instead of changing the data structure, you keep the same structures but add auxiliary meta information inside the language to to handle it better.
[CH] 00:31:49
Bob?
[BT] 00:31:49
Yeah, J would be a tremendous disadvantage if you could only, have a single type in an array, which is true, but the way we get around that is that you can box or nest those values so you can create any structure you want and then have those as the elements or the atoms within that array.
So if I wanted to have have information that was not only numeric but character, I can't put them in the same array, but I can box them together, so each then becomes boxed numeric, boxed character and now my element is a pair of boxes and I can do that.
So that so that's how I mean. The constraint is that I have to stay all within the same type, but the way I get around that is I can box anything and now I have a common type and then the contents of the box can be the different types.
[AB] 00:32:44
Well, for a long time in APL it has been common to not have that constraint. That doesn't mean you should mix your data, because underneath the hood there will be pointers going here and there to deal with the fact that you have mixed data.
Which I think makes APL the most flexible, but also gives the program writer tools to write code that doesn't have so good performance, but I think I want to go back to to Conor's question. You're saying? What does it provide us as array programmers?
To store things in arrays, in multidimensional arrays, and even in k and q, there are plenty of built-ins that apply to arrays as a whole that you don't see in in non array languages.
I think that humans have this orthogonal or rectangular nature. We like making things rectangular. Just look at all the things we build and produce.
Unless somebody deliberately wants to evoke some special emotions by making a house that has all strange angles, we for practical purposes, we tend to make things rectangular.
And and even our computers are rectangular. There was a great presentation by somebody called Martin Thompson at a Dyalog user meeting called “Rectangles all the way down” where he's describing how how the computers work underneath, and how it's all actually stored as rectangles or conceptual rectangles in in the computer and and well, humans built these computers right the way we think about things, say the relationship between two variables variables in the sense that it's a value that can change and makes a table. We teach the children in school multiplication tables. We don't teach them multiplication lists of lists, right?
We give them an entire table that's formatted like a table, and they learn that as a table and the the way we think of things is as a table.
And people with bright minds play chess. It's a matrix of values. Which pieces are in which which positions. And I think that what the array languages do, and we we touched on this in the in our first episode on what makes the array languages so great is that it enables us to to think about the things that we do with the problems that we have and express algorithms in terms of of movements of data manipulation, mangling of data in ways that not only fit the human mind, but actually fit the machines as well. So we can.
We can say that it now allows us to write sympathetic code that's sympathetic both to the human mind and to the computer, and that gives us great performance both on the computation side and on the man hours.
[BT] 00:35:55
I think as well and and on the so the the human side of it is kind of a form of chunking, if you think about if you had to track every element that was in an array, you're going to have a long list of you know, scattered dots so.
OK, but as soon as you organize it into an array, you're going to have a certain number of rows.
The length of the row will be a list, you know, but if you think about, you know like a table or even a brick, which is a number of tables sort of stacked on top of each other. As soon as I say the dimensions are 3 by 4 by 5, you immediately know you've got 60 elements because you just have to multiply those dimensions. It's a way of chunking the information and then as soon as you can do that sort of thing and you can manipulate, say, a row at a time.
Now you can, you can do something with that row and then the order can become important. A lot of different things come into it with that constraint.
As soon as you can break it into these parts and arrays are great not only for assembling things and getting information, but also later to be able to break apart and and use in a specific way.
[NP] 00:37:00
I think one of the drawbacks of the way q treats matrices, if you want to define it as a matrix is that, uhm, there's an invariant when you know, as you said, it's 3 by 4 by 5. There's an invariant and you don't have to change, check the dimensions of the of the data structure when you're about to do a matrix multiplication, but on the on the q side, if you have a 3 by 4 table and a 3 by 5 table or or you know one of the one of your lists happens to be longer than it should have been. You're going to run into trouble, and that forces the actual algorithm to do matrix multiplication to check not only the type of every record in the matrix, uh, if it's the right. If it's a float floating point number vector, but also all the dimensions matching.
But if you had a dedicated matrix type, you could record this is a matrix of type float and its dimensions of 3 by 4 by 5, and you're all set. You don't have to check anything beyond that. So definitely as a performance benefit when when you can have these native types that are beyond just a single list.
[AB] 00:38:02
I think there's a benefit also in, let's say we're exploring a problem domain and we're trying to find an algorithm to solve our problem to recognize the relationships between, say, adjacent elements of an array. So for example, something like the nesting level of parenthesis. I think Conor has been doing some videos on that and if we if we look at a mathematical matrix like we have in in linear algebra, then two elements of this matrix, 2 numbers in the matrix that are next to each other, right, left, they are not more or less related to each other than two elements that are above and below each other.
Those that are next to each other, they differ in their index in 1 along one dimension and those are above and below each other, they differ in only in the other dimension, but it's still only in one coordinate that they differ and the relationship there is is the same. And so by having this concept of relationships both horizontally and vertically and along every dimension going to 3, 4, 5, 6, 7 dimensions, however many you need and you can discover things that you wouldn't otherwise notice. If you just looked at it as separate two separate lists so, beginning to solve the problem of of of nesting level of the parenthesis for example, and you would create, just like a multiplication table, you have a string with characters and you have the open paren and the close paren and then you see that there's a 2 dimensional table will indicate a bit, it's a Boolean table indicating on the 1st row where the open parens are, and on the 2nd row where the close parens are.
And now as you see that 2 dimensional table you see there's a relationship between the elements that are above and below each other, meaning those that are open parens and those that are close parens.
And if you just had sat with two different lists in your hands, you don't think of that close relationship. So I think that this array model allows us to even discover algorithms we otherwise might not see.
[CH] 00:40:24
Yeah, it's while you've all been answering, I've been thinking about my Iron Man analogy of of where you know he has this holographic model of his suit and he blows it up and sort of takes things away and I think Adám when you were speaking a couple times ago, you were talking about, you know the ability to reason about and Bob you said something very similar about when you have a matrix or cube with dimensions, it's just it's simple. Like you know, if you have a 3 by 4 matrix, you just instantly know there's 12 elements and and you can, you can see that in your head very easily, or at least I can, but if you have like an irregular array that's supposedly two rank or I don't even know what you call that, but like it's a matrix, but every row has a potentially different number of elements, my ability to reason about that that matrix of data is now like.
It's not simple anymore. I now need to like store, “what's the length of every row?” in my head.
In order to be able to do what Dave Thomas in one of his great talks calls like “Shape thinking” like, the ability to sort of explode a couple vectors into like a couple, one rank arrays into a matrix with an outer product, and then do row-wise reductions and all this, like this ability to think in shapes, uhm, is only possible when you have like these complete arrays. And anyway, this is just an interesting thought that sometimes you solve problems in your head by like thinking of exploding things up the dimensionality and then reducing them back down to a single element, and arrays definitely, at least for me, enable that.
And if you had different data structures that weren't as regular in terms of their structure, you wouldn't be able to, at least for me, like reason about that as easily. Bob?
[BT] 00:42:19
Well, I think also one of the things you gain when you have this structure called an array is you also gain the mathematical tools that you can use with arrays.
So there's things like you know, if they make sense, if you're using numbers, things like determinants, all these kind of strict, you know, strictly defined mathematical terms are things that you can use, concepts you can use that you normally might not think about, because when we're thinking about just adding single numbers and stuff, we're not usually thinking about arrays. But as soon as you move into arrays now you have some power that you didn't have.
You have the power of linear algebra. You can do things with that that you hadn't thought of when you're dealing with single numbers, and it comes back down to this.
Not only is it values, but it's positions of values and those positions are really key when it comes down to the mathematics of them.
[NP] 00:43:10
Yeah, I mean with respect to performance, if you take, you know any, uh, you know, say a neural net or a class on machine learning.
You know the the naive implementation of any of the assignments. For example, in homework assignments would be 2 `for` loops.
You know I'm going to loop around this dimension, then I'm going to loop around that dimension and you're going to be, you know, hurting by that the amount of time it takes to complete it, and if you if your brain was already thinking in terms of vectors and matrices or tensors, uhm you realize to yourself. Wait, I'm just multiplying these together and adding them up. I I should be just doing a matrix multiplication here and and you know, that's that that that way of thinking it.
It's not natural at first, but if if you come from an array language it's you know like I can't possibly. I can't possibly be resorting to a `for` loop here. There must be a better way than that.
That's that's all my thinking, when it when it comes to, even when it comes to Python and things like that, it's like I can't possibly be needing to afford that.
There must be an algorithm out there that will do this much better than I could implement it myself.
[CH] 00:44:08
All right, well, we're getting we still have a little bit of time left, but I want to.
I was going to say this to the end, but I'll say it now. So Nick, your initial response is actually like probably number one reason for liking a single data structure, and you basically articulated a quote from Alan Perlis and his epigrams on programming. Alan Perlis, I think he's come up a couple times on this podcast before, but he's the first Turing Award winner in 1966.
And one of, he has this, we'll link it in the show notes, but he has like these hundred quotes sort of aphorisms, and one of them is “It is better to have 100 functions operate on one data structure, then 10 functions on ten data structures” and and that is. That is basically like exactly what you said, that when you have a very very rich set of primitives that are that work basically like rank polymorphically like, doesn't matter the rank of your array, they basically all work. The the power that that gives you is immense, and it's not something that I've experienced in any other language. You can actually technically argue in C++ here's even like a better version of this 'cause technically in C across the algorithm and numeric headers, there is 100, roughly 100 algorithms, and they actually work on roughly ten data structures because in C++ there's an iterator abstraction that sits between the algorithms and the data structures. So if you have an array or a vector, or even like a hash map. It obviously because it's node based, some of the algorithms don't work, but for the most part you have like this rich set of algorithms that because there's this iterator abstraction it works across all these different algorithms.
But I would. I would argue that the operators, what some people in functional languages might refer to as, you know, your higher order functions your reduces your scans, your keys, etc. The the power that that gives you is not matched in a language like C++ and I have yet to like master all those, all the primitives and all the operators, but already the things that I can do with my limited knowledge of the languages, it's just. It's just yeah you feel like a superhero. You feel like Iron Man. Adám.
[AB] 00:46:26
Well, I'd like to, tied to that. We've got the less data types.
One thing that all these array languages have in common is no dedicated Boolean type, and it may be underneath the hood some optimizations, but conceptually for the programmer, Booleans, are just zeros and ones, not true and false, and I think that's really important, even though many languages.
They do say the word true, the word false for Booleans allow you to do mathematics on them and they will then equate to zero and one the fact that we think about them as 0 and 1 makes it much more nearer to take mathematical approaches.
You instead of counting how many elements are true, we just sum them because true is 1 and false is 0.
So again, we don't need any of those extra functions, algorithms dealing with Booleans and Boolean domain because it's just in the number domain. A number is a number.
And we don't have separate strings, they're just characters and characters behave in much the same way as as numbers numbers do, and so we have a much smaller vocabulary, which means the programmer can master a much larger part of the vocabulary with the same power and yes, then he's Iron Man.
[CH] 00:47:56
Yeah, that there's a, that was actually one of the things that I struggled with a lot or not struggled, but the like filter is a very common operation and not just functional languages, but just your your bread and butter. You know, Python, Java, C++ just got it.
And trying to filter in array language. UM, if you search for like filter in APL or filter in J like the verb, that word does not exist 'cause we don't, we do not have a filter operation. You can obviously filter things in APL. It's called compress, but like typically you know, for instance, if if you want to count the number of like Ls in the word hello, uhm, there might be a custom algorithm in C++ like `count_if` where you can just check but a lot of functional languages you'll just filter and then take the length and in an array language it's completely different. You you basically create a bit mask or a Boolean vector where you check you know is each character equal to L and then you end up with 00110.
So and then you do a plus reduction, and that's like a very, very different way to think. Thinking about like how you typically would filter something in a functional or an imperative language to starting to think in terms of like masks.
And I I was just talking to Aaron Hsu yesterday. We're both attending attending the HOPL conference and he was talking about how encode and decode are like two really important like bread and butter primitives in APL. And I was like “Really?”. Uhm, because the only time I ever use and I never can keep them straight. But if I need to convert an integer into a vector of digits, that's when I reach for that, and then he just sort of like he's his head sank and he was like that's the only time you reach for it, and this conversation came out of actually a follow up to on a previous episode where I had remarked that like what do what do array programmers do when the expression that you need is like 20 characters long and this came up from like you know, generating all possible subsets or sub sequences from a list of numbers and he was like, Oh yeah, that's pretty simple. You just you generate the bitmasks etc. We even brought it up on APL cart and it was it's called “Power set”, more commonly in mathematics.
But then he was like, well, what's what's wrong with this expression, and I was like, well, it's 22 characters long.
That's what's wrong. Like I don't. I don't want to have to copy and paste this, but his take was that like it's actually, not a 22 character expression. It's three like 6 to 7 character expressions that are composed together that are like bread and butter things that array programmers know how to do.
Uhm anyways I just I just thought that that there's these, you know and this sort of ties into the topic of what is what is array oriented programming and and that there's the I don't want to call it tribal knowledge, but it's I think you know one of our co- hosts. I can't remember who said it previously that there's this knowledge in array programmers' heads that hasn't like been documented well in terms of like you know, there's no “how to be an array programmer” book and and it's like how to how to go from thinking functionally thinking imperatively to thinking really the way that like a professional array programmer thinks, but yeah, I'll stop rambling. Bob. I think you had something you wanted to say or add.
[BT] 00:51:09
Well. Just your initial example with filter.
Really, really, I think that's a great example because it to me it's it's, you know you think of filter. You're going to compress, so that's the end stage of it because you're going to take those.
You're going to filter those ones out, but the first step you take can be different in every single thing that you're trying to filter, so it's a two stage process and you think, well, that's really simple.
But that, to me, is sort of the beginning of array programming. Thinking you've got something that can be used in a multitude of different ways, but your first step is to do something to it that will create a Boolean string and then your next step is to compress that and you as soon as you do those two things together, you know you think, well, it's it's almost like saying one and then two, but one can be almost anything you're working with in the concept is when they're put together.
And then you can take it to literally another dimension where you say I'm not only doing the you know the the creating the Boolean and then I'm going to do this with it, but I can do other things with those same operators and and it sort of keeps going and going and that's the sort of thing.
You start working with your, you start working with the operators, you become more familiar with the operators over and over again.
Somebody says, well, have you tried this and encode and decode is a great example, because as soon as you're doing the encode and decode, you're bringing in the power of the base. You know concept in arithmetic.
You can take, you know, a number and break it into whatever you know 60 minutes. You know, base 60.
You could do Boolean. You can do all these different things just by encoding and decoding, and now you've got you've taken your initial value and you've broken it, literally broken into different parts.
And those parts have mathematical meaning, and you can do things with them that you didn't think you could before.
[CH] 00:53:12
Yeah, it's basically exactly what Aaron said. Like his, this was like trying to. We were trying to solve. I actually brought up the Leetcode problem and and it yeah his point exactly was, this 22 character expression if you teach someone. If you walk them through this, you're not just solving this problem, you're you're giving them, it's the whole, you know, teach someone or catch someone a fish, you know you feed them for a day.
Teach someone to fish. You feed them for life and that was what he was trying to argue. And and I actually pushed back a little bit and I was like Aaron I I agree with that.
Whatever you're saying, like it is, it's an amazing point. I'm just trying to solve the easiest problem on this Leetcode contest though, and if you have to take me through just to get the subsets, a 22 character expression.
Like that's not a good like that's such a barrier to entry for beginners when it's like this is the easiest problem in a lot of languages. There's some built-in, you know, subsequences function or subset function, and then you can just brute force it.
Yeah, so the question I I completely agree that like learning you know how to compose these different primitives. You know it's it might be more difficult to solve this one problem, but you have now gained the power to solve a whole category of problems.
The question is, is like how do we make that the onramp to that like easier than it is now? Because for a certain class of problems it's like OK, we're going to solve this and then two hours later. Or maybe maybe if you're smarter than me, it's it takes less time, but then then you've sort of learned all the pieces and now you can go solve that problem.
But sometimes people just want a simple solution that because we don't have this, the libraries and the sort of the package management. I'm not sure if, if folks have thoughts on.
[BT] 00:54:57
Well, when when I was was starting learning J one of the things that was advised is go go spend some time with the phrases or often so it's called idioms.
Just spend some time with those. Play around with those for a while and and I think those become the building blocks that form those larger patterns. Because when you have an idiom and what I was suggesting with filter is almost an idiom. You do something creative, string of Booleans, and then do something else with that.
You can start to see where a very simple phrase that might be 2 step or 3 step. Now you can pop whatever you want into those steps and they still work.
Now you have to discover the things with relating to your problem that you want to put into those positions, but what you've learned by playing with the phrases in those relative positions, and so it's another form of chunking you've taken. You know A then B, then C.
And it turns out B is D, E, and F, but you've figured the D, E, and F, out with relation to your program, or your particular problem, but the A, B, and C, you can do other things with A and other things with C and other things with B, but you're working within that constrain of what essentially initially is that very simple idiom or phrase, and that's why I think it's a great way to learn a language is. Go in to find those idioms because over and over again, they'll be used in at least that structure, even though that structure might be more complex by the time you build it out for your particular problem.
[CH] 00:56:30
I just got a talk idea called “Think different”, which is like the Steve Jobs Apple phrase. I'm not sure if you remember those iPad iPod commercials that were like the white silhouette on different colors when you were saying that Bob, I was like thinking like oh think different.
That's a great talk title, but then like insert into the ad like how with a question mark and then just like APL programmers being like, huh? Just sort of shrugged their shoulders and just do it. Or yeah, that would include the Nike slogan. Just do it and then the Python programmer is just sort of crying, being like we don't, we don't know how to do it and and then they just put up the subset 22 character expression.
Can't you just see it's a 2D code inverse with a you know blah blah blah iota each over and it's it's pretty simple. Just generating the bitmasks and yeah.
[BT] 00:57:16
But when you see that at a primitive level, like if you just see the primitives, it's I don't even it's it's like you know it is and it's like master chess players.
[CH] 00:57:23
It's it's overwhelming, yeah?
[BT] 00:57:26
They talk about looking and they get. They immediately know the layout of a board and they know what they're dealing with there.
They don't need to know the position of every piece. They do know the position of every piece, but it's done in chunks so they they know at another level they know the pattern they're looking at.
And if you know that pattern, suddenly it becomes three things as opposed to 22 things that you don't know how they're related to each other.
[CH] 00:57:51
Alright, well we are at the hour mark.
We want to. I know there's a couple announcements, but before we get to those, is there any last remarks we want to make just about arrays, array thinking?
Or the array oriented paradigm? I mean I I can comment that yeah, even though I haven't fully mastered it, it is intoxicating being on that like learning journey and and it's, it's both sort of like a a win lose situation like it's a win because it's intoxicating while you're learning it. And then it's a lose whenever you go back.
So whatever language you program in on a day to day basis for work.
Because unless if you're Nick and that's what you do for work. Oh, or, I guess Adám as well. If you work with APL or J or k or q mean ignore what I'm saying. But I I'd code in C++ and every once in a while I'm just I'm just like oh, that's sad. I know I know how I would like to do this and then I go type you know 50 characters and hit Enter a few times. A bunch of semicolons and braces, but yeah, it's it's I can, and if you want to experience like the drug that APL is like, you know, head over to TryAPL or you know, for J and k and q as well, but definitely know that that there is. There is a learning curve, and at times you're going to hit a wall, and at that point, if my talk's out, go watch that talk. If not, head over to like the APL Orchard, or any of the forums, but yeah, I'll kick it to the three of you if there's any last final comments there.
[NP] 00:59:19
People often ask me if I've if I've taught my my children q or not and I I definitely have not, and it's not because it's not my, you know, fantastic language, but it's exactly what you say.
But once you teach them that they're not going to look at Python or or C, and be like, why do I have to learn this?
This is so bad this is so hard. I didn't want to ruin them in their classes, so let them discover it on their own time. But yeah, but.
[BT] 00:59:46
And I guess the only thing I would sort of add to all of this is at certain times we were diving into the implementation at a, you know, pretty deep level about how you store arrays and and all these kind of things.
Those are important when you start to get into trying to deal with performance and you're actually writing code that needs to be performant, you need to be thinking about that.
But when you start out learning the language, you don't need to be thinking about that. That's not the way to start.
The way to start is to get in and start to learn the patterns and those flows and what you'll find is those patterns have already been optimized because they're patterns you know know you don't have to work on every combination of every different operator to bring it up to an incredible level of performance.
That's because you know the ones that people are going to use most commonly are going to be based on those idioms they're going to be faster to start with, and then if you really need to go to that next level, that's when you start to look at how the arrays are actually implemented in the languages.
Why for some reason it might be stored in a way and you're thinking of it in a different way. You don't need to start out that way, that's kind of the masters level, but initially just get used to what you're doing in the languages and play with those things and you'll get there and it'll be quick to start with because the language has been implemented that way to make those things quicker.
[CH] 01:01:04
Adám we'll give you the last word and then we'll close with announcements.
[AB] 01:01:09
I'm sure it's simpler to use a normal knife, but you take an array language and you've got a Swiss army knife.
[CH] 01:01:18
No better way, no better way to close it than that. Alright, so I actually totally forgot at the beginning I was supposed to make an announcement about the Dyalog '21 conference.
So that was originally going to be held in person in Portugal in early October, but just I think if it's getting released on Saturday a week ago, or a week and a half ago there was an announcement made that that is going to be virtual the same way it was in in the last time it was held 2020, so it's now going to be Monday 8th to Tuesday 9th in November.
I can't confirm that it's going to be free, but it was free last time, so I would assume that it's going to be. Yeah, Adám's, nodding his head. It'll be free again. I had a blast attending last year.
So it should be awesome this year as well. And then Adám, I think you had one or two other things you wanted to mention at the end.
[AB] 01:02:06
Well, there's an APL campfire. For those that are interested in in the history of APL and array languages on July 4th and then there's still time to participate in the APL problem solving competition. The deadline is at the end of July.
[CH] 01:02:25
Awesome and I think yeah, well we don't mention this every time, but if you want to reach out to us I don't even know all the so we're @arraycast on Twitter. You can leave comments on the posts on the subreddit r/apljk. Bob, what am I missing?
[BT] 01:02:40
Contact@arraycast. You can, you can email us at contact@arraycast.com.
[CH] 01:02:45
Awesome, yeah, so any place you want to leave feedback, we'd love to hear from folks. And yeah, I think with that we will say happy array programming and see you in the next one.
[Music theme] 01:02:55