Designing a General-Purpose Language for Computation (for Effects Pedals)

It's been a while since I made any progress on our little language for writing and combining audio effects. The last post I made was on Multitudes, an approach to doing array programming on Arduino-compatible hardware. Array programming is pretty handy for audio effects because you're working with arrays of audio samples. However, this work led me into a deeply philosophical state of introspection that destroyed all productivity on pragmatic projects. I was not idle, I experimented with a couple of things that might be of interest. The SwiftIO board finally came to market. It uses the same processor as the Teensy, but includes a compiler for my favorite programming language, Swift! So naturally, I started porting the Teensy Audio library to Swift, check it out, it's called Audio-Swift. I also started on a major refactor of the C++ Teensy Audio library that separates out the platform-specific stuff for the Teensy and SAMD51 versions from the platform-neutral core. You can find that work here: Audio-core, Audio-Teensy4, Audio-SAMD51. I think this is a superior approach moving forward. It does require that you install both the core and either Teensy4 and SAMD51 support in order for your sketch to compile, so make sure to do that if you use it.

The big philosophical quandary that I've been pondering instead of moving our audio processing language forward has to do with the best way to express general purpose computations, which are unfortunately required for audio effects. While I could provide a rich set of operations you can do on arrays of numbers and that will get you through most common effects, it doesn't cover the case where you want to create a new effect that you just dreamt up, and isn't that kind of the point? So we need a nice way to write general computations, and I'd like it to be nicer than just writing C++ functions, because you can already just do that.

A lot of my time spent philosophically procrastinating was taken up learning more about array programming by implementing bits from popular array programming languages such as Dyalog APL, kona (an implementation of k), BQN, and J. I implemented these in Swift, and you can find them in the Starfish project. Starfish is just my open notebook on my explorations in array programming and not intended for any specific purpose other than my own enlightenment. However, it has been very revealing so far, and I'd like to share some thoughts.

Array programming is programming with first-class arrays, which just vaguely means that arrays are treated as fundamental and not just a data structure made out of more fundamental things. Arrays are atomic in a loose design sense. This is evident in that things like binary operators work on arrays more often than in other styles of programming. Functional programming is programming with first-class functions, once again they are atomic and you can pass them around as arguments, put them in variables, etc.. In nice languages, like Haskell and Swift, you can even have binary operators that work on functions. Effective programming, is where you have first-class effects. I think you probably get the parallel construction by now. There is one more thing I'd like to mention, and that's functional combinators. While you tend to find these in functional programming, you surprisingly also see a flavor of them in array programming, even without first-class functions! They form their own whole little model of computation and I think they're pretty important and interesting. So, you take all your atomic components and put them together and you get something from which you can build the whole universe of computation. Which building blocks you choose determine the details of how you get there, but ultimately everything is Turing-complete and universal computations and universal computations, no matter how you build them. However, when you're doing low-level stuff, the choice of building blocks can seem very important.

The biggest philosophical shift for me is to realize that each style of programming is somewhat incomplete without the others and the way that they privilege their chosen atomic building blocks somewhat cuts out the ability to do some pretty cool things from other languages. In particular, I'd like to discuss the primacy of function application, concrete vs abstract arrays, and the power of functional combinators.

Function application is the default meaning of juxtaposition in math, and this is kind of true in programming as well:

f x
f(x)

The first is the math style and also the Haskell and APL style. The second is the C style. In functional languages that use C-style syntax, such as Swift, the () mean application, but in languages in which they are always required they are more a form of grouping. Functions take a list of 0 or more arguments, and () is a special syntax for writing arrays when the elements are function arguments.

Binary operators are a special case syntax than underneath is just a function application, so we can rewrite them to be the general-purpose case for function application:

x + y
add(x, y)

Functions and binary operators both support overloading of the meaning of the symbol representing the function based on the types of the arguments. Even in languages that don't allow for user-defined operators, there is usually some level of operator overloading. In object-oriented languages, overloading of function names is a fundamental feature.

x = 1
y = 2
x + y -- 3

x = 1.0
y = 2.0
x + y - 3.0

x = "a"
y = "b"
x + y -- "ab"

x.append(y)

The first two examples show how C provides operating overloading for addition of ints and floats. The third example shows how some languages reuse the + operator for string concatenation. The last example shows how OO languages also allow overrides, but of function names instead of operators, which as we've shown are just two different styles of writing what is fundamentally the same thing. This contextual meaning for operators and function names is used extensively in math, where concepts like + depend on the domain of things on which you are operating. You can add integers and you can add complex numbers, for instance, and these are distinct operations. In OO languages, the meaning of a function name is determined by the object on which it is defined. Don't let the name fool you, it could mean anything! The same is true of operators in languages that allow user-defined operators. This is why some people don't like them, because they can hide surprises. For instance, it would be unwise to assume that x + y == y + x just because it is so for addition of integers. In the example above, where + concatenates strings, such an assumption is false, and this is a popular use of +.

Back to array programming, APLs do something that some people find disturbing, but which I hope you'll now agree is actually more common than one might think, which is having several definitions for every operator. +, for instance, works numbers, arrays, between a number and an array (or an array and a number), and also has a meaning when it's used as a unary prefix +x. In OO languages, the equivalent thing would be defining a function that behaves differently based on the number of arguments, for instance add(x) and add(x, y). Perhaps surprisingly, this is something you can even do in C, with varargs functions.

I've come to terms with this, and it has some nice benefits. The multiple meanings of a symbol are sometimes related, which can provide scaffolding for learning new uses. Where I take issue is not the overloading of symbol, or even the use of particularly strange symbols that aren't found on a standard keyboard, like × and ÷. No, my issue comes with function application being the default meaning of juxtaposition. I will use some binary operator examples, but the same applies to all operators and named function calls.

1 + 2 -- 3
1 + [2, 3] -- [3, 4]
[1, 2] + [3, 4] -- [4, 5]
+1 -- 1, complex conjugate which is a noop on real numbers
+/ [1, 2, 3] -- 6, reduce +
(+∘2) [1, 2, 3] -- [3, 4, 5], map + with the right argument bound to 2

Here, + is overloaded to do a variety of things. However, we have little local control over it. There are other possible meanings that we might want instead. Here are some alternatives:

1 + 2 -- [1, 2]
1 + [2, 3] -- [1, 2, 3]
[1, 2] + [3, 4] -- [1, 2, 3, 4]
+1 -- (+∘1)
+1 [1, 2, 3] -- [3, 4, 5]

When we choose the overloads, we lose the ability to express the alternatives, perhaps in a more elegant way would otherwise be possible. What ends up happening in APL is that we need whole new symbols, like this:

1 , 2 -- [1, 2]
1 , [2, 3] -- [1, 2, 3]
[1, 2] , [3, 4] -- [1, 2, 3, 4]
+∘1
(+∘1) [1, 2, 3] -- [3, 4, 5]

The alternative that I propose is that we take away the primacy of function application and instead explicitly notate when we want to apply a function. This makes working with functions as values easier, and it allows us to choose between a whole menu of function application types besides the basic flavor. We can also use functional combinators freely to create a whole menagerie of variations. I think binary operators might confuse you here, so I'll switch to prefix names.

add apply 1 2 -- 3
fork-add-ravel apply 1 2 -- [1, 2]
add-bind-1 map [2, 3] -- [3, 4]
add-ravel apply 1 [2, 3] -- [1, 2, 3]
add apply [1, 2] [3, 4] -- [1, 2, 3, 4]
add-bind-1 -- +∘1
add-bind-1 map [1, 2, 3] - [3, 4, 5]
add reduce [1, 2, 3] -- 6

We did add a lot of new symbols here as well: apply, map, reduce, fork, bind, ravel. However, these are universal and will combine similarly with all the other functions we might want to use. This makes the language overall smaller and it allows you to reason about new constructions rather than memorizing them, because they are made of smaller parts. You don't need to know about all the ways that add can be used in order to understand what "add apply 1 2" means.

The next thing I'd like to discuss is concrete vs abstract arrays. What is an array? Well, it depends on the language. C arrays and APL arrays have some significant differences. However, abstractly an array is a mapping between an index and a value. We don't even necessarily need to keep track of the index because, as long as there is a process that we can follow to handle the values in a set order, then we can reconstruct the specific index number as we go. So an array is just something that can be traversed in a set order. Does it really need to be a block of contiguously-allocated memory with fixed-size elements, as in C? Hardly! This is a place where array programming could learn some tricks from functional programming. If a data structure has a function by which values can be handled in order, then it is as good as an array in the abstract sense. In fact, we should be able to just provide such a function and be good to go, deferring all of the messy details to that function. This is something you can find in Python and Swift, and of course Haskell and it's very handy. Of course, we have an a "real" array then it should come with one of these functions. When we compile the code to C++, we can eliminate this function call in such cases and just access memory directly. There is no need for "boxed" types as in Java where we can have either a C-style "int" or an OO-style "Int", with very difference capabilities and performance. The language should provide all of the fanciest features you could ever want, and compile to the most performant case when you don't use any of those fancy features.

Finally, let's talk about functional combinators. If we make it easy to work with first-class functions, so easy in fact that we sacrifice the primacy of function application, then you can get a lot of work done with combinators, which are functions that take functions as arguments and return functions. In fact, we can get rid of most of the need for {} in C-style languages, which are often used for flow control, a facility entirely subsumed by combinators. Here are a few fun combinators that I've implemented in Starfish, taken from a variety of APLs:

swap-divide apply 2 4 -- 2, swap arguments, then divide
try-swap-divide-bind-0 apply 2 1 -- 1, try (2/0), if it fails use 1 instead
fork-add-ravel apply 1 2 -- [1, 2], apply ravel to both arguments, then add
dup-add apply 1 -- 2, copy the first argument to the second, then add

I know that's a lot to take in. It's been a year of me futzing around, implementing random parts of APLs in Swift. It might seem like a lot of new concepts, but ironically what I want to express here is how simple programming can be, simple and succinct. All we really need are functions (as long as functions are powerful enough to include combinators). We add a few alternatives to application, such as map and reduce, and we get back the niceties of array programming. Data structures can be thought of as just the functions that they provide, so functions arrays generalize to trees and a variety of other structures that can be ordered. Combinators remove the need for a lot of syntax, and we end up with a very clean language that is very compact to write.

So how are we going to get back to the business of audio effects processing? Well now that I have figured out how I feel about general-purpose computation, the next step is to figure out a unified syntax for all of these idea, rooted in our original concept of a minimal Smalltalk, and of course we'll need to incorporate effects as well. Then we'll need to figure out how to compile it into C++, which will be interesting!