Nothing has ever convinced me about the potential for array languages in practice quite like watching Aaron Hsu describe how he develops his parallel APL compiler [0] using two Notepad.exe windows side-by-side: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
He has also written many comments (arcfide on HN) about this stuff before, e.g. discussing "semantic density" [1]
> The compiler is designed so that I can see as much as possible with as little indirection as possible, so that when I see a piece of code I not only know how it works in complete detail, but how it connects to the world around it, and every single dependency related to it in basically one single half screen full of code (usually much less than that) without any jumps, paging, scrolling or any movement. [...] The idea of semantic density is critical to this point. The semantic density of the APL code I'm using to solve the problem is at a certain rate. I maintain a consistent density rate by choosing my variable names in such a way that they visually align with the expressivity per character of the built in primitive symbols.
And
> [...] idiomatic programming methods that are so concise, they can begin to be read as we read and chunk English phrases. By doing so, it becomes actually easier to just write out most algorithms, because the normal name for such an algorithm is basically as long as the algorithm itself written out. This means that I start to learn to chunk idioms as phrases and can read code directly, without the cost of name lookup indirection. I can get away with this because I've made reusability and abstraction less important (vastly so) because I can literally see every use case of every idiom on the screen at the same time. It literally would take more time to write the reusable abstraction than it would to just replace the idiomatic code in every place.
I wonder if we can use transformer models to render text in a compressed form, not human-readable, but which allows other LLMs downstream to work more efficiently on the compressed data. The compression can be lossy or fuzzy and it's OK in this case.
In a way we could look at novels this way — highly compressed semantic data that allows the reader to extrapolate the writer’s vision without including every detail.
They have to write the crazy paragraphs because the code is ugly to look at, so they have to spend 18 hours convincing someone to use it. They could choose symbols that don't look so ugly next to each other, then they would not have to spend as much time convincing people the language does not suck.
I think I'd rather have a half page of APL with a page of explanations (given a little time to learn the language better than I do now) than 20 pages of Java that I have to scroll through with comments and unintelligible class paths.
Either way it takes time to consume the logic, but it's nice to have it all in one place than scattered about all over creation. I think that's what he's getting at with Aaron's more macro based view. He wrote thousands and thousands of loc before being able to whittle it down to such a terse amount. I can't read it, but that's less to do with APL and a lot more to do with knowing nothing of the domain of compilers.
The symbols actually make a lot of sense and can help you remember what they do. I can remember quite a few after only playing around with it a bit and reading a book on it ages ago.
For APL I started with the Mastering Dyalog APL book they have for free on their website which is good, but long. Someone recommended an ancient book I found on Amazon called "APL An Interactive Approach 2nd Ed." I think by Gilman and Rose that is very easy to follow. There are plenty of tutorials online now too (a lot more than when I started looking 8 years ago).
For J, I read a good bit of "Numerical Programming in J" or something along those lines. I've found J to be more difficult than APL or K to pick up tbh. The tacit trains is just a bit too hard for me to follow.
Your criticism amounts to "if it isn't pretty, it isn't worth it". Haven't we got past judging worth on surface beauty yet? Didn't we hear the story of the ugly duckling as children? Haven't we learned that there are tastes which can be developed (like cheeses, beers, spirits, cigars) and worthwhile skills that need time and effort and perseverance to develop?
> "They could choose symbols that don't look so ugly next to each other,"
Not as easily as you might think, given all the Unicode symbols exist because they already have a meaning to someone, and many of those might not render in typical font which computers already have installed.
That's a very reductive and bad-faith interpretation of the criticism. A much better one would be: "You can write either write a symbol soup with multiple paragraphs explaining what the soup does and why it is good, or you could write an equivalent amount of code in a verbose, readable language. The former option introduces two places for errors: they could be either in the code, or in the mapping from the code to the prose, while the latter only has one."
Symbol soup is just fine when you're working in a highly restricted domain with limited scope for novel abstractions - which may well suit the idiomatic usage of array languages. Math expressions are symbol soup, but a trained mathematician can read them quite directly.
Math expressions and notations are far more expressive than APL or J, because they are graphical, highly flexible, and not meant to be compiled. They also tend to be accompanied by text for whatever cannot be efficiently conveyed by the notation.
This is an argument which has been going on for years; "crazy paragraphs because the code is ugly" is a thoughtless low effort criticism and it doesn't deserve a steelman fleshed out rebuttal if the person hasn't put any effort in.
You say "a symbol soup with multiple paragraphs explaining what the soup does and why it is good" - honestly, do you think people write multiple paragraphs explaining the code to beginners who can't read APL every single time they write any APL? Of course they don't! Your proposal relies on "symbol soup" being a fair and accurate description, which it isn't.
And, are you suggesting that people don't write comments explaining their code in common popular languages? Of course they do! (and should)
And, are you suggesting that people don't have to learn and practise to be able to read common popular languages when they learn to program? Of course they do, look at posts around the internet on people learning Java and Rust and C# and C++ and Python asking what some code means, what some syntax means, and not only beginners, lots of people ask like "I can code but what is this syntax?" and it's a Python generator comprehension, or a ternary operator, or a C# LINQ SQL style or a pattern match or an anonymous function or a compiler hint or a documentation generator template or a generic type or a turbofish or whatever thing they hadn't seen before in their previous languages or codebases.
And, are you suggesting that comments getting out of sync with code is only a problem in array languages? Of course it isn't.
Or that nobody ever complains about the readability of Java because it's so verbose and has so much abstraction you can't see what's supposed to be happening? People do. I do.
And as always, what about regex? It's so useful as a text processing language that it's often still shorter and cleaner to write a complex regex and paragraphs of comments explaining it, than to code the equivalent in classic string indexing and slicing and if/else branches. You'd end up writing a Greenspun-esque ad hoc, informally-specified, bug-ridden, slow implementation of half a regex engine.
That's not to say there is no criticism of APL's style possible, but if you want people to take the criticism seriously, have something new to say about it or some solid support and explanation for it. "Whenever you look at a problem somebody’s been working on for a week or a month or maybe years and propose a simple, obvious solution that just happens to be the first thing that comes into your head, then you’re also making it crystal clear to people what you think of them and their work." - https://exple.tive.org/blarg/2019/04/17/why-dont-you-just/
The language doesn't suck for people who use it. They learn the symbols just fine and are able to understand what's going on. Same thing for math, which can also be very terse.
Which is better, compact or verbose code? That's a style issue and it all depends on who you ask. Verbose code requires you to read more. And more code to maintain.
You can do 'regular' stuff in array languages too. And distributed searching/sorting sounds like something array languages would be good at anyway. kdb being the obvious example. The IPC in q for example is very easy to use, and seems better than most languages that aren't Erlang.
Well, I agree in the absolute sense. Not in the practical sense. In fact there is a ranking because on natural affinity and baseline-existence-of-what's-already in the domain. That's is what it is ...
I'm far from an expert on such things, but Co-dfns appears to be genuinely cutting edge research that could have utility for many language ecosystems (or do you disagree that this direction of GPU-based compilation holds promise?). If that work has to look like a "mess" to non-APLers in order to get done then so be it.
I criticized the approach some in [0], after writing the BQN compiler in a similar style. Pioneering the array-based compiler paradigm is a major accomplishment, and if you did any programming with Aaron, you wouldn't question his ability. The Pareas compiler demonstrates that an APL-like language isn't required to do it though. And while the research may be applicable to other problems, I have serious doubts that it will be useful for speeding up optimizing compilers, which spend time on very different things than simple ones. Also possibly worth mentioning that Co-dfns still doesn't self-host, which I believe means it can't run on the GPU. I'm still unclear on what GPU program was timed in his thesis, a hand-translated version?
Thank you for the link! That's a very interesting overview. Do you think the commodification of FPGAs could add another angle of interest/motivation here? Or is that hardware model likely to be incompatible with how these compilation techniques work?
I'm personally rather curious about the intersection of compilers and database query engines, where ~cheap dynamic/incremental compilation across extremely diverse runtime workloads is often a basic requirement.
As in, compiling for FPGAs or running on them? Can't really say anything about compiling-for. I know building Verilog takes forever but I have no idea what it's doing.
For running-on, APL adapts well to most hardware. I mean, we're talking about a paradigm that's existed longer without the concept of GPGPU than with it. I don't know if FPGAs would have an advantage over GPUs, since the bottleneck is often memory bandwidth and from a quick search it seems FPGAs are worse there. But the problem is still implementing compiler passes in APL.
Ah I was thinking about running-on, but compiling-for is probably relevant also :)
> I don't know if FPGAs would have an advantage over GPUs, since the bottleneck is often memory bandwidth and from a quick search it seems FPGAs are worse there
Thanks, that makes sense, though I believe (and hope) the situation can reverse.
> Brags about how easily he understands his giant ball of overly messy code (2- letter variables in the name of “semantic density”)
@arcfide left one of my favorite comments ever, in response to another comment similar to yours (for which the author apologized). I refer to this often.
> “Don't complain that Chinese is ugly and unreadable just because you speak English as your native tongue.”
The analogy here slightly breaks down since there are billions of people who speak and read Chinese already, while apparently the coding style in question is more of a niche thing trying to justify itself.
I don't know enough about APL or using 2-letter variables to comment on whether they're actually justified, but my personal hunch is that their usefulness is going to be limited to particular problem domains and people with particular inclinations. (The same goes for verbosity on the other extreme like particular Java projects...)
From memory (not very reliable but I'm not going to rewatch hours of video to find sources), Aaron said that when he asked around about working on a nano-pass compiler as a PhD thesis, nobody would take him seriously because it was believed to be impossible to do in a performant way. And he has done it, with this style of code. An world first. And it worked out orders of magnitude faster and less memory and less code than a comparable compiler written in Scheme (which Aaron is pretty good with - he used to be involved in the Scheme R5RS and R6RS standards committees).
He's also built the world's first APL compiler which runs on a GPU and outputs GPU code.
> - Brags about using Notepad instead of the fancy IDEs that us weak-minded plebians use
One of his points is that he's convinced programming as an industry went wrong by sidelining array languages, and we shouldn't need to be writing so much code to get things done. It's not so much bragging about using Notepad, as making a point that a) Notepad is enough for a complex piece of code, b) IDEs can't help much with tacit array code because there isn't tons of boilerplate to autocomplete, and c) concentrating on the code is easier without a lot of distractions.
> - Brags about how he can understand his own code. We can all understand our own code. Good code is understandable by others.
Another one of his points is that people who have not learned traditional programming find array-based programming much easier to pick up. And that's aside from the usual discussions here where you're basically saying "Brags about understanding Chinese. We can all understand our own native language, Good writing is written in English". Other people have contributed pull requests to co-dfns (apparently).
> - Brags about how easily he understands his giant ball of overly messy code
Given your previous criticism is that it's "not understandable", emphasising how it not only is understandable it's quite easy to understand, seems like a reasonable rebuttal for him to make. Apparently he's damned if he does, and damned if he doesn't.
> - (2- letter variables in the name of "semantic density")
That is the array style; his compiler is tacit (no variables) as much as he can make it, which means the few variables which are left are much easier to keep track of in memory. Regardless of that, there's a big gap between languages where people write 'k[i]=m[j]uv' and languages where people write 'pyramidPointVector[pyramidPointVectorOffset]=adjustedShadowMaskBools[rowAlignmentCounter]...' or whatever.
> - Uses an obscure (in the modern era) outdated language like some Cinema aficionado who refuses to watch movies in color like all those plebians
But also like someone who uses any highly specific tool for experts instead of the standard thing an ordinary person might find at Walmart.
> Another one of his points is that people who have not learned traditional programming find array-based programming much easier to pick up.
I have had the same experience when teaching SQL.
I feel like it is difficult for people who have worked with imperative languages to grasp, while people who come from the Excel school (e.g. business people or researchers) actually enjoy it and may even pick it up faster.
I believe SQL and array languages have this and probably much more in common. I am probably out of my league here, but I think I'd call SQL a set language rather than array language. But feels like they are related.
I listened to the first ~5 episodes of The Array Cast wanting to be persuaded, but I just couldn't buy in.
They downplayed the terseness and non-ASCII symbols of the array languages as something you get used to and something that's worth it to get the benefits of array languages, but the benefits they listed were mostly ones that I'm already very familiar with from working with higher-order functions in most mainstream languages today.
It felt like the hosts had missed that map/filter/reduce have gone mainstream and are now available ~everywhere without having to learn a whole logographic writing system first.
As an array language fan I also feel like a lot of the reasons people give for why array languages are powerful are outdated, and sometimes (not all the time) that's because someone tried both APL and C in the 1970s and their opinions haven't changed since.
However I still find them useful (and fun!) because of the terseness, not in spite of it. Terseness means array languages are very mathematical in nature + can be really ergonomic to write, especially with the repl. If someone said "learn an array language, they're easy to write on paper" everyone would think they were insane... but there is something to it, in certain cases. The idea of "fearless refactoring" is popular in the FP world, but it can also be true in the array language world too.
> "learn an array language, they're easy to write on paper" everyone would think they were insane... but there is something to it, in certain cases.
Indeed, and sometimes not needing a computer to quickly splash out an idea you're thinking/talking about is extremely useful!
Over Christmas, I showed my brother {+⌿⍤2(∘.≤)⍤1⍨⍵} as a small expression to explore attribute to pick playing Top-Trumps admist a discussion. Not something you'd be able to do in many other languages!
Sure - idea is you've got a 6×30 matrix of the 6 card attributes for each of the 30 cards, and want to know for each attribute how many other cards they'd beat.
{+⌿⍤2(∘.≤)⍤1⍨⍵}
{ ⍵} ⍝ single argument (monadic) function with argument ⍵
{ ⍨⍵} ⍝ "selfie" - ⍵ f ⍵ where f is (∘.≤)⍤1
{ ⍤1⍨⍵} ⍝ on each row (1 dimensional element)
{ (∘. )⍤1⍨⍵} ⍝ cartesian (outer) product of each row with itself
{ (∘.≤)⍤1⍨⍵} ⍝ ≤ comparison of those elements - produces 6 30×30 boolean matrices
{ ⍤2(∘.≤)⍤1⍨⍵} ⍝ on each of those matricies (2 dimensional element)
{+⌿⍤2(∘.≤)⍤1⍨⍵} ⍝ sum the columns
leading to:
{+⌿⍤2(∘.≤)⍤1⍨⍵} ⍝ compare each row (⍤1) to itself (⍨) and count (+⌿) how many cards that beats
Thinking about your comment further (and having read TFA and some of the comments) inline usage does seem to make more sense as it's only a few more characters. In that way it's transparent. Decreasing indirection (assuming that the operators always function simply and plainly.
Array languages come up a lot on HN so I’ve looked into them a few times. I think it’s a hard thing to gauge without trying to use them in anger for a while. One of the core arguments for them that resonates with me is that once you understand the operators, many patterns become so terse and repeat so often, you can refactor large portions of code very rapidly. I use a lot of F#, and can see the beginnings of this where translating from C# to F# often shrinks the code size to the point where I see patterns that weren’t obvious before. I believe APL, K, J, Nial, BQN, etc all have more extreme versions of that happening.
It also makes differences stand out so logic bugs are more visually obvious.
Sometimes the benefit of shorter codebases is that you can actually see the code.
Understanding that your logic bug is obviously somewhere within a handful of lines of K/Q/etc that fit neatly on a single screen vs scrolling through 200 lines of logic in Python/Java/whatever is focussing.
Sure each line is more compact and may take more time to digest, but that is a reasonable trade-off in most cases.
For me, 10 lines you need to read carefully beats 100 lines of having your eyes glaze over and repeatedly skip over the bug because you are so dulled to all the boilerplate.
I can corroborate: That same feeling of as simple and terse code as possible happens in Haskell too.
However the most popular professional style of Haskell code is far too verbose for me to be able to "see the essence" in many cases without a round of refactoring.
Its far worse and far more grating for Java code that makes you do so much for so little.
Map/filter/reduce are just primitives. The composability built on top of them and coherent system of using these higher level combinators is where other languages fall short.
Other languages support regex for example, but perl takes it to a different level that changes the language experience.
I am often in these threads on HN arguing in defense of the underdog (array languages); I do tend to agree with you here. I think the early days of APL (and Prolog) were that they were high level casually-typed REPL based interpreted languages, in a world of Fortran, PL/1, COBOL and C, and the amazing nature of them back then is stuff we take for granted writing items=[1,2,3] and lookup={'key':'value'} in Python and not worrying about allocating and freeing memory or pre-declaring the variables and their types, the string length, and compiling, and whatever.
Still, there is a fun about a desk calculator on so many steroids that it's a Turing-complete programming language. One of the ArrayCast podcast guests said array languages were "like a Domain Specific Language (DSL) with an enormously wide domain". How many mainstream languages will let you fork and hook and have inverses and over and under and recursively descend into anonymous functions, without ceremony or boilerplate code? You could have that now to play with, without waiting for it to go mainstream, just by learning a two or three dozen unfamiliar glyphs - compare that to the effort of learning a whole new framework for making web applications and it's much smaller.
This is how I found out about BQN. I'm still not sure I'd use it in production somewhere. Even though I like it, most array languages seem rather foreign if it's not, I don't know R, NumPy, Julia maybe.. venturing deeper into APL, J, BQN I'd just alienate any support I could hope to recruit.
I’m super curious about exploring array languages. What domains have you found it particularly effective, or at the least provides you with a new way of solving a problem?
I discovered APL/APL2 in the 70's (using actual overstrikes on a paper terminal) and fell instantly in love with it. But when I later discovered functional programming with ML and Haskell, I realized that what I really enjoy about APL had little to do with arrays, but more with its ability to compose functions.
Haskell is so much better at this, being completely pure and typed throughout, and is even more fun and powerful than APL; I've used it to write a lot of small and medium-sized projects, prototype LLVM Flang's parser to prove the concept of using parser combinators for Fortran, and do Advent of Code each year in a few hundred lines of code total. If you like APL, try Haskell.
Today, I think that the whole "notation as a tool of thought" aspect of APL is a rationalization for excessive brevity -- which can be a good way to demonstrate the power of composition, but which can work against clarity.
Yes. I'm a broken record on this topic, but I largely stopped messing with J and K once I got decent at writing point-free Haskell. Verb trains are even more powerful with functors in the mix. <=< is already available, and once you write an equivalent for fmap, you really start cooking. |||, +++, &&&, and *** are great too. And you can always write UTF-8 operators to make it even shorter and prettier.
It's unfortunate that the serious Haskell I've seen at work/in the wild is rarely friendly to vertical screen realestate in this way.
I have a question about array languages that I've been wondering for a while: lets say you have the task "find all numbers smaller than N where predicate P is true". You know, like, "find all primes smaller than 1000", or "find all pythagorean triplets where Z is less than 1,000,000", something like that. The general pattern for doing this in an imperative language would be to have a for-loop that tests the predicate inside and then does something with the number. In a functional language, you'd use recursion or map/filter on a lazy list, something like that.
(to be clear, this is in the general case where you don't know exactly what P is. for the specific problem of finding primes smaller than N, you could obviously use sieves and stuff, but i'm more curious about the general pattern of problems like this)
Having only had limited exposure to array languages, my understanding is that in general the way to do that would be to do something like:
1. Generate an array from 1 to N
2. Test the array against the predicate, getting a new array with 0s and 1s (a mask, essentially)
3. Apply that mask to the array to get only elements where the predicate is true
Which is all fine, and I imagine that it takes a stupendously small amount of characters to do this. But my question is: what if N is large, and the predicate isn't true very often? Like, what if N is a billion or something? This is not an issue in the imperative/functional cases, because they don't have to generate the array in step 1, they can just loop/recurse/lazily generate the values (i.e. memory is O(1) for this). But it seems extraordinarily wasteful in array languages both of memory and resources to generate two different billion element arrays (the 1..N array and the mask) just to get out a handful of values.
That question is pretty specific, but this is one of my biggest questions about array languages in general. Aren't you always generating TONS of temporary arrays for no real reason, that will just pass through the calculation? Isn't that really slow? Or does the implementation somehow optimize this stuff away, maybe by using something like lazy evaluation?
Yes, you waste a lot of memory. Memory's cheap. If you need to, you can do the computation in blocks. Well, it's pretty rare to actually run out of memory but blocking is useful for staying at a lower cache level.
Scalar languages have a different problem: the default is to process one value at a time, which wastes the potential parallelism that array languages take advantage of with SIMD algorithms. Because this is the status quo, it's not as easy to see this as a big concern. And the solution is also blocking. That is, the best algorithm for SIMD-friendly stuff is generally a blocked array method.
In practice, whether an array language is good or not really depends on the specific problem. Of course, for most practical uses performance doesn't matter at all; I believe k's reputation mostly comes from kdb being fast as a database rather than k implementations being fast languages. But array languages can be surprisingly fast just by focusing on elegant array algorithms rather than machine-specific considerations. I have comments and benchmarks comparing with C here:
Languages that can stay in L1 cache for the duration of a computation will run circles around a language that explicitly computes and stores all intermediate values in full.
Also, array-based languages can easily hit the wall of system memory capacity whereas traditional code tends to be streaming and can handle unbounded input lengths.
Which is exactly why I said you block the computation to stay at a low cache level. With SIMD loads and stores I don't think this matters quite as much as you suggest, even without blocking. It's pretty much only arithmetic that can saturate L1. I timed the BQN compiler on various files (some old version of itself, repeated). For 18K it runs at 21.4MB/s; for 1.7M, 16.5MB/s; for 17M, 12.0MB/s. So even when the source won't fit in L3 (mine's 8MB) the degradation is under a factor of 2 (and of course the compiler makes no consideration of cache, who writes a megabyte of BQN?).
There are a couple options for working around this. Lazy evaluation is indeed one option (e.g. Kap[0] uses it). Another clear option is loop-fusing the entire body together such that there are no temporary arrays.
Then there's the slightly simpler option of splitting the operation in chunks of a couple dozen kilobytes of input/output arrays such that unnecessary temporary memory usage is bounded; as far as I know no array language does this, but I hope to one day do something like this for CBQN. And this is even a thing that a user can manually do in an array language (and indeed often have to for maximizing perf).
Your intuition is largely correct, but it is rarely a practical problem. The k language, including the ngn/k dialect has some lazy constructions for example !10000000 (iota of 10 million), will not create an array of with 10 million ints but a simple range from 0 to 10 million. Depending on the operator you will of course end up with such an array. There are also certain optimisations (I think they are called colloquialisms) where things like +|x, reverse x and take the first element, is translated into just take the last element.
I think you might think the array instantiation is literal. Nothing prevents an array language from handling it in chunks under the covers. If I ask it to give me an array of 10 billions integers, it may not naively do that. Not an expert , just a thought.
Many array languages do have this issue. To be precise, the issue is that the simple straightforward approach tends to compute a lot more than necessary.
It's of course possible to do it in a different way to deal with that issues but those solutions can be a bit longer and less pretty.
The APL dialect I'm working on (Kap) solves this problem in many cases by delaying the computation until the result is needed, which means that you can write the code using the straightforward approach but still avoid computing results that will be thrown away.
Briefly: yes, you generate lots of temporary arrays, but it is not slow because it often allows the use of vector instructions and parallelism, it can be faster than a constant-memory loop that does not take advantage of vectorization or parallelization. Also note that most array language implementations reuse temporary arrays a lot doing in-place modification when possible.
If the necessary temporary arrays are really huge, array programmers will just do the computation in chunks that fit comfortably in memory.
I am not sure if R meets the definition of an array language to the extent that K does, but it produces the “cannot allocate vector of size” error not infrequently.
This is not quite the problem I was asking (i wanted to know how many numbers smaller than N this is true for, not the first N numbers it's true for), but it illustrates my point anyway: the i.1000 generates an array of all numbers [0,1000) that is then immediately discarded. In imperative and functional languages, you don't need to do that: in an imperative language it's just loop counter, and in a functional language with lazy evaluation (e.g. Haskell), it's a lazy list that doesn't ever store all 1000 numbers.
My question is: will J cleverly optimize away the i.1000 array? Is it lazily generated, like in Haskell? Or is this just one of those "we don't really care about the memory of the i.1000 array, it's usually small in practice"? Like, for high performance stuff, it seems relevant to me that you spend an extra O(n) memory for no real reason.
So basically you already have an arbitrary list of 1000 numbers.
That may or may not be prime? And you want to know how many are prime? (Let me know if I am wrong)
1. Pick the highest number, H in the arbitrary list of 1000 numbers.
2. Generate all prime numbers up to the highest number, H.
3. Use e., Verb also known as member of to check for prime numbers present in arbitrary list. +/(all prime numbers up to H e. arbitrary list of 1000 numbers) will give you the number of items in the arbitrary list that are prime.
> will J cleverly optimize away the i.1000 array?
The primitives & verbs in array languages are designed to be as fast and efficient as possible.
So even if your code is mediocre, it will perform better that any mediocre imperative code.
I believe J doesn't have any optimizations specifically for the problem of large temporary arrays (not to say that such can't exist, but I don't think anyone's written such yet). With multiple temporary operations, each making a temporary array larger than cache, it could in fact end up slower than mediocre imperative scalar code.
in general one doesn't want to materialize the intermediates. one evaluation strategy is treat the sets as streams. this removes the for loops, and leaves the evaluation strategy intact. for more complicated expressions, also allows you to move the filters first (referential transparency for the win), just like you would if you were compiling a relational query.
> "I imagine that it takes a stupendously small amount of characters to do this."
You're right, but it's not just codegolf; ideally the few characters are a clean high level way to express intent - and that is in tension with caring how a machine executes the algorithm most quickly.
> "This is not an issue in the imperative/functional cases, because they don't have to generate the array in step 1, they can just loop/recurse/lazily generate the values (i.e. memory is O(1) for this)"
It kind of is the same problem, just pushed down a level or two; writing it casually in Python will not get you the fastest performance, you should be working in C or you're wasting a lot of potential running the Python layer, then care about how you can parallelize the computation or you're wasting 7/8ths of an 8-core processor, then caring how you can make best use of the CPU SIMD instructions or you're wasting another half or more of the machine potential, caring about branch predictors, and caches, etc. That a loop written in Python is "not wasteful" but materializing a large array "is wasteful" is where the industry draws a fairly arbitrary line. The ArrayCast podcast episode 52 touches on this[1], me cutting/editing some relevant parts from the transcript; [ML] is Marshall Lochbaum who did performance optimizing work on Dyalog APL and designs/implements the BQN array language, and [CH] is Conor Hoekstra who hosts the podcast and works in nVidia research:
> ML: "using linear memory is just how array languages work. For any problem, pretty much, you're going to have to make a bunch of new arrays."
> CH: "there could be an array language that avoids [materializing] arrays when possible."
> ML: "it's going very much against the grain of the language to say, "All right, I've specified my answer in these high-level array terms, and now I want you to turn it into a C program for me"."
> ML: "it's still nice to specify a problem this way, but this array form for specifying gives you some pretty big advantages. [...] if you try to pack that all into a big iteration, your algorithm is no longer expressed as an array operation - and these array operations are things that we know how to do really quickly. You are giving up some performance information if you tell it, well, yes, I'm in an array language, but don't actually make me any arrays."
> CH: "my dream is that I want to be able to write like the most expressive solutions to problems and then have [the array language implementation] do the most performant thing. Like for Kadane's [algorithm], for example, the most performant thing is to hand roll that reduction yourself. It's going to be faster than materialize."
> ML: "I'm not convinced of that"
> CH: [where I work we have to optimize for teams working on large problems, recently had a discussion where 2 billion items is a small number]
> ML: "2 billion /is/ a small number"
> ML: "what you can do, even when you have an array algorithm, you can split it into to smaller arrays. this is often a lot better because you get to use vector operations with these. So for Kadane's algorithm in particular, I don't know how to express that purely with vector operations, but I think there probably is a way. And in that case, if you write it in C style, where you interleave scan and reduction, then it's much harder to go from that to a vectorized algorithm which (if it exists) would almost definitely be the fastest way. The way you would get the array thing to be cache friendly is that you run it blocks. And then within a block, it's doing a bunch of vector operations, but what you really want is like, you know, working on two vector registers, say at a time. the array language doesn't automatically chunk, but it's not that hard"
> ML: "Yeah, and I think the way for the implementation to get the best [performance] - maybe not with this particular problem - but definitely for things that are friendlier to arrays where you don't have any compound functions inside scans. The way to optimize those is not to immediately break it down into a series of scalar operations, but instead to be more careful and start with your whole array stuff and break that as necessary, and maybe even compile these array operations into operations of individual registers, which is hard. Nobody's really done that, but coming from the other side, from C, there have been who knows how many man hours poured into work on auto vectorization. And it's still pretty terrible. It would have absolutely no chance of handling something like Kadane's algorithm."
> ML: "getting the best implementation of an idea is pretty difficult. But I think actually starting from an array representation, you do have a pretty good chance without going through a C style scalar representation first."
That's edited parts from a longer chat; but yes if you want to write X algorithm without wasting machine resources, that's a hard problem and takes a lot of low level C/SIMD/CPU skills and time. Array languages can vector-accelerate the primitives of array symbols much easier than C compilers can identify vector-accelerate arbitrary looping code.
Troels Henriksen (Futhark developer) pointed out to me that in expanding the state to make the scan associative I'd reinvented a fairly well-known method. The transformation from a specification as "maximum over the sums of each subarray" to the associative scan is very often used as an example of the power of the Bird-Meertens formalism or Squiggol[0], and some newer papers have demonstrated that it can be derived automatically, although not very quickly. Troels also wrote a simpler ISPC[1] implementation[2] that tested slower than C on an older CPU and faster on a newer one. Then I translated that to BQN and found it was about 4x slower than sequential C.
I don't know, my personal/biased/limited impression from solving K language problems for the job interview is that the language is on purpose obtuse. It's a nice language for puzzles and clever solutions.
But IMO, working with numpy arrays in Python -- that's what teaches you array language, and how to think in arrays.
I have some experience here and I spent 50 hours or so on J, but frankly I found the paradigm too biased.
I’m not sure it helps —- as a tool of thought —- to conceive every problem as a nesting of arrays. IMO, having freedom to produce data structures which capture your problem can greatly simplify the algorithmic part.
I think you do have to be smarter to use APL/J/K because of this bias: it’s often the case that a direct approach available in a more flexible language will not be available, and you have to transform the problem, which may require a lot more thought.
but why give it a name when spelling it out is as short as the shortest reasonable name for it (and then you might need to put spaces around the name).
For people who understand the language, there is little point to naming it. For illustrating to people unfamiliar with the language, it helps to break apart the "this is the thing I'm talking about" part from the "here's how you would use it" part.
The APL/J/K/Klong versions are more general; they all work for a variety of ranks of input, whereas the Haskell version- which is the longest and most visually noisy- bakes in a single rank's mapping explicitly.
Looking at the example, is there a point to this? Is it more performant in anyway?
The syntax for matrix multiplication is shorter, but that’s only because there is a bunch of built in context you have to keep in your head about how the K language works.
It's more concise, which has value. In particular, think about how maths really consists of packing more and more concepts into higher level definitions. This is similar: higher level concepts become primitives and allow you to think faster and build more complex objects.
I can see that, though it really depends on what these abstractions are, how complete they are in solving in a variety of problems, or I suppose, how frequent the problems it makes easier in relation to ones it makes harder.
I’d have to know a lot more and spend a lot of time before judging.
But I am not impressed seeing a single example. I could hypothetically write a language where mergesort is the operator * and reversing an array is the operator + and showcase how in my language 30 lines of code becomes 1. That would be insanely nice if you’re doing something which just requires thinking about sorting and reversing arrays but all together, very poor thing to build a standard language on.
That's what people do on codegolf.stackexchange.com with the dedicated golfing languages. What's interesting about APL is that it started out as linear algebra and became array programming, and the primitives are more "things which are useful transforms to do on arrays" rather than "thing people wanted to do in one problem turned into a symbol", and that's enough to be useful in many tasks.
> "That would be insanely nice if you’re doing something which just requires thinking about sorting and reversing arrays but all together, very poor thing to build a standard language on."
Prolog has linked lists as its main data structure, which means prepend is more performant than append. In the SWI Prolog documentation for foldl[1] it says "No implementation for a corresponding foldr is given. A foldr implementation would consist in first calling reverse/2 on each of the m input lists, then applying the appropriate foldl. This is actually more efficient than using a properly programmed-out recursive algorithm that cannot be tail-call optimized". i.e. you don't have to have a problem which involves reversing arrays, for reverse to be a useful part of a solution.
In APL reverse is one character ⌽. In C# to find the first comma in a string you use IndexOf(',') and to get the last one you use LastIndexOf(','). In APL you would use the equivalent of indexOf(Reverse(string)) and then you wouldn't need the specialised LastIndexOf - and wouldn't every other function which works from the left of a string or array to have an equivalent which works from the right. https://aplcart.info/ is a database of idioms and samples of useful APL and it has 168 pieces of code using ⌽.
It _can_ be more performant because computers are exceedingly fast at cranking through arrays, especially if you can leverage SIMD, but its not just that.
It's useful to play around with an array language until the paradigm clicks. Often, imperative code can be better handled in an array style. Sometimes long, fiddly functions can be greatly simplified if you use array operations instead or in conjunction with other styles.
If you believe that verbosity has a cost and that only the most complex functions should have the privilege if being verbose, it's easy to see a point.
Here's a Haskell example:
(+) <$> Just 1 <*> Just 2
Versus:
do x <- Just 1
y <- Just 2
Just (x + y)
I would always prefer the first for something of this complexity because the latter example implies something more complex is happening to me because it takes more space.
If I had something more complex, I'd prefer to factor that operation into functions small enough that the first variation makes sense over using the second.
This does trade "beginner+ can read this quickly" for "some beginners can read this".
I'm of the opinion you shouldn't optimize for "some beginners can read this" because of very diminishing returns.
Instead I aim for "beginner+ can read this" or in some cases "intermediate+ can read this".
There are all sorts of reasons for using any language and there are just as many reasons for not using that language.
But the problem is not the terseness or the relevant clarity of any language or its ability to compile to fast code. It is the ability of any programmer who comes along later to make changes to that code in support of its use.
All too often, programmers want to show their [leet] skills and fail to take into consideration the poor sods who have to come after to support that code. The reality is that much [leet] code has to be discarded or completely rewritten to get something that is supportable long term.
It took me a long time to understand this and after this, I made sure that my code could be supported by others - clean, simple and comprehensible. Too much throwaway code becomes the basic infrastructure used in organisations and becomes entrenched and incomprehensible to following generations.
Should be interesting to see what people will do the the RISC-V (V)ector extension with array languages. I would think there is a pretty straight 1:1 conceptual correspondence there, and one could write a pretty nifty compiler to go from an APL-ish thingy to those instructions, and get some serious oomph.
While RVV still makes for a good target for arraylang implementations, RVV isn't really much closer to arraylangs than AVX-512, or really any SIMD if you squint hard enough (the scalability of RVV/SVE is unrelated as you still need to have loops; and the existence of VL, while nice, doesn't give any new fundamental possibilities).
Basic list operations might have a roughly-1:1 mapping to simple RVV loops, but many others still require a decent bit of extra code (all search functions (hash- or lookup tables), narrow matrix ops (processing multiple rows at a time); even compress operations get questionable when there's multiple of them due to their variable-length nature).
One thing I always wondered: how do these codebases pan out in terms of maintainability? Are there J/K/APL programs with many programmers working for many years on the same code, with people joining and leaving the project? Do they continue to follow the same terse style that is beloved by most users of these languages?
Good point, also not convinced while following the topic. I also received an APL manual from an economist using APL in the 70/80s. It was a gift.
Regarding interesting programming paradigms I am biased toward SMTs and things alike where you just specify your problem and a solution and tests are generated. Not saying that you can build a big part of a system using logic now but I think will be evolving to more areas of expertise in the future. In a way, from a software engineer point of view, I see AI in the same vein: a black box that could produce interesting results for speeding up software development.
Fortran has the matmul intrinsic function, and you can define an operator .x. so that a .x. b is equivalent to matmul(a,b). APL, J, and K are not unique in being able to express linear algebra operations concisely.
You can’t define a generic interface in terms of another generic interface in Fortran. To do what you suggest in actual Fortran, you would have to write specific functions for all the combinations of data types and ranks supported by MATMUL (hundreds).
Array-oriented languages (or Vector-oriented languages, if you like) are generally distinguished by features like concise syntax, implicit conforming/mapping over homogenous collections, and a strong de-emphasis on explicit looping or recursion in favor of abstract (and often parallel) iteration.
Some of these features could be implemented- to an extent- in a Lisp, but they do not reflect normal Lisp programming style.
list languages and array languages are quite different.
in LISP, the lists are heterogeneous i.e. each element can contain different types, which is also how you can e.g. make a tree out of lists in LISP.
typically in array languages all elements are the same, and you use operations that apply to the whole array e.g. one operation for summing the array rather than a loop.
Several people here are questioning the utility and/or the comprehensibility of this. I'm no expert on array languages -- I've played with J and solved maybe a few dozen project Euler problems with it, but here's my take:
1. Array languages aren't well suited to *every* problem.
2. They *are* ridiculously capable for many types of problem.
3. The people using array languages are generally insanely smart.
4. Learning how array languages work is a steep challenge. As shown in the linked article, it's possible to write "procedural" code in an array language, and that is a Very Bad Thing. It's like using a screwdriver as a hammer.
5. In particular, understanding how tacit programming works is an awesome mind-expander
6. Likewise when you internalize verb trains
7. Likewise when you realize how array-based languages handle *any* dimension array.
8. Likewise when you comprehend how "under" works
9. Likewise when you understand how function exponents work
There are many other awesome aspects of array languages; the above are just a few.
Tacit programming is not unique to array languages, many FP and FP-like languages support it. Generally array programming languages will be a bit terser if you're working in problem domains that are idiomatic for the language, but FP languages can be more general and extensible. The "people using these languages are so smart" attitude is often criticized as it can devolve into gatekeeping, but at least FP communities make somewhat of an attempt to be friendly to outsiders.
FWIW I think array language communities are generally very friendly and helpful too. Not many programming languages/companies employ people to help people in chatrooms.
Are there any type systems that work well for the array programming problem domain? Not the kind of ‘everything is an operator’ syntactic sugar, to be clear. More things like supporting the kind of general operators you see in array languages while also expressing the constraints on dimensions, eg for matrix multiplication you need the number of columns on the left to match the number of rows on the right. But the thing written at the end of this post presumably also does things on arrays of higher rank too…
There's a fundamental opposition between the functional programming approach to types and array programming principles, as I see it. In functional programming (particularly Haskell), types are used to make fine distinctions for safety. Even if an existing type would work for something, it's often recommended to make a new one so two different use cases don't get mixed up. But the APL family works to make as few type distinctions as possible: everything is an array, booleans are numbers, and some k features are to unify multi-dimensional arrays with nested ones and sort-of-unify (it's complicated) functions, dicts, and arrays.
The reason to do this is that it allows one function to do more things. As you guessed, the matmul function from the tutorial works if the right argument has rank 1 or more, which means it also does matrix-vector products. Less code is another form of safety, the theory goes. And handling more things with the same function also lets you draw higher-level connections.
Of course you can type the arrays anyway. Remora is one attempt. To me it feels like just a technical exercise and I think this question calls for more high-level investigation of what exactly the goals are before jumping into PL theory details.
I want a type system that can reject attempts to add a vector of length 3 to a matrix of size 4x5. And I would want it to allow writing a single type for + rather than the way that Julia (iirc) handles these cases where there are various methods and the rules of method selection are applied to construct the effective method that does the right broadcasting.
This isn't really a fundamental disagreement. If we think of array functions as functions `Array<Index1, Element1> → Array<Index2, Element2>`, then essentially all you need to be able to say is that a function is generic over `Index1` and calculates some output index type `Index2` as a function of `Index1`. This is perfectly possible to do with Rust traits or Haskell type classes (although not all that ergonomic).
You basically need types that can depend on program constants (like the size of an array) and to be able to do compile-time computation on these constants. These are emerging features of sorts, but languages like C++ and Rust support them. They're also inherent to dependently-typed languages. (Of course you can alternately pick array sizes at runtime, but then you'll be dependent on a runtime check wrt. correctness.)
Surely most of the time you don’t need program constants? You could already implement a slow matrix multiplication that is well typed in a language like Haskell or OCaml. It would have a type something like:
.) This could work for dimensions that are unknown at runtime for Haskell or OCaml as their polymorphic functions can be implemented by a single machine code function where C++ templates / Rust generics must monomorphize (generate different machine code functions for different types). You would probably want existential types (though OCaml and Haskell have them).
I think the problems are more things like:
- that type only works on matrices, you can’t so easily express that eg * in APL works on two scalars, or two vectors of the same length, or a matrix and a rank-3 array so long as their dimensions line up appropriately.
- handling operations that change lengths is hard: concat probably wants you to be able to unify through certain arithmetical expressions, and the filter operation (take an vector and a bitvector the same length, and produce the vector of elements where the bit was set) means you probably want a natural way to handle those kinds of existential types for lengths: you get a vector, and it has a length, but you’re not sure what it is.
I don’t understand how to express the type of + with the shaped api. The examples are either operating on equal shapes or take advantage of fromInteger to multiply by a scalar. One could write eg add x y = broadcast x + broadcast y, but that now allows + to output arrays with arbitrary extra outer dimensions, whereas an apl + rejects some inputs but has an output shape that is a deterministic function of the input shapes
My first (and only) programming course (1976) in college used APL. It was populated by normal undergraduates, most of them in humanities fields. It was fine. You don’t have to be a super genius, but a lack of exposure to boring languages may be an advantage. I still love APL.
My second introduction to programming was also with APL in 1976. My high school had a few APL terminals that had a dialup connection to a computer at the University of Rochester. The math department had a course in APL. It dovetailed well with their introduction to linear algebra. It was an eye-opening experience.
In college, they were teaching assembly language (IBM/370) and Fortran. I dabbled with the APL interpreter on the mainframe, but had little time to do more. There just wasn't any support/community around APL on campus (that I was aware of). Nevertheless, I'm still very fond of APL.
Learning array languages makes you a better programmer in any other language. The way you think changes. We are taught to approach a problem procedurally. Actually the for loop is your enemy.
If numpy/matlab/octave/... was 'all the same stuff' with none of the downsides and all of the benefits, why would k or array languages in general have such a passionate community? Either every arraylang-er is masochistic (only slightly true) or there's more to it than you think.
That's a weird argument... passion is not always connected to efficiency/practicality/usefulness, in fact I feel that in a lot of cases it's the opposite.
As a great example, look at old computers: they are pretty popular (there is one link on HN front page right now about N64!) and people are super passionate about it, and yet you would not recommend "everyone to play at least one Nintendo 64 game".
For non-computer examples, somehow a number of my friends are extremely passionate about super hot (as in spicy) sauces. They bring a new bottle for every meal, and they can talk about the kinds of peppers for hours. It's interesting to hear, but I would not want to try them myself, nor would I recommend this to everyone.
I'm sure people who are into retrocomputing or spicy food or any other topic could tell you why they prefer that to something more mainstream. Whether or not you would agree, you could recognise that they had different opinions. The issue I had with your comment was writing off k as simply an inferior version of numpy etc rather than trying to consider why people like it, and what it may even do better than the mainstream alternatives.
> Learning array languages makes you a better programmer in any other language. The way you think changes. We are taught to approach a problem procedurally. Actually the for loop is your enemy.
I happen to strongly agree with most of this: learning array-based "operations", writing the code where "the for loop is your enemy" is a very valuable experience, and if will make you a better programmer in any language. Everyone should try writing some code like this.
The problem is K is a mix of three things: array-based operations, point-free style / tacit programming, and extreme brevity via punctuation abuse and lack of types. And not all of them are equally useful.
It's like trying to introduce someone to Chinese cuisine and giving them the spiciest Hunan dish there is. Unless the person already happened to love spicy food, the chances they will just write-off the entire cuisine.
I bet there people today who associate "array programming" with obscure character soup of APL/J/K and ignore it because of that. Who knows, maybe if they knew that numpy/octave offers the same thing in more palatable package, there would be more arrays and less "for" loops in the world.
The original comment said learning "array languages". There's some debate about what that means, but generally it means APL/J/K/etc not numpy/matlab/etc.
As far as I can tell (correct me if I'm wrong) you haven't learned an array language, yet you're telling someone who has (and anyone else who reads your message) not to bother.
To use your food analogy, this is like saying "Don't try real Chinese food in a restaurant, just cook some rice at home. Same thing."
It's not the same thing. The flavour is completely different.
What would you see as the big benefit of array languages over simply array-based programming in other languages? Or in other words, what sorts of things will I learn from trying out J or APL, that I wouldn't learn by playing around with Numpy or Pandas?
In addition to what rak1507 said, knowing what parts you’re composing gives you a more intimate feel for how the pieces fit together. Knowing that you’re building on top of a handful of functions you probably already have some intuition for is quite different from using a library function and simply trusting that the authors have done their due diligence.
It's hard to think of concrete benefits on the spot when the biggest benefit is the somewhat nebulous "feel" of the language. But generally: array languages typically make use of composition of primitives rather than larger, more complicated built in functions. For example in k, there is no 'sort' primitive. Instead of sort, you have grade (<). In APL this is ⍋. In numpy this is np.argsort
At first this is a bit counterintuitive. But then you realise, x@<x is sort. y@<x is sort by. <<x is 'rank'. There are all these 'recipes' that are based on <, and some of them you may not discover using numpy, as there would be another function that did it for you. You don't typically solve things by composing simple elements, as that would be far too verbose, instead using complicated built in functions, often with many parameters to describe the desired behaviour.
I'm sure other people will have other opinions on what the benefits are, but that was just one example off the top of my head.
I've read books on APL, J, and K and have played around a bit with all of them for some toy problems. I've also used Python's Numpy & Pandas at work.
The APL/J/K and Python + Library philosophies for programming are super different and if this doesn't make sense to you, I'd recommend downloading Dyalog (it's free to play around with) and go through some tutorials and see if you still feel the same way.
Yes it's all programming like how rice and french fries are both food. They're both awesome too. With Python you have a general purpose language that lets you build up a matrix in a manner you're used to. You've then got an object you call methods on to delete columns or update an entry or whatever. With APL, you've got what is like a hyper optimized DSL for doing that. I'm a lot more proficient with the Python option and it's both popular and free, so it's probably the only option I'll ever have to use at work. Using the APL/J/K options are a ton of fun and I think I could get hyper efficient with them as well given the time. Using the APL is so alien compared to what I'm used to though. The idioms (e.g. ohh you want to do that...just use an outer product which is these two characters combined) are just so different than how I'd typically think about solving the problem (e.g. I'd use a nested couple of for loops or whatever). It really does change the way you think.
Off topic: I work with a lot of extremely large sparse matrices though (like 40,000 x 40,000 with most being 0s), so I'm not sure if APL is as optimized here and as a result it's also easier to stick to Python.
100% this. I've never done real-world programming in J, but to the extent I learned it (I am far from capable in it) I thought differently about how I work in other languages.
Regarding #4, an advantage of Modern Fortran is that you have array operations and the ability to write procedural code with loops without a speed penalty if the problem cannot be easily decomposed into array operations.
>7. Likewise when you realize how array-based languages handle any dimension array.
Deserves to be ranked higher, especially for the "blub" programmer. With specific examples. I not-so-recently saw an implentation of euler's method that replaced the ODE solvers of MATLAB for pegagogical reasons. I return to it when I want to think about generalizing in that way.
I didn't say it was a reason to "decide" on a programming language. I started with a premise and then said "here's my take" but nowhere did I say "this is my take on why you should use K/J/APL for real work." It's just a list of bullet points about why J (in my case) is interesting.
He has also written many comments (arcfide on HN) about this stuff before, e.g. discussing "semantic density" [1]
> The compiler is designed so that I can see as much as possible with as little indirection as possible, so that when I see a piece of code I not only know how it works in complete detail, but how it connects to the world around it, and every single dependency related to it in basically one single half screen full of code (usually much less than that) without any jumps, paging, scrolling or any movement. [...] The idea of semantic density is critical to this point. The semantic density of the APL code I'm using to solve the problem is at a certain rate. I maintain a consistent density rate by choosing my variable names in such a way that they visually align with the expressivity per character of the built in primitive symbols.
And
> [...] idiomatic programming methods that are so concise, they can begin to be read as we read and chunk English phrases. By doing so, it becomes actually easier to just write out most algorithms, because the normal name for such an algorithm is basically as long as the algorithm itself written out. This means that I start to learn to chunk idioms as phrases and can read code directly, without the cost of name lookup indirection. I can get away with this because I've made reusability and abstraction less important (vastly so) because I can literally see every use case of every idiom on the screen at the same time. It literally would take more time to write the reusable abstraction than it would to just replace the idiomatic code in every place.
[0] https://github.com/Co-dfns/Co-dfns
[1] https://news.ycombinator.com/item?id=13571159