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:

• Multiple data types without constraints on code generation or manipulation.
• Arbitrary modularity without constraints on code generation or manipulation.
• Evolved module architecture with no extra machinery.
• Support for explicit, arbitrary recursion.
• Support for ontogenetic "development" of code as it runs, via code-manipulation instructions.
• Automatic program simplification (in some implementations).
• Support for the evolution of tag-based modularity (in some implementations).
  

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:

• The Push 3.0 Programming Language Description.
• The GECCO paper introducing the major new features of Push3: http://hampshire.edu/lspector/pubs/push3-gecco2005.pdf.
• Most actively supported software by the Hampshire College Computational Intelligence Lab:
• Clojush, an implementation of Push/PushGP in Clojure: http://github.com/lspector/Clojush.
• Other software (some developed independently of the Hampshire College group):
• pushSwift, an implementation of Push/PushGP in Swift: https://github.com/Vaguery/pushSwift
• PyshGP, an implementation of Push in Python: https://github.com/erp12/PyshGP
  
• Rubypush, an implementation of Push in Ruby: http://github.com/jonklein/rubypush.
• Psh, a subset of Push3 implemented in Java: http://github.com/jonklein/Psh.
• Psh in Processing: a symbolic regression demo is at: http://hampshire.edu/lspector/psh/demo/regression/PshApplet. An arts-oriented visual demo is at http://hampshire.edu/lspector/PushBrush/.
• ScalushGP, an implementation of PushGP in Scala: https://github.com/lvilnis/ScalushGP.
  
• RushGP, an implementation of PushGP in Typed Racket: https://github.com/lvilnis/RushGP.
  
• Common Lisp Push3/PushGP implementation: http://hampshire.edu/lspector/push3.
• C++ Push3/PushGP implementation: http://sourceforge.net/projects/push-evolve/.
• PushScript, a subset of Push3 implemented in JavaScript: http://www.spiderland.org/PushScript/.
• Schush/SchushGP, a subset of Push3/PushGP implemented in Scheme: http://hampshire.edu/lspector/schush.ss.
• The BREVE simulation environment, which now provides integrated Push interpreters (based on the C++ Push implementation) and an integrated version of PushGP. This is probably the simplest way for new users to try PushGP; download BREVE and run the "PushRegression" demo.

Push2:

• The Push 2.0 Programming Language Description.
• Push2/PushGP Lisp implementation: http://hampshire.edu/lspector/push2.
• Push2/PushGP C++ implementation (BETA version): http://helios.hampshire.edu/~jkCS/push2_beta.tar.gz.
• Push2 plug-in for the BREVE simulation environment (BETA version): http://www.spiderland.org/breve/breve_pushPlugin_beta.tar.gz. This currently works only with the latest BETA release of BREVE, available from: http://www.spiderland.org/breve/breve_beta_1.8
• Push2 test suites (see The Push 2.0 Programming Language Description and implementation documents for notes on how to use these): http://hampshire.edu/lspector/push2/tests

Push1 (Lisp implementation of Push and PushGP):

• README
• load
• random.cl
• push.lisp
• pushgp.lisp

Related projects/work:

• Maarten Keijzer's Push-forth: a light-weight, strongly-typed, stack-based genetic programming language (paper).
• Bill Tozier's Nudge (a little Push): http://www.ohloh.net/p/Vaguerys_Nudge
• Krzysztof Krawiec has conducted genetic programming studies using Push, e.g. this paper.
  
• PushGP for Automatic Quantum Computer Programming: PushGP has been used in conjunction with the QGAME quantum computer simulator to evolve novel programs for quantum computers. More information, including code, is available from the web page that accompanies the book, Automatic Quantum Computer Programming: A Genetic Programming Approach.
• Pushpop: pushpop-alife8.tar.gz This is the code used to generate data for: Spector, L. 2002. Adaptive populations of endogenously diversifying Pushpop organisms are reliably diverse. In R. K. Standish, M. A. Bedau, and H. A. Abbass (eds.), Proceedings of Artificial Life VIII, the 8th International Conference on the Simulation and Synthesis of Living Systems, pp. 142-145. Cambridge, MA: The MIT Press. (pdf 488KB)  NOTE: This is sparsely documented and contains many "experimental" features that were not actually used in collecting data or described in the paper -- most of these were turned off via parameters in pushpop.lisp. This code is being posted "as is" to document the results in the paper cited above. Note also that this package uses a now-obsolete version of the Push1 interpreter.
• SwarmEvolve 2.0: See source code, documentation, and movies posted at http://hampshire.edu/lspector/gecco2003-collective.html
• Russ Abbott's Java-based Push Genetic Programming

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.