brandonwillard
commented
5 years ago For the sake of completion, here's an extension of the previous example that uses a relation that performs a single step of graph-based reduction. It defines a relation on reductions of subgraph-producing expression arguments and then a reduction of the resulting expression.
from kanren.term import operator, arguments
from kanren.assoccomm import buildo
from symbolic_pymc.unify import etuple
def graph_reduceo(in_graph, out_graph):
"""Relation for an expression (sub-)graph reduction."""
in_op = operator(in_graph)
in_args = arguments(in_graph)
res = (lall,)
reduced_args = etuple()
for a in in_args:
a_reduced = var()
res += ((reduceo, a, a_reduced),)
reduced_args += (a_reduced,)
arg_red_graph = var()
arg_reduce = (buildo, in_op, reduced_args, arg_red_graph)
res += (arg_reduce,)
res += ((reduceo, arg_red_graph, out_graph),)
return res
def reduce_expr(input_expr, n=None):
reduced_expression = var()
res = run(n, reduced_expression,
(graph_reduceo, input_expr, reduced_expression))
return resNow, the example from before will reduce as expected:
print(tt_pprint([res.reify() for res in reduce_expr(tt.log(tt.exp(a)) + tt.log(tt.exp(a)))]))a in R**(N^a_0)
(2 * a)
(log(exp(a)) + a)
(a + log(exp(a)))
(2 * log(exp(a)))
(a + a)
(log(exp(a)) + log(exp(a)))A conde-based recurrence would likely be sufficient for complete graph reduction/normalization (assuming that the relations and input actually have a fixed-point, of course).
The basics of graph traversal and mutation in miniKanren—instead of standard Python graph traversal (e.g. over meta object graphs) with orchestrated miniKanren use—seems quite simple and succinct, especially with respect to "backtracking"-like capabilities. Likewise, it seems as though the standard graph traversal choices are just as accessible (e.g. depth/breadth, graph-first/args-first, etc.), but we'll have to experiment with those ideas a bit more.
Actually, it seems exceptionally simpler to include a diversity of those graph-processing choices in the context of miniKanren. One could conde branch over different processing orders entirely, and, with something like condp, such choices could be more efficiently chosen/short-circuited!
We need generalized graph traversal and manipulation functions—especially since we cannot use Theano
FunctionGraphs and optimizers on TensorFlow graphs. Since the core graph operations will be in miniKanren, these functions might benefit from being in miniKanren, too.What might this look like? For a reduction relation, a simple recursive miniKanren relation would work. Here's a complete example of such a relation:
Using the above, for
a + awe get the following:miniKanren produces two results—each corresponding to the branches in
conde: the reduced expression and its original. The nature of these results brings up some questions:There are "impure" versions of
condethat performcut-like operations—effectively stopping at certaincondebranches—and those can be used to more efficiently produce fixed-point-like results. There's also this "guided" version ofcondecalledcondpthat might allow for fewer relational compromises.The same questions apply to general graph traversal, but also include considerations for how graphs (expression graphs, really) are traversed. In the example above, the graphs aren't really walked:
Notice how the first—and most reduced—expression has not applied the
log(exp(a)) = areduction. This is because the entire graph does not match said reduction; instead, a subgraph does.We can, for instance, easily produce the desired result by transforming these objects into their S-expression-like forms and using
condeto walk the arguments incons-fashion (well, after this PR goes through). Thecondes in this process are also subject to the above questions (or at least similar ones).