art with code

2010-04-07

Algebraic transformations

Algebra is the study of structure and the transformations you can do to a computation while preserving its result. If you can prove that an operation fulfills an algebraic axiom, you can use that axiom to transform a tree of such operations.

With binary operators, the basic axioms are

No external side-effects: a x b = a x b
Closure: the operation preserves the type; t -> t -> t
Associativity: the nesting doesn't matter; a x (b x c) = (a x b) x c
Commutativity: the order of parameters doesn't matter; a x b = b x a

Neutral element is a value that does nothing. When one of the parameters to the operator is a neutral element, the operator returns the other parameter.
Left neutral element: when applied to the left side of the operator; NL x a = a
Right neutral element: when applied to the right side of the operator; a x NR = a
Neutral element: left and right neutral elements are the same; NL = NR

Inverse is a way to make the operator return the neutral element for any value.
Left inverse: inverseL(a) x a = N
Right inverse: a x inverseR(a) = N
Inverse: inverseL = inverseR

Then there are two-operator axioms like

Left-distributivity: a x (b + c) = (a x b) + (a x c)
Right-distributivity: (b + c) x a = (b x a) + (c x a)

To use the axioms in transforming a tree of operations (say, the AST used by your calculator program), create a list of axioms matching the nodes in the tree. The new trees generated by applying the axioms in the list are the neighbor nodes of the original tree. Then you toss in a cost function and a search algorithm and emerge with a program optimizer.

Hand-waving


The nice thing about the axioms is that they're kind of stackable. For example, if you know that your operator x is an abelian group (that is, it has closure, associativity, inverse, neutral and commutativity), an operator o, defined as a o b = a x b x C where C is a constant, is also an abelian group (ditto for permutations of the order of operations thanks to commutativity).

If you create a list of axiom-preserving tree transformations, I think you could create a search graph to figure out the axioms an operator fulfills. Take the AST of the operator, apply transformations until you find an already proven operator. Then automatically add the axioms to the operator's documentation and generate tests for them.

Digression


Maybe you could generate time-complexity figures for a function too. Determine the maximum amount of times it calls other functions wrt its parameters, multiply the other function complexities with that. For space-complexity, multiply the space-complexity of the other functions by the time they're called and add the current function's number of allocations.

For an empirical version of that, the IDE could call each pure function with different-size inputs and measure the CPU time and memory used. Then plot a nice graph, do some curve-fitting, embed into documentation. If you do this profiling live in a background process, you could have performance metrics that update while you code. A real-time view of the efficiency of your code...

No comments:

Blog Archive