Working with Multitudes for Fast Arduino Effect Processing

In my last post I promised that I had some wild ideas for doing operations on arrays on numbers, so here we are. In the olden time, operations on arrays of numbers were done by taking operations on individual numbers in the array and combining them with flow control structures such as for loops to iterate over the elements of the array one by one, applying the operation. This is still how it's done in C, but in the modern world we have alternatives. The APL familiar of languages such as J and BQN elevate arrays as first-class types that allow for common numeric operations to be applied to the whole array, with iteration over the elemnts implied but without the need to directly implement it time and again in a variety of for loops. These languages also come with a rich vocabulary of operations for modifying arrays to combine, split, and reshape them into the arrays. You find some of these ideas making their way into mainstream programming language with the advent of things like NumPy and pandas in Python, libraries that take over the work of manipulating arrays and do it more efficiently than it can be done in just pure python. Usually this speedup is achieved by implementing the operations in C with a thin python wrapper to invoke the mostly C code. However, even Haskell, which is a fast compiled language, has an array library called vector that can do array operations even faster through advanced loop optimization techniques. Of course the ultimate speedup is to move array operations off of the CPU entirely onto a GPU or other hardware specialized for array operations, which a handful of languages support as well.

In our case, our main need at the moment for doing array calculations is processing the audio buffer in the tremolo effect we are implementing. However, we are likely to want to do other operations on arrays of numbers in the future as it is a common enough computational task. In order to provide array programming in the Bell language, I have developed a new Arduino library called MultitudeArduino for working with Multitudes.  A Multitude is a collection or more than one value and a structured shape for those values. Currently, only 1-dimensional arrays are implemented, but the intention is to allow for a good amount of freedom in the shape. There are a few different types so far in Multitude. First, there are the main semantic types, Multitude and MutableMultitude. A Multitude is immutable with all functional operations that yield modified copies. A MutableMultitude provides all of the same operations as a Multitude as well as mutating operations that modify it in place. This is a pattern that I'm following generally while building up a suite of data structures to use as pure functions in the Bell language with the mutable variants provided in the Ultraviolet virtual machine as stateful effects.

To give a taste of array programming style, let's look at an operation that I have already implemented: replicate. I don't have array literal syntax for Bell yet, so just for these examples we'll use traditional bracket syntax for array literals, so "1" is a number and "[1 2]" is a list of numbers and we'll use "->" to show what an expression produces. Array programming gets a lot of traction out of overriding a single symbol with different behaviors based on the arguments. For example, let's use replicate with just numbers:

2 replicate 3 -> [2 2 2]

We take the left argument (a number) and replicate it by the number of times specified on the right side, so in this case 3 times. This is a handy operation to have available. If we replace the right argument with a list, we get a sensible extension of the behavior that we've already seen in the simplest case:

2 replicate [3 4] -> [2 2 2 2 2 2 2]

We replicate the 2 first 3 times and then 4 times, and this all gets smoothed out into a single list (as opposed to a list of lists). In functional programming terms, it is as if the behavior with a list as the right argument is the same as doing a flatmap of the function that takes a number as the right argument.

Now let's try a list on the left and a number on the right:

[3 4] replicate 2 -> [3 3 4 4]

The behavior with a list as the left argument and a number on the right argument is once again like doing a flatmap of the simple number-number case. Since the list is on the left now, this is the list we iterate over, so we get the concatenation of "3 replicate 2 -> [3 3]" and "4 replicate 2 -> [4 4]", which is "[3 3 4 4]".

The behaviors for number-number, number-list, and list-number all seems pretty reasonable and useful. How about for list-list? Well the rules are a bit different, but I think still sensible, but first we need to look at a special case, replicating 0 times.

0 replicate 2 -> [0 0]
2 replicate 0 -> []

If we want to replicate 0, this is the same as any other number. However, what if we want to replicate a number 0 times? Well then in this case we omit the number from the result. Some further examples, which should be clear if you understood the above:

[0 1 2] replicate 2 -> [0 0 1 1 2 2]
[1 2 3] replicate 0 -> []
2 replicate [0 1 2] -> [2 2 2]
2 replicate [0 1 0 2 0 0 0] -> [2 2 2]

So now we can cover the list-list case:

[0 2 4] replicate [1 3 5] -> [0 2 2 2 4 4 4 4 4]
[1 3 5] replicate [0 2 4] -> [3 3 5 5 5 5]
[0 1 0] replicate [1 0 1] -> [0 0]

As you can see, for the list-list case we pair up the elements in the left and right lists by index and the do the usual number-number operation, flattening the results into a list. Having a zero on the left size is just another number and has no special behavior. Having a number of the right side means that we make 0 copies, or in other words skip or delete this entry.

However, what if the sizes of the arrays on the left and right side don't match? For replicate, there is no defined behavior for this case, so it is an error. If both sizes are arrays, then their lengths must match. For some operations, there is an alternative interpretation where missing elements get filled in with a "fill value", but replicate traditionally does not support fill values.

I hope you enjoyed getting a taste of array programming and the Multitude library for Arduino that is beginning to implement these array programming concepts. There are quite a few array programming operations to implement, but we'll add them as we go, as needed by specific projects.