Evolutionary Computing with Push

Lee Spector
Hampshire College Computational Intelligence Lab

Push is a programming language (actually a family of languages; see below) designed for evolutionary computation, to be used as the programming language within which evolving programs are expressed. Push features a stack-based execution architecture in which there is a separate stack for each data type. In Push, "code" itself is a data type, allowing programs to manipulate their own code as they run and thereby to implement arbitrary and potentially novel control structures. This expressiveness is combined with syntactic minimality: the only syntax rule is that parentheses must be balanced. It is therefore trivial to generate and transform syntactically valid Push programs.

The reason that it is more accurate to call Push a family of languages than a single language is that it has been the subject of continuous variation and research for many years, over which time the emphasis has been more on experimentation and research than on standardization or stability. Versions of Push have been written in several languages by several people, and each new version has generally added new features, dropped old features, and/or changed naming conventions. All versions of Push share a stack-based execution architecture with a separate stack for each type, and with types and instructions that permit the runtime manipulation and execution of code.  But beyond these core features there is considerable variation.

PushGP is a genetic programming system that evolves programs in the Push programming language. PushGP has been used for a variety of applications, ranging from intelligent agent design to automatic quantum computer programming. Features include:

Other Push-based evolutionary computation systems have been developed, including several that implement autoconstructive evolution. In an autoconstructive evolution system the evolving programs manipulate code to construct their own children. Through this they construct their children's reproduction/diversification mechanisms, and thereby the evolutionary process itself. This contrasts with standard genetic programming systems (like PushGP) in which hand-written genetic operators are used to produce children from parents. Many features of the Push programming language were developed specifically to support autoconstructive evolution, although they are often useful even in the context of more standard genetic programming systems.


Documentation


Code

Push3 and subsequent variants:

Push2:

Push1:


Related Work


Acknowledgments

This material is based upon work supported by the National Science Foundation under Grants No. 0308540, 0216344, 1017817, 1129139, and 1331283. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.

This project was also supported by the Defense Advanced Research Project Agency (DARPA) and the Air Force Research Laboratory (AFRL) through funding for the project "Multi-type, Self-adaptive Genetic Programming for Complex Applications.