Transcript
Transcript prepared by Bob Therriault and Adám Brudzewsky
[ ] reference numbers refer to Show Notes
00:00:00 [Troels Henriksen]
Yeah, so you spent the last episode discussing what are array languages and to me array language is a social definition. So my definition would be that it's an array language if you get to talk about it on array cast.
00:00:15 [Marshall Lochbaum]
Well, he's got us there.
00:00:18 [Music]
00:00:28 [Conor Hoekstra]
Welcome to another episode of Array cast. I'm your host, Conor, and today with us we have a special guest who we will get to introducing in a second, but before that, we're going to go around and do brief introductions. We'll start with Bob and go to Rich then go to Marshall and then go to Stephen.
00:00:41 [Bob Therriault]
I'm Bob Therriault, and I am A J enthusiast working on the wiki, and that certainly keeps me busy.
00:00:48 [Rich Park]
I'm Rich Park. I'm an APL programmer and educator working for Dyalog limited.
00:00:53 [Marshall Lochbaum]
I'm Marshall Lochbaum, former J programmer, former Dyalog developer, and current BQN designer.
00:00:56 [Stephen Taylor]
And I'm Stephen Taylor, APL and Q programmer.
00:01:02 [CH]
And I think we have 1 1/2 announce announcements, so we have half an announcement from Bob and then two half announcements from me. So we'll go to Bob first, OK.
00:01:11 [BT]
My half an announcement is that I always say that I'm a J enthusiast, you know, singular. I'm not sure what the refer to is a group, but collective? I suppose I'm one of many. Uh, my maybe I spent this weekend with a lot of the J software people. Had a wonderful time down in Victoria, and I may be moving towards being THE J enthusiast. So. Not saying that there won't be others, Marshall suggested that maybe it that was my job to go out and eliminate other J enthusiasts. That is not what I mean. I mean, like maybe a person who primarily promotes J and many people, people will call that evangelist, but I'm, I'm anything but an evangelist. I do not push things on people, but I'm very enthusiastic.
So that is my announcement that I. You know, full disclosure, if I start to sound like I'm really enthused about J, hopefully I've felt sounded that way already, but if I do sound more enthused about J, realize that I may be the J enthusiast.
00:02:10 [CH]
Alright, so we will have to monitor Bob's enthusiasm levels and get some what do they call that the metrics or whatever over time?
00:02:18 [BT]
We if we do more YouTube, we may have a sort of a meter on the side that indicates how enthusiastic.
00:02:26 [CH]
All right, listeners, yeah, keep track and let us know if Bob gets too out of control.
00:02:31 [CH]
My two half announcements the first half announcement is that on my other podcast, ADSP, the most recent episode was entitled The K Programming Language, where Bryce, my co-host, asked a bunch of questions, asked a bunch of questions about the K programming language. [01] I can't verify that everything I said was true, but if you're interested in the content that you know gets talked about on this podcast, you'll probably be interested in that. So and the second-half announcement that I just remembered while doing this whole intro was that I gave a talk. Just I mean when this comes out it will be a week ago, so just sort of mid-September, that was at the Paradigm Conference,[02] sort of the esoteric langCamp.com that we had mentioned before where it was a hackathon for high school students and also I think first year university students, if they had only taken, you know, one computer science course and that talk was entitled, Popular versus less well known programming languages and sort of comparison contrasts 5 popular languages versus 5 less well known languages, which is what the hackathon sort of was endorsing to use for your projects, and one of those is APL. So if you're interested once again in the stuff we talked about here, you might be interested in that talk as well. So with all of that you can find, you know, show notes. All the links will be there. And with all that out of the way I'm excited to introduce today's guest, Troels Henriksen.
You will have maybe not heard his name before, but at the tail end of our last episode, we started talking about Futhark, which is a language that he works on. So a little bit about Troels. On his website you can find him at sigkill dot DK [03] and also sigkill under score K on Twitter it says that he's a Danish hacker and a general enthusiast in all matters computing. He's presently an assistant professor at DIKU. I'm not sure if they pronounce that differently, which is the computing department at the University of Copenhagen and as mentioned before, works on optimizing compilers for data parallel languages, and is currently working on the Futhark [04] language, which is, I think, what we are going to mainly focus on today, but I'll throw it over to Troels. Feel free to take us back to whenever you want to tell us a story of you know, how you got into computing, and how you ended up working on this Futhark language.
00:04:41 [Troels Henriksen]
All right. Well, I can I can take it all the way back to when I started. So my history is actually pretty conventional I was the one I just I like playing video games and I had this vague idea I wanted to do something with computers. And then I remember it was one summer in the boundary between elementary school and high school in Denmark, which is when you're about 14 years old. I found one of my my dad's old books about about DOS and it was it was partially basic stuff like this. Here's how you is what the file system looks like, and so on, but it actually went quite fine and ended with the assembly programming in 16 bit real mode on X86 and I didn't have access to task machine at a DOS machine at that point, but I really like the descriptions that had the descriptions of the command line, the idea that you could have a textual conversation with the computer. I was used to graphical user interfaces and this idea that you could talk to a computer in text really, really gripped me, so I knew that DOS was obsolete, but I heard about this Linux [05] or Unix thing where that that's still used command lines. So pretty much from one day to the other, I installed Linux and tried to learn how to use a command line and I've been doing that ever since. And then I took the usual path of start studying computer science at university and learning more and more about programming in my own time at school. And I just grew from there and I'm still around university, I guess. I mean, academics are just students who never figure out how to leave. Yeah, so.
00:06:04 [CH]
So that was at 14 you said that you picked up that book and then ended up installing Linux at age 14. That's pretty impressive. I can't say that I was even successful the first time I tried to do that when I was in university.
00:06:13 [TH]
Oh, I wasn't successful I installed Debian and Debian didn't have the right driver for my graphics card, so the first thing I had to learn how to use VI to edit the X free configuration file to ask to use a different driver. I have no idea why I put up with it, why I didn't give up and today I would have given up.
00:06:33 [CH]
I guess at the time they didn't have like PowerShell, which is kind of similar to CLI stuff for Windows, but, I guess Mac Mac did at the time. Has Mac always had?
00:06:44 [RP]
We've always had CMD right, but those?
00:06:45 [TH]
Yeah, yeah, but I didn't have a Mac.
00:06:48 [ST]
I love hearing the command line described as an advance on the graphical user interface like it's still an improvement on its successors.
00:06:58 [RP]
Now as I see things like that, there's a company called Textualize that's like the Python rich text thing the guy does that is working on an entire framework for building text based user interfaces. I think people have gotten to the point. They're like, man, this GUI stuff doesn't work, does it? No one figured out how to how to make a good looking GUI. Let's just go back.
00:07:20 [CH]
We'll put links in the description to the Textualize thing [06]. I mean, it is pretty impressive. There's a bunch of stuff, I mean, if even the J interpreter when you run it is very impressive, the stuff that they are able to render in terms of the boxing and whatnot, but anyway, so you end up going did you study at University of Copenhagen? That's where you did your undergrad in your.
00:07:39 [TH]
Yeah, I did my undergrad at University of Copenhagen. Yeah, and we were told you had functional programming Standard ML [07] as the first language, we just, yeah, we. It was pretty cool, so I picked up Common Lisp a few years earlier, so I was dimly aware of the idea of functional programming which you can do in Common Lisp, even if it's not always idiomatic. And but what I was new to me was static type systems, as instead I mean I've got a bit of C and so on, but those are pretty simple. So that was that was quite eye opening, and a few years later I learned Haskell, and then that's probably been my primary language ever since. I got into array languages, kind of by accident or by coincidence. And so I was I made my way through university, but by being a teaching assistant. DIKU has a pretty strong tradition of hiring undergrads and early graduate students to help tutor the student. It works pretty well. And I've been a teaching assistant in a compilers course under a newly hired postdoc, Cosmin Oancea [08], who will eventually go on to be the co-creator of Futhark and actually the originator of it and here and that this course was built around having the students. They were given a a draft of a compiler and they had to finish it. So improve or extend the parser, the type checker, coaching with all that's pretty standard stuff, but I didn't really like the way that that that Cosmin had designed the compiler. There was some technical things. It was written in Standard ML, and I think, so I felt that things were not done as well as they could be. So after the course was done, he sent an e-mail to the TAS saying that he was starting up a new research effort to construct a compiler for a parallel language and and I didn't really care that much about parallelism at the time, but I care a lot about compiler design, so I joined just to show off how I thought that a compiler could be designed. And the first thing I did was rewrite it from Standard ML to Haskell. And I think they they only put up with me because I actually wrote some code that worked. I don't think Cosmic really cared which language, he just cared that someone was doing some work, and that compiler initially was essentially compiled a very tiny subset of Standard ML to sequential SQL path to an interpreter and whatnot, but eventually that compiler grew to be Futhark.
00:09:58 [CH]
So maybe before we hop into the technical details of Futhark, for those listeners out there that only maybe heard about Futhark for the last time last episode, what's the maybe overview of Futhark, the language for those that haven't heard anything about it.
00:10:10 [TH]
So Futhark is a language in the ML family, so it looks a little bit like Haskell or another like Ocaml [09] and it feels like programming not in ML, Haskell or Ocaml and the kind of win or the benefit of a Futhark is that it can be compiled to parallel code. That's pretty much all this for, so it has lots of limitations. It's not nearly as nice as standard functional languages, but it it runs pretty fast.
00:10:35 [CH]
So basically a functional language that can be accelerated and is it just onto GPUs or is it any sort of devices that do parallel computation? It's a hardware agnostic language, it just doesn't expose any low level details. Our best compiler generates GPU, but we also have a compiler that generates a multicore CPU. New code and even one that generates code for ISP, which is Intel's Vector CPU language. OK, so heavily, heavily mixed right CPU code.
00:11:03 [CH]
And what is kind of the state of the language is there is it still kind of research level language or are there companies or you know teams out there that are actually using this to run sort of parallel computations.
00:11:15 [TH]
I mean, it's it is definitely research language and it's a very obscure language, but it's documented and it's stable and there are people who are using it for some form of production, I think most users are themselves academics who need to write simulations or models or or whatnot that are more flexible and can be expressed in just by just putting together a Numpy [10] or Pytorch or Tensorflow primitives, but that need to run faster than they would if they just wrote in the world them in Haskell. So there's this kind of very small niche I'm not even sure I'm not sure how big it is. Well, that even really exists and the few Futhark users are tend to be in in that niche. I also sometimes hear of companies that use it, but I think it's mostly in certain prototypes and experiments. It's it's a very obscure link. I mean, what we're researching is is compiler optimizations. It's great if we can create a useful tool, but that's that's more of a hobby thing. The language design is my hobby and the research is so was supposed to be my day job.
00:12:16 [CH]
This is a sort of hogging all the questions. I'm sure Marshall has 1000 questions that he wants to ask as well, but the last question I'll ask is. 'cause, you're probably a great person to ask this is you said you know, it's a very small niche that is being programmed for, but I'm aware of, you know, single assignment C [11], and you even shot me a note about that is, are there other languages like, well, is it, you know, just single assignment C and Futhark. Or are there other languages or libraries that sort of operate in the same space, you know, adjacent to Futhark?
00:12:41 [TH]
No, there's a bunch of them. So you could even argue that the Cod-fns that is the APL compiler that's GPU is in the same dish [12].
00:12:49 [TH]
And that's also DEX, which is done by Adam Passkey and and and Dougal Magorian at Google which is fairly recent and and there's a handful of these. Well there's Accelerator for Haskell, which is a Haskell embedded language. So that's that's a bunch of these and they are all pretty niche but but they do pop up here and there those Copperhead for Python ones, but, but I'm not sure. I'm not, I don't know of any that are really penetrate into wide use. The closest you can get are probably these GPU DSL's in Python like TensorFlow and and JAX and so on. They're the most similar interests.
00:13:22 [CH]
So we we will put links to all of those for folks that are interested 'cause it's definitely basically like very adjacent to what I do for work. But yeah, all of those projects that were enumerated there by Troels. We'll throw links in the show notes for us, right? I said that was my last question. I'll I'll throw it to Marshall or whoever whoever's got the the next thing that they want to ask about Futhark or anything, go ahead.
00:13:45 [ML]
I don't know if I'm a great question asker 'cause I have read a fair bit about Futhark, but one thing that struck me as I read is that you have a lot of work done by students. And often kind of short term projects, so I was kind of interested about you know how that works, how it is getting, you know, a lot of new developers adjusted to the project and and getting them to make a contribution in uh in usually a year or so.
00:14:12 [TH]
Yeah, yes. So that that's interesting. The original motivation for for doing that was that when I was a student I was really starved for interesting projects and I had a lot of infinite free time as students and to do and I just want something cool to do. So when I became a PhD student, and later on Professor I just wanted to make sure that the students didn't go through the same thing, but they actually hasn't been interesting to work on, so I try to come up with interesting projects for them eventually. Later, I've grown jaded and I'm just seeing them as a source of free labor, of course And originally I didn't really really plan on the best way to integrate students and it was kind of random where the the projects worked out or not. Then later on we become more conscious about this, about coming up with projects where the students only have to to study or work on a small part of the compiler because it's a big compiler now it's a big optimizing compiler for an untrivial Lang. It's written Haskell, which not all of the students may be be familiar with. So our most successful projects tend to be the ones that focus very narrowly on either front end stuff or tooling or their back end stuff because when you're working in in those areas you you only have one interface. You're already concerned about what you can't get what you receive from the rest of the compiler, or you have to pass the rest of the compiler, whereas when you're working in the middle of the compiler, you kind of have two different customers or two different interfaces, both what comes in and what comes out. You can't change either of those.
00:15:35 [ML]
So what kind of stuff does go in the middle is that?
00:15:38 [TH]
The optimization passes.
00:15:39 [ML]
Yeah, so you have some sort of intermediate representation, and you're working with that.
00:15:43 [TH]
Yes, and those are tricky, especially the use of the optimization patterns that transform the representation. I mean the ones that I kind of work on the same representation. Those are not so bad, but when you have to do work and change from 1 representation to another, or even extend the representation. Those are beyond most students, unless they are exceptionally talented or having lots of lots of free time, yeah.
00:16:03 [BT]
And and something you said, you know, source of free labor and actually if anybody is going into academia as as part of what may become a source of free labor. I just understand that that is the case because as I went back for my Masters degree, it became apparent that students are used for research purposes or support purposes. If but, and this is I think the most important thing, when it's done properly and it sounds like you're doing it properly, Troels, there is an exchange of information and the benefit that the student gets is they're working on an actual system and they're getting actual practical experience on what that's like. And that's something that often if you don't go into these kind of things, you may think, oh, they're just using me, but what they if they're done right, what they're doing is giving you great experience working in these areas and that's invaluable. I think the only other students that would get access to that kind of experience would be Co-op students working in the industry. And then it becomes a question of what company you're working for, how well you're supported. But I just sort of point that out there because a lot of times people think of it, they're just using me, you know, to do this. But honestly, there is a real advantage if you understand what your advantage could be, you can leverage that integrate experience and just by the questions, the thing when I went back to school to do my masters was when I went back into that, I thought I'd spent 15 to 20 years having to discover things in practical applications and suddenly I could just ask a question and somebody would say, well, that's a good question and start to answer the question. It was just like, you mean I don't have to go out and figure out what's going on, you're going to give me a framework to work from it's until you've been in the real world, you don't have a real sense of how rare and you know, affirming that is just have somebody saying, oh, well, these people are doing that kind of research you probably want to look at that. Those signposts don't exist when you're dealing in, you know, with things you're exploring things there's just no signposts out.
00:18:00 [CH]
There, yeah, usually we would wait to do this maybe at the end but it seems topical, if I recall I saw a tweet from you Troels that was saying that you actually have open was it PhD positions I think?
00:18:12 [TH]
Yes, I have an open PhD position [13]. The application deadline is somewhere in mid-october, so I guess the listeners this podcast will have time to apply, yeah?
00:18:22 [CH]
So yeah, I mean I was in the back of my head keeping going to hang on to that to announce at the end, but seeing as we're talking about it right now, I guess some yeah they'll we'll put a link in the show notes for if you are happen to be looking to do graduate work on compiler design could be something that definitely, especially if you're listening to this podcast you might be interested in.
00:18:40 [TH]
Oh, that's that's not free labour, but you get paid for being a pH D student.
00:18:43 [CH]
This is true, yes.
00:18:46 [TH]
And about Bob, I think you're I think very right that the students do get something out of it. Now, when I recruit students in these projects, first of all they are volunteers and and I may look secret about the fact that these are applied projects and there is some overhead in trying to create production quality code and I and so I start to be honest about it, but and we're still developing our technique so the last batch of projects I ran very much like I would and and like an open source contribution. So I had them open pull requests very early gave them detailed code reviews all along and I mean that that worked out pretty well. Probably the most successful batch of projects we've had so far, but still, there is a significant amount of overhead that is in principle not necessary. You can get a top grade without writing production quality code, even for an applied project, but for some students really like the experience of working on something real and I expect that it will that they also be more accomplished afterwards because they've written something that's actually going to be used.
00:19:41 [BT]
Yeah, there's a form of learning called I think it's called experiential learning [14], where you put the student through the experience. I taught an online television course in production, so that you run your own television studio, but what you do is you present the students with a series of problems that simulate what a person who's running a television studio would go through. And in that case, by the end of, I think it was a seven week semester. At the end of the semester, they had a very, very deep understanding of what a person running a television facility would feel and understand because they had seen the challenges and realized the tradeoffs that you have to make all the time, and that's not something that usually is explored unless you're putting a person into the experience.
00:20:23 [CH]
I think not to switch topics, but there was at some point on the stack of things we were talking about, you had mentioned, and I can't recall if we actually got to the end of that question was how you stumbled onto the array languages because you sort of started with Standard ML, then picked up or Common Lisp before that, then picked up Haskell, which you said you've been doing most of your development in, and then you said along the way you kind of oddly stumbled into array languages.
00:20:47 [TH]
Right. OK. So that's actually also, but it's somewhat interesting. So the department where I'm at DIKU [15] got a grant or create a large research project with a lot of money from the government around 2011 to investigate high performance financial. It probably it was called Hiperfit and had a bunch of industrial collaborators. One of them was Simcorp, which I think are the largest commercial uses of APL. In other words, Dyalog, which you all know, so because a lot of these these these companies especially simple part bunch of financial code, a lot of it written in APL and they wanted it to run faster, that was the idea. Financial companies, what Simcorp sells is a portfolio management system to people places like pension funds and so and this system has to constantly compute the risk of the portfolio, how much it's worth based on potential market fluctuations and so on bunch of math that I never quite managed to understand, but it's very computationally heavy and a lot of it is written in APL. So there was this idea that they wanted it to run faster because you have a large portfolio you need to be able to very rapidly determine how much it's worth. Some some legal requirements that I also didn't fully understand. So we had this APL angle and I say there was APL code out there and we had this this angle that we wanted performance which implies parallel programming and especially in in those days GPUs and still GPU's for that matter. So this Hiperfit project investigated many things concurrently. One was investigating how you can analyze and transform APL, so one of my colleagues, Martin Elsman developed an APL compiler called Tail, [16] which the type inference of APL code and turned into a typed intermediate language and and will maybe return to that. Another investigated high performance functional, high performance GPU programming and it did it by kind of working backwards. He took a bunch of programs or algorithms like maybe sequential C++, C++ programs and then they implemented them in in GPU code, in CUDA, or in Opencell and optimize them as well. He could make it run really fast. And they looked at the generated code and he reasoned, well, how could I compile have generated this because the people who actually need these computations, actuaries or or whoever, are not going to be writing hand tuned GPU code that that's not within their purview. We had this idea that they needed a high level language, but we wanted to generate very efficient GPU code, we work backwards from from the hand to encode and figure out, well, what kind of compiler optimization could have produced this code and then what kind of language would have allowed those optimizations? And then we kind of work backwards and eventually we reach a ML-like, functional language with basic parallel constructs like maps, scans, reduce, which is also the APL, array programming vocabulary, essentially. So we kind of worked backwards and reach something the very core of APL, the static core, without the dynamic behavior and then because another part of Hiperfit was working on an actual new API. They kind of converged and and connected at some point. And and yeah, that was how I got into both parallel programming and and then they feel like I kind of blended into all of this because I was just interested in writing compilers and there were a bunch of people there who needed to compilers to be written.
00:24:04 [CH]
Interesting. So to recap, 'cause, I want to make sure I didn't miss any of the connections there in 2011 I think that was the year a bunch of grant money showed up because of this, you know, and a part of the people funding that with simcorp and Dyalog who obviously had a vested interest in APL. At that point was Futhark already existed, or.
00:24:28 [TH]
No, it didn't so so Futhark that was a language that eventually rolls out of this idea that we needed a language that could allow the transformations that eventually turn into highly performant GPU code, but it was kind of the design bottom up where we started by looking at the kind of code we wanted to generate. And originally we didn't even want to create a language, we wanted to create a compiler, and then later on we would figure out which language that compiler would then transform? And at some point we we thought it would be be apple and at some point it was actually APL. We proved that was originally supposed to be a call language, so an intermediate representation for our compiler and we'll also assume that something else would be compiled to Futhark, and we just gave it a surface syntax only issue. We could write benchmark programs so we could test our compiler. But then eventually it grew because language design is fun. And so but it wasn't really planned that way and the language design part is, as I think I mentioned before, not really or wasn't originally the academic work that was just the the hub for me, interesting, so Futhark actually was initially designed or or planned to be more of an intermediate language in between, you know, accelerated, you know, CUDA, or GPU code, whatever that looks like, and then some higher level language, which, as you mentioned even at one point, was actually APL.
00:25:51 [ML]
Well, the obvious question here is what's wrong with APL for our purpose tables.
00:25:56 [TH]
So at that point Co-dfns didn't exist, so nobody had compiled APL to GPU code or maybe even highly efficient parallel code. I wasn't really that involved in the APL side of things this one compile it to single assigned to single assignment C at least. Yeah, APEX but I think that wasn't available at that time. Or it was I don't remember.
00:26:19 [RP]
I think it's available now.
00:26:21 [ML]
Yeah, I think it has been but so that is what APLTail did, right eventually, more or less.
00:26:28 [TH]
Yes, yeah, yeah. So that compiler appealed into a language called Tail, which is basically just explicitly typed APL, and both because, well, it's just one person doing it. And if it is a big language, and also there are probably some part of the very dynamic behavior that you cannot compile, probably.
But there's a subset of well behaved APL that isn't actually that difficult to analyze for a compiler. And that was so he created this is tail compiler and he wrote a code generator that generated sequential C code and I think they added some open MP for multicore execution at some point. But then we also had some students take this tail, which was the compiled from from APL and turn that into Futhark and that was when APL was really the probably the most flexible surface interface to through the compiler. And it actually run quite fast and we go to a paper about it showed that you could then compile APL code, CPU code, and get significant speedup over handwritten C code. That was that was pretty fun work, and so just just the listener is keeping up with us because I've read a few of the Tail papers.
00:27:38 [CH]
Tail stands for Typed Array Intermediate Language, correct?
00:27:41 [TH]
That's right.
00:27:41 [CH]
Yeah, and so did it sounds like Tail and Futhark were developed at the same time, or was there?
00:27:50 [TH]
Pretty much so. Again, this Hiperfit project was large by academic standards, so you had lots of people working or concurrently on things that perhaps try to solve the same problem, but there was no foundation, so there's a bunch of things growing up at the same time. And some of them eventually died out and others kept kept living on and some of them kind of joined forces later like like Tail and Futhark. That's just how it is in academia. There are lots of other offshoots that also.
00:28:17 [CH]
And so, at a certain point in time, Tail was being used to transpile or compile APL code down into the Futhark intermediate language as it was at the time, because it was less of a language as it exists today, and more of a sort of IR at the time.
00:28:33 [TH]
Exactly, and this was before Futhark look at things like polymorphism, which APL does have in some sense, so it was actually significantly more powerful than Futhark was.
00:28:44 [CH]
And so when you say polymorphism there, do you mean like type classes in Haskell or do you mean like rank polymorphism?
00:28:49 [TH]
Right, I mean Parametric polymorphism [17]. So even even more basic than that right?
00:28:56 [CH]
And so then and so we're at the point now where APL is being compiled with Tail into Futhark, which is more of an IR instead of a language. And how did things progress from there to where they are kind of today?
00:29:07 [TH]
Well, uh, I don't. The tail compiler doesn't work anymore. At least the pilot generates Futhark code because through their changes was like five years ago. So Futhark has changed since and the reason we didn't go further with that is that API turned out to have some problems handling. The full scale of APL turned out to be problematic. APL is a big language, and for this to be practically useful on real APL programs, you probably need to handle a significant subset of APL, and when we looked at the kind of industrial APL code that this might apply to it was, and then that code wasn't written in a style that was compatible with what Tail could handle. I mean, a lot of industrial APL code isn't really this kind of minimalist, tested style that that most APL hobbyists or enthusiasts like. And then I also like the that's the stuff that fascinates me about APL. It's more like it's more, it's more imperative in style and it look uses a lot of what you would probably call legacy features, but I don't think industry agrees that they are they're legacy. It just turned out to be a lot of effort to handle industrial APL code, and that was ever we couldn't justify putting in because we were compiler researchers. We didn't really want to be in the language front end business, so it was easier for us to just extend the Futhark box surface language, the kind of intermediate representation so we can continue with our compiler research, which was what we were really there to do.
00:30:31 [ML]
Yeah, I think that's actually how a lot of compiler work at Dyalog went as well we. And I I didn't work on any compiler compiled APL projects but aside from Co-dfns which is still in progress, I guess like Dyalog worked on a bytecode compiler which you can run but the basic conclusion there was that it's just too much work to get all this code that's out there and running and using whatever, you know, old features APL has that have been thrown in over the years. It's too much work to get that all to run on the compiler. So what our response to that was to end up working on speeding up the interpreter and its handling of scalar code instead uhm, but you can also if you're not working at an APL vendor go the route of changing your programming language of course.
00:31:22 [CH]
I did not know that at one point Dyalog limited was working on a compiler, a bytecode compiler.
00:31:28 [ML]
Yeah, that was about the first thing that Jay, the Jay big project when he started working at Dyalog.
00:31:35 [CH]
That's Jay Foad [18], yeah, not the J programming language.
00:31:38 [ML]
The source of endless confusion, but yeah, so he he had a lot of compiler experience before that, and so he started working on a bytecode compiler there, which it is, uh, it shipped with Dyalog. It's where it works. You can run it.
00:31:54 [RP]
I think it's 400 I beam.
00:31:55 [ML]
Yeah, and the the usual numbers like here are roughly 2 times faster for scalar code if it works well, but it's just, you know, too hard to maintain it.
00:32:06 [BT]
One of the things you just mentioned was that maybe the tacit [19] or the maybe what a lot more hobby hobbyists are interested in that style of writing may be more conducive to parallel programming, at least the way Futhark does it, is that. Is that something that maybe gives us hope that always you know, trying to do the fancy little tricks and elegant code and I think often what Stephen refers to is cool code. That kind of process often when I look at it, let you know applications in industry, you're right, there's a whole lot of sequential working through cases, working through selects those kind of things is very practical, and I'm not arguing against that 'cause it's also actually pretty easy to figure out, which is, I think, why they do it, but when you actually can create something else the same thing in a couple of lines that does it elegantly and uses the primitives? I suppose that's the reason that it's a little easier to compile to is.
00:33:07 [TH]
Sort of, so tacit is not an advantage for a compiler because that's just a question of notation, but what tacit style does is encourage a data flow that is, is pretty that is based on bulk operations on data and is kind of like I guess maybe right to left. So a single pipeline of fault transformations of data. This is what also Aaron Hsu observation in his in his Co-dfns thesis and that style of programming is very friendly to compile and interpreters for that model is that it's just a very machine friendly way of programming. And I think the big lesson of APL is is really that there's also a very human friendly way of programming, and at APL nowadays probably isn't even the main example of that. I think Numpy is probably the main demonstration that that massively parallel computing based on expressing bulk operations and data structures is both friends, humans and to computers that that's not a prize where I usually point to as my example when I teach this stuff, but the API of course today before anyone else and it's still doing it in a more flexible way. Yeah, so so it's not about tested as such like tacit because of its of its elegance but if as we look at it pragmatically as what what is helpful to a compiler, then it's not really the tacit itself.
00:34:22 [TH]
You can give your variables names. That's fine, the compiler doesn't care, but it helps that you encourage nothing in terms of data flow and bulk operations.
00:34:32 [BT]
Yeah, the tacit part of it just becomes what moves you into thinking that way you can introduce variables and, I suppose 'cause that's almost a hybrid I would think for somebody who's programming because it some ways it the explicit looks a little bit more obvious where you're bringing in variables, but the task that actually enforces you to work that way because you don't have the variables to work with.
00:34:58 [TH]
Yes, well, I don't, I don't. I don't know enough to say, well, it forces you to do it, but it strongly encourages you to write in a way that has machine sympathy.
00:35:07 [BT]
I like your way of phrasing it much better.
00:35:10 [RP]
Yeah, there's something that's true in in at least interpreted APL I think, where it's the array oriented way of doing it is focusing on the transformations and taking, you know, applying a small and collection of primitives as you can get away with to as large a set of data and then chaining those together, but I suppose when it's a compiler, since it cannot analyze that ahead of time, it can do the joining for you, whereas someone using the interpreter has to like, think of those steps sort of independently.
00:35:41 [TH]
And yes, and this actually also have another significant difference here, because the compiler knows how to deviate from this paradigm in ways that are also more machine friendly. So if I tell my favorite example of this is.
00:35:54 [TH]
Computing the Mandelbrot set [20]. So in the Mandelbrot set you have a huge bunch of pixels points in the complex plane. For each of those points, you need to do essentially a while loop, and then count how many iterations you get through the while loop before you before you have your termination criterion is reached. And then you can turn the trip count of that loop into a pretty color. That's why people want to compute it. But I I that is very parallel because you know all of the points can be computed independently, but that while loop in there, it's not very easy to express in an idiomatic way in in APL, because in APL you want your sequential looping on top and then you do bulk operations on entire. But that's not really a very efficient way to express this, because at different points minus two different number of iterations through the loop, so you and you really don't want them some of them to exit early. Also, I think the dramatic obstacle in APL is to continue looping across all of the points as long as at least one of them still need to go through it's small little loop and that eventually evolves repeatedly, manifesting the entire big array of loops. I'm sorry, that entire big array of intermediate states in memory and then reading the bag in all the time. And that's that's very, very expensive in terms of memory traffic. Now, the optimal way of doing it is just to have a single small sequential loop for each thread or each point or whatever with the intermediate values kept in register. Well, that's that's kind of a nested thing. You can write it in APL I don't see why not, but I don't think an interpreter would be able to handle it, because it will essentially be and each containing a while loop over or over a big array and I don't think. Yeah, but to compile that's not a problem. It's just like you have a parallel loop OK and I'll generate code for the loop inside and then but a long term bunch of threads. So that's something that a compiler can do that interpreter cannot. Yeah, it would be a lot slower.
00:37:43 [ML]
Although it is a little disappointing me. So you can't run. Well, I guess you could, but you don't want to run. Say you know four points at a time and stop when all of those.
00:37:53 [TH]
Well, I mean, you can do that. But you don't. I wouldn't want the human to write the code like that and that's.
00:37:59 [ML]
Yeah, it's definitely, uh, that's something that you would have to you'd have to be actively machine sympathetic instead of sort of just using the language.
00:38:08 [TH]
Yeah, and maybe maybe a compiler can even generate that for you, yeah. That's not particularly difficult as essentially how at GPU would execute the code anyway. It would just implicitly do it, well I guess 16 at a time instead of four at a time.
00:38:23 [CH]
So I have a queue of questions that we're going to hop around and maybe we'll splice in other folks questions so that hopefully we can get to all before the end. So one of them, I think it was kind of answered at one point, but the question is that, you know, sort of on the Futhark website. It it has a description of the Futhark language, and you know a few of the key words in the middle are, you know, a purely functional array language. And so I guess the and we talked about this a tiny bit at the end of the last episode is. What about Futhark? Sort of gives it that array because it definitely looks different, and you mentioned earlier that as you were working backwards from the sort of compiled accelerated code, you got back to this sort of core set of primitives, map scans, reduces and and that maybe that is part of the answer anyway, so I'll let you answer you know where the array part comes in, because it's both functional like Haskell and then also array. Insert your answer.
00:39:21 [TH]
Yeah, so you spent the last episode discussing what are the array languages. And I'm an academic, so I'm a big fan of discussing definitions and and so array language is a social definition, so my definition would be that it's an array language, if you get to talk about it on Arraycast.
00:39:37 [ML]
Well, he's got us there.
00:39:40 [TH]
So that's why Futhark is now an array language. But it wasn't previously, but so I'm actually, if you look at the various things we've written about Futhark over the years. So we were not even consistent in what we call it. Originally we just called an array language. Nowadays I tend to call it a functional array language, which is a term that Sven-Bodo Scholz the creator of SAC came up with and I'm mostly using it because isn't really an array language in the sense that APL is. It lacks a lot of the features that you mentioned as important. It doesn't have a rank polymorphism. That's probably the most important omission.
00:40:13 [RP]
Yeah, you do have to write your maps.
00:40:15 [TH]
Yeah, you have to buy a lot of maps, we kind of actually have an idea of how to eliminate some of those.
00:40:20 [ML]
Yeah, so you you think, uh? But it won't be that way forever as you're you're thinking.
00:40:24 [TH]
Right, so, so rank Futhark is a type language, and that's kind of because I was trained to like typed languages, but also partly because it really helps a compiler when it doesn't have to work hard to figure out what things are. And rank polymorphism. You can do it in a type system, but it's really complicated. There have been entire PhD's written about how to incorporate APL style rank polymorphism in the types system [21], and it tends to conflict a lot with other type system features that you might want to have, like parametric polymorphism. I actually have a suspicion that it's not possible to combine rank polymorphism with parametric polymorphism at all and that it is simply fundamentally incompatible, but I haven't yet proven it. That's why we want to get around to writing in Futhark that we would. Nobody likes writing map all the time. I mean, it's nice if you can just make it clear what's going on, but even you write very heavy matrix, or indeed numerical code and Futhark like, it really sucks having to write map all the time. So we have this idea. We have this hypothesis that a lot of rank polymorphism, at least in non APL code, is pretty simple and really just corresponds to inserting a bunch of maps on top. Which is also exactly what the leading array axis theory [22] is basically doing pretty much. So we think that you can actually pretty easily in a Standard ML type checker do some kind of map inference where we apply a function you just check. OK, this function code isn't well typed, but if we added a bunch of maps on top would it be well typed and then we can just do that this. Be less flexible than APL style rank polymorphism in particular, you will not be able to write rank polymorphic functions, but your function applications would then be rank polymorphic in a limited sense, and that means the types in Word doesn't get more complicated. In contrast, SAC single assignment C does have rank full movement, and you can directly write a rank polymorphic function, and you can do all kinds of cool things where you can do rank specializations and so on, right? But it really complicates the type system. And then they don't have parametric polymorphism, and I think for that reason it doesn't really work with rank polymorphism.
00:42:27 [BT]
One of the things that occurs to me that seems to be cropping up as a pattern is that you seem to work backwards to what you want to get to, but honestly you you laugh, but I think that's really neat. And often when you're trying to approach problems, it's that kind of change in perspective that will open up a problem for you rather than everybody else tries to do the other way and they just keep hitting this brick wall, well, you've by going backwards you actually find a way around the brick wall to getting your solution.
00:42:55 [TH]
It at least allows you to think differently. So I mean there are lots of really nice programming languages out there. I mean, I like Haskell a lot, and I also like APL. I actually like k little more, but that's a different topic. I think a lot of these languages were written with humans in mind, and then later on if you try to figure out how to make them run efficiently in computers and and so sometimes you get lucky. I mean when Ken Iverson designed APL [23] he was pretty much thinking about humans and it just turned out to also have a lot of mechanical sympathy you it was pretty easy to make APL win. But a lot of languages weren't really designed with that in mind, and so if we wanted a niche, if we wanted to have a language that we could compile efficiently, we figured that we would have to start from from the other direction and start by looking at the code we wanted to generate. So I've realized that.
00:43:46 [CH]
We've mentioned now parametric polymorphism, maybe two or three times and there's probably a handful of listeners that aren't familiar with that term, so I'll do my best to define it and then Troels can correct. So rank polymorphism we've talked about a ton. It's basically implicit iteration where you don't need to map so scalars work with matrices, etc. Parametric from my understanding is when you have a function that works the same way for multiple different types, where and, then in Haskell they have both parametric and ad hoc polymorphism. Ad hoc is where you have same named functions that have different behavior for different types. So you use typeclasses in order to get that and famously Go has not had parametric polymorphism for a very long time. I think in 1.18 they added it for the GO language but what that meant is that, and this is like my favorite example to kind of give GO a hard time is that when you want to take the maximum of two integers, you can't do that. They have a Max function, but it only works on floats. So in GO you have to cast your integers into floats, then pass those two numbers to your maximum function and then you get a a float back and then you cast that back into an integer. Which if you are in a language with row type polymorphism like Python or you know generic programming in C++ like that seems incredibly backwards that you can't support you have to write you know, a function in different times for the N different types you have in order to get it to work. And so yeah, Troels that I get that close enough, or is there's things you want to add to that, yes.
00:45:15 [TH]
But I think the really crucial part you you didn't spend all of words on, so parametric polymorphism is about writing functions that do the same thing for different types that that's really the that's. That's more difficult than it sounds because for example, when you have the identity function, let us type X to X for any X, and just by that type you can you can deduce that it must be out of the identity function, or a function that explodes that diverges doesn't return anything. And that really breaks down very easily if you allow code to inspect the actual type, like if you have reflection for example that's the most obvious way. Then you break what's called parametricity. That means that you get and, and that means you have risks that the code that is supposed to be reusable isn't as reuseful as you expected. Because it doesn't anymore do the same thing for the same for the same type. And as well, it does no longer does the same thing for different types. And the problem when you add rank polymorphism is that you lose parametricity because you can expect things based on that shape. If you take an A any A and you ask for its shape, then you get back a value that depends on the actual type. Because if it's a matrix, you get back a two element vector, if its avector you get a one element vector. So you lose parametricity when you add rank polymorphism, and I don't see if I see a way to to fix that without either significantly restricting rank polymorphism? And then you might not then you might not even want to have it anymore, or losing parametricity, which is kind of the main advantage of parametric polymorphism? Maybe I'm just too fundamentalist.
00:46:49 [BT]
If you were to try and extend that a parametric view of it you'd need a different type for each shape of array is that right?
00:46:58 [TH]
Yeah, yes, exactly. And that's how it is when you write.
00:47:00 [BT]
It's it's impractical, but you, yeah.
00:47:02 [TH]
That's how you do it when you write info that, for example, so and and the idea the hypothesis would then have is that most instances of array polymorphism really are just about adding more implicit maps at the application site. And if you do that, then you haven't touched the type system and you can get away with it. But there are some function that you cannot write this way. And so I but I also have a suspicion that so in APL, rank polymorphism is really important because it's about doing an entire flat bulk operations on data and then the next operation and so on in a pipeline nested operations in APL are kind of discouraged because interpreters don't handle them well because then you have these complicated code inside of your, inside of your Dfuns and the interpreter will have to well, it's Tailorize the outer part or something like that I don't know what it's called.
00:47:48 [ML]
Well, the interpreter just spends more time running 'cause it has to run every time a primitive is applied.
00:47:54 [TH]
So it makes sense I think that's why rank polymorphism is is really crucial in April, because not only will it otherwise they could be larger, but it also run a lot slower. But in through there you can say map with a complicated function and that'll just work, there's no performance overhead. So a lot of Futhark our code is is more nested than that would be good style in APL, and I think that's one reason why we can get away with not having ranked polymorphism, only having a very limited form of rank polymorphism. So interesting to ask more like it is simple shows from Single Assignment C where they have rank polymorphism? Because they also have a heavily optimizing compiler, so they don't have this performance requirement. And so it may be that they have some some insight I don't about why rank polymorphism is is not just nice to have, but but really important even in the presence of an optimizing compiler.
00:48:42 [CH]
But as you mentioned, they don't have parametric polymorphism, and that's if you've right. I've mentioned my sort of array language comparison GitHub repository [24], and there's a a table on that where I show reduce scan and outer product and how they exist in sort of nine or ten different array languages. And then Single Assignment C is the only one that doesn't have any three of them, because single assignment C doesn't have support for basically generic operations and when I talked to Bob Bernecky at the Toronto APL meet up a couple weeks ago and he said that basically when he's working on APEX [25], his compiler that compiles APL down into single assignment C, He just has a bunch of macros, which is, you know, a very common thing you'll see in C code base is. So it's it's very interesting to sort of contrast these, you know, Futhark, sort of Haskell inspired, single assignment C inspired, and one has rank polymorphism but not parametric polymorphism, and the other one has parametric polymorphism but not ranked polymorphism. And the trade off some which kind of maybe takes me to one of the other questions that I had is we haven't talked at all about SOACs, so-axe, or second order Array combinators [26], which basically if you go to one of the preload libraries in the Futhark documentation, it talks about, you know, map scans and reductions, and even has. I think Futhark is one of the only languages that I know of that has both uh, reduce and then uh reduce, under score, under score commutative, or comm, which has basically two different reductions that have different requirements on, like the associativity and commutativity [27], which is something we've talked about in NVIDIA parallel libraries of the fact that we are missing a couple of these. Do you want to talk a little bit about how how do you pronounce them? Is it SOAC's or so-ax and?
00:50:30 [TH]
I could just say so acts. I should say so. Yeah, those are interesting. So these are things like map and reduce and and scanned as you said. And these are pretty much all taken from pretty much original APL, because API originally appeared did come with the essentially the core of a very effective work vocabulary for parallel programming. Now APL unfortunately got some things a bit wrong because it assigns sequential semantics. So the APL reduce is more like a fold in that it's guaranteed to be left to right execution, which means you can parallelize it. Because you can pass it, you have no idea what kind of function is passed and APLs.
00:51:05 [ML]
Well, wait, what you do is inspect at runtime.
00:51:08 [TH]
Yeah, you can check it, yes, sure.
00:51:10 [TH]
And the scan in APL is.
00:51:11 [CH]
Oh, it's so bad. It's so bad. BQN fixed it.
00:51:16 [TH]
Yes, I think all successive APL's fixed it.
00:51:20 [ML]
No, it's not really J.
00:51:21 [TH]
Yeah, but but it's unfortunate because that was really the core of it and and what we realized pretty early on is you don't really need much more than that and even things like scanning with you 'cause, they don't really have to be primitives, it's it's useful to other massive primitives so the compiler can can can knows what they are and can generate custom code for them because they are so common but they're not. Technically, you don't actually need them. They're just they're more for humans than for machines. So there's the 2nd order in the sense that you pass in the function that you want to use or for metrics, give the function as an argument you for user given operator for scanned activity. And operator and to enable parallel execution, some algebraic properties must hold for these operators. Associativity is the main one for for reduction, and there must also be a neutral. Yeah, this this is in most cases most reductions are with plus or multiply or Max or something that is known to be associative and commutative. And there are a few cases where it's useful to be able to pass in a custom operator, but it has been our experience that humans are really bad at thinking at thinking about associativity, so it's very common for people to pass all right operators that aren't actually associative and then they get the wrong results because then the parallelization doesn't work out. And that's so some of my colleagues would say that it's a mistake to even allow user provided operators because it's so easy to get them wrong, and it's kind of. It's, it's, it's a it's a big hole in the language. You can say you can get done in simplistic results, but on the other hand, sometimes it's just so convenient and I can really help performance too. So you can do something very complicated and just run reduce that would otherwise take multiple scans so whatnot.
00:53:02 [CH]
And so do these in general, like the special thing about them is that when provided the correct operators with the correct requirements, it'll be highly accelerated. Or is there something more in terms of like if you chain them together in a certain way that they'll they'll fuse 'cause I I think it says what does it say at the top of the page that they can be exploited by the compiler like this exploitation just mean like simple things or fancy things.
00:53:29 [TH]
It means fancy things, so the compiler knows what our scan is. It it knows, it reduces these are primitives in intermediate language, and that's a few of those. It has a fusion engine that knows of how these things can be combined, so we can reduce multiple paths into into one pass. We have a flattening algorithm that is that determines we list these things how they should be flattened out so they can fit on non nested hardware like GPU's? So all everything is ultimately expressed in terms of I think we have 5 primitives at the at the very bottom level, and the and the compiler knows about those. And adding new primitives is something we try to do very rarely, because when you add a new primitive you need to take, you need to worry about how to interact with everything else. I mean, you have a combinatorial problem here. It's not like an interpreter where if you can, if you add a new thing, you just have to make that thing run fast in isolation. We also have to consider its interaction with everything else.
So we try to keep the number very low.
00:54:23 [ML]
Well, I gotta hold this over the K, people. I'll say, oh, your language has 25 primitives. Well, the Futhark intermediate language has five.
00:54:31 [TH]
Oh, that's the parallel primitives called the scaler. Once we have tons, I mean, yeah, we have 9 building types, and each of those has all has a full arithmetic library. I guess there's hundreds. If you count all of them.
00:54:42 [RP]
Then I realize now why I think you have 5 maps is because you don't have rank polymorphism.
00:54:47 [TH]
Oh, you mean we have? So actually that's different.
00:54:50 [RP]
Or do they do very different things?
00:54:51 [TH]
So we mean we have MAP 1, MAP 2, MAP 3 map 4.
00:54:55 [RP]
Yeah, I I mean, I I didn't look in in detail. I saw that in those.
00:54:57 [TH]
So that that's that's not ranked polymorphism and that's map one is when we want our function takes one argument over 1 array. You have choose when you want to measure function that takes 2 arguments over 2 arrays. So it's just shorthand for as first zipping and then mapping because it's.
00:55:10 [RP]
So it's a notational deficit.
00:55:12 [CH]
And this is actually something that exists in like many functional languages, I think Haskell, Scala, they all like. I think they they have map, they have zip with and then they have like zip with 3456 which is.
00:55:19 [TH]
Right. Yeah, it's it's exactly that.
00:55:26 [ML]
While an APL. Those got this problem pretty badly 'cause it has each is map and zip width, so it goes one and two and you can't go past that. So actually K does does do a good job of that. You can map over a a large number of arrays, but APL does not.
00:55:44 [CH]
A kitten that has entered Troels space as well. The kittens been visiting throughout the episode.
00:55:50 [TH]
I'm not sure he yeah, I have I did feed him. I'm not sure why.
00:55:54 [CH]
He wants, he wants to mention on the podcast he knows he hasn't been or is it he or she?
00:55:57 [TH]
It's, uh, he. His name is Toxoplasma gondii [28].
00:56:04 [TH]
I asked the question when we did the tech check. Explain the background to that the Troels.
00:56:09 [TH]
Yeah, so the Toxoplasma gondii is a parasite that lives inside of cats and is reputed to cause a crazy cat lady syndrome in humans.
00:56:20 [CH]
This a thing that you're not supposed to have if you're pregnant.
00:56:25 [TH]
Yes, it's it's mostly not. I mean it's, I don't think it's dangerous beyond that. It it affects I think rodents. It makes them all risk seeking. So then they get eaten by cats and then that's the life cycle of the parasite.
00:56:36 [RP]
He named the cat after a parasite.
00:56:39 [CH]
We should wrap up, I guess. The last section which was had a visit from a kitten, is to say that it sounds like if you're writing Futhark code, if you can express a majority of your program, or at least the computation significant hotspot of it, in these soac combinators you're going to get a huge performance windfall because of this, this fusion algebra that you mentioned.
00:57:06 [TH]
Yeah, but it's not just because of that. It's also because if you just write it through that, you can write a sequential loop, and that's just that's just sequential. It's not, uh, parallelizing compiler it doesn't analyze your code to figure out where that could be. Well, it can parallelize something that you wrote a sequential. You have to use the power vocabulary to get performance, and that's actually a wonderful thing called a parallel cost model that tells you asymptotically whether something in parallel? Not so soon, without worrying about how the code would look like on a GPU or in a multicore or whatever. You can reason about well, what is the maximum number of sequential dependencies I have in my program? So how can I expect it to scale in runtime when the data set? There was some wonderful work done by I think I I think Guy Blelloch [29] mostly 90s about parallel cost models. As a high level concept, I think you could also write up parallel cost model for APL. It's a very, very general. So that's how I would like programmers to think about Futhark eco. But that they write not about this fusion star, fusion is just a constant time optimization. It's great when it works and it it it matters. But it's not what what gives you the parallelism. It just means you have a little bit less memory traffic or a lot less memory traffic. And I and and Futhark, I guess in many ways, kind of a low level language in that it's it doesn't rank polymorphism, it it doesn't have typeclasses, you it's sometimes a bit tedious to write, but it does encourage you to think at a very high level about how what your parallelism looks like, and I think that's very useful to any program, also programmers in every languages. And of course, in a real language, most programmers do those already because it's a natural way to phrase things.
00:58:39 [CH]
Yeah, we'll, we'll put the link to Guy Blelloch. He's got a bunch of great papers, but he also has a website that hosts most of his Nestle work, which I'm sure controls you're familiar with, which is his sort of toy ML accelerated language, where he has a bunch of implementations of algorithms like scans and stuff, which is pretty. It's pretty interesting to read through and very illustrative of of the ideas there. Any I mean I I think we should end with the question why do you like K better, but before we do that? Are there any other questions? I feel like we're going to have to have you back at some point because I feel like we've only touched the surface and there's a maybe what we'll try and do is we'll try and cycle through, we'll try and get someone from decks on, try and get someone from a single assignment C on, and we can go through all all the array, you know, parallel languages. Bring Aaron back on to talk about Co-dfns.
00:59:37 [ML]
Though by the way, the term that I use for these is typed array languages 'cause they all share that static typing.
00:59:42 [ST]
Yeah, that's the best.
00:59:43 [CH]
Typed array languages, So what fit also Futhark, single assignment C.
00:59:48 [ML]
So everything you just mentioned Futhark, single assignment C?
00:59:51 [CH]
Does Co-dfns count.
00:59:53 [ML]
No, no 'cause. It's dynamically typed.
00:59:54 [CH]
I mean, it compiles down to arrayfire, right? So which is typed, but that's and that's the tricky thing about this, right?
00:59:59 [ML]
Yeah, so the the target is statically typed, but the language is dynamically typed. I think it moves all the type checks to runtime.
01:00:07 [TH]
What about Remora [30]?
01:00:09 [CH]
Yeah, Remora. I assume when you mentioned there's been PhD dissertations written about typed languages with rank polymorphism, you referring to Remora, and that was Justin Slostex's dissertation, yeah, is Remora.
01:00:22 [ML]
I think it's typed.
01:00:23 [TH]
Well, it is typed, but it's essentially APL with types. So why isn't just an array language?
01:00:29 [ML]
A central feature of APL is that it's dynamically typed, I would say.
01:00:33 [BT]
We're back into that discussion.
01:00:36 [CH]
We're back into the last episode of.
01:00:38 [ML]
I mean, I'm not saying typed array languages. I consider typed array to be a subcategory of array languages, so it is also an array language.
01:00:43 [TH]
All right.
01:00:46 [CH]
So now I need to add. We need to whip out my now what? Upgraded from a paint picture to a PowerPoint Venn diagram and I gotta put a type circle in [31]. It now it's.
01:00:57 [RP]
Not very Iversonian to care what a decimal point does to the computer, yeah, I guess 'cause he was on a whiteboard, just like numbers.
01:01:07 [BT]
And so now we fire up the the YouTube and the Venn diagrams and everybody who's walking their dogs is ripping their hair out. Although I did get feedback that people said that it wasn't too hard to follow, so that was that was encouraging.
01:01:20 [CH]
Yeah, and it's got a I'm surprised. I thought it would only get a couple 100 views that the what we're talking about Troels, is, uh, at the tail end of our last episode, I launched a paint application and started drawing a Venn diagram. We posted it to YouTube and it's, I think it's gotten close to, I don't know, 3000 or 4000 views now. I'm I'm not sure how many people actually started watching it and signed up for the whole thing and stayed, stayed through it but. All right. So we'll we'll have you back in the future. But before we let you go, even though we're a little bit over the hour marks, we we appreciate you staying with us. You mentioned it at some point and we can't not revisit this question, that you prefer K to APL, so the floor is yours Troels, tell us why.
01:01:59 [TH]
Yeah, OK. So this is going to be very boring answer. So the main reason is that my kind of first love as a pro in program language was Common Lisp and K [32] is more like Lisp than the other APL dialects.
01:02:12 [CH]
Do you stay up to date with all the different K's and Shakti and stuff like that, or?
01:02:18 [TH]
And no, not really, but when I do program in K I use, I think it's called Kona, I I just, I'm, I'm not a very advanced K'er. I mean, I just pick one of the free implementations and they all support what I need, which is also playing around.
01:02:32 [CH]
'cause Kona which K is that is that K6 so I think it's .
01:02:35 [ML]
Three or four? So like, uh, like Kx k.
01:02:40 [BT]
And being a Lisp fan, what about April [33] or have you followed that at all?
01:02:44 [TH]
A little. I really enjoyed the episode the podcast did about that and I did. That's great, but what is one of the things he said really yeah, I realized was was a phrasing of a thought that I've had for a while. He just said APL is really great for the expressions, but it's less great for the control or that sense is rounded. And in Dyalog APL you have the APL and it's great, but the imperative things are not really very nice. I mean the you can do imperative control flow in in Dyalog APL. But it's it's not great. Whereas if you had common Lisp around, is surrounding it, and said that's really good at the embed imperative control flow, and has a great object system and all that nice stuff, then maybe that's really what APL should should be. It's the language for the expressions for the computation, but not for the tedious bookkeeping on top. I haven't actually tried April, but it's close to what I think may actually be a good design for a language or a programming environment or whatever you want to call it.
01:03:39 [BT]
I think Andrew Sengul will be very happy to hear you say that. He's and I'll probably get an e-mail about that and we'll put a link in back to that episode 'cause it was interesting and he is using a combination of Lisp and APL, and using list for a lot of the imperative stuff that allows more flexibility in controlling the structure of of your program.
01:04:01 [CH]
Yeah, it's. I mean, I can't do we enumerate the list [34] when we had Andrew on because there was basically APL in Common Lisp AKA April, APL in Python AKA Pineapple. APL in Julia, which I don't actually think has a name, but someone has a lightning talk, once implemented some subset of APL.
01:04:20 [ML]
Yeah, there's an APL JL is, I think, APL dot jl.
01:04:23 [CH]
And so it's it's interesting. I'm not sure if there's more of, you know.
01:04:26 [RP]
There's there's May as well, which is the other Lisp.
01:04:30 [CH]
Oh, Closure.
01:04:31 [RP]
That's right. Closure.
01:04:32 [CH]
Yeah, yeah, right. 'cause it may come after April, so there's there's about four different implementations of APL and insert language.
01:04:39 [ML]
Well, pineapple is.
01:04:40 [CH]
There's a bridge or a bridge.
01:04:41 [ML]
It's more of a.
01:04:43 [RP]
Not an implementation.
01:04:43 [ML]
So yeah, we had three.
01:04:44 [CH]
But it is kind of interesting to think that potentially like the evolution of APL is more like regex, where you end up with like little regex expressions.
01:04:53 [TH]
No, yeah, I think you're thinking too narrowly, it's more like the like mathematical notation. Every programming language supports mathematical notation in its expressions. That is almost just a sub language like if you say plus divide APL it's just like interesting. So.
01:05:06 [CH]
You're thinking like, you know, take the Julia language where you can define your own Unicode operators and add you know the min and Max glyphs as extensions to the infix operators of like plus, minus and multiplies and kind of thing.
01:05:18 [TH]
You have to think bigger.
01:05:19 [CH]
Bigger. Not thinking big enough.
01:05:20 [TH]
So we wanted we once we once interviewed against Bjarne Stroustrup [35] the C++ Creator, what C++ would look like in 10,000 years. And he said that maybe by then it would have a decent syntax, and I think maybe what he meant is that the expression syntax would just be APL by that by that point.
01:05:35 [RP]
You talk about shoehorning APL concepts into other languages she missed the simplicity of, like being able to explore the syntax being able to just like chuck things together.
01:05:49 [TH]
Yeah, that's, that's, that's true, but you would have kind of a prompt way to do that I don't know. It's program language design is difficult.
01:05:56 [CH]
And yeah.
01:05:58 [RP]
We're saying it's like awkward to have to like write a string representation of an APL program, and then have the piece of the have the sort of interface.
01:06:07 [TH]
Yeah, you right, you don't want that. You need some kind of textual flexibility in the host language. So it's, so it's not just a string that you execute. I don't know what it would look like. I think common Lisp has a lot of flexibility.
01:06:20 [RP]
Maybe, but but April still does that I think, yeah.
01:06:22 [CH]
I think so. It is an interesting thought experiment 'cause like you think about, you know for all of us that work in Linux, or you know the shell in some other environment and you know how often are we catting the contents of some file and then piping it to, you know, grep and then piping it to WC-L. All of which is like, in my opinion, just as esoteric as the Unicode symbols in APL. But like, that's like a bread and butter tool if you live in Shell and it's like we all know that WC is word count and hyphen ls. Lines and like grepping to search for stuff and can't, like we learn this language that is to some extents foreign and like looks odd. It's like what is cat and what is grep and what is? I see, but because it's right there, people learn it as this like bread and butter tool and it's interesting, yeah. It's an interesting thought experiment to think about. What would a future programming language that has some translated version, you know, if yarn is saying in 10,000 years will actually have a nice syntax? It's like, you know. Folks that use that all the time, it becomes just like second nature. It's like we could have some kind of merged, I don't know, Python or C++ language with all of the power of, you know, the rank polymorphic glyphs of APL and, yeah, that would be it. Would be neat. I would enjoy my day job much more if that was something like that exists for sure? Hopefully it doesn't take 10,000 years because unless cryogenic freezing happens and I've got the money for that, which I probably won't. I won't be around for that, so. Alright, I think that's probably a good enough place to edit, seeing as we've we've gone over by quite a few minutes here. But thank you so much, Troels, for coming on and talking to us about Futhark and everything you know about sort of parallel computation. This has been so awesome. I've learned a ton, and and I have to go now and find some papers to read about both Futhark and SAC digging a little bit deeper to this stuff 'cause it's super interesting to me, and I'm sure our listeners will enjoy the conversation thoroughly.
01:08:26 [TH]
Fine, let's hope so and really, you should you should care.
01:08:29 [TH]
Other SAC on here.
01:08:30 [TH]
SAC did everything before anyone else in terms of high performance, high level, functional, array programming.
01:08:36 [CH]
Yeah. Are you familiar with the folks I know. I don't know, but it shows like, who would be the best person, do you think to reach out to, to have to talk about a single assignment C?
01:08:46 [TH]
Sven-Bodo Scholz is an extremely entertaining speaker. Artem Shinkarov I actually not seen Artem present. I know, I know of him, but I was. I would recommend Sven-Bodo. I think he was also the original designer.
01:08:59 [CH]
OK. Yeah. Well, we'll reach out and try and get some. I mean, yeah. And he's been working on that since it was in the late 90s or early 2000s.
01:09:08 [TH]
Early 90s something.
01:09:08 [CH]
Now early 90s. All right.
01:09:09 [TH]
I mean before, before people thought this was a cool subject to work on.
01:09:12 [CH]
Wow, yeah, we'll throw a link as a as a teaser. There is a I think it's a Microsoft. I was going to say Google Tech talk, but I don't think it was actually Google. It was like a Microsoft research from 2006 or 7. He went and gave a talk on single Assignment C, which is, you know, 15 years old at this point, but will be a little bit of a a teaser for folks that are interested in learning more about languages in this space?
And yeah, we'll try and get him on in a future episode, but once again, yeah, thank you so much for taking the time. This has been absolutely awesome. And with that we will say oh wait. Bob got one more thing.
01:09:45 [BT]
To say, I'm just going to plug, you can contact us at contact at array cast dot com because we've had some very interesting we've always had really great interaction with the listeners. But I think in the last two weeks we had Scott Locklin and then Stevan Apter actually chimed in again some really, really interesting things for us to think about, I think for our next episode, which is a teaser I think we're going to talk or may talk about Iversoniam versus other array languages, but that can all change because we're very flexible, creative people, and who knows what we'll do next? And so maybe you just have to turn to the next episode. Sorry for interrupting what will be the wrap up for the show?
01:10:22 [CH]
Not a problem not a problem so yeah contact at arraycast dot com all the links for all of the research and projects and paper as we mentioned will be in the show notes and yeah with that we will say happy array programming
01:10:35 [ALL]
Happy Array Programming
01:10:37 [CH]
The kitten joined for the end.
01:10:40 [MUSIC]