[HN Gopher] Thinking in an Array Language
___________________________________________________________________
Thinking in an Array Language
Author : tosh
Score : 125 points
Date : 2024-01-13 16:43 UTC (6 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| rekttrader wrote:
| Thank you for posting this, I just this week tried to explain
| array programming.
| account-5 wrote:
| If you never heard of array programming and are interested in an
| introduction I recommend:
|
| The Array Cast https://www.arraycast.com/episodes/
|
| RSS address: https://www.arraycast.com/episodes?format=rss
| lolinder wrote:
| 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.
| nickpeterson wrote:
| 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.
| ParetoOptimal wrote:
| 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.
| steveBK123 wrote:
| 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.
| rak1507 wrote:
| 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.
| bear8642 wrote:
| > "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!
| ParetoOptimal wrote:
| 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.
| jodrellblank wrote:
| 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.
| Keyframe wrote:
| 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.
| theusus wrote:
| Isn't lisp a list language? Isn't easy to index but gives similar
| functionality
| ginsider_oaks wrote:
| 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.
| lispm wrote:
| There are attempts to combine those...
|
| a cool example is April (Array Programming Re-Imagined in
| Lisp), which runs on top of Common Lisp...
|
| https://github.com/phantomics/april
|
| One can see that the Lisp macro APRIL-F compiles APL-like
| code to Lisp. APRIL> (macroexpand '(april-f
| "3r4J9r5x[?]4")) (LET ((OUTPUT-STREAM *STANDARD-
| OUTPUT*)) (DECLARE (IGNORABLE OUTPUT-STREAM))
| (SYMBOL-MACROLET ((INDEX-ORIGIN APRIL-WORKSPACE-
| COMMON::*INDEX-ORIGIN*) (PRINT-
| PRECISION APRIL-WORKSPACE-COMMON::*PRINT-PRECISION*)
| (COMPARISON-TOLERANCE APRIL-
| WORKSPACE-COMMON::*COMPARISON-TOLERANCE*)
| (DIVISION-METHOD APRIL-WORKSPACE-COMMON::*DIVISION-METHOD*)
| (RNGS APRIL-WORKSPACE-COMMON::*RNGS*)) (A-OUT
| (A-CALL (APL-FN-S x) (A-CALL (APL-FN [?] INDEX-ORIGIN) 4)
| #C(3/4 9/5)) :PRINT-PRECISION PRINT-
| PRECISION :PRINT-TO OUTPUT-STREAM))) T
|
| we can run that: APRIL> (april-f
| "3r4J9r5x[?]4") 3r4J9r5 3r2J18r5 9r4J27r5 3J36r5
| #(#C(3/4 9/5) #C(3/2 18/5) #C(9/4 27/5) #C(3 36/5))
|
| It has created a Lisp vector of complex numbers.
| APRIL> (describe *) #(#C(3/4 9/5) #C(3/2 18/5) #C(9/4
| 27/5) #C(3 36/5)) [simple-vector] Element-
| type: T Length: 4 ; No value
| RodgerTheGreat wrote:
| It does not.
|
| 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.
| aeonik wrote:
| Clojure actually has a fair amount in common with Array
| Languages, at least the mapping and conformation.
|
| That being said, I really really like Array Languages for
| certain subsets of problems over anything else.
|
| I kinda think every language and have an embedded Array
| Language engine, kinda like how Regex works so well for text
| processing.
| cmrdporcupine wrote:
| The key thing is that lisp type (and most functional)
| languages, including Clojure, emphasize function
| application and (often) recursion.
|
| Array languages try to get you to formulate your problem in
| terms of batch applications across whole vectors at a time,
| rather than piece by piece.
|
| Which is actually potentially insanely faster on modern
| hardware where branches are expensive and we have special
| SIMD and/or vector hardware support.
| account-5 wrote:
| There's an array programming language implemented in lisp
| called april: https://github.com/phantomics/april
|
| EDIT: someone beat me to it in a comment further down or up the
| thread...
| OskarS wrote:
| 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?
| nickpeterson wrote:
| 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.
| dzaima wrote:
| 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).
|
| [0]: https://aplwiki.com/wiki/KAP
| max_ wrote:
| I don't know what a Pythagorean triplet is but for primes you
| can do it as follows in J.
|
| 1. The primitive _p:_ generates the nth prime number so, _p:0_
| generates the first prime number 2, _p:1_ generates the 2nd
| prime number.
|
| _P: 6_ generates the 6th prime number 17.
|
| 2. _P:_ supports arrays so _p: 0 1 2 3_ will print the prime
| numbers at index 0, 1, 2 & 3. Which are 2 3 5 7.
|
| 3. The primitive/verb _i._ Generates a sequential list. So _i.
| 5_ will generate 0 1 2 3 4
|
| 4. _p: can consume other verbs like_ i:*
|
| So to print the first 1,000 prime numbers, it is simply _p:
| (i.1000)_
| OskarS wrote:
| 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.
| max_ wrote:
| 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.
| dzaima wrote:
| 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.
| max_ wrote:
| Thanks for the insight.
| mlochbaum wrote:
| 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:
|
| https://mlochbaum.github.io/BQN/implementation/versusc.html
| jiggawatts wrote:
| Memory is cheap, but memory bandwidth isn't.
|
| 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.
| mlochbaum wrote:
| 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?).
| DrDroop wrote:
| 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.
| jodrellblank wrote:
| > " _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.
|
| You can read more interesting things about the implementing of
| BQN and comparing with co-dfns and performance here:
| https://mlochbaum.github.io/BQN/implementation/codfns.html
|
| [1] https://www.arraycast.com/episode-52-transcript - around
| 00:39:21*
| mlochbaum wrote:
| Following this episode, I did find an AVX2 implementation of
| the maximum subarray sum that's about 25% faster than the
| sequential version, published here: https://gist.github.com/m
| lochbaum/b6e9701c6c1c617a2c2a4fb107...
|
| 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.
|
| [0] https://en.wikipedia.org/wiki/Bird%E2%80%93Meertens_forma
| lis...
|
| [1] https://ispc.github.io/index.html
|
| [2] https://gist.github.com/athas/f016084ea749602476b96c05ae4
| 15a...
| convolvatron wrote:
| 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.
| andoando wrote:
| 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.
| maest wrote:
| 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.
| andoando wrote:
| 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.
| jayd16 wrote:
| 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.
| ParetoOptimal wrote:
| 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".
| cmrdporcupine wrote:
| 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.
| dzaima wrote:
| 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).
| p1esk wrote:
| Is Numpy or Pytorch an array language? With things like einsum
| and elaborate slicing/indexing mechanisms.
| 7thaccount wrote:
| More like an array framework/library on top of a general
| purpose Object Oriented language.
| Qem wrote:
| https://analyzethedatanotthedrivel.org/2018/03/31/numpy-anot...
| sega_sai wrote:
| 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.
| gitonthescene wrote:
| Where were you interviewing?
| sega_sai wrote:
| DB (10 years ago)
| Bostonian wrote:
| 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.
| pklausler wrote:
| 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).
| mlochbaum wrote:
| Previous discussion:
| https://news.ycombinator.com/item?id=31377262
| gcanyon wrote:
| This is based on K. Another array language is J
| http://jsoftware.com In J this would be: dot =:
| +/ . * P =: 2 3 4 Q =: 1 0 2 P dot Q
|
| That will return 10, the dot product P and Q.
| eismcc wrote:
| In KlongPy, dot product is: dot::{+/x*y}
| P::[2 3 4] Q::[1 0 2] dot(P;Q)
| abrudz wrote:
| The original array lang is APL: dot-+.x
|
| 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).
| refset wrote:
| 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.
|
| [0] https://github.com/Co-dfns/Co-dfns
|
| [1] https://news.ycombinator.com/item?id=13571159
| baseball_coach wrote:
| 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.
| gitonthescene wrote:
| Maybe the criticism could be a bit more precise than "it
| sucks". Though I am a fan of the animated series The Critic.
| jodrellblank wrote:
| 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.
| Analemma_ wrote:
| 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."
| zozbot234 wrote:
| 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.
| sudosysgen wrote:
| 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.
| jodrellblank wrote:
| This is an argument which has been going on for years,
| and I've been involved in it many times before; " _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
| into expanding on their criticism. Your expanded reply is
| still predicated on "the symbol soup is unreadable" being
| a fundamental truth about the world - which it isn't.
|
| You say "You can either write 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!
|
| And, are you suggesting that people _don 't_ write
| comments explaining their code in common popular
| languages? Of course they do!
|
| 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
| 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.
|
| 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.
|
| 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/
| 7thaccount wrote:
| 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.
| feoren wrote:
| This is like walking into someone's office that's completely
| overwhelmed with mess, boxes and binders to the ceiling, but
| they swear to you they know where absolutely everything is.
| They don't, and certainly nobody else has any chance of ever
| finding anything. Except in this case he's publishing videos
| and articles about how superior his personal method of just
| being intimately familiar with his own Giant Mess is.
|
| That is not good code, sorry. His average variable name length
| is about 2.5. He can't "literally see every use case of every
| idiom". He's fooling himself, seemingly convinced by his own
| brilliance. He:
|
| - Brags about using Notepad instead of the fancy IDEs that us
| weak-minded plebians use
|
| - Brags about how easily he understands his giant ball of
| overly messy code (2- letter variables in the name of "semantic
| density")
|
| - Uses an obscure (in the modern era) outdated language like
| some Cinema aficionado who refuses to watch movies in color
| like all those plebians
|
| - Publishes articles in journals that everyone else in our
| industry would just write as blog posts
|
| - Brags about how he can understand _his own code_. We can all
| understand our own code. Good code is understandable by
| _others_.
|
| Any one of these alone wouldn't be that weird, but taken
| together it sure seems like he's optimizing for self-promotion
| and feeling infinitely superior to all us mere mortal
| programmers.
| refset wrote:
| 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.
| mlochbaum wrote:
| 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?
|
| [0] https://mlochbaum.github.io/BQN/implementation/codfns.h
| tml#i...
| jodrellblank wrote:
| 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] _u_ v' and languages where people
| write 'pyramidPointVector[pyramidPointVectorOffset]=adjustedS
| hadowMaskBools[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.
| fifilura wrote:
| > 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.
| gcanyon wrote:
| 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.
| zozbot234 wrote:
| 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.
| rak1507 wrote:
| 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.
| mlochbaum wrote:
| Complain about the language or documentation, but array
| language _communities_ are absolutely friendly to outsiders!
| This tutorial lists some active forums, give them a try:
| https://github.com/razetime/ngn-k-
| tutorial/tree/main?tab=rea...
|
| Also, have to shout out the APL Orchard, where Adam will give
| any visitor a personal tutorial:
| https://chat.stackexchange.com/rooms/52405/the-apl-orchard
| dan-robertson wrote:
| 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...
| zozbot234 wrote:
| 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.)
| dan-robertson wrote:
| 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: val
| matmul : ((float,'a) fixed_length, 'b) fixed_length ->
| ((float,'c) fixed_length, 'a) fixed_length -> ((float,'c)
| fixed_length, 'b) fixed_length
|
| (And observe the similarity to function composition too:
| val compose : ('a -> 'b) -> ('c -> 'a) -> ('c -> 'b)
|
| .) 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.
| ithkuil wrote:
| > function exponents
|
| Including negative exponents, namely automated computation of
| the inverse function!
| pklausler wrote:
| 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.
___________________________________________________________________
(page generated 2024-01-13 23:00 UTC)