Brush handling in Mite

[axch]

Architectural question: Are traces required to maintain the invariant that the current state of a trace could have arisen from an (incomplete) forward evaluation?

This invariant has various implications:

• Dangling requests are impermissible. [Definition: A dangling request is one whose result is not consumed by anything currently traced (including "traced evalution in progress").]
• Dangling subexpressions are impermissible too.
• If the evaluator needs a value that isn't there, evaluating subexpressions and compound procedures cannot hit a value that is there.

Should this invariant be enforced?

• Pro: The evaluator, and the regeneration algorithms, are written assuming so.
• Pro: Lite and Puma are like this.
• Pro: It seems like a nice invariant from the point of view that the model program is the primary object and the trace is, well, a trace.
• Pro: Until about noon today I didn't have any other ideas for how to interpret a trace.
• Con: Scaffold construction and detach algorithms have to maintain the above implications.
• Con: To meet this constraint, extract and regen have to implement some default brush handling strategy.
• Con: Any candidate "trace literal" has to satisfy this invariant too.
• Con: Philosophically, it seems odd for the "runtime system" to impose a requirement like this on allegedly "pluggable" trace structures.

Why is this acute now?

• As of 819dcbb, Mite's detach does not actually respect this invariant, though the interpreter and other trace code still assume it. The discrepancy causes crash Resolve the multiple request registration problem in Mite #650.

What alternatives are there?

• It may be possible to re-imagine traces as primary. A kind of "active memory", for which the model program, if any, serves only to define the relationship(s) among its storage locations. See Can we view a trace as an "active memory" rather than an "execution history"? #655 for a fuller exposition of this view.
• Another variant would say "here is how the evaluator is written; a trace can do what it wants as long as it doesn't crash when called according to this pattern."
• There may be other coherent views, but I don't know currently know any.

What does implementation look like?

• To enforce the invariant, I would need to modify scaffold construction and regeneration, selecting and implementing a default strategy for handling brush (i.e., things that the invariant requires must be detached).
• To implement the "active memory" view, I would need to review the evaluator and the traces to make their implementation make sense under the view of traces as "active memories" rather than "execution histories". For example, not assuming that the trace does not interrupt subexpression evaluation by sticking a value in there, etc.
  • I anticipate that this will cause base-line evaluation to look more like regeneration, in particular being able to emit weights.
  • Many corner cases and discrepancies may be discovered by the review.
• Implementing the "whatever the trace wants" view is similar, but maybe with more of an emphasis on tweaking the trace rather than the evaluator proper. Don't know how coherent that is.