Learn to auto-include new brush nodes in block enumeration

[axch]

Consider the following innocent-looking program:

[assume coin (flip)]
[assume coin2 (if coin (flip) (flip))]
[infer (gibbs default all 1)]

One would think that this would lead to the uniform distribution on two coin flips, but no. In Lite, one gets

Exception: Cannot deterministically propose values for nodes whose existence is conditional

(run (gibbs default all 1))
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Caused by
Cannot deterministically propose values for nodes whose existence is conditional

In Puma, one gets the even less helpful

python: backend/new_cxx/inc/concrete_trace.h:79: virtual VentureValuePtr ConcreteTrace::getValue(Node*): Assertion `answer' failed.
python: backend/new_cxx/inc/concrete_trace.h:79: virtual VentureValuePtr ConcreteTrace::getValue(Node*): Assertion `answer' failed.
Aborted (core dumped)

Why? Because the global Gibbs attaches DeterministicLKernels to all the extant choices in the program, and then assumes it will always find them there as it varies the control flow. However, regen (when not acting as restore) creates new nodes for the brush, whose node identities do not match the identities of any nodes that existed before (regardless of whether it is reprising the control flow path of choosing a new one). That's why Puma messes up, whereas Lite checks for this problem in advance and gives a nicer error message.

In principle, we can do better. We could index LKernels by the Trace addresses of nodes [*] rather than their machine addresses. Then regenerating the same control flow path would find the same LKernel again. We could also define a "node added to scope" hook that would allow dynamic addition of LKernels to newly created nodes. Together with the solution proposed to #462, that will enable implementation of global enumeration in the presence of (non-recursive) brush.

If we also want to deal with recursive brush, we can implement [1].

[*] Addresses currently uniquely identify locations in program source, which do not uniquely identify nodes, because every application form produces a RequestNode and an OutputNode. However, the tuple (address, node-type) does uniquely identify nodes.

[1] A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs, Stuhlmuller and Goodman, Sta-RAI 2012 http://arxiv.org/abs/1206.3555

[axch]

Marking blocked on #462, because the current plan calls for implementing that search tree first.

[lenaqr]

What does "recursive brush" mean here? Example program?

Edit: Oh, okay, it's clear from the reference. Something like

assume f = proc () { if (flip()) { some_result() } else { f() }
observe f() = some_value

where we'd like to enumerate over all the flips produced by f, even though in principle there's infinitely many.