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:
Multiple data types without constraints on code generation or manipulation.
Arbitrary control structures without constraints on code generation or manipulation.
Arbitrary modularity without constraints on code generation or manipulation.
Automatic program simplification (in some implementations).
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.
The Push Language Discourse Site provides orientation and a forum for discussion of Push and its use in evolutionary computation.
Many Push-related publications can be found on Lee Spector's publications page, including the 2002 article in the journal Genetic Programming and Evolvable Machines which provides an introduction to the general principles and philosophy of the Push project. The GECCO-2005 paper introduced significant new features of Push3, many of which have been maintained through subsequent versions of the language. Additional extensions are described in subsequent publications.
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) also provide information about the current status of the project.
Older (in some cases obsolete) information is available in The Push 2.0 Programming Language Description, The Push 3.0 Programming Language Description, the archives of the inactive Push email list, the inactive Push project blog.
Push3 and subsequent variants:
Most actively supported software by the Hampshire CI Lab:
Clojush, an implementation of Push/PushGP in Clojure: http://github.com/lspector/Clojush
Other software (some independent of the Hampshire CI lab, listed roughly from most recent to least recent):
Pysh2, an implementation of Push in Python: https://github.com/erp12/Pysh2
Elixush, an implementation of Push in Elixir: https://github.com/benfb/elixush
Push in Clojure, an alternative implementation of Push in Clojure: https://github.com/Vaguery/push-in-clojure
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 provides integrated Push interpreters (based on the C++ Push implementation) and an integrated version of PushGP. See, for example, the "PushRegression" demo.
Push2:
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:
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
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.