# Unifying AI Algorithms with Probabilistic Programming using Implicitly
Defined Representations

Avi Pfeffer
Charles River Analytics
<EMAIL_ADDRESS>Michael Harradon
Charles River Analytics
<EMAIL_ADDRESS>Joseph Campolongo
Charles River Analytics
<EMAIL_ADDRESS>Sanja Cvijic
Charles River Analytics
<EMAIL_ADDRESS>
###### Abstract

We introduce Scruff, a new framework for developing AI systems using
probabilistic programming. Scruff enables a variety of representations to be
included, such as code with stochastic choices, neural networks, differential
equations, and constraint systems. These representations are defined
implicitly using a set of standardized operations that can be performed on
them. General-purpose algorithms are then implemented using these operations,
enabling generalization across different representations. Zero, one, or more
operation implementations can be provided for any given representation, giving
algorithms the flexibility to use the most appropriate available
implementations for their purposes and enabling representations to be used in
ways that suit their capabilities. In this paper, we explain the general
approach of implicitly defined representations and provide a variety of
examples of representations at varying degrees of abstraction. We also show
how a relatively small set of operations can serve to unify a variety of AI
algorithms. Finally, we discuss how algorithms can use policies to choose
which operation implementations to use during execution.

##  1 Introduction

Probabilistic programming (PP) has made significant progress over the years.
Early papers [Koller et al., 1997, Sato and Kameya, 1997] contained very
limited languages with one-off algorithms and were focused more on theory than
practical applications. As the first generation of practical systems developed
(e.g. ProbLog [De Raedt et al., 2007], IBAL [Pfeffer, 2007a], Infer.NET [Winn
and Minka, 2009], Church [Goodman et al., 2012], Stan [Carpenter et al.,
2017]), the focus was on greater practicality of representation and efficiency
of algorithms. Some languages, like Hakaru [Narayanan et al., 2016], attempt
to establish fundamental principles of computation in probabilistic
programming. Recent languages like Venture [Mansinghka et al., 2014] and Gen
[Cusumano-Towner et al., 2019] have focused on frameworks for organizing
inference, while other languages like Edward [Tran et al., 2016] and Pyro
[Bingham et al., 2019] offer increased scalability and development of
practical applications. Our goal is to continue this tradition and develop PP
as a major organizing framework for development of intelligent systems.

In recent years, we proposed Scruff (citation withheld for anonymity) to be a
framework for building AI systems based on predictive processing. As we have
developed Scruff, we have come to realize that achieving our goal of
developing a general AI framework requires a new way of writing PP systems.
The challenges include:

  * •

If we are to develop a general framework for AI, components of a system take a
variety of forms, such as code with stochastic choices, neural networks,
differential equations, and constraint systems. Although only the first would
traditionally be considered a probabilistic program, we would like to include
them all under a single umbrella, with PP at its core as a Turing complete
abstraction supporting native description of uncertainty.

  * •

As the number of different kinds of model components increases, the difficulty
of writing algorithms that work with all the different components also
increases significantly. In particular, it is unlikely that any traditional
algorithm (e.g. Monte Carlo sampling or belief propagation) will work with
every kind of component. It should be possible to use algorithms that are not
fully general in applications that support them.

  * •

Furthermore, it may be that certain effects are achieved in different ways for
different kinds of component. For example, if a distribution over the state of
a variable at a particular point in time is required, this can be computed
analytically for some ODEs, while others require simulation; for probabilistic
models sampling can achieve the desired result, but again analytic methods
could work for some models. Many PP languages only offer a single method of
performing computations (e.g. Infer.NET uses expectation propagation); even
those that offer a choice of algorithms typically require that once chosen,
the same algorithm is applied to all model components (Stan?). It should be
possible to combine different methods of computing within a single execution
to best exploit sub-model properties.

Scruff’s approach to addressing these challenges is centered on the idea of
_implicitly defined representations_. The idea is simple but has significant
implications for the design of the system. We define a set of standard effects
we might want to perform with model components and call them operations. These
operations might include, for example, to generate a representative value for
the component, to compute the probability of a value, to generate a
representation of a probability distribution over the values of a component,
to infer conditions on the inputs to a component given observations on its
output, or to compute the gradient of parameters given observations of the
inputs and outputs.

The operations serve to separate the representation of individual model
components from the implementation of algorithms. The term ”implicit” comes
from the fact that, as far as the algorithms are concerned, the components are
defined implicitly by the operations they support; the specific representation
of the components does not matter to the algorithms. Algorithms are written
using these standardized operations and work for any components on which those
operations are defined. For example, if an algorithm requires generating
representative values for a component, it can use a sample operation that can
be implemented for generative probabilistic models employing Monte Carlo
sampling as well as ODEs employing simulation. These kinds of components can
be freely combined in a model without any extra work. Furthermore, other
modeling frameworks and algorithms can be wrapped with operations, enabling
them to be incorporated into Scruff. These properties lead us to believe that
Scruff does indeed have the potential to be a general organizing framework for
AI systems. Furthermore, although the motivation has been PP, the ideas apply
to any reasoning framework that involve connected model components. So, for
example, we could potentially use Scruff to organize different kinds of deep
learning components.

Implicitly defined representations enable Scruff to address all the challenges
liste4d above. By making the implementation of operations the salient explicit
property of a representation, algorithms can readily examine whether a
particular model component supports a specific operation, and decide whether
or not to use that operation. Meta-reasoners can also determine whether an
algorithm can run on a model by examining whether the components support the
operations required of the algorithm. In some cases, an algorithm might only
require some of the components to implement an operation, while others do not.
For example, for a feed-forward neural network (NN) component that processes
an image to produce a classification, it is hard to compute a probability
distribution over the image given the classification. An algorithm like belief
propagation (BP) generally requires such a distribution, but for a leaf of the
model, like an image classifier, it can be dispensed with. Combining NNs with
BP is not new (e.g. [Kuck et al., 2020, Jia et al., 2021]); the innovation is
that it is done in a fully general way and accomplished with little extra work
in a common framework.

Scruff uses policies to control the invocation of operations. Policies
stipulate which implementation of an operation to use or which values of
hyperparameters should be chosen (e.g. number of samples in a histogram
estimation). Policies can be specified using a small number of standard
concepts (e.g. laziness), to provide a uniform way for operation implementers
to communicate the choices and for algorithm designers to state their
preferences. Policies can also be optimized to identify novel heterogenous
operation execution patterns resulting in superior accuracy or speed.

From a design point of view, implicit operations have driven the designers of
Scruff to push for increasing degrees of abstraction. The goal is to find a
relatively small number of operations that support a large number of
algorithms, while being sufficiently general to enable implementation on a
wide variety of components. We have also sought to identify abstract
representations of model components that include a large number of concrete
implementations, enabling a relatively small number of operation
implementations to hold for a wide variety of model components.

In this paper, we first present briefly the basic architecture of Scruff and
terminology used, and give examples of some of the most frequently used
operations. We then present details of the implementation of the implicit
operations framework, including policies. We then describe some of the
modeling abstractions used to support a large number of model components with
a small number of operation implementations. Then, we present examples of
Scruff’s support for different kinds of algorithms and choices. Finally, we
conclude with a discussion of future possibilities, including meta-inference
and planning using operations.

##  2 Scruff Architecture and Terminology

In the introduction, we used terms like ”model” and ”model component”, which
make intuitive sense, but Scruff has specific and precise terminology which we
will use from now on. Scruff is implemented in Julia and we will use Julia
code to explain concepts.

One of the central concepts in Scruff is a _stochastic function_ (called
SFunc), which is a representation of a relationship from inputs to outputs, in
which the same input can produce multiple outputs. We allow deterministic
functions as a special case with a single output for each input. Although we
use the term ”stochastic”, the probability distribution over outputs is not
necessarily specified; operation implementations (OpImpls) that require a
specific probability distribution (e.g. the closed-form expectation of a
parameterized normal distribution) will not be supported by other SFuncs, but
it can still implement that operation in another way and participate in some
algorithms. In addition, an SFunc is not necessarily represented by generative
code as in most probabilistic programming languages, but can be any
mathematical representation of the required relationship.

Formally, an SFunc is parameterized by three parameters, SFunc{I,O,P}. I is
the type of inputs to the SFunc, which must be a (possibly empty) tuple type.
In other words, an SFunc has zero or more inputs, each of which can be any
Julia type. O represents the output of the SFunc, which can be any Julia type.
In particular, O, as well as components of I, can be SFuncs, which enables
higher-order SFuncs. Also, O can be the Julia type Nothing, which enables
SFuncs to be used as entities that do not produce an output but score the
inputs. P is the type of parameters to the SFunc, which is important to
machine learning with Scruff, but is not essential for this paper. Examples of
SFuncs and their abstractions are presented in Section 4.

Scruff uses the term _model_ to describe something that generates an SFunc at
different points in time to represent the evolution of some domain entity.
Such a domain entity that evolves over time under a model is called a
_variable_ in Scruff. We will use variable to denote an entity whose value is
described by an SFunc. While the model concept is central to Scruff’s ability
to reason about dynamically changing systems, they are not essential to the
topic of this paper, and we will not use them further, other than to point out
that we will avoid using the term model from now on because of its Scruff
usage. We will restrict use of the term model to examples from the literature
where the usage is standard.

For what we called ”model” in the introduction, Scruff uses the term
_network_. A network consists of a directed acyclic graph over SFuncs.
Specifically, for each SFunc in the network, there is an assignment of an
SFunc in the network to each of its inputs. Despite the acyclic structure of
networks, the use of scoring SFuncs in which the output type is Nothing
enables Scruff to represent undirected graphical models.

Recursively, a network is also an SFunc. Some of the SFuncs without parents in
the network are designated as placeholders, corresponding to inputs. Other
SFuncs in the network are designated as outputs. The input of the network is
then a tuple of output types of the placeholders, while the output of the
network is a tuple of the outputs of the output SFuncs. As SFuncs, networks
support operations that enable them to be used in algorithms.

An _operation_ is a representation of a type of computation performed on an
SFunc. It has a type signature that describes the expected input and output
types, depending on the type parameters of the particular SFunc. An operation
also has a set of _operation implementations_ , or OpImpl, each of which is a
Julia method that takes inputs and returns an output of the appropriate types
for a given SFunc. There may be more than one implementation of a particular
operation for a given SFunc that employ different strategies. We defer more
detailed discussion of operations to Section 3.

An _algorithm_ is a program that uses operations on a set of SFuncs to perform
some calculation. An algorithm may use a _policy_ the defined how it
dispatches against multiple OpImpls. That policy can set the hyperparameters
of an OpImpl, for example expressing its preferences for runtime/accuracy
tradeoffs. BP [Pearl, 1988], variable elimination (VE) [Zhang and Poole, 1994,
Dechter, 1998], and sequential Monte Carlo [Doucet et al., 2000] are examples
of algorithms in Scruff.

Many of Scruff’s algorithms (like sequential Monte Carlo) explicitly involve
time and dynamics, but this is not a necessary feature of an algorithm. Just
like a network can recursively be an SFunc, so an algorithm that performs
reasoning tasks on a network can become the implementation of an operation on
the network as SFunc at the higher level. Scruff also includes a framework for
runtime support of algorithms, providing services such as message passing and
memory management. Algorithms and policies will be discussed in Section 5.

##  3 Operations

One of the primary contributions of Scruff is the design of an interface for
computing and composing the application of higher-order functions on SFuncs.
We refer to these higher-order functions as operations. Operations are
associated with an intended mathematical function. For example, an expectation
operation has the standard mathematical definition in a probabilistic
framework of $\mbox{{Expectation}}_{f}(y\mid x)=\int yf(y|x)$. A particular
OpImpl may compute this statistic exactly, or it may use an approximate
algorithm, possible controlled by a hyperparameter (e.g. number of samples).

Because the intended mathematical function is stated, algorithms generally
know what to expect from implementations of operations. Scruff does not have
any means to verify the correctness of implementations, however. Instead,
Scruff can verify that different operation implementations are compatible with
one another to some degree of accuracy. For example, any SFuncwith vector
output type that supports a Sample operation implicitly supports a generic
Expectation operation via monte carlo method. Thus, if some closed form
OpImplfor Expectation is implemented Scruff can verify the degree to which an
existing sample-based implementation agrees with the new method.

Operations also define a type signature transformation that produces the type
signature of the resulting operation from the type signature of the
SFunc{I,O,P}. For instance, an operation SampleN might produce a set of $n$
conditional samples from an SFunc, where $n$ is an argument to the
operation—in that case, we say that SampleN has signature (I,O): (I, Int) ->
Vector{O}. Any implementation of SampleN for a given SFunc must satisfy that
defined signature. Note that we use camel case for the operation itself, which
is a type in Julia, and lower case for the OpImplmethod, in accordance with
Julia standards. In practice each ‘OpImpl‘ is assigned a unique name to enable
controlled dispatch.

The creation of the appropriate type and function is achieved using a macro
`@op`. Implementations of the operation for specific SFuncs are created using
the `@op_impl` macro. Specifically, the type of the operation is parameterized
by the type of the SFunc on which it is implemented. The SFunc on which an
operation is invoked is always the first argument to the operation’s function;
when the function is called, the SFunc is wrapped in the appropriate type to
ensure that the correct OpImpl is called. Because the SFunc type is already
present in the type of the OpImpl, it is omitted from the arguments in the
`@op_impl` definition. For example, an implementation of SampleN for a Flip
SFunc might be given by:

    @op_impl function SampleN{Flip}(x::Nothing, n::Int)
          # Flip has no parents, so x is Nothing
    Ψ  ps = rand(Float64, n)
    Ψ  # sf refers to the sfunc on which the implementation is defined
    Ψ  return [sf.prob < p for p in ps]
    end

In contrast with typical method definition and usage, SFuncs may have multiple
implementations of the same operation. This is common when there are fast,
approximate ways to compute something as well as slow, exact approaches. Each
OpImpl can define a set of hyperparameters that affect the calculation
performed. For instance, an iterative algorithm might specify the number of
iterations, or a histogram calculation might internally take a number of
samples. For convenience each hyperparameter must have an associated default
value, though they can be changed manually or automatically at operation
invocation. Consider an example of inverting a deterministic linear SFunc
using a builtin procedure versus using an iterative algorithm. In the code
below, the struct in each @op_impl creates a specific type for the OpImpl.

    @op_impl begin
        struct InvFullMatMul <: Invert{MatMul} end
        function invert(y)
            global matmul_invert_count += 1
        return sf.mat \ y
        end
    end

    @op_impl begin
        struct InvIterativeMatMul <: Invert{LinearOp}
            num_iters::Int = 5
            step_size::AbstractFloat = 1.
        end
        function invert(y)
            x = zeros(shape(sf))
            for i in 1:op_imp.num_iters
                res = sample(sf, x) - y
                x = x - op_imp.step_size*res
            end
        return x
        end
    end

Operations can take SFuncs as arguments and return them as well. This is
critical for the operations used in algorithms like belief propagation. Here
we present simplified versions of definitions of the ComputePi operation, for
SFuncs that only have a single parent, and leaving out additional arguments
that provide the ranges of the SFunc and its parent. In this case, ComputePi
takes a message from a parent, in the form of a Dist, which is an SFunc that
defines an unconditional distribution, and returns a prior probability
distribution over the child, also represented as a Dist. In that section we
also show a complete implementation of ComputePi that includes the additional
arguments and works for any number of parents.

    ComputePi: (I,O): Dist{I} -> Dist{O}

In addition to specializing on the type of SFunc on which the operation is
invoked, the operations can also specialize in their other arguments following
the multiple dispatch design of Julia. For example, ComputePi for a normal
distribution can be difficult and may require sampling from or discretizing
the range of the normal distribution. When the parent message is normal,
however, it can be computed in closed form. We can create a specialized
implementation of ComputePi for this case. This example exploits the fact that
Normal is a kind of Dist, so can be used as the parent message.

    @op_impl function ComputePi{Normal}(ps::Normal)
        mu = expectation(ps)
        var = variance(ps) + sf.var
        return Normal(mu, var)
    end

##  4 SFunc Abstractions

Since Scruff implementation is centered around the implementation of
operations, it is vital to find the right abstractions that enable a small
number of OpImpls to apply to a large number of specific SFuncs. These
abstractions are centered around notions of composition, with the idea being
to develop composition SFuncs, in which the implementation of operations is
derived automatically from the implementations of components. SFuncs can have
input and output types described by other SFuncs, so it is possible to
implement models described by expressive recursion - this ensures our SFunc
composition representations are Turing complete.

###  4.1 Basic abstractions

The most basic abstractions specialize on the types of inputs and outputs. We
have already introduced Dist. In particular, we define

    abstract type Dist{O,P} <: SFunc{Tuple{}, O, P}

to represent an SFunc with no parents (Dist stands for distribution for the
most common case, although as before an explicit distribution does not need to
be defined). Examples of Dist include Cat for categorical, Flip for Bernoulli,
and Normal SFuncs. The Dist representation is useful because not having an
input can make certain operations easier to define. For example, sending
$\lambda$ messages for BP, an operation difficult to derive tractably from
pure generative models, is trivial because there are no parents to send to.

Similarly, for an empty output type we define

    abstract type Score{I,P} <: SFunc{I, Nothing, P}}

Implementations of Score can be used to represent evidence or soft
constraints, as well as implement undirected graphical models as discussed
earlier. Examples of Score include HardScore, which only allows one value;
SoftScore, which weight different values; and FunctionalScore, in which the
score is not represented explicitly but is defined by a function that takes a
value and returns a score. This kind of functional score is useful when there
are infinitely many values.

###  4.2 Mixtures

A simple example of a composition SFunc is Mixture. Mixtures are a standard
concept in probabilistic programming, in which the generative process randomly
selects between one of several possibilities, each with a given probability.
In a similar way, Scruff’s Mixture randomly selects between several SFuncs,
but from the Mixture’s point of view the specific types of SFuncs is
completely abstracted away; they could be probabilistic models, ODEs, NNs, or
perhaps a mix of all these. The OpImpls for Mixture invoke the corresponding
operations on the components; the operation will be supported by the Mixture
whenever it is supported by all the components, and the implementation will be
derived automatically.

For example, here is the implementation of the ComputePi operation for
Mixture. ComputePi is an operation used in BP, as defined by Pearl’s classic
algorithm [Pearl, 1988]. The purpose of this operation is to take a set of
$\pi$ messages from the parents of the SFunc, representing probability
distributions over parent values, and compute the $\pi$ distribution for the
SFunc itself, which is the expected distribution over values of the SFunc
given the distributions over the parents. ComputePi takes three arguments: The
range of the SFunc (in this case the mixture), the ranges of the parents, and
the incoming $\pi$ messages, whose type is a Dist. (This also illustrates
another abstraction of Scruff; rather than represent the $\pi$ messages as a
vector of floats, as it would be in most other PP systems, we let it be any
Dist. We will discuss this point more in the next section). The implementation
of ComputePi is as follows:

    1 @op_impl function ComputePi{Mixture}((range, parranges, incoming_pis))
    2    function f(i)
    3         cp = compute_pi(sf.components[i], range, parranges, incoming_pis)
    4         sf.probabilities[i] .* [cpdf(cp, (), x) for x in range]
    5     end
    6     scaled = [f(i) for i in 1:length(sf.components)]
    7     result = sum(scaled)
    8     return Cat(range, normalize(result))
    9 end

Lines 2 to 5 defined a function that is performed for every index i from 1 to
the number of components. (Julia array indices start with 1). For each
component, the function delegates to the compute_pi implementation of the
component, with the same values of the arguments. (Note the automatic
transformation of case from Julia’s standard type case (ComputePi) to function
case (compute_pi)). In Scruff’s abstract implementation, this can return any
kind of Dist. Therefore, the operation cpdf (which stands for conditional
probability density function) is used to get the probability of each element
in range. This is the operation through which any Dist can be converted to the
usual vector of floats representation. The function f then uses Julia
broadcasting to multiply each of these probabilities with sf.probabilities[i],
which is the mixture probability for the corresponding component. Once this
function has been defined, most of the work is done. The function is invoked
for each component index in line 6, and the vectors for each component are
summed in line 7 and normalized in line 8. Since a Dist must be returned, this
result is packaged into a Cat (for categorical).

Mixture is perhaps a simple and fairly standard example, but before we move on
to more sophisticated composition operators, we show how Scruff uses the
Mixture abstraction to represent an interesting class of SFuncs and to
automatically derive OpImpls for them. A Separable SFunc [Pfeffer, 2001] is a
representation of a conditional probability table for $X$ given parents
$U_{1},\ldots,U_{n}$ with special structure: $P(X\mid U_{1},\ldots,U_{n})$
decomposes into $\sum_{i=1}^{n}P_{i}(X\mid U_{i})$. Separable SFuncs are
desirable for both representational and computational reasons. The
representation of Separable uses a number of parameters that is linear in $n$,
rather than exponential in $n$ for the usual representation. Furthermore, the
cost of performing BP operations such as ComputePi is also linear in $n$ for
Separable SFuncs, rather than exponential. This fact was actually not known to
us until we developed an explicit Separable implementation rather than relying
on standard conditional probability table implementations.

The additive decomposition in the definition of Separable SFuncs suggests a
mixture, but each of the $P_{i}$ has a different parent $U_{i}$, violating the
standard assumptions of a mixture. To fix this, Scruff provides an Extend
SFunc that takes an SFunc with one parent and converting it to an SFunc with
many parents, while ignoring all the new parents. By applying Extend to the
individual $P_{i}$, we align them to the same set of parents and can then
represesnt the separable SFunc as a mixture. Once this is done, no operations
need to be implemented for Separable; they are all derived automatically from
Mixture. In fact, the derived version of ComputePi implements the efficient
linear time algorithm we discovered. In fact, once we realized that Separable
can be represented as a Mixture, the algorithm we discovered became obvious,
because the implementation of ComputePi for Mixture is straightforward. This
shows the potential of Scruff’s abstract approach to provide useful and
efficient new implementations.

###  4.3 Conditionals

Scruff provides a rich class hierarchy, rooted in the Conditional SFunc, to
represent different kinds of conditional probability relationships. To orient
the reader through this subsection, Figure 1 shows a hierarchy of the SFuncs
we will discuss.

Figure 1: Hierarchy of conditional probability relationships

At the root of the hierarchy, Conditional captures the general notion of
probabilistic dependence, without minimal assumptions about how that
dependence is represented. The definition of Conditional is as follows:

    abstract type Conditional{I <: Tuple, J <: Tuple, K <: Tuple, O,
                                           Q, P, S <: SFunc{J, O, Q}}
      <: SFunc{K, O, P}
    end

The plethora of type parameters indicates that there is a lot to unpack here.
A Conditional has two sets of parents, known is the $I$ parents and the $J$
parents. The type parameters I and J represent the tuple types for these two
sets of parents. The type parameter K represents the concatenation of I and J
into a single tuple of parents. (As far as we know, Julia cannot express this
concatenation without having to introduce the additional type parameter.)The
type O is the output type of the Cconditional.

The $I$ and $J$ parent sets serve two different roles. The Conditional has an
embedded SFunc type S, which is an SFunc{J, O, Q}. That is, its input is a $J$
parent set and its output is O, which is the output of the Conditional. S also
has parameters of type Q. Thus, the role of the $J$ parent set is to serve as
parents of another SFunc. The role of the $I$ parent set is to determine which
other SFunc to use, so long which must be of type S. If we think of SFuncs as
generative models, we can imagine a generative process of looking at the $I$
parents to choose an SFunc $s$, and then using the generative process of $s$,
given the $J$ parents, to generate an output $o$. However, we caution that
SFuncs are not necessarily generative models, but the idea of using the $I$
parents to choose the relationship and the $J$ parents to participate in the
relationship holds in general.

The Conditional as a whole is an SFunc{K, O, P}. We have already seen that K
is the concatenation of the $I$ and $J$ parent type tuples, while $O$, the
output of the embedded SFunc type S is also the output type of the
Conditional. P is the type of parameters of the Conditional, which are
different from the parameter type Q of the selected SFuncs.

It is surprising how many OpImpls can be developed even at this very abstract
level. These implementations capture the essence of the process of using a set
of parents (the $I$ parents) to choose a probabilistic relationship that may
depend on other parents (the $J$ parents). Operations implemented for
Conditional include computing support, drawing a sample from the conditional
probability distribution, computing the log conditional probability density,
creating a tabular factor to represent the conditional probability
distribution, as well as the BP operations ComputePi and SendLambda. All these
implementations rely on a method gensf that takes a tuple of values of $I$
parents and returns the SFunc of type S selected.

Unfortunately, the implementations of these operators are either trivial (as
in the case of Sample or Logcpdf) or too long to show here. We will show the
code for Sample to illustrate the easy case and show pseudocode for some of
the other cases. Here is the implementation of Sample:

    @op_impl function Sample{Conditional}(parvals)
        (ivals, jvals) = split_pars(sf, parvals)
        sfg = gensf(sf,ivals)
        return sample(sfg, jvals)
    end

split_pars is a utility function that decomposes a tuple of values into $I$
and $J$ tuples. This code illustrates why Sample is so easy to implement; it
simply selects the SFunc to use for the given $I$ parent and then delegates
sampling to it. In general, however, the implementation needs to reason about
and integrate different possible choices of the $I$ parents. The more complex
OpImpls demonstrate that this reasoning is general. For example, here is
pseudocode for ComputePi:

ComputePi(sf::Conditional, range, parranges, incoming_pis)

  1. 1.

Split parranges and incoming_pis into $I$ and $J$ components, called
(iranges,jranges) and (ipis,jpis).

  2. 2.

Compute the Cartesian product of iranges.

  3. 3.

For each tuple $i$ in the Cartesian product:

    1. (a)

$R\leftarrow\texttt{zeros(length(range))}$.

    2. (b)

$p_{i}\leftarrow\prod_{k=1}^{n}\texttt{ipi}_{k}(i_{k})$.

    3. (c)

$s\leftarrow\texttt{gensf}(\texttt{sf},i)$.

    4. (d)

$p_{j}=\texttt{ComputePi}(s,\texttt{range},\texttt{jranges},\texttt{jpi})$.

    5. (e)

$R\leftarrow R+p_{i}~{}\mbox{.*}~{}p_{j}$ # element-wise product

  4. 4.

Return $R$

The important thing about this implementation is not just the fact that it can
be implemented but what it says about the general process being described. In
short, it sums, over all the possible cases of $I$, the probability of that
case times the $\pi$ value computed for the selected SFunc for that case. This
is the essence of this operation for conditional relationships and it has wide
applicability. All the other operations on Conditional are implemented along
similar lines.

Before we get to the applications, we introduce a useful special case of
Conditional, known as ParamGen. ParamGen stands for Parameter Generator, which
is the role of the $I$ parents, who select the SFunc $s$ by setting the
parameters of a fixed embedded SFunc. This allows a particularly easy
implementation of gensf using a function gen_params, which takes a value of
the $I$ parents and returns the parameters for the embedded SFunc. The
significance of ParamGen is that it enables the implementation of operations
related to the Expectation-Maximization (EM) algorithm, including computing
expected sufficient statistics and maximizing the parameters given expected
sufficient statistics. As a result, SFuncs that derive from ParamGen are able
to participate in EM learning processes by parameter estimation.

One application of Conditional and ParamGen is the linear Gaussian model. A
linear Gaussian represents a conditional distribution of one real-valued child
on a number of real-valued parents. Specifically, the child is Gaussian (i.e,
normally) distributed with a mean that is a linear function of the values of
the parents.

Scruff implements LinearGaussian in a straightforward way by deriving from
ParamGen. In this case, all the parents are $I$ parents and there are no $J$
parents. The embedded SFunc is a Normal. The gen_params function takes the
values of the parents and returns the output of the linear function and sets
the mean of the Normal appropriately with fixed variance.

Another application is the Table, which is actually a general kind of ParamGen
where the $I$ parents select the appropriate SFunc $s$ by indexing into a
table of parameters. Again, the implementation is straightforward. The $I$
parents are used for table lookup, while the $J$ parents are the parents of
the embedded SFunc. The gen_params function simply performs the table lookup.

Once we have Table, we can define a variety of different representations of a
conditional probability table. For example, DiscreteCPT is a traditional
conditional probability table as it appears in standard discrete Bayesian
networks (BNs). In this case, the embedded SFunc is a Cat, i.e., an explicit
probability distribution over a discrete set of values.

A richer representation is the CLG, which stands for _conditional linear
Gaussian_. In the BN literature, a CLG is viewed as a representation for a
continuous child with a mix of continuous and discrete parents [Lauritzen,
1992]. The discrete parents determine which specific linear Gaussian SFunc to
use for the relationship between the continuous parents and the child. In
Scruff, a CLG is simply a Table in which the embedded SFunc is a
LinearGaussian.

Although algorithms for inference with BNs that include CLGs are well-known
and implemented in commercial-grade systems like HUGIN [Andersen et al.,
1989], they are not easy to implement in general and non-commercial systems
often do not support them. In Scruff, the OpImpls are derived automatically
from the operations on Normal, ParamGen, and Conditional, so CLGs can
participate in any algorithm that uses these operations, including VE, BP, and
EM, in addition to easier-to-implement algorithms like importance sampling and
Markov chain Monte Carlo. Furthermore, they can be combined with a far wider
variety of representations than in traditional software.

###  4.4 Other Composition SFuncs

While the Conditional family of SFuncs captures a general class of
probabilistic dependencies, Scruff provides a number of other composition
SFuncs, besides Mixture which we presented earlier. These include Det for
deterministic relationships; Switch and If to represent conditional execution;
and Apply, which is a type of higher order SFunc. We discuss each of these in
turn.

Det very simply represents a deterministic function from the inputs to the
output. This is extremely useful, for example, to include physics models in
Scruff programs. We have used this technique to integrate physical models of
electrical components with generative probabilistic models of system behavior
for health monitoring applications.

The implementation of Sample is straightforward: simply apply the given
function to the inputs and return the result. Many of the other operations,
such as ComputePi, are also straightforward; if we have a distribution over
the inputs, we can easily get a distribution over the output.

However, operations that invert the SFunc by attempting to infer properties of
inputs given observations on outputs are more difficult, for multiple reasons.
First, it is not in general tractable to invert a function to determine what
inputs might have led to an observed output. Second, many candidate output
values according to the SFunc type might not correspond to any given input, so
they have probability zero. This can be a source of significant error.

While Scruff does not have a complete solution to this fundamentally difficult
problem, the approach of allowing multiple implementations of operations
provides a developer the freedom to implement partial solutions that work well
in some cases, enabling these SFuncs to be used in situations that might not
otherwise have been possible. For example, one implementation Scruff provides
of the SendLambda operation uses interpolation. Given ranges of values of the
parents, potential values of the child are generated by calling the given
function. Observed values of the child are then compared to the generated
values by interpolation, leading to evidential $\lambda$ messages being sent
to the parents. Although this technique will not work in general, it seems
reasonable for some physical models, and works well in our applications. It’s
also important to note that OpImplsdo not need to be exact, even if you wish
to employ exact inference - any approximate inference algorithm can be
converted to an asymptotically exact one by using it as a proposal
distribution for importance sampling or similar algorithm. In this way even
very rough approximations can result in major improvements over e.g. sample-
based methods.

Switch is a simple SFunc that derives from Det to represent situations in
which one of a set of SFuncs is chosen based on the state of a switch. Switch
can be compared to Mixture. In Mixture, the choice of SFunc is stochastic
based on a probability distribution, while in Switch, the choice is
deterministic based on another parent.

These connections suggest alternative implementations. For example, Mixture
could be implemented by a Switch in which the switch is implemented as a Cat.
It would be interesting to explore whether OpImpls for this more general
representation will recover the efficient implementations for Mixture and
Separable. Finally, we remark that using Switch, we can also implement a
simple conditional If where the switch is Boolean and there are two choices.

Finally, Apply{J,O,P} is a higher-order SFunc that has two inputs. The first
input is an SFunc{J,O,P}, which takes the second input of type J as parent.
Apply implements the concept of functional uncertainty in PP, which is
uncertainty over the identity of the function to use in a function
application. This can be seen by considering a network with three SFuncs:

  1. 1.

A Dist{S,Q} where $S$ is SFunc{J,O,P}, with no parents.

  2. 2.

A Dist{J,R} where $J$ is any type, with no parents.

  3. 3.

An Apply{J,O,P} with the first two SFuncs as parents.

Again, there are intersting connections to explore that may be fruitful.
Conditional might be implemented using Apply, in which the gensf function is
reified in a Det that takes the $I$ parents as arguments and returns the
selected SFunc. We currently only have a small set of operations implemented
for Apply; this is work in progress, and it would be interesting to see
whether it is possible to reimplement Conditional using this more general
mechanism and recover the OpImpls.

##  5 Algorithms

One of our main claims is that a small set of well-chosen operations can
support a variety of algorithms in different representational frameworks. This
has two main benefits. First, it enables us to generalize implementations of
algorithms across paradigms, reducing development effort. Second, and more
significantly, it enables us to combine different paradigms in a single
application, using networks that have different kinds of SFuncs in them.

In this section, we show how several algorithm families can be treated in this
way. We discuss elimination algorithms, message passing algorithms, and
generate and score algorithms. However, we do not claim that all algorithms
are amenable to this approach. For example, Markov chain Monte Carlo (MCMC)
algorithms, widely used in probabilistic programming, are as far as we know
specific to probabilistic models. Although they can be readily incorporated
into Scruff, the two benefits above are not achieved for these algorithms.

In this section, we build on the work of Dechter [Dechter, 1999, Dechter,
2019], who has unified different AI frameworks under the umbrella of
elimination and conditioning algorithms. We go beyond this work in two ways.
We consider a wider variety of frameworks, including NNs and ordinary
differential equations (ODEs) for inclusion in this approach. We also present
a general software paradigm for implementing these algorithms that is flexible
because it allows the algorithm developer to combine different operations as
desired.

###  5.1 Elimination Algorithms

Elimination algorithms, of which VE [Zhang and Poole, 1994, Dechter, 1998] is
the canonical example, work by systematically removing SFuncs from a network
until only a target set of SFuncs remains, with information computed about
those target SFuncs. In general, these algorithms formulate a computation as a
sum-of-products expression over factors and use the commutative and
distributive laws to manipulate this expression to reduce computation.
Expressed in this way, several authors have shown that elimination algorithms
can be applied to any semiring [Goodman, 1999, Pfeffer, 2007a, Eisner et al.,
2004].

For example, for standard BN inference, factors are tables of real numbers,
sum is the usual sum on reals, and product is the usual product on reals.
Computing the most likely explanation is similar, except that sum is a
maximization function. For logical systems, sum is disjunction and product is
conjunction. For EM learning, sum and product operations also process
sufficient statistics, which often also form a semiring. For decision-
theoretic problems, sum and product process utilities, which are also a
semiring.

To implement elimination algorithms, Scruff uses a Semiring class hierarchy,
where each type of Semiring has appropriate sum and product functions. Each of
the above algorithms will use a different type of Semiring; although
probabilistic inference and most likely representation have the same factor
representation, they use different sum functions. To implement an elimination
algorithm, a MakeFactors operation, which creates the factor for the SFunc
over the appropriate Semiring, needs to be implemented for the relevant
SFuncs. MakeFactors takes the Semiring as an argument, enabling the same
SFuncto be used in different elimination algorithms.

Once the Semiring type and corresponding MakeFactors operation has been
implemented, the VE algorithm is obtained. Furthermore, there are many
variants of elimination algorithms, such as the junction tree algorithm
[Lauritzen and Spiegelhalter, 1988] used in commercial-grade BN
implementations and the mini-buckets approximation scheme [Dechter and Rish,
2003]. If these algorithms are implemented using the MakeFactors operation,
they are obtained automatically for all the different frameworks.

Scruff’s expression of all these algorithms in a common framework is not
novel; other PP systems (e.g. IBAL [Pfeffer, 2007a]) have used semirings to
implement a variety of elimination algorithms. However, implementing these
methods within a standard flexible framework leads to surprising new
possibilities. The product function each take two values as arguments. In
Julia, which uses multiple dispatch, we are able to define different methods
for these functions that take different Semiring types as arguments. For
example, we might provide an implementation of product that takes a logical
value and a probabilistic value and zeros out the probabilistic value when the
corresponding logical value is false. We would then obtain elimination
algorithms that work jointly on networks including both probabilistic and
logical SFuncs. An alternative way to implement this idea is to use the
standard probabilistic semiring also to implement logical elimination
algorithms, but this would be unnatural for implementers of the logical
algorithms. Furthermore, integrating the framework in the way we have
described allows for alternative implementation; for example, we might combine
the logical and probabilistic entries by treating the probabilistic entry as a
Boolean that is true if the value is non-zero.

###  5.2 Message Passing Algorithms

The name ”propagation” is common to many algorithms used in AI, including
constraint propagation, belief propagation, and NN backpropagation. This
sharing of name is not a coincidence. All these algorithms are based on
message passing on graphs. In general, message passing on directed graphs
includes three kinds of operations: ”forward” message computations, ”backward”
message computations, and local updates. However, from now on we will avoid
using the terms ”forward” and ”backward” as these have opposite meanings in
different communities. In the probabilistic reasoning community, ”forward” is
the generative direction from causes to effects, while ”backward” is the
direction of inference from observations on effects to beliefs about causes.
In feed-forward NNs, ”forward” is the direction of inference, i.e. predicting
unknown values (e.g. classifications) from observations on effects (e.g.
images), while ”backward” is the direction of inferring gradients on weights
in the network from errors in the prediction. Instead of ”forward” and
”backward”, we will follow Pearl’s terminology and use the $\pi$ direction for
the direction from causes to effects and the $\lambda$ direction for
observations on effects to inferences or predictions about causes.

Generative probabilistic models and NNs have complementary strengths and
weaknesses. Generative models are generally good at computing in the $\pi$
direction, which requires sampling or computing values. These generative
models have predominated in PP, which is one reason why sampling algorithms
have been so prevalent. While reasoning in the $\lambda$ direction can be
achieved, and much effort has been expended on making it efficient, in general
it requires inverting the SFunc and can be very expensive. Meanwhile, NNs are
very good at reasoning in the $\lambda$ direction, where prediction is a
linear time operation in the size of the network. However, it is extremely
difficult to infer inputs given outputs in the $\pi$ direction. ODEs can
generally be used well in both directions.

These facts have led researchers to develop bidirectional models that use a
generative probabilistic model in the $\pi$ direction and a NN in the
$\lambda$ direction. The intention is that the that the two models express
(approximately) the same relationship between inputs (in the Scruff sense of
inputs to an SFunc) and outputs. Inference compilation techniques [Le et al.,
2017] implement this idea by using the generative model to generate a training
set to train a NN that can be used in the $\lambda$ direction. Variational
autoencoders [Kingma and Welling, 2014] are another implementation of this
idea.

Scruff implements message-passing in a general way through operations that
reason in the $\pi$ direction, $\lambda$ direction, or locally within an
SFunc. For example, we have already shown ComputePi, which produces a
representation of the prior knowledge about a variable, and SendLambda, which
sends a $\lambda$ message to a particular parent. An example of a local update
operation is ComputeBel, which combines prior and evidential knowledge to form
beliefs about the variable. In Bayesian reasoning, this is the process of
multiplying prior probabilities with likelihoods. In other frameworks,
ComputeBel might be implemented lazily, using a function that gets the
appropriate belief when desired. In Section 6, we show some examples of
alternative implementations along with policies to choose between them.

Figure 2 shows the general structure of Scruff networks that are used in
message passing. The top layer consists of SFuncs that can support $\pi$
operations but not $\lambda$ operations. These include, for example, SFuncs
that are hard to invert. As we have discussed, Det SFuncs can be hard to
invert. Although we have implemented an approximation method using
interpolation that enables them to be used in a more general way, a safe way
to use them is to include them in the top layer of the network. The drawback
is that it is not impossible to send evidential messages to their parents.
Despite this, they can still have interesting parent-child relationships and
can be used to represent rich priors, including from physical models.

Figure 2: Structure of Scruff networks used with message passing

The bottom layer consists of SFuncs that support $\lambda$ operations but not
$\pi$ operations. These are most typically used to interpret sensor
observations, for example with NNs. Since the sensors are observed, the
inability to propagate priors to them is not a significant drawback.

The middle layer consists of SFuncs that support both $\pi$ and $\lambda$
operations and can participate fully in the message passing process. This
includes bidirectional SFuncs as well as most of the examples of probabilistic
SFuncs we discussed in Section 4. Note that the other two layers can also
include these types of SFuncs. However, they will not be able to participate
fully in message passing, because they are ancestors of SFuncs that do not
support $\lambda$ operations or descendants of SFuncs that do not support
$\pi$ operations.

The benefit of this approach is that it enables SFunc developers to support
the operations they are able to support without worrying about completeness of
implementation, while algorithms can be flexible about using the SFuncs in the
appropriate way. For example, a BP algorithm can begin with an analysis that
determines on which variables it can perform $\pi$ and $\lambda$ operations,
and then proceed to do as much work as possible, obtaining beliefs about as
many variables as possible.

To this point, we have focused on inference but not learning, which is of
course vital in many modeling frameworks. In NNs, stochastic gradient descent
is used to train the weights of the network. Although EM is usually used to
learn the parameters of Bayesian networks in practice, it is well-known that
the parameters can be learned by gradient descent as well [Russell et al.,
1995]. In an earlier paper, we showed (citation surpressed), using automatic
differentiation techniques, that gradient descent computations for Bayesian
networks can be achieved as a byproduct of the BP process, using message
passing. Scruff’s support for gradient-computation message passing algorithms
is very similar to its support for inference. The major difference is in the
direction of the messages. In NNs, inference is used in the $\lambda$
direction to predict hidden state, while gradient messages proceed in the
$\pi$ direction to process the errors. For BNs, predictions of outputs is done
in the $\pi$ direction, and then gradient messages are then processed in the
$\lambda$ direction.

Figure 3 shows the structure of networks used in gradient descent, similarly
to Figure 2. Fortunately, many SFuncs will play the same role in both
structures. For example, NNs will appear in the bottom layer, while
deterministic functions, which are generally not learnable, might be in the
top layer.

Figure 3: Structure of Scruff networks used with gradient descent

###  5.3 Generate and Score Algorithms

Generate and test is a standard algorithmic framework used to search for an
value that satisfies certain properties. It requires a generator of value and
a way to determine whether an value satisfies the required properties. Values
are repeatedly generated by the generator and then tested; only values that
pass the test are preserved. In probabilistic inference, this is the basis of
the rejection sampling algorithm.

Generate and test can be generalized to generate and score algorithms. Instead
of a Boolean test whether an item satisfies a property, it is scored with a
number, and items generated are weighted by their score. In probabilistic
inference, generate and score is implemented by importance sampling.
Importance sampling is also the basis for sequential Monte Carlo algorithms,
also known as particle filtering, widely used to reason about dynamic
probabilistic models.

These ideas are so simple as to be ubiquitous. Scruff provides a very general
implementation of these ideas using a Sample($s$) operation to generate a
value from the SFunc $s$ and a GetScore($c,x$) operation to score the value
$x$ with the Score $c$. As we have discussed, the Score family of SFuncs is
flexible and can include, for example, both explicit vectors and functional
computations. Although the ideas here are simple, the flexibility is useful.

Things get interesting, however, when we combine these generate and score
algorithms with other kinds of algorithms. A drawback of generate and score
algorithms is that it can be difficult and expensive to generate values that
have reasonably high scores and are representative of the values of interest.
To mitigate this problem, researchers have developed lookahead sampling
techniques [Dearden and Clancy, 2002, Ahmed et al., 2012] that use the
observations to guide the generation of samples. A simple implementation of
lookahead sampling is likelihood weighting [Sato and Kameya, 1997, Shwe and
Cooper, 1991], which only looks ahead one step. In probabilistic programming,
researchers have used various strategies to look ahead in importance sampling
[Pfeffer, 2007b, Nori et al., 2014].

Using Scruff, we get a highly general version of lookahead sampling with
little effort by combining it with message passing. If we consider again the
structure shown in Figure 2, we see that $\lambda$ messages can be propagated
all the way up except into the top layer. $\lambda$ messages are in fact
represented as instances of Score. Therefore, they can be used in a generate
and score algorithm to score the values generated by the top layer. Dechter
has developed in depth similar ideas combining conditioning with elimination
[Mateescu and Dechter, 2012, Dechter, 2019]. Scruff’s approach demonstrates
how a simple set of operations can be used to easily create implementations of
algorithms that have hitherto required significant research.

##  6 Policies

A policy in Scruff is a program that, upon invocation of an operation, selects
a compatible operation implemetation to employ as well as values for any
available hyperparameters. We refer to this as a policy with inspiration from
Markov Decision Processes (MDP); a policy determines the choice of OpImpl at
every point. The act of selecting OpImpls over the course of algorithm
execution with the goal of producing an accurate, fast result essentially
defines an MDP. Automatically deducing a performant set of operation choices
is thus equivalent to a policy optimization problem. However, methods for
performing these optimizations are left for future work. For now, we allow the
programmer to explicitly implement policies, but have also provided the
framework for automatic optimization in future.

Policies are programs that take as input the inputs, outputs and SFuncs
associated with each operation call during the execution of an algorithm.
Then, when an operation is invoked, the policy can use any computational rule
to produce a valid OpImpl for the invoked operation and SFunc. If no policy is
specified, the default is to rely on Julia’s standard methods using multiple
dispatch. Scruff provides support functions for finding all the candidate
OpImpls that could be used for a given call.

Policies can make use of performance characteristics of OpImpls, which are
implementer-specified descriptions of expected performance of the OpImpl.
These are implemented using the @op_perf macro, which defines an operation
performance chartacteristic or OpPerf. The macro takes an OpImpl type and the
arguments to the OpImpl and returns a standard performance measure. For
example, the runtime performance measure estimates, naturally, the running
time of the OpImpl on the given arguments. The compositional nature of SFuncs
also enables composition of OpPerf implementations. For example, the runtime
of calling ComputePi for a Mixture is approximately the sum of the runtimes
for the components.

One useful performance measure in Scruff is support_quality. Scruff relies
heavily on the ability to compute the support of SFuncs for a variety of
algorithms. This support computation can have different characteristics, which
are useful for algorithms to know.

  * •

For some SFuncs, particularly those with a small discrete range, this is
straightforward and can be done completely. This is important for algorithms
that want to provide exact answers.

  * •

For others, such as continuous SFuncs like Normal, the range cannot be
enumerated fully. Nevertheless, Scruff provides operations for computing the
support of SFuncs like Normal incrementally, producing increasingly rich
support sets on each iteration, with the support set after each iteration
being a superset of the previous iteration. One of the algorithms in Scruff is
a lazy algorithm that iteratively refines a network until the desired accuracy
is achieved, which makes use of this incremental support computation. The
iterative improvement quality enables this algorithm to guarantee improvement
of the answers computed on each iteration.

  * •

For other SFuncs, support computation is neither complete nor incremental, but
done on a best effort basis. Although these provide no guarantees, they can
still be useful in approximate algorithms.

One way to deal with these different kinds of guarantees about the support
computation would be to use three different operations for complete,
incremental, and best effort support. However, this would be both inconvenient
and misleading, since they all intend to compute exactly or approximately the
same mathematical definition, which is the set of values that have positive
probability. The difference is only in the success they can offer. Therefore,
we use a single support operation for all these cases and express the
different guarantees using support_quality. An implementation of support will
declare its guarantees using an OpPerf. For compositional SFuncs, the
implementation of the OpPerf will recurse to the arguments. For example, the
support_quality for Mixture will be the minimum support_quality of the
components, where the ranks are complete, incremental, and best effort.

Another useful performance characteristic is laziness. Some OpImpls will
compute values eagerly while others will defer them until later. For example,
the compute_bel operation takes a Dist, representing information from the
inputs coming in the $\pi$ direction, and a Score, representing information
from the outputs coming in the $\lambda$ direction, and computes a belief,
i.e. a distribution over the value of the variable considering all the
information, which is also implemented as a Score. Mathematically, the belief
is the element-wise product of the Dist and the Score. While simple
implementations can be created for specific types of Dist and Score, there are
generic implementations that work for any type of Dist and Score. Here are two
implementations, one eager and one lazy. The eager implementation needs to
immediately produce a score, so it needs to sample values of the variable. The
lazy implementation returns a function that can be used later to compute the
belief and wraps it in a FunctionalScore.

    @op_impl begin
        struct EagerComputeBel <: ComputeBel{SFunc}
            num_samples :: Int # hyperparameter
            EagerComputeBel() = new(100) # default value of hyperparameter
        end
        function compute_bel(d::Dist, s::Score)
            values = Vector{I}()
            scores = Vector{Float32}()
            for i in 1:num_samples
                x = sample(d)
                push!(values, x)
                push!(scores, score(s,x))
            end
            return SoftScore(values, scores)
        end
    end

    @op_impl begin
        struct LazyComputeBel <: CompiuteBel{Sfunc}
        function compute_bel(d::Dist, s::Score)
            f(x) = density(u,x) * score(s,x)
            return FunctionalScore(f)
        end
    end

The laziness characteristic of the two OpImpls are declared using is_lazy.
Specifically, the following OpPerf declarations are used:

    @op_perf is_lazy(EagerComputeBel) = false
    @op_perf is_lazy(LazyComputeBel) = true

Algorithms that wish to make a preference, say, for lazy inference, can use
is_lazy in their policy implementations. Given a choice between multiple
OpImpls, they can prefer the lazy ones, perhaps along with other criteria.

##  7 Future Prospects

Scruff has been under development for several years. Although work is ongoing,
we feel that much has been achieved and the time is right for publication. We
are planning an open source release in the next few months (the release will
be delayed until after the POPL reviewing period).

We would like to highlight two potential directions for future work. The first
is meta-reasoning. We have already hinted at meta-reasoning in the discussion
of policies. Determining a policy for choosing OpImpls is one form of meta-
reasoning. Our OpPerf framework provides an initial basis for this. More
interesting would be to view OpImpls, whose performance is uncertain, as
themselves being SFuncs. OpPerfs would then become OpImpls for OpImpls as
SFuncs. This approach could potentially enable us to create systems that
reason about their environment and their internal operation in an integrated
way.

A second potential direction is to AI planning systems. Planning has been
integrated into PP using the planning as inference paradigm [Botvinick and
Toussaint, 2012], where planning is accomplished by inferring the actions that
are likely to lead to desirable states. However, it is possible that a wider
variety of AI planning algorithms could also be integrated into the Scruff
framework. Many planning algorithms can be viewed as message passing using
forward or backward reasoning over a set of planning operators. Achieving this
unification could enable new forms of AI agent design that do joint inference
and planning.

## References

  * [Ahmed et al., 2012] Ahmed, M. O., Bibalan, P. T., de Freitas, N., and Fauvel, S. (2012).  Decentralized, adaptive, look-ahead particle filtering.  arXiv preprint arXiv:1203.2394.
  * [Andersen et al., 1989] Andersen, S. K., Olesen, K. G., Jensen, F. V., and Jensen, F. (1989).  Hugin-a shell for building bayesian belief universes for expert systems.  In International Joint Conference on Artificial Intelligence (IJCAI), volume 89, pages 1080–1085.
  * [Bingham et al., 2019] Bingham, E., Chen, J. P., Jankowiak, M., Obermeyer, F., Pradhan, N., Karaletsos, T., Singh, R., Szerlip, P., Horsfall, P., and Goodman, N. D. (2019).  Pyro: Deep universal probabilistic programming.  The Journal of Machine Learning Research (JMLR), 20(1):973–978.
  * [Botvinick and Toussaint, 2012] Botvinick, M. and Toussaint, M. (2012).  Planning as inference.  Trends in cognitive sciences, 16(10):485–488.
  * [Carpenter et al., 2017] Carpenter, B., Gelman, A., Hoffman, M. D., Lee, D., Goodrich, B., Betancourt, M., Brubaker, M., Guo, J., Li, P., and Riddell, A. (2017).  Stan: A probabilistic programming language.  Journal of Statistical Software, 76(1):1–32.
  * [Cusumano-Towner et al., 2019] Cusumano-Towner, M. F., Saad, F. A., Lew, A. K., and Mansinghka, V. K. (2019).  Gen: a general-purpose probabilistic programming system with programmable inference.  In Programming Language Design and Implementation (PLDI), pages 221–236.
  * [De Raedt et al., 2007] De Raedt, L., Kimmig, A., and Toivonen, H. (2007).  Problog: A probabilistic prolog and its application in link discovery.  In International Joint Conference on Artificial Intelligence (IJCAI), volume 7, pages 2462–2467.
  * [Dearden and Clancy, 2002] Dearden, R. and Clancy, D. (2002).  Particle filters for real-time fault detection in planetary rovers.  Technical report, NASA, Moffett Field, CA, Ames Research Center.
  * [Dechter, 1998] Dechter, R. (1998).  Bucket elimination: A unifying framework for probabilistic inference.  In Learning in Graphical Models, pages 75–104. Springer.
  * [Dechter, 1999] Dechter, R. (1999).  Bucket elimination: A unifying framework for reasoning.  Artificial Intelligence, 113(1-2):41–85.
  * [Dechter, 2019] Dechter, R. (2019).  Reasoning with probabilistic and deterministic graphical models: exact algorithms.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 13(1):1–199.
  * [Dechter and Rish, 2003] Dechter, R. and Rish, I. (2003).  Mini-buckets: A general scheme for bounded inference.  Journal of the ACM (JACM), 50(2):107–153.
  * [Doucet et al., 2000] Doucet, A., Godsill, S., and Andrieu, C. (2000).  On sequential monte carlo sampling methods for bayesian filtering.  Statistics and computing, 10(3):197–208.
  * [Eisner et al., 2004] Eisner, J., Goldlust, E., and Smith, N. A. (2004).  Dyna: A declarative language for implementing dynamic programs.  In Proceedings of the ACL 2004 on Interactive poster and demonstration sessions.
  * [Goodman, 1999] Goodman, J. (1999).  Semiring parsing.  Computational Linguistics, 25(4):573–606.
  * [Goodman et al., 2012] Goodman, N., Mansinghka, V., Roy, D. M., Bonawitz, K., and Tenenbaum, J. B. (2012).  Church: a language for generative models.  In Uncertainty in Artificial Intelligence (UAI).
  * [Jia et al., 2021] Jia, J., Baykal, C., Potluru, V. K., and Benson, A. R. (2021).  Graph belief propagation networks.  arXiv preprint arXiv:2106.03033.
  * [Kingma and Welling, 2014] Kingma, D. P. and Welling, M. (2014).  Stochastic gradient vb and the variational auto-encoder.  In International Conference on Learning Representations (ICLR), volume 19, page 121.
  * [Koller et al., 1997] Koller, D., McAllester, D., and Pfeffer, A. (1997).  Effective bayesian inference for stochastic programs.  In AAAI Conference on Artificial Intelligence, pages 740–747.
  * [Kuck et al., 2020] Kuck, J., Chakraborty, S., Tang, H., Luo, R., Song, J., Sabharwal, A., and Ermon, S. (2020).  Belief propagation neural networks.  arXiv preprint arXiv:2007.00295.
  * [Lauritzen, 1992] Lauritzen, S. L. (1992).  Propagation of probabilities, means, and variances in mixed graphical association models.  Journal of the American Statistical Association, 87(420):1098–1108.
  * [Lauritzen and Spiegelhalter, 1988] Lauritzen, S. L. and Spiegelhalter, D. J. (1988).  Local computations with probabilities on graphical structures and their application to expert systems.  Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157–194.
  * [Le et al., 2017] Le, T. A., Baydin, A. G., and Wood, F. (2017).  Inference compilation and universal probabilistic programming.  In Artificial Intelligence and Statistics (AIStats), pages 1338–1348. PMLR.
  * [Mansinghka et al., 2014] Mansinghka, V., Selsam, D., and Perov, Y. (2014).  Venture: a higher-order probabilistic programming platform with programmable inference.  arXiv preprint arXiv:1404.0099.
  * [Mateescu and Dechter, 2012] Mateescu, R. and Dechter, R. (2012).  The relationship between and/or search and variable elimination.  arXiv preprint arXiv:1207.1407.
  * [Narayanan et al., 2016] Narayanan, P., Carette, J., Romano, W., Shan, C.-c., and Zinkov, R. (2016).  Probabilistic inference by program transformation in hakaru (system description).  In International Symposium on Functional and Logic Programming, pages 62–79. Springer.
  * [Nori et al., 2014] Nori, A., Hur, C.-K., Rajamani, S., and Samuel, S. (2014).  R2: An efficient mcmc sampler for probabilistic programs.  In AAAI Conference on Artificial Intelligence, volume 28.
  * [Pearl, 1988] Pearl, J. (1988).  Probabilistic reasoning in intelligent systems: networks of plausible inference.  Elsevier.
  * [Pfeffer, 2001] Pfeffer, A. (2001).  Sufficiency, separability and temporal probabilistic models.  In Uncertainty in Artificial Intelligence (UAI).
  * [Pfeffer, 2007a] Pfeffer, A. (2007a).  The Design and Implementation of IBAL: A General-Purpose Probabilistic Language, page 399.  MIT Press.
  * [Pfeffer, 2007b] Pfeffer, A. (2007b).  A general importance sampling algorithm for probabilistic programs.  Technical report, Harvard University.
  * [Russell et al., 1995] Russell, S., Binder, J., Koller, D., and Kanazawa, K. (1995).  Local learning in probabilistic networks with hidden variables.  In International Joint Conference on Artificial Intelligence (IJCAI), volume 95, pages 1146–1152.
  * [Sato and Kameya, 1997] Sato, T. and Kameya, Y. (1997).  Prism: a language for symbolic-statistical modeling.  In International Joint Conference on Artificial Intelligence (IJCAI), volume 97, pages 1330–1339.
  * [Shwe and Cooper, 1991] Shwe, M. and Cooper, G. (1991).  An empirical analysis of likelihood-weighting simulation on a large, multiply connected medical belief network.  Computers and Biomedical Research, 24(5):453–475.
  * [Tran et al., 2016] Tran, D., Kucukelbir, A., Dieng, A. B., Rudolph, M., Liang, D., and Blei, D. M. (2016).  Edward: A library for probabilistic modeling, inference, and criticism.  arXiv preprint arXiv:1610.09787.
  * [Winn and Minka, 2009] Winn, J. and Minka, T. (2009).  Probabilistic programming with infer.net.  Machine Learning Summer School lecture notes.
  * [Zhang and Poole, 1994] Zhang, N. L. and Poole, D. (1994).  A simple approach to bayesian network computations.  In Proc. of the Tenth Canadian Conference on Artificial Intelligence.