Evolutionary Computing with Push

Project Documentation and Code

Lee Spector (lspector@hampshire.edu)
School of Cognitive Science
Hampshire College



Push is a programming language designed for evolutionary computation, to be used as the programming language within which evolving programs are expressed.

Push has been developed continuously over many years, and several distinct versions have been implemented. These all share core concepts of the Push language, including 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 syntactically valid random Push programs, and to develop genetic operators that transform Push programs into new Push programs.

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:

A variety of  Push-based evolutionary computation sytems other than PushGP have been developed, including several (e.g. Pushpop, SwarmEvolve 2.0, AutoPush) that implement autoconstructive evolution. In an autoconstructive evolution system the evolving programs construct their own children (and thereby their children's reproduction/diversification mechanisms and the evolutionary process itself). This contrasts with standard genetic programming systems (like PushGP) in which hand-written mutation and crossover operators are used. 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.

The 2002 article in the journal Genetic Programming and Evolvable Machines provides an introduction to the general principles and philosophy of the Push project, although that article was based on Push1 and one should therefore subsequently read the GECCO-2005 paper that introduces significant new features of Push3, many of which (most notably, the "exec" stack) have been maintained through subsequent versions of the language. While attempts have been made from time to time to provide stable documentation or discussion fora for the Push ecosystem (e.g., the Push email list, the Push project blog, and some of the documentation on the Hampshire College Computational Intelligence Lab site, but none of this is very active or current), the best way to track the status of the project (or at least the related work being done in the Hampshire College Computational Intelligence Lab) is currently via Lee Spector's publications (search for "push") and the README file and commit comments in the source code repository for the most actively developed current version of the language (Clojush, which is implemented in Clojure).

Versions of Push written in Clojure, Common Lisp, C++, JavaScript, Java, Scheme, Python, Swift, and Ruby are available (see below). Note, however, that Push is the subject of continuous research and development, and that  implementations vary in many ways.


Software and Documentation

Push3 and subsequent variants:

Push2:

Push1 (Lisp implementation of Push and PushGP):

Related projects/work:


Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant No. 1017817. 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 has also been 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," and by the National Science Foundation through funding for the project "Acquisition of Instrumentation for Research in Genetic Programming, Quantum Computation, and Distributed Systems" (NSF Major Research Instrumentation program and Research in Undergraduate Institutions program). It has also been supported by a National Science Foundation Director's Award for Distinguished Teaching Scholars.