Store
The word store refers to memory, as used in a programming language.
The word is common in UK English.
One of the first appearances of the word is in the very influential set of lecture notes Fundamental Concepts in Programming Languages by Christopher Strachey. Here is the first occurrence of the word:
One of the characteristic features of computers is that they have a store into which it is possible to put information and from which it can subsequently be recovered. Furthermore the act of inserting an item into the store erases whatever was in that particular area of the store before—in other words the process is one of overwriting. This leads to the assignment command which is a prominent feature of most programming languages.
Kinds of store
A basic division may be made along two axes: the what and the where.
What
The nature of a store is highly dependent on what can be put in it. The set of things that may be put in the store are called storable values (after Christopher Strachey).
The basic division here is the following:
- First-order store. A first-order store can only store first-order values, e.g. base types like integers and booleans. In some cases this can include types recursively built up from base types along with sums and products, e.g.
\textbf{int} + (\textbf{string} \times \textbf{string}) . - Higher-order store. A higher-order store may store functions/procedures themselves; the name is usually used to refer to storing higher-order functions, as in ML. In this case higher-order functions may themselves read or write to the store when called on an argument.
Between these two extremes there are intermediate situations, e.g.
- Full ground references. These consist of first-order data, and also references to other cells of the store. This allows pointer-linked structures, but not functions and/or thunks.
Where
This referes to the way locations are allocated and deallocated. It can pose surprising difficulties.
- Global store. In this case every location in the store is globally accessible at all times.
- In all other cases the number of variables available during the execution of a program may change. Thus, it is possible to allocate a new variable. The scope of this variable leads to two cases:
- Local variables. In this case a variable's scope is limited to a certain block; when execution of the block is finished, the variable is deallocated. Such variables are usually allocated on the stack of a runtime environment. See models of local variables.
- Dynamic variables. In this case a variable's scope may escape the scope of a block. Such variables are usually allocated on what we call the heap. See models of dynamic variables.
Where vs. what
In some cases the where interacts with the what.
For example, it is difficult to imagine storing a higher-order function in memory without heap allocation.
This point is put forward very convincingly in PFPL (2nd ed, §35).