Here is the promised description of the retirement plan mentioned in the Lucid – Eduction post. This description is a slightly edited version of section 3 of “An eductive interpreter for the language pLucid”, by myself and A. Faustini, which appeared way back in 1987 in PLDI87.

3. Memory in the Interpreter

One of the most surprising properties of eduction is that it does not require any static memory at all. The program is not changed during an eductive computation. As a result, values that have been computed but not saved can be recomputed (from scratch) if they are needed again. Of course, a memoryless educer will be hopelessly inefficient. For example, if I is defined as

I = 0 fby I + 1;

then the computation of the time t value of I involves computing the values of I at times t−1, t−2, t−3, . . . , right down to time 0. The simple pLucid squares generator

I = 0 fby I+1
J = 0 fby J+2*I+1

is apparently linear in complexity, but without memory, the interpreter has to perform O(N³) operations to output the first N squares.

The interpreter avoids endless recomputations by storing computed values in a large cache called the “warehouse”. Every time a new demand is generated, the interpreter first checks the warehouse to see if the value is not already available. Values in the warehouse are labeled by (1) the variable whose value is stored and (2) the tag identifying the particular value in question. Items in the warehouse are accessed by their labels; it is an associative memory. Accesses are handled using hashing and require only a few operations each.

In Calvin Ostrum’s first draft of the Lucid interpreter every value every computed value was stored in the warehouse, and nothing was ever thrown away. This scheme is very time-efficient (nothing is ever recomputed), but is incredibly wasteful of space.
Even the simplest programs soon fill the warehouse with  thousands of tagged items, most of which will never be used again. Ostrum made no attempt to implement a more sophisticated memory-management scheme, but he did leave software hooks for one. Provision was made for periodic sweeps of the warehouse, during which items which failed a certain predicate would be discarded. The question was, which predicate?

It is easy to see that in general we cannot predict which stored values will later be needed. We would have to predict the values of the tests in if–then–else expressions. Fortunately, the memory-management scheme does not have to be perfect. If it fails to throw out a few useless items, only a little space is wasted. On the other hand, if it is overeager and discards a few items that are later required, no real harm is done. These values can always be recomputed so that (usually) only a little time is wasted. The memory-management scheme can therefore be a heuristic and still be very useful.

For the sake of simplicity, we concentrated on finding one that did not involve analyzing programs. After a few experiments with simple-minded least-recently-used first-out methods, we settled on a heuristic which is reasonably simple, requires no program analysis, and yet performs remarkably well. The heuristic used by the pLucid interpreter is called the retirement plan. It involves discarding those items which experience shows are too old to be of any further use.

More precisely, the age of an item in the warehouse is the number of garbage-collecting sweeps that it has survived since it was last used. The age of an item is initially 0. Every time a sweep of the warehouse passes over the item without collecting it, its age is increased by one. Every time an item is requested and used, its age is reset to 0. The age of an item is stored with the item itself. Different items can of course have different ages.

The interpreter also maintains a “global retirement age” (actually, a retirement age limit). During sweeps of the warehouse, the interpreter discards all those items that have reached the age limit. If this results in an insufficiently large percentage of the items being discarded, the warehouse is enlarged (more storage is demanded from the operating system).

The retirement age limit is quite small and changes dynamically. During computation, every time an item is fetched from the warehouse, a note is made of its age (before this age is reset to 0). If the age in question is greater than or equal to the retirement limit, the limit is increased to the age of the item, plus one. On the other hand, after every sweep, the retirement limit is decreased by one. The retirement age moves up and down and ‘adapts’ to the demand patterns of the interpreter. The provision for increasing it helps avoid
retiring items which will be later needed, while the regular decrementing ensures that unused values are soon collected.

The interpreter uses a simple but vital refinement of this scheme: it keeps a separate retirement limit for each distinct program variable. By maintaining a whole vector of retirement limits, it is able to allow for different demand patterns for different variables. In practice, the retirement limits for different variables can be quite different, though they are usually small. The retirement scheme has proved to be extremely successful, certainly in comparison with the strategy of saving everything. Programs often use one tenth the storage or even less, and simple iterative ones (like the square generator given above) run in constant space. The retirement plan is capable, in principle, of discarding values that are later required; but we have never found a ‘sensible’ program in which this ever happens. It seems that the plan takes advantage of the fact that demand patterns are almost chronological (non-anachronistic), even if in general they are not exactly so.