Data Parallel Programming Languages

Data parallelism is a style of programming that I find alluring because it mixes human and machine sympathy - meaning they are easy to use and easy to execute. The downside is that not all problems are natural to express in a data parallel setting. The below is an ad-hoc list of programming languages that focus on data parallelism, that I have encountered during my studies, along with my personal notes. I focus on the more obscure or academically interesting languages.

APL

APL is one of the oldest languages of all, and naturally also one of the oldest data parallel languages. It was designed by later Turing Award winner Ken Iverson. Today, APL is mostly renowned for its supposedly cryptic syntax, which makes heavy use of bespoke characters (that are today supported in Unicode - I hear it was quite a mess when APL also required custom character sets). In truth, APL’s syntax is mostly quite simple, with all functions being right-associative and with the same priority. I strongly recommend reading Ken Iverson’s Notation as a Tool of Thought for a mind-opening eludication of why APL’s syntax is not, in fact, just pointlessly obtuse.

For quite a while, APL was quite widely used, even by (or particularly by) non-programmers. I suspect the reason was not so much the merits of the language itself, but the fact that APL environments provided a high level layer on top of the primitive operating systems of the day. It allowed people to work directly with the semantic objects they cared about, rather than worrying about files and such. Today, APL has largely been replaced in this role by IDEs for languages such as Matlab, Excel, Python, R, etc.

Today, the main industrially used APL implementation is Dyalog APL, which is proprietary. There is no compatible free software implementation of APL available. Although GNU APL is established and well maintained, it implements a somewhat older dialect of APL, and lacks some of the features that were added Dyalog in the 90s (such as anonymous functions, called dfns) which I consider core to modern APL style.

Futhark

Futhark (futhark-lang.org) is a data parallel functional language originally designed by Cosmin Oancea and Troels Henriksen, originally under the auspices of the HIPERFIT. It is intended to imitate the feel of languages in the ML family, although with significant restrictions on data and control flow in order to enable good run-time performance. Futhark is perhaps most interesting for its highly mature ability to generate efficient GPU code (this was the original project goal), as well as certain type system features, such as uniqueness types and size types. In contrast to most languages on this list, Futhark does not feature rank polymorphism, except in an experimental and limited way.

Lift

Lift (lift-project.github.io) is a functional data parallel programming language developed by Christophe Dubach, Michel Steuwer, and their students. It is designed to investigate rule-driven optimisation and compilation, by which always-correct rewrite rules are automatically applied in order to improve the program. The idea is that the compiler itself explores the search space of possible rewrites. While to my knowledge this idea was never realised in Lift itself, it is still the subject of study in succesor languages like RISE. Lift was never usable for end user programming, and instead programmers were expected to write Lift programs as ASTs embedded in Scala.

Remora

Remora is a data parallel programming language by Justin Slepak and Olin Shivers that can be described as a statically typed APL. Since APL has a lot of rather dynamic behaviour, describing this in a type system is quite challenging. For years Remora was more of a theoretical construct and a calculus, but it has also recently been (partially) implemented with a proper compiler by Liam Stevenson.

Single-Assignment C

SaC (sac-home.org) is a purely functional language designed for parallel programming. It was originally conceived of by Sven-Bodo Scholz in the early 90s, although Clemens Grelck was also an early and regular contributor. SaC was specifically designed for high performance computing, and also bears a syntactic (but not semantic) similarity to C in order to make it more familiar to HPC programmers (which also explains the name). SaC has strong APL influences in the form of rich support for rank-polymorphic programming, which is probably the most notable feature of its static type system.

It is my impression that SaC was far ahead of its time, and was willing to make the tradeoffs necessary to obtain performance on real computers that were unreachable by other functional languages at the time such as SML and Haskell. Despite a pragmatic design and an effective implementation, SaC failed to become very popular (although it is still actively maintained and used for research). While this is not by itself particularly unusual (the median programming language has zero users), I suspect that part of the reason is that SaC was non-free software for most of its lifetime, until it was released as open source software in 2022.

Today, SaC does not necessarily have significant performance advantages compared to similarly designed functional languages, but is primarily interesting for being one of the few statically typed languages with support for rank polymorphism, and is in particular useful as a vehicle for studying how rank polymorphism can be used for algorithmic expressivity.