Generalized Tensor Algebra and Graph Normalization

[brandonwillard]

Now that we're actively working toward support for more than one backend (e.g. Theano and TensorFlow), we'll also need to generalize some tensor algebra operations and define our own normalized/canonical graph forms.

For example, addition, dot products, index operations, etc., are all pretty generalizable, so we'll need corresponding meta operations. We can then define our math-level relations (in miniKanren) using those objects—which we're already doing to varying degrees.

Concomitant with that is the need to develop relations and/or meta object logic for meta graph normalization. Using addition as an example, when variable outputs of addition operations are added together, the entire graph can be collapsed into a single addition operation given the combined inputs (which might also need to be deterministically ordered).

Normalization can always be performed manually and/or as part of certain internal steps (e.g. Theano does this during function creation), but some normalizations can also be built into the/a factory-like function that constructs sub-graphs for an operation (e.g. tt.add and tf.add).

For some operations—like the standard associative, commutative and variadic ones—"on-the-fly" normalization is most likely preferables. In general, as long as an operation's normalization steps are quick and cheap, we might want to consider this.

A complete example of how this work can be done in miniKanren is given in #6.

[twiecki]

Would things be simpler if Theano support was dropped?

[brandonwillard]

Not so much; plus, Theano support might actually be done. We just need to focus exclusively on the meta objects now, but that stops us from being able to make use of some overlapping/related backend-end-specific features (e.g. Theano's existing graph normalization/canonicalization). Even so, Theano's normalization serves a few different purposes and doesn't completely provide what we'll need, so we would have to do this anyway.