NumPy-style broadcasting in Futhark (opens in new tab)

I actually think Julia's behaviour (partially) copied from matlab is bad. I had to review a lot of matlab/Julia simulation code write by PhD/grad students (as well as my own) and most of the time when things somehow are not working debugging becomes a task of "find the missing dot". If they would have decided on a more obvious symbol (the dot is really just way too easy to overlook) for broadcasting it would be much better, but I still much prefer that broadcast and matrix operation would use entirely different operators/named functions. Instead we have the case that a little annotation can dramatically change the behaviour of the code (the matrix exponential is in fact a great example).

That said I mainly work with fields and calculus so I might be biased because the majority of operations are broadcast and I only rarely use matrix operations.

I'd actually say what we did in Futhark is more similar to what Julia does (in the sense that the dot operator is syntactic sugar for Julia's `broadcast`) than what NumPy does---I wrote "NumPy-style" in the title just because I figured that's what most people would be familiar with. A more accurate title might be "Rank-polymorphic function applications in Futhark".

Ultimately it's quite different from both languages, though. Futhark has a strict static type system and we figure out how to broadcast completely statically without runtime information (NumPy and Julia both do it dynamically). This is really the main challenge that the system addresses and it permits you to have broadcasting in an ML/Hindley-Milner/Haskell-style type system along with full type inference and all the usual jazz and goodies.

Our system also doesn't have anything to do with vectorization/performance optimizations---in Futhark, `[1,2,3] + [4,5,6]` is just syntactic sugar for `map (+) [1,2,3] [4,5,6]` (which is how you'd write it without broadcasting), where `map` is already a parallel construct. So broadcasting in Futhark is literally just syntactic sugar for constructs that are inherently parallel, anyway---anything you can express with broadcasting can already be written in stock Futhark and there's no "magic" going on. Broadcasting in Futhark just means that some `map`s can be implicit, rather than explicit.

So it's a very disciplined and transparent (since it's static you can ask the compiler to show you exactly how the broadcasting will work) approach to broadcasting that the user has a lot of control over.

> it’s very important to distinguish between the element-wise application of a function, and a function that is applied to an entire array

Broadcasting in Futhark isn't inherently "element-wise" in the sense of descending through all the ranks of an argument until you get to the scalar level. It tries to actually use the fewest number of `map`s to get a rank-correct function application, so there's a preference for applying a function to higher-dimensional elements over scalars. This might sound non-intuitive/confusing, but it actually almost always aligns with what the programmer intended.

All it really does is use the minimal number of `map`s (and `rep`s) to massage a function and an argument with a rank mismatch into something that makes sense (or is rank correct)---it doesn't even have a notion of scalars, only rank differences!

I'd strongly advise taking a page from J's book and allow rank specification for function application. Julia having ranks element and infinite is nice, but what about application row-by-row ? On on regular sub arrays?

Futhark is a statically typed language, so it can’t have the same ambiguity.

This is in the surface language only: Futhark's arrays must be "rectangular" (if you have an array of arrays, the subarrays are mandated to be equally-sized; this is statically checked in most cases, and when it can't, it becomes a runtime check), and thus they are represented as a single, actual multi-dimensional array.

> Congrats on both the paper and the graduation!

Thanks! Although I still have to actually graduate and the paper is in review, so maybe your congratulations are a bit premature! :)

> A long time ago, I worked on optimizing broadcast operations on GPUs [1].

Something similar happens in Futhark, actually. When something like `[1,2,3] + 4` is elaborated to `map (+) [1,2,3] (rep 4)`, the `rep` is eliminated by pushing the `4` into the `map`: `map (+4) [1,2,3]`. Futhark ultimately then compiles it to efficient CUDA/OpenCL/whatever.

First I'm hearing of the programming language, but Futhark is the name given to several forms of the Old Norse runic alphabet, not made up wholesale or derived from other less-serious names.