As I’ve already explained, Lucid can be understood as functional programming with an added time dimension. What about other dimensions? In particular, what about a space dimension?

The late Ed Ashcroft and I discovered this possibility when we tried to “add arrays” to Lucid. Initially, we intended Lucid to be a fairly conventional, general purpose language. So we considered various ‘features’ and tried to realize them in terms of expressions and equations.

Static structures like strings and lists were no problem. We ran into trouble with arrays, however. We tried to design an algebra of finite multidimensional arrays (along the lines of APL) but the results were complex and messy to reason about.

Frozen Stream

Finally it dawned on us that we should consider infinite arrays – sort of frozen streams. And that these could be realized by introducing (in the simplest case) a space parameter s that works like the time parameter t. In other words, Lucid objects would be functions of the two arguments t and s, not just s. These things (we had various names for them) could be thought of as time-varying infinite arrays.

The details were pretty straight forward. We would add space versions of the temporal operators first, next, fby etc. The programmer as before could define variables with arbitrary expressions involving these operators. Let’s call the space operators initial (corresponding to first), succ (successor, like next), and sby (succeeded by, like fby).

In imperative languages arrays are usually created by loops that update components one by one. You can emulate this in Lucid. You need an update operator that takes an array, an index, and a value, and returns an array like the old on except that the value is now stored at the index. However we realized this was kludgey and likely inefficient.

The ‘idiomatic’ way to do it is to define the whole array at once, like we do for streams. Thus

nums = 1 sby  nums+1

defines the array of counting  numbers and

tri = 1 sby tri + succ nums

the array of triangular numbers.

If we mix spatial and temporal operators, we can define entities that depend on both dimensions – that are time-varying arrays. Thus

stot(A) = S where S  = A sby S + succ A; end
P = 1 fby stot(P)

gives us Pascal’s triangle (tilted to the left)

1   1   1   1   1   …
1   2   3   4   5   …
1   3   6 10 15   …
1   4 10 20 35   …
1   5 15 35 70   …

with the space dimension increasing to the right and the time dimension increasing towards the bottom.

The function stot is not defined recursively and we can eliminate it by applying the calling rule, giving

P = 1 fby (S where S = P sby S + succ P end)

and we can promote S to a global giving

P = 1 fby S
S = P sby S + succ P

The first equation implies that S is equal to next P and substituting in the right hand side of the second equation gives

P= 1 fby S
S = P sby next P + succ P

Now we can eliminate S to get

P = 1 fby P sby next P + succ P

So we can use the usual rules to transform two-dimensional programs. Even though there are two dimensions, the programs are still equations.

We can use the space dimension to generate primes without recursion. We define a stream of arrays in which on each time step the next array is the result of purging the current array of all the multiples of its initial element.

N = 2 sby N+1
S = N fby  S wherever S mod initial S ne 0
P = initial S

This defines P to be the stream of all primes.

Finally here is a program that crudely approximates heat transfer in an infinite metal bar. The bar is initially hot (temperature 100) at the left end (initial point) and 0 elsewhere. Thereafter at  every timepoint each spacepoint receives or gives a small percentage of the temperature difference with its neighbour.

eps = 0.1
B0 = 100 sby 0
B = B0 fby 100 sby succ B + eps*(B-succ B) + eps* (succ succ B – succ B)

The output shows the bar gradually warming up as the heat travels from left to right.

100   0.0   0.0   0.0  …
100  10.0  0.0   0.0  …
100  18.0  1.0   0.0  …
100  24.5  2.6   0.1  …
…

The eduction process is easily extended to two dimensions. Instead of demands specifying a variable and a time coordinate, they specify a variable and a time coordinate and a space  coordinate. These demands give rise to demands for possibly different variables at possibly different time and space coordinates.

There is one complication, however, involving the warehouse (cache). Some variables may be independent of one or more of the coordinates. For example, in the primes program above the variable N does not depend on the time coordinate. In principal, if we cache values of N tagged with both the time and space coordinates we risk filling the cache with duplicate values of N with the same space coordinates but with different time coordinates.

That doesn’t happen with the primes program because it works out that all the demands for N will have time coordinate 0, so no duplicates. Many programs are well behaved in this sense. But not all.

For example, in the heat transfer program, demands for B at different time points and space points will lead to demands for eps at different time- and space points. But these demands for eps at different contexts will all return 0.1, so if the results of these demands are each cached, we’re wasting time and space.

Avoiding this problem requires what we call dimensionality analysis. The dimensionality of a variable 𝒱 is the set of dimensions that it depends on; the least set of dimensions with the property that knowing the coordinates of these dimensions allows you to compute 𝒱.

If there are two dimensions s and t there are four possible dimensionalities:

{}, {s}, {t}, {s,t}

For example, of the dimensionality is {t}, we need to know the time coordinate but not the space coordinate.

In practice we can’t always compute the exact dimensionality because it could turn out e.g. that a complex looking expression always has the same value. But we can compute bounds on the dimensionalities and that’s almost always good enough.

I’ll leave dimensionality analysis to another post – it’s very similar to type inference. Applied to the prime program, for example, it finds that the dimensionality of N is {s}, of S is {s,t}, and of P is {t}. Applied to the heat program, it finds that the dimensionality of B is {s,t}, of B0 is {s}, and of eps is {}.

This information allows us to cache and fetch the values of these variables with the minimum tags.

Notice that P and N are both one-dimensional – only one coordinate is required to compute a value. But they don’t have the same dimensionality. The rank of a variable is the number of coordinates needed. It is the cardinality of the dimensionality. Knowing the rank is not enough to tell you how to cache and fetch a value.

In future posts I’ll talk about what happens when there are a few more dimensions, or a lot more dimensions, or dynamic dimensions, or dimensions as parameters of functions.