Anticipatory optimization in domain specific translation

Combinatorial increases in programming productivity are possible by the introduction of high level operators and operands for composite data structures such as arrays, matrices, trees, record composites, etc. Such operators and operands can be composed to generate combinatorially many virtual components. However, the performance of such compositions is often inadequate because of code fragmentation and delocalization engendered by the building blocks. Attempts to automatically reorganize this code to optimize performance using conventional optimization strategies are usually impractical because of the large search spaces engendered. Anticipatory optimization (AO) is a method for compiling such compositions directly to optimized code without large search spaces and indeed, without any search space at all. The keys to AO are: distributed optimization plans expressed via code annotations; and transformation based optimization planning that concurrently reasons over the domain information, the generated program and the evolving optimization plan