Though this model would in fact already be sufficient for the machine, we do have more requierements to meet to get a memory strong enough for real life operation. There are two additional services to be provided by the reference memory, and these are garbage collection and persistence.
Because the memory of our current hardware is still very limited, we need to have efficient means to recycle it. This can either be done manually by use of explicit release operations (like "free" in C). Since this method is pretty expensive (in cost of programmer's working hour) and cannot applied to the intended central task of the Xaron engine, term rewriting, we need to do automatic garbage collection.
Though there are different approaches of how to do automatic garbage collection, we use the most direct way, the mark-scan method.
By this, the values in the memory are recursively traversed starting from some roots (as the slots on the stack), following their possible references (pointers) to other values while marking the traversed values as visited. This marking process continues until we cannot reach any unmarked value.
The following scanning phase passed through all objects in the memory and can safely free all values not visited, since the are not reachable from any root.
Implementing automatic garbage collection is particular simple in the reference memory as defined earlier. It only takes the following ingredencies:
As we see, we have come to define the infrastructure of the types, by requiering to operations to be defined for each type:
| enum: T -> ( V -> Set(N) ) | free: T -> ( V -> void )
Note that in a recursivly defined data type, the above operation are defined such, that they only take care of the immediate value, not of its (transitive) decedents. I.e. freeing a node of the tree means to free the node, not the whole subtree. Likely, the enumberation is to deliver the braches of the node not the closure of the subtree.
The automatic garbage collection is well suited to needs of the implementation of the reference memory by a hash table, which needs to be reorganized as while is filled to maintain the guaranteed constant costs of its operations.
Thus, we can simply trigger the garbage collection as soon as the hash table is filled to a certain water mark (e.g. 100% or 75% or whatever the desired efficieny is.).
After the scanning phase, a new hash table can then be allocated in a size continuing to guarantee the hash table completety, and the values of the old table can be entered into it.
Even better, it is possible to keep the old indexes (names) of the values stored in the table if one accepts that the table is never shrinking.
Keeping the indexes has the great advantage, that a renaming of the application of the storage names is then not necessary. This does not only save an additional pass over all values kept in memory, but more.
Not only that renaming might not be possible with every (external) data type, it can also become a costy operation. For instance, Xaron uses many finite maps, which are implemented by dynamic hashing with names as their domains. Doing a renaming operation on these maps practically means that they have to be fully reconstructed, since otherwise name clashes would become possible.
On the other hand, a ENGLISH("Verzicht") of the renaming during usual collection does not exclude it in general. One could either do it on demand, or if the size of the hash table is not longer well balanced with (i.e. very larger) then the total size of the values organized by it.
To add a renaming feature we requiere a substituion operation bound to each type:
| subst: T -> V * (N->N) -> void
As a result, the chosen construction does provide nothing as opportunities here.