Canonical representation of programs I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume canonicalization is generally intractable, but NP algorithms and more-constrained problems (e.g. pure functions) are also interesting. Normal forms may be useful too. My goal is not to be able to represent and manipulate all programs, but some of them (the trivial ones).
The brief survey contained in this paper might be of interest:

J. Swan, Z. A. Kocsis, and A. Lisitsa. 2014. The 'representative' metaheuristic design pattern. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO Comp '14). ACM, New York, NY, USA, 1435-1436. DOI=http://dx.doi.org/10.1145/2598394.2609842.

It discusses the existence of canonical forms for various forms of representation (groups, rings, boolean functions etc) and in particular normal forms for the lambda calculus using $\beta$-reduction as a rewrite rule.