History of storage allocation

The history of the development of programming languages can be considered to be an account of the provision of greater support for abstraction and the automation of actions that were previously manual or explicit.

In the early days of computing all communication between programmer and machine was on a bit-by-bit basis, which simple switches for input. Shortly afterwards, the introduction of simple input and output devices made the exchange of hexadecimal values between operator and machine easier. The next step was to allow programmers to use mnemonic codes that were mechanically translated into binary notation. Nevertheless, users were responsible for every detail of their program’s execution. For example, special attention was needed to count the number of words in the program and find the absolute address of instructions in order to determine whether there was enough space available to load the program and in order to specify the destination of jumps.

By the late 1940s and early 1950s, this book-keeping burden had been transferred to macro codes and assembly languages [Metropolis et al, 1980]. Symbolic programs are easier to write and to understand than machine-language programs primarily symbolic codes. Nevertheless the programmers must still be intimately concerned with how a specific computer operates, and how and where data is represented within the machine. The large number of small machine-dependent details continues to make assembly language programming an exacting task.

To overcome these problems, ideas for high-level programming languages, intended to make the programming task simpler, appeared during the mid to late 1940s. By 1952 the first experimental compilers had appeared, and the first Fortran compiler was delivered in early 1957. A compiler for a high-level language must allocate resources of the target machine to represent the data objects manipulated by the user’s program. There are three ways in which storage can be allocated.

Static allocation

The simplest allocation policy is static allocation. All names in the program are bound to storage locations at compile-time: these bindings do not change at run-time. This implies that the local variables of a procedure are bound to the same locations at every activation of the procedure. Static allocation was the origin implementation policy of Fortran, and it is still used by Fortran 77, for example, static allocation has three limitations.

• The size of each data structure must be known at compile-time.
• No procedure can be recursive since all its activations share the same locations for local names.
• Data structures cannot be created dynamically.

Nevertheless, static allocation does have two important benefits. Implementations of statically allocated languages are often fast since no data structures, such as stack frames, need to be created or destroyed during the program’s execution. Since the location of all data is known by the compiler, storage locations can be accessed directly rather than indirectly. Static allocation also offers a safety guarantee: the program cannot fail by running out of space at run-time since its memory requirements are known in advance.

Stack allocation

The first block-structured languages appeared in 1958 with Algol-58 and Atlas Autocode. Block-structured languages overcome some of the constraints of static allocation by allocating storage on a stack. An activation record or frame is pushed onto the system stack as each procedure is called, and popped when it returns. Stack organization has five implications.

• Different activations of a procedure do not share the same bindings for local variables. Recursive calls are possible, thereby greatly enhancing the expressivity of the language.
• The size of local data structured such as arrays may depend on a parameter passed to the procedure.
• The values of stack-allocated local names cannot persist from one activation to the next.
• A called activation record cannot outlive its caller.
• Only an object whose size is known at compile-time can be returned as the result of a procedure.

Heap allocation

Unlike the last-in, first-out discipline of a stack, data structures in a heap may be allocated and deallocated in any order. Thus activation records and dynamic data structures may outlive the procedure that created them. Heap allocation has a number of advantages.

• Design is about creating abstractions to model real-world problems and many of these are naturally hierarchical: the most common examples are lists and trees. Heap allocation allows the concrete representation of such abstractions to be recursive.
• The size of data structured is no longer fixed but can be varied dynamically. Exceeding built-in limits on the size of data structures, such as arrays, is one of the most common sources of program failure.
• Dynamically-sized objects can be returned as the result of a procedure.
• Many modern programming languages allow a procedure to be returned as the result of another procedure. Stack-allocated languages can do this if they prohibit nested procedures: the static address of the returned procedure is used. Functional and higher-order imperative languages may allow the result of a function to be a suspension or closure: a function paired with an environment of bindings of names to locations. These bindings will therefore outlive the activation of the function that created them.