Lee Spector, Chris Perry, and Jon
School of Cognitive Science
November, 2003 - April, 2004 (see document version history)
This document is under collaborative construction. Send comments/updates to firstname.lastname@example.org.
Random Code Generation
Push2 vs. Push1
Document Version History
Push is a programming language intended primarily for use in evolutionary computation systems (such as genetic programming systems), as the language in which evolving programs are expressed. Push has an unusually simple syntax, which facilitates the development (or evolution) of mutation and recombination operators that generate and manipulate programs. Despite this simple syntax, Push provides more expressive power than most other program representations that are used for program evolution. Push programs can process multiple data types (without the syntax restrictions that usually accompany this capability), and they can express and make use of arbitrary control structures (e.g. recursive subroutines and macros) through the explicit manipulation of their own code (via a "CODE" data type). This allows Push to support the automatic evolution of modular program architectures in a particularly simple way, even when it Push is employed in an otherwise ordinary genetic programming system (such as PushGP, which is a "generic" GP system except that it evolves Push programs rather than Lisp-style program trees). Push can also support entirely new evolutionary computation paradigms such as "autoconstructive evolution," in which genetic operators and other components of the evolutionary system themselves evolve (as in the Pushpop and SwarmEvolve2 systems).
This document describes version 2.0 of the Push programming language (a.k.a "Push2"), which shares general features with the first version of Push (a.k.a "Push1") although several details have changed. Although it is based on Push1, the best introduction to the basic principles of Push and its use for evolutionary computation is still:
Spector, L., and A. Robinson. 2002. Genetic Programming and Autoconstructive Evolution with the Push Programming Language. In Genetic Programming and Evolvable Machines, Vol. 3, No. 1, pp. 7-40. (pdf 216KB)
The present document is a self-contained specification for Push2 that also describes differences between Push1 and Push2. That is, one should be able to use or re-implement Push2 using this document alone, but one should read the article cited above (and/or additional references listed below) to find out why one might want to use Push in the first place.
Publications on Push and Push-related projects are listed at http://hampshire.edu/lspector/push.html, as are freely available Push implementations. Other implementations may be known or under development; contact the Push mailing list with queries. The Push mailing list can be accessed via http://lists.hampshire.edu/mailman/listinfo/push.
Push achieves its combination of syntactic simplicity and semantic power through the use of a stack-based execution architecture that includes a stack for each data type. A CODE data type, with its own stack and an associated set of code-manipulation instructions, provides many of the more interesting features of the language. Push instructions, like instructions in all stack-based languages, take any arguments that they require and leave any results that they produce on data stacks. To provide for "stack safe" execution of arbitrary code Push adopts the convention, used widely in stack-based genetic programming, that instructions requiring arguments that are not available (because the relevant stacks are empty) become NOOPs; that is, they do nothing. Because Push's stacks are typed, instructions will always receive arguments and produce results of the appropriate types (if they do anything at all), regardless of the contexts in which they occur.
The syntax of Push is simply this:
program ::= instruction | literal | ( program* )
In other words:
Some implementations may require spaces around parentheses. (Our current C++ implementation does; our current Lisp implementation does not.) Parenthesized sequences are also referred to as "lists" in some of the documentation, and Push programs can in fact be treated as list data structures. Literals are constants such as "3" (an integer constant) and "3.14" (a floating point number constant) and "TRUE" (a Boolean constant). Instruction names are not case sensitive and they can include the "." character. Instruction names generally start with the name of the type that they primarily manipulate, followed by a "."; for example, INTEGER.+ is the instruction for adding two integers, and BOOLEAN.DUP is the instruction for duplicating the value on the top of the Boolean stack. In some cases, such as type-conversion instructions, it is not obvious to which type the instruction "belongs"; in these cases the instruction prefix is usually taken from the type with which the instruction is defined.
Execution of a push program involves the recursive application of the following procedure:
To execute program P: If P is a single instruction then execute it. Else if P is a literal then push it onto the appropriate stack. Else sequentially execute each of the Push programs in P.
A top-level call to the interpreter can be provided with a list of literals to be pushed onto the appropriate stacks before the program is executed. In addition, the program passed to the top-level call will itself pushed onto the CODE stack before execution; this convention simplifies the expression of some recursive programs (see below for an example).
The CODE.QUOTE instruction is an exception to the execution procedure given above. Execution of CODE.QUOTE has no immediate effect, aside from changing the state of the interpreter such that the subsequent piece of code considered for execution will not in fact be executed --- it will instead be pushed onto the CODE stack. This provides a way to get additional code onto the CODE stack, where it may be manipulated and/or executed by later instructions.
The standard NAME data type provides for symbolic variable names and associated binding spaces via GET and SET instructions. Any identifiers that do not represent known Push instructions or literals of other type (e.g. TRUE and FALSE) are recognized as NAMEs, and are pushed onto the NAME stack when executed. Note that CODE, like any other type, has a binding space; this means that NAMEs can be used to name subroutines (or pieces of code for any other purpose) in the same way that they can be used to implement variables of other types.
A Push interpreter contains a random code generator that can be used to produce random programs or program fragments. This can be called from outside the interpreter (e.g. to create or mutate programs in a genetic programming system) or from a standard CODE.RAND instruction (which is analogous to RAND instructions available for other types). An "ephemeral random constant" mechanism allows randomly-generated code to include newly-generated literals of various types.
Execution safety is an essential feature of Push, in the sense that any syntactically correct program should execute without crashing or signaling an interrupt to the calling program. This is because Push is intended for use in evolutionary computing systems, which often require that bizarre programs (for example those that result from random mutations) be interpreted without interrupting the evolutionary process. The "stack safety" convention described above (that is, the convention that any instruction that finds insufficient arguments on the stacks acts as a NOOP) is one component of this feature. In addition, all instructions are written in ways that are internally safe; they have well defined behavior for all predictable inputs, and they typically NOOP in predictable "exceptional" situations (like division by zero). Additional safety concerns derive from the availability of explicit code manipulation and recursive execution instructions, which can in some cases produce exponential code growth or non-terminating programs. In response to these concerns a Push interpreter must enforce two limits:
The convention regarding the order of arguments for instructions that are normally rendered as infix operators is that the argument on the top of the stack is treated as the right-hand argument and the argument second-from the top is treated as the left-hand argument. This means that the linear representation of an expression containing one of these instructions looks like the normal infix expression, except that the instruction is moved to the end. For example, we divide 3.14 by 1.23 using "( 3.14 1.23 FLOAT.%)" and we subtract 2 from 23 using "( 23 2 -)".
While Push's stacks are generally treated as genuine stacks---that is, instructions take their arguments from the tops of the stacks and push their results onto the tops of the stacks---a few instructions (like YANK and SHOVE) do allow direct access to "deep" stack elements by means of integer indices. To this extent the stacks can be used as general, random access memory structures. This is one of the features that ensures the Turing-completeness of Push (another being the arbitrary name/value bindings supported by the NAME data type and SET/GET methods; see below).
This section contains just a few simple examples, to give the reader a feel for the language. For more examples, including test suites, see the files at http://hampshire.edu/lspector/push.html.
First, some simple arithmetic:
( 5 1.23 INTEGER.+ ( 4 ) INTEGER.- 5.67 FLOAT.* )
Execution of this code leaves the relevant stacks in the following states:
FLOAT STACK: (6.9741) CODE STACK: ( ( 5 1.23 INTEGER.+ ( 4 ) INTEGER.- 5.67 FLOAT.* ) ) INTEGER STACK: (1)
A few points to note about this example:
Here is a tiny program that adds an integer pre-loaded onto the stack to itself:
( INTEGER.DUP INTEGER.+ )
When run with 5 pre-loaded onto the INTEGER stack, for example, this leaves 10 on top of the stack. The following does the same thing in a slightly more complicated way, pushing code onto the CODE stack and then executing it:
( CODE.QUOTE ( INTEGER.DUP INTEGER.+ ) CODE.DO )
The following more complicated example computes the factorial of an integer pre-loaded onto the INTEGER stack. This example makes use of the fact that top-level calls to the interpreter push the executed code onto the CODE stack before execution:
( CODE.QUOTE ( INTEGER.POP 1 ) CODE.QUOTE ( CODE.DUP INTEGER.DUP 1 INTEGER.- CODE.DO INTEGER.* ) INTEGER.DUP 2 INTEGER.< CODE.IF )
This works by first pushing two pieces of code (for the base case and recursive case of the recursive factorial algorithm, respectively) onto the CODE stack; these are pushed on top of the code for the full program, which is pre-loaded onto the CODE stack by the top-level call to the interpreter. The subsequent code compares the provided integer with 2 and, depending on the result of this, executes one of the pushed pieces of code (and discards the other; see the documentation for CODE.IF in the Type/Instruction Catalog below for details). In the base case this will produce an answer of 1, while in the recursive case it will recursively compute the factorial of one less than the provided number, and multiply that result by the provided number. When called with 5 pre-loaded on the INTEGER stack this leaves the relevant stacks in the following states:
CODE STACK: (( CODE.QUOTE ( INTEGER.POP 1 ) CODE.QUOTE ( CODE.DUP INTEGER.DUP 1 INTEGER.- CODE.DO INTEGER.* ) INTEGER.DUP 2 INTEGER.< CODE.IF )) BOOLEAN STACK: ( ) INTEGER STACK: (120)
A Push2 interpreter can be configured (using an implementation-specific mechanism) according to the specification in a plain text configuration file. In the configuration file any line beginning with "#" is a comment and is ignored. Actual configuration lines come in four forms:
A parameter-setting line lists an implemented parameter (see below) and a value for that parameter. A type lines consists of the word "type" followed by the name of an implemented type, and it has the effect of making the named type available in the interpreter; that is, it "turns on" the type. An instruction line consists of the word "instruction" followed by the name of an instruction, and it has the effect of making the named instruction available in the interpreter; that is, it "turns on" the instruction. A constant line consists of the word "constant" followed by a type name and a constant name. The processing of a constant line creates a new instruction (with the given constant name) which, when executed, will push a value on the named stack. The new instruction is also automatically "turned on" in the interpreter, and can appear in randomly generated code. The value that the new instruction will push is set by the interpreter's "client" (see Implementation Notes), via the SETCONSTANT call. If no external call to SETCONSTANT has been made for a declared constant then execution of the constant instruction pushes the default value for the given type.
Ideally an implemention should warn the user if the configuration "turns on" instructions that access stacks of "turned off" types, or if there are other apparent inconsistencies in the configuration. But it is not necessary that implementations do this, and there is no standardized set of inconsistencies that must be reported.
The following is a fragment of a valid configuration file (generated by the current Lisp Push2 implementation, except that the "constant" lines have been added by hand):
## PARAMETER SETTINGS MAX-RANDOM-FLOAT 1.0 MIN-RANDOM-FLOAT -1.0 MAX-RANDOM-INTEGER 10 MIN-RANDOM-INTEGER -10 EVALPUSH-LIMIT 1000 NEW-ERC-NAME-PROBABILITY 0.001 MAX-POINTS-IN-RANDOM-EXPRESSIONS 25 MAX-POINTS-IN-PROGRAM 100 ## TYPES type FLOAT type NAME type CODE type BOOLEAN type INTEGER ## INSTRUCTIONS instruction INTEGER.FROMBOOLEAN instruction INTEGER.FROMFLOAT instruction INTEGER.> instruction INTEGER.<
## CONSTANT INSTRUCTIONS constant INTEGER INPUT1 constant FLOAT INPUT2
Every Push2 implementation should provide a way to generate a complete configuration file, containing type and instruction lines for all implemented types and instructions. A reasonable way to configure a Push2 interpreter is to start with such a complete configuration file and to comment out lines to turn off types and instructions. Note, however, that many instructions may depend on multiple types; for example, many code-manipulation and stack-manipulation instructions use integer indices and therefore require the INTEGER type, many comparison instructions require the BOOLEAN type for depositing their results, and all SET and GET instructions require the NAME type. Ideally, implementations should provide warnings when such dependencies are not satisfied by an implementation, but they need not do so; the person specifying the configuration should be sufficiently familiar with the instruction set to ensure that necessary types are "turned on."
The following are the parameters that are currently supported in configuration files:
Additional parameters will probably be added (and suggestions are welcome). Items that have not yet been standardized but probably ought to be include random number seeds and limits to prevent overflow/underflow.
Several algorithms for the generation of random code have been described in the genetic programming literature. Code generation is less complicated for Push programs than it is for Lisp-style code trees, since in Push one doesn't have to worry about function "arity" or about function vs. argument positions when generating code. So it is easier, for example, to generate programs with predictable size and shape distributions.
The following is the standard Push random code generation algorithm, which is used for the CODE.RAND instruction. It may also be useful for the initialization of programs in evolutionary computation systems, and it is used for this purpose in PushGP. It produces a uniform distribution of sizes and what seems to be a reasonable distribution of shapes, in a reasonable amount of time.
Function RANDOM-CODE (input: MAX-POINTS) Set ACTUAL-POINTS to a number between 1 and MAX-POINTS, chosen randomly with a uniform distribution. Return the result of RANDOM-CODE-WITH-SIZE called with input ACTUAL-POINTS. End Function RANDOM-CODE-WITH-SIZE (input: POINTS) If POINTS is 1 then choose a random element of the instruction set. If this is an ephemeral random constant then return a randomly-chosen value of the appropriate type; otherwise return the chosen element. Otherwise set SIZES-THIS-LEVEL to the result of DECOMPOSE called with both inputs (POINTS - 1). Return a list containing the results, in random order, of RANDOM-CODE-WITH-SIZE called with all inputs in SIZES-THIS-LEVEL. End Function DECOMPOSE (inputs: NUMBER, MAX-PARTS) If NUMBER is 1 or MAX-PARTS is 1 then return a list containing NUMBER Otherwise set THIS-PART to be a random number between 1 and (NUMBER - 1). Return a list containing THIS-PART and all of the items in the result of DECOMPOSE with inputs (NUMBER - THIS-PART) and (MAX-PARTS - 1) End
This section describes a few of the common features of our current implementations and their interfaces. They can also be interpreted as suggestions for anyone building their own Push2 implementations. These are not features of the Push2 language per se, but they help one to use our current implementations and to ensure that two implementations are consistent with one another. Implementation-SPECIFIC installation and usage notes should accompany each implementation.
Test suite scheme: A more-or-less standardized "test suite" scheme is intended to help ensure that a Push2 implementation behaves like other implementations. The scheme is to process three files (a configuration file, a file containing a list of literals for initializing the stacks, and a file containing a program) and to produce an output file that contains a list of literals which, if read back in to the interpreter (that is, if "executed" as a program), would re-create the stacks as they were at the end of the computation. The values in the output file are listed type by type, following the order in which types are declared in the configuration file. Each implementation should also provide some mechanism for comparing its output files with those of other implementations (for example by reading the files and comparing stack states, or by comparing the files in a way that disregards insignificant white space).
Templates: It often makes sense to create slightly different versions of the same basic instruction for multiple types. For example, many of the standard stack-manipulation instructions (e.g. DUP, POP, etc.) make sense for all types (and depending on the way that the interpreter is written it may be possible to use identical method implementations for all of them). In Push1 an instruction overloading mechanism, using a TYPE type in the language itself, allowed one to exploit these commonalities (and also affected the semantics of the language in complex ways). In Push2 the TYPE type was dropped and all instruction names refer to single methods; instruction names often include type names but this is just a convention. To recapture the software engineering benefits of the overloading mechanism (e.g. code reuse) an implementation should provide a template mechanism for type and instruction definitions.
Libraries: The configuration mechanism in Push2 is intended to simplify the integration of new types/instructions into an interpreter. Any implementation of the language should provide a clear API for including libraries of types/instructions and for building/loading configuration files (which set parameters and turn on/off available types/instructions).
Client-provided instructions with call-backs: Push interpreters are generally imbedded within "client" programs that invoke interpreters on various inputs and do various things with the outputs. The integration of the interpreter into the client environment should be as tight as possible. Minimally, the client should be able to process a configuration file, call SETCONSTANT to provide values for constant instructions defined in configuration files, push/pop onto/from stacks, and invoke the interpreter. Ideally, the client should also be able to install new instructions that interact both with the client's environment and the interpreter state. For example, we use our C++ interpreter as a plug-in to the BREVE simulation environment (http://www.spiderland.org/breve), and we provide a way in which the BREVE user can write instructions in BREVE's scripting language (which may, among other things, manipulate the interpreter's stacks) and add them to an embedded interpreter.
Push2 differs from Push1 mainly in the following ways:
Changes to the language per se:
Refinements to our implementations and their interfaces:
Rejected alternative names for Push2:
Following are a couple of items that are currently under discussion for possible inclusion in future versions of Push:
The following are descriptions of "standard" types and instructions, in the sense that any Push2 implementation that provides these types/instructions should implement them in ways that conform to these descriptions. However, some implementations may not implement all of these types or instructions, and some implementations may implement more; use your implementation's configuration mechanism (described briefly above) to configure your implementation appropriately.
Unless otherwise noted all instructions POP all arguments that they consult. For example, the description of INTEGER.= states that it "Pushes TRUE onto the BOOLEAN stack if the top two INTEGERs are equal, or FALSE otherwise." I this case two items (the two that are compared) are popped from the INTEGER stack by the INTEGER.= instruction. In addition, unless otherwise noted all results are pushed after the arguments are popped. So for example BOOLEAN.= pushes the result of the comparison onto the BOOLEAN stack after popping the two values to be compared from the BOOLEAN stack. If any needed argument is not available then the instruction acts as a NOOP; that is, it does nothing, and leaves all stacks in the states that they were in prior to the call.
Indexing into stacks, e.g. for SHOVE, YANK, and YANKDUP instructions, is zero-based; that is, the top of the stack has index 0. Negative indices into stacks are interpreted as 0 (the stack top), and indices that exceed the stack depth are interpreted as the highest meaningful value (e.g. the stack bottom for YANK, or one beyond the stack bottom for SHOVE).
|Description||For use in comparisons, logic, etc. Literals are TRUE and FALSE. Required for use of various comparison operators (e.g. INTEGER.=) and CODE.IF.|
|Description||For explicit code manipulation and execution. May also be used as a general list data type. This type must always be present, as the top level interpreter will push any code to be executed on the CODE stack prior to execution. However, one may turn off all CODE instructions if code manipulation is not needed.|
|Description||Floating-point numbers (that is, numbers with decimal points).|
|Description||Integer numbers (that is, numbers without decimal points).|
|Description||For creating bindings between symbolic identifiers and values of various types; that is, for implementing (global) variables. There is an independent binding space for each type, accessed with the type-specific SET and GET instructions. Any identifier that is not a known Push instruction or a known literal of any other type becomes a NAME literal (and is pushed onto the NAME stack when encountered).|
This work was supported by an NSF Director's Award for Distinguished Teaching Scholars, by NSF grant EIA-0216344, and by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory, Air Force Materiel Command, USAF, under agreement number F30502-00-2-0611.
The first version of this document was created in November, 2003.
YYYYMMDD 20031229: - Created this version history. - Addition re: use of names for code variables. - Additions related to instruction constants. - Addition of RANDOM-SEED parameter. 20040109: - Tweaked descriptions of *.GET instructions (thanks Maarten Keijzer) 20040112: - Added Random Code Generation section. - Changed specified behavior of division/modulus by zero to be NOOP rather than pushing zero. (& related text changes). - Change specified behavior of *.GET with unbound NAME to be NOOP. - Added "Under Discussion" section. 20040113: - More rejected names for Push2. 20040412: - Added CODE.FROMBOOLEAN, CODE.FROMINTEGER, CODE.FROMFLOAT CODE.FROMNAME, CODE.DO*COUNT, CODE.DO*TIMES.