Generative Programming System and Method Employing Focused Grammars

Abstract

A system and method may employ, focused grammars to facilitate automated generation of computer programs. Such implementation of focused grammars enables a new form of symbolic regression referred to as generative programming or automated programming. The search through the space of possible programs may be guided by a streak search method in accordance with which identified candidate programs that improve on the current streak may be used to create focused grammars for directing an additional localized search. In some embodiments, candidate programs are generated by randomly traversing focused grammars from the starting rule, and subsequently through the grammars, until a complete candidate program parse tree has been constructed. Candidate programs may then be executed, for example, by an evaluator, which may employ an interpreter adapted for use in conjunction with a Stack Manipulation Language or other interpreted language.

1 . A generative programming system; said system comprising:
 a processor operating in conjunction with a grammar module, a program generator, and an evaluator;   said grammar module to generate a stochastic grammar;   said program generator to generate a candidate program in accordance with the grammar; and   said evaluator to evaluate the candidate program in accordance with predetermined criteria and under control of said processor;   wherein said grammar module is operative to modify the grammar using a modulating program designated in accordance with results of the evaluation, the modifications based upon a decomposition of terminal and non-terminal nodes of the modulating program and including at least a structural modification and a probability modification to focus results during subsequent iterations of generating a candidate program.