Arrays as functions

In the early days of functional programming a number of people picked up on the notion that arrays could be implemented as functions. In this article we explore some early appearances of this idea. The dates given are those of the published references.

1962 - Lisp 1.5

Lisp 1.5 was the first major Lisp implementation, created under the auspices of Lisp's inventor, John McCarthy. A function to access an array would be created by the ARRAY special form:

(ARRAY (A 30))

The value of an element could then be accessed using the obvious function call:

(A 10)

Setting the value of an element was achieved with a distinguished first argument:

(A 'SET 10 5)

We might think of this as an early form of object orientated programming, with the 'method' name being added to the domain of the function. This idea will recur later in Gendanken.

1968 - Pop-2

The Pop-2 language, developed by Burstall and Popplestone at Edinburgh, introduced the notion of a doublet. This was a function with two entry points, one of which would be called when the function was used normally, the other for when the function was used in 'update mode' as the target of an assignment.

So F(X) would call the function normally, and F(X)=Y would call the 'updater' entry point, with Y being passed as an extra parameter. Doublets are then used to implement arrays with a function, NEWARRAY, taking a list of dimensions and returning a new doublet function to access that array.

Papers written around this time are very clear about the benefits of this unification of functions and arrays. For example, the identity matrix (ie a two dimensional array) is shown expressed as a function:

FUNCTION IDENT(I,J)
   IF I==J THEN
      1
   ELSE 
      0
   ENDIF
ENDFUNCTION

Of course, this is an immutable array so it has no updater. A limitation of Pop-2 was the inability to programatically determine the bounds of such an array.

1970 - Gedanken

The Gedanken language was developed by John Reynolds. In many ways it provided the most complete implementation of arrays as functions. The domain of a function providing an array is extended with the atoms LL and UL to return the lower and upper limits of the array. For example, for an array A, A('UL) is the upper bound.

Gedanken provides assignments through reference data types. Thus only arrays that are arrays of references will be assignable. So if A is such an array, the we can update a value with A(10):=5. The works because the evaluation of A(10) will return a reference object that is then the target of the standard assignment.

1973 - MicroLisp

MicroLisp was a byte code implementation of Lisp developed at Xerox PARC for the locally developed MAXC computer, a PDP-10 clone, and later for the Alto.

This system had a similar concept to the doublets of Pop-2, with separate load and store entry points to functions, supported by special byte code instructions.

Syntactically, the SETFQ syntax was used to access the store version of the function:

(SETFQ (A 10) 5) 

However, this doesn't seem to have been used to implement arrays, instead this was used for structure access, such as changing the CAR or CDR of a list cell. The SETF syntax was later picked up by Common Lisp, but the implementation used macros, so it would not be convenient to use for array access.

The paper describing this system by Deutsch credits Alan Kay with the idea of a function having a store entry.

Conclusion

It's long been known from theoretical studies of the lambda calculus that arrays could be modelled as functions (just as other types can be, such as numbers or booleans). The examples above show that this can also be a practical approach. What is less clear is whether it is desirable. There seem to be two issues, the first is syntatic with the same notation being used for function call and array subscription. The second is more semantic, with the ability to write functions like identity which can be used in contexts where arrays are expected.

With regard to the syntax, the question is whether it helps the reading or writing of code to distingish between function call and array subscription. Certainly most programming languages have used () for the one and [] for the other, and mathematics usually uses a special notation for subscription too. It may be that writing a[i] gives a hint than whatever type a actually is, it would support assignment with a[i]=x.

For semantics, dynamic object languages of the modern era, like Python and Ruby, treat subscription as a method that can be overridden like any other, allowing a wide range of array and collection implementations. At the same time, for me, the lingering suspicion persists that a single concept is better than two.