Inspect kanren states generated by walko

[brandonwillard]

Looking at the walko example in aesara-devs/aesara#1082, I'm starting to wonder if some of those entries in the state are necessary or not. In particular,

from kanren import eq, var
from kanren.core import lall
from kanren.graph import walko


# A simple tuple-based graph that's easier to investigate than an Aesara graph
graph = (1, (2, (4, 5)))

# A logic variable representing the "output" of the relation that follows
res_lv = var()
res_lv
# ~_139

# Apply the goal `eq` to each matching element in the graphs between `graph`
# and `res_lv`.
# This goal implements a relation like `apply(eq, graph) == res_lv`.
goal = walko(eq, graph, res_lv)

initial_state = {}
stream = lall(goal)(initial_state)

# First node
next_state = next(stream)
next_state
# {~_139: (1, (2, (4, 5)))}

next_state = next(stream)
next_state
# {~_146: 1,
#  ~_147: ((2, (4, 5)),),
#  ~_139: ConsPair(~_144, ~_145),
#  ~_144: 1,
#  ~_158: (2, (4, 5)),
#  ~_159: (),
#  ~_145: ConsPair(~_156, ~_157),
#  ~_156: (2, (4, 5)),
#  ~_157: ()}

# After a few more iterations, we get the following:
next_state = next(stream)
next_state
# {~_146: 1,
#  ~_147: ((2, (4, 5)),),
#  ~_139: ConsPair(~_144, ~_145),
#  ~_144: 1,
#  ~_174: (2, (4, 5)),
#  ~_175: (),
#  ~_145: ConsPair(~_172, ~_173),
#  ~_182: 2,
#  ~_183: ((4, 5),),
#  ~_172: ConsPair(~_180, ~_181),
#  ~_180: 2,
#  ~_206: (4, 5),
#  ~_207: (),
#  ~_181: ConsPair(~_204, ~_205),
#  ~_204: (4, 5),
#  ~_205: (),
#  ~_173: ()}

For instance, there are two logic variables mapped to 1, and only one of them (i.e. ~_144) is referenced elsewhere in the states that are generated. The gives the impression that ~_146 could be removed or avoided altogether.

We should take a closer look at what walko is doing and see if there are "temporary/intermediate" unifications that can be trimmed from the state (or removed altogether), because we don't want graph walking to generate unnecessarily large state dicts.