Memoise all data

[rolyp]

All data in our system has a persistent location or address, and comes in one of two variants:

• "versioned" data, where the location is a memo-id independent of the content;
• "interned" data, where the location is a hash of the content.

Evaluation creates versioned nodes, based on the locations of versioned nodes given to it as input. However, internal data types like Expr use interned data in some places, e.g. for storing the field expressions of a constructor expression. That means that when (via reflection) we treat such an expressions as data, the interpreter will sometimes encounter interned nodes rather than the versioned nodes it currently expects.

Therefore: promote all data to versioned data, which involves promoting all internal compiler functions to memoised functions (or rather functions whose outputs have memo-ids; we won't do any actual memoisation yet).

• [x] FunctionId, ApplicationId, memoId memo key builders
• [x] Constr.ctr
• [x] uses of non-versioned cons
• [x] uses of non-versioned nil
• [x] delete Env.entries
• [ ] Env
• [x] replace EvalId by use of memoId
• [x] unaryOps can be versioned; no need to copy values in let or primitive
• [x] ConstNum, ConstStr
• [x] Trie, join
• [x] Pair, FiniteMap
• [x] Expr.Def and Expl.Def forms, RecDef
• [x] revisit/inline unary, binary primitive helpers
• [x] runtime Elim forms
• [ ] delete point and rect helpers
• [ ] ExplValue
• [ ] drop some/all explicit uses of Versioned
• [ ] additional annotation propagation for slicing rules

[rolyp]

Thoughts some more about this, and decided it's a red herring:

1. Versioned nodes only exist because I don't want to throw away the hard work already done relating to node identity. But nothing yet uses node identity, so it's a classic example of a solution looking for a problem. I should probably just be mature about it and delete it.

2. It is only a problem because versioned nodes are how the interpreter tracks annotations. However, these concepts aren't necessarily coupled; we could also allow annotations on interned data. Interned data by its very nature is constant and that's the rationale for their not having annotations, but maybe we can think of annotations as ephemeral metadata that can vary at a single version of the overall system.

3. Interned data also currently lacks an __id field, which is needed to construct the memo-ids for evaluation, but presumably this would just be a question of storing the interning key in the interned object.

4. Making all data versioned (memoised) is, nevertheless, doable, but involves significant complexity. Moreover, we are still left with the question of what to do with uniformly present annotations. What to do with annotations on the list nodes used to store the fields of a constructor, for example? There is a deeper question here about how to make our system truly reflective. If internal lists become versioned, then all internal list functions need to be memoised (which may indeed be what we want, at some point); but a prior version of this problem is that if internal lists become annotated with usage, then all internal list functions need to propagate usage information.