Abstract:
While there are many concrete examples of how program generation helps, we do not yet have a general theory for explaining these various concrete examples. At the same time, a key impediment in the adoption of software generation technology is that it often requires software developers to learn new languages (which are also often domain-specific). To address the first point, we propose the use of Kolmogorov complexity as a basis for explaining some of the basic qualities of program generation. To address the second point, and to provide an effective path for the adoption of program generation, we propose a new approach to managing large software systems, and which can be described as Regenerative Programming (RP). The technical novelty in this approach lies in automatically extracting a program generator capable of exactly reconstructing the full code base. To illustrate the potential of this approach, we propose, implement, and test a basic algorithm extracting such generators. Preliminary experimental results on various benchmarks (including the Linux kernel) are encouraging.

This work suggests that there can be significant benefit from viewing program generators as a device to capture the content of a computation both concisely and precisely without incurring an additional runtime overhead.