4.5. Tables

Orc programs occasionally require a data structure that supports constant-time indexing but need not also provide mutable storage. For this purpose, an Array is too powerful. The standard library provides another structure called a Table to fill this role.

The call Table(n,f), where n is a natural number and f a total function over natural numbers, creates and returns an immutable array of size n (indexed from 0), whose ith element is initialized to f(i). A table can also be thought of as a partially memoized version of f restricted to the range [0, n). Table does not return a value until all calls to f have completed, and will halt if any call halts. Given a table T, the call T(i) returns the ith element of T. Notice that unlike array access, the ? is not needed to subsequently dereference the return value, since it is not a mutable reference.

Tables are useful when writing algorithms which used a fixed mapping of indexes to some resources, such as a shared table of communication channels. Such a table could be constructed using the following code:

val size = 10
val channels = Table(size, lambda (_) = Channel())

Notice that the lambda ignores its argument, since each channel is identical. Here is another example, which memoizes the cubes of the first 30 natural numbers:

val cubes = Table(30, lambda(i) = i*i*i)