Limited-memory computation model

gistfile1.txt

An entity can be a pair of entities, with the first being in command of the second's content and execution. For instance, the first can be an imperative computation that only invokes the second computation when (and if!) it finishes. As another example, the first entity can be an interpreter, manually walking over the second entity and updating it. The first entity has exclusive control over the second, except inasmuch as some other entity has control over it. The second cannot even refer to the first except by doing open-ended communication side effects.

All working memory in the system is partitioned into an infinite binary tree, where at each level, the first branch is in command of the second's content and execution. For instance, the first branch can be an imperative computation that only invokes the second computation when (and if!) it finishes. As another example, the first branch can be an interpreter, manually walking over the second branch and simulating it. The first entity has exclusive control over the second, except inasmuch as they may both be under control of some branch higher in the tree. The second branch cannot even refer to the first except by attempting open-ended communication side effects.

At any given level of the binary tree, certain subtrees may be unusable because they're occupied by metadata that's needed by some interpreter branch higher in the tree. Other subtrees may be occupied by pointer constants or limited-size bit strings. For any given implementation of the system, the infinite structure of the tree is not usefully infinite, because all subtrees are occupied this way.

If the binary tree has a depth of 3, the metadata will be laid out in the tree like this:

[kernel-level metadata for region[]]
[kernel-level metadata for region[0]]
[kernel-level metadata for region[00]]
[kernel-level metadata for region[000]]
[data in region[000]]
[kernel-level metadata for region[001]]
[region[000]-level metadata for region[001]]
[data in region[001]]
[kernel-level metadata for region[01]]
[kernel-level metadata for region[010]]
[region[00]-level metadata for region[01]]
[region[00]-level metadata for region[010]]
[data in region[010]]
[kernel-level metadata for region[011]]
[region[00]-level metadata for region[011]]
[region[010]-level metadata for region[011]]
[data in region[011]]
[kernel-level metadata for region[1]]
[kernel-level metadata for region[10]]
[kernel-level metadata for region[100]]
[region[0]-level metadata for region[1]]
[region[0]-level metadata for region[10]]
[region[0]-level metadata for region[100]]
[data in region[100]]
[kernel-level metadata for region[101]]
[region[0]-level metadata for region[101]]
[region[100]-level metadata for region[101]]
[data in region[101]]
[kernel-level metadata for region[11]]
[kernel-level metadata for region[110]]
[region[0]-level metadata for region[11]]
[region[0]-level metadata for region[110]]
[region[10]-level metadata for region[11]]
[region[10]-level metadata for region[110]]
[data in region[110]]
[kernel-level metadata for region[111]]
[region[0]-level metadata for region[111]]
[region[10]-level metadata for region[111]]
[region[110]-level metadata for region[111]]
[data in region[111]]

Note that some of the data sections may be empty (if only for being overcome by metadata), and many of the metadata sections may be empty (e.g. if the memory layout is consistent enough to be fully specified at a high level of the tree).