Resolve the multiple request registration problem in Mite

[axch]

The manifestation is that running extract/regen cycles in Mite can register a request for a given address without unregistering the previous request registered at that address. To date, all discovered instances of this behavior have equivalent exp-env pairs in the pre/post requests.

Why is this a problem?

• I don't like it; it violates what I thought was an invariant of the system, namely that the set of addresses that key a trace's registered requests exactly represents the potion of the traced program that has been executed and has not been unexecuted.
  • This emotionally impedes me investigating other bugs that may interact with this odd behavior, at least until I learn the correct invariant that governs this area.
• If evaluations are not being unevaluated, then kernels of SPs are not getting their extract methods called, which may mess up exchangeably coupled SPs.

Why does it happen? In the cases I have been able to diagnose, the story goes like this

• For some reason, the system decides to attach a proposal kernel to a compound SP or to a memoized SP. [*]
• Scaffold construction (by the single_site_scaffold program corresponding to either flat or graph traces) never discovers that the extract method of this proposal kernel will unregister a request (call it request A), and never attaches any kernels to any applications that occur because of it.
• If request A contained an application of a compound procedure (which happens for basically all uses of mem, and for any compounds that call other compounds), that application must have made another request; call it request B.
• When extract touches the application that made request B, it asks the scaffold "have you any kernels for this?" and the scaffold says "No."
• At this point, there is a shortcut in unapply_sp that says "OK: the trace fragment is the value of the output, and we do not recur." No kernel is called, and request B is not unregistered.
• When regen eventually traverses the same location, it does recur, causing a request equivalent to request B to be submitted, at the same address, causing the crash.
  • This last might also be a mistake: it happens that way because RegeneratingTraceHandle does not override eval_request, so when the compound application that made request A is regenerated, it ends up following the code path of TraceHandle's eval_request, which loses the scaffold and performs a bare eval_request. The check in RegeneratingTraceHandle.apply_sp for whether there is a kernel in the scaffold for that application, which is symmetric with unapply_sp, is never invoked.

Note: The "shortcut" was an intentional change made in commit 819dcbb . The rationale given in the commit message is to treat all nodes that do not occur in a subproblem as completely uninvolved in the proposal. "This is a step toward toward subproblems and regen having the same probabilistic meaning, independent of the structure of the trace."

Options:

• Override eval_request in RegeneratingTraceHandle to make sure the scaffold keeps being respected even recursively.
  • Concern: I expect the resulting behavior will be to reuse rather than regenerate all the computations in the position of request B, which is likely to still be a bug.
  • Concern: I don't have the theory of what the Evaluator, Regenerator, TraceHandle, and RegeneratingTraceHandle class hierarchy is meant to accomplish, so I'm not sure how to do this right. May figure it out on further investigation.
• Just permit multiple request registrations and carry on
  • Concern: What is the invariant of registered requests, then?
  • Concern: I am loath to debug the next bug while the system is in this state, and I have confirmed that there are next bugs relating to the paper's examples.
• Reintroduce implicit kernels for brush, in defiance of the goal listed in 819dcbb.
  • Concern: Presumably that change was made for a reason, so I don't want to unilaterally back it out.

[*] In the case of compound SPs, this is arguably somewhat odd -- Lite, for example, never does anything analogous. However, it seems reasonable to permit resimulating applications of compounds, and the rest of the story happens with memoized SPs too.

[axch]

On further thought, I don't know whether tweaking RegeneratingTraceHandle will be enough, because the same problem may recur on a later transition. It also sounds risky, because the eval_request method is presumably also what is called when generating genuinely new structure.

Another variant on this hack would be for the evaluator to check whether a new request already exists and reuse its output if it does.

Either of these plans does lead to traces that have extra evaluated requests hanging around, whose results are not used by anything. Such traces cannot arise from forward simulation, but may be semantically ok. Even if their bodies contain applications that are exchangeably coupled to stuff that does exist, as long as inference tweaks them from time to time, it will marginalize them out.

[lenaqr]

I haven't thought about this for a couple of months, but let me know if I can help figure out what I was thinking.

[axch]

@LuaC Any help would certainly be appreciated. I don't know what more to tell you to help you (re-)orient, though.

[axch]

It may be possible to work around this problem at least for now by restricting random_scan to only pick random primitives; though I am not sure offhand what would be a good way to make sure it doesn't think that memoized procedures are primitive (they are supposed to look primitive, since they are created with make_sp).

[axch]

It's not completely impossible that orphan families left around by requests whose unevaluation was stalled for lack of kernels might violate some node interlink invariants in dependency graph traces (e.g., lookup nodes that are not registered as children of their sources, or something like that).