Arrays

Version 3.2 of uLisp added multidimensional arrays to the 32-bit versions of uLisp, and Version 3.3 extended the array support to include bit arrays.

uLisp's implementation supports arrays with an arbitrary number of dimensions, and packs bit arrays as efficiently as possible, so they take up a factor of 32 less storage than the equivalent-sized integer array.

24th March 2025: Added more information about getarray(), together with an example.

6th April 2025: Extended the information about getarray() to cover bit arrays.

Implementation

The traditional way to implement an array is as a block of contiguous memory, so the address of an array element can simply be calculated as an offset from the base address of the array.

However, this approach would have been difficult with uLisp. It would require a separate block of memory to be allocated for array storage, and a separate garbage collection mechanism would be needed for arrays.

Instead I decided to use the existing uLisp memory model by implementing arrays using a binary tree. This could use the existing memory allocation system, and would be able to use the same garbage collector.

This wouldn’t be as efficient as a conventional array, using sequential memory, but it would still be a big improvement over using a list with nth. For example, a 1024-element array would require 10 steps to index to an element rather than, on average, 512 when using a list.

Building an array

The function that creates a new array structure in the workspace is buildarray(); this takes three parameters:

  • n - the size of the array
  • s - the size of the binary tree, which is a power of two
  • def - the default value for each array element

The size s is the smallest power of 2 that is equal to or greater than n. It's calculated by the routine nextpower2():

int nextpower2 (int n) {
  n--; n |= n >> 1; n |= n >> 2; n |= n >> 4;
  n |= n >> 8; n |= n >> 16; n++;
  return n<2 ? 2 : n;
}

Here's the definition of buildarray():

object *buildarray (int n, int s, object *def) {
  int s2 = s>>1;
  if (s2 == 1) {
    if (n == 2) return cons(def, def);
    else if (n == 1) return cons(def, NULL);
    else return NULL;
  } else if (n >= s2) return cons(buildarray(s2, s2, def), buildarray(n - s2, s2, def));
  else return cons(buildarray(n, s2, def), nil);
}

For example, the call:

object *array = buildarray(7, 8, zero);

where zero is a pointer to the Lisp number zero, will create:

Array.gif

Getting an array reference

The function arrayref() returns a pointer to a particular element in an array:

object **arrayref (object *array, int index, int size) {
  int mask = nextpower2(size)>>1;
  object **p = &car(cdr(array));
  while (mask) {
    if ((index & mask) == 0) p = &(car(*p)); else p = &(cdr(*p));
    mask = mask>>1;
  }
  return p;
}

The parameters are as follows:

  • array is the array object
  • index is the array element to be returned
  • size is the number of elements in the array

It returns a pointer to the array element, rather than the element itself, so the same routine can be used to modify an array element with a Lisp statement such as:

(setf (aref a 6) "Hello")

The routine arrayref() works as follows: for each of the bits in index starting with the nth, where n is the number of bits needed to represent size, follow down the tree, taking the left branch if the bit is a '0', or the right path if the bit is a '1'. The final cell will be the array element specified by index.

Getting a pointer to an element in an array

The function getarray() returns a pointer to an element in a multi-dimensional array, given a list of the subscripts:

object **getarray (object *array, object *subs, object *env, int *bit)

It in turn calls arrayref(). The parameters are as follows:

  • array is the array object
  • subs is a list of the integer array subscripts
  • env is the environment
  • bit is a pointer to an integer giving the bit position for a bit array, or -1 for other arrays

Bit arrays

If the array is a bit array, getarray() instead returns a pointer to the word containing the bit corresponding to the subscript(s), and the variable bit is set to an integer specifying the bit position in that word.

Example

Here's an example of how you could use getarray() to write a Lisp function test to change an element of an existing two-dimensional array. It takes the array, two subscripts, and a value:

(test array x y value)

It sets the specified element of the array to that value:

object *fn_test (object *args, object *env) {
  int bit;
  // Get the four parameters
  object *array = first(args);
  object *x = second(args);
  args = cddr(args);
  object *y = first(args);
  object *value = second(args);
  // Build a list of the subscripts
  object *subscripts = cons(x, cons(y, NULL));
  // Get a pointer to the required array element
  object **element = getarray(array, subscripts, env, &bit);
  // Set it to the value
  *element = value;
  return value;
}

For example:

> (defvar a (make-array '(2 3)))
a

> a
#2A((nil nil nil) (nil nil nil))

> (test a 1 2 73)
73

> a
#2A((nil nil nil) (nil nil 73))

Example - bit array

Here's a similar example that sets a specified element of a bit array to a bit value:

object *fn_test (object *args, object *env) {
  int bit;
  // Get the four parameters
  object *array = first(args);
  object *x = second(args);
  args = cddr(args);
  object *y = first(args);
  object *value = second(args);
  // Build a list of the subscripts
  object *subscripts = cons(x, cons(y, NULL));
  // Get a pointer to the required array word containing the bit
  object **element = getarray(array, subscripts, env, &bit);
  // Mask out the bit and set it to the value
  *element = number((checkinteger(*element) & ~(1<<bit)) | checkbitvalue(value)<<bit);
  return value;
}

Demonstration:

> (defvar a (make-array '(2 3) :element-type 'bit))
a

> a
#2A((0 0 0) (0 0 0))

> (test a 1 2 73)
Error: 'test' argument is not a bit value: 73

> (test a 1 2 1)
1

> a
#2A((0 0 0) (0 0 1))

Other routines

The following additional routines are provided for working with arrays:

makearray() builds an array with an arbitrary list of dimensions by calculating the total size, and then calling buildarray(). It also handles bit arrays.

rslice() recursively reads a slice of an array.

readarray() reads in an array definition, calling rslice().

pslice() recursively prints a slice of an array.

printarray() prints an array, calling pslice().

In addition, the following general routines needed to be extended to handle arrays:

place() handles the case of an array reference being given as an argument to the in-place functions such as setf.

fn_length() is extended to return the length of one-dimensional arrays.

Previous: Strings

Next: Read, Evaluate, Print