Make arrays immutable

[ssoelvsten]

Currently, Troupe includes the following three (mutable) array operations implemented in rt/src/builtins/localarrays.mts:

• arrayCreate: O(n) allocation of array
• arrayGet: O(1) access to element
• arraySet: O(1) update with side-effects

Basics

Having mutable data types is really messy when it comes to sending messages (should arraySet on an array from another node change the other node's array?). So, instead we would like to replace localarrays.mts with arrays.mts which includes the following operations:

• arrayMake (n, x): O(n) allocation of an array with n copies of x.
• arrayGet (xs, i): O(1) access to element of a at position i (zero-indexed).
• arraySet (xs, i, x): O(n) returns a copy of a with position i replaced with x.
• isArray a: O(1) whether the given element is an array.

Based on these three operations, we can implement an Array module in lib/ with the operations below; this is enough to support Stencil Vectors with arrays. This hopefully will improve cache locality and hence its performance.

• make n x: alias for arrayMake
• get xs i: alias for arrayGet.
• set xs i x: alias for arraySet.
• foldl f y (n,xs): fold over an array of size n.
• toList (n,xs): turn the array of length n into a linked list.

Reallocation

But, for the Stencil Vector we would like to not have the array immediately be its full size. So, we need a way to reallocate an array (i.e. an arrayRemake in the TCB). Adding this also provides the possibility to create a Vector module.

Iterated Construction

Finally, to support the operations below we would have to make arrayMake into an operation that takes a function f as its second argument and calls it once for each index (this also makes arrayRemake obsolete). Otherwise, they would have a quadratic rather than a linear running time.

• range n: Create the array [0..n-1]
• map f xs: apply f to each element in xs.
• mapi f xs: same as map but also with the index provided.
• filter f xs: keep elements of xs where f is true.
• filteri f xs: same as filter but also with the index provided.

To support a merge sort routine, the function f in arrayMake should not be provided the index; instead the function f should return the f' called on the next index.