  Efficient inference is often possible in a streaming context using
Rao-Blackwellized particle filters (RBPFs), which exactly solve inference
problems when possible and fall back on sampling approximations when necessary.
While RBPFs can be implemented by hand to provide efficient inference, the goal
of streaming probabilistic programming is to automatically generate such
efficient inference implementations given input probabilistic programs.
  In this work, we propose semi-symbolic inference, a technique for executing
probabilistic programs using a runtime inference system that automatically
implements Rao-Blackwellized particle filtering. To perform exact and
approximate inference together, the semi-symbolic inference system manipulates
symbolic distributions to perform exact inference when possible and falls back
on approximate sampling when necessary. This approach enables the system to
implement the same RBPF a developer would write by hand. To ensure this, we
identify closed families of distributions -- such as linear-Gaussian and finite
discrete models -- on which the inference system guarantees exact inference. We
have implemented the runtime inference system in the ProbZelus streaming
probabilistic programming language. Despite an average $1.6\times$ slowdown
compared to the state of the art on existing benchmarks, our evaluation shows
that speedups of $3\times$-$87\times$ are obtainable on a new set of
challenging benchmarks we have designed to exploit closed families.
