Transcript of A Quick Introduction to the Push Programming Language
by Lee Spector
This is a quick introduction to the Push programming language.
I am Lee Spector, professor of computer science at Hampshire College and the University of Massachusetts, in Amherst, Massachusetts.
Push is a programming language for programs that evolve. It was developed for genetic programming systems, which produce programs automatically through random variation and selection. It may also be useful in other kinds of automatic programming systems. It is NOT intended to be a language in which human programmers write programs manually.
Push has unusually simple syntax, which makes it particularly easy to randomly generate and vary valid programs. It nonetheless supports rich data and control structures, which in most other languages involve syntax restrictions.
Push achieves this combination of features by providing typed data stacks, from which all instructions take their inputs, and to which all instructions push their outputs. In most languages, data flows are specified by the adjacency of instructions to their inputs, and sometimes by the use of specialized syntax like brackets. This is unnecessary in Push, because all instructions take their inputs from stacks, and push their outputs to stacks. Because there are stacks for each data type, the instructions, which are written to access stacks of the appropriate types, always receive appropriate inputs, regardless of their placement in programs. Push programs consist of instructions and literals such as numbers, along with parentheses that serve only to group code. Any parenthesized sequence of instructions, literals, and parentheses is a valid Push program as long as its parentheses are balanced.
We use the name PushGP for any genetic programming system that evolves Push programs. Several versions of PushGP have been developed, differing in the specific genetic programming techniques that they have used.
Push and PushGP systems have been developed in a variety of host languages, and some of these are publicly available. That said, the core concepts of Push are simple enough that competent programmers should be able to build their own Push system, relatively quickly. A simple Push interpreter with a useful set of instructions can be written in a few hundred lines of code in any reasonable high-level language. If you are developing an automatic programming system and you want to use Push, you may just want to write your own Push interpreter, in the host language of your choice, possibly the one in which you are developing your automatic programming system.
We say that Push is expressive, relative to many of the other program representations that are used for genetic programming, because it allows for the use of multiple data types, arbitrary control structures, including novel forms of conditional execution, iteration, and recursion, and the completion of multiple tasks, through the production of multiple outputs from multiple inputs, by a single program.
Push programs can even, optionally, express methods for their own reproduction and variation within a genetic programming system. The basic idea is that a Push program can produce, among its other outputs, other Push programs that can be used as offspring in a genetic programming system. Work on this idea has been conducted under the name Autoconstructive Evolution.
Push programs also combine this expressiveness with flexibility and resilience, in the sense that many modifications of Push programs, such as added, deleted, or reordered instructions, will often have no impact on what the programs do. This supports neutral variation, which may facilitate evolutionary search.
Here we see a representation of a Push interpreter, which can also be thought of as a Push virtual machine, in the midst of a computation. There is a stack for each data type, and several items on each of the shown stacks. The exec stack contains code, and is central to the operation of the interpreter. Here we see several instructions and program fragments on the exec stack, and integer, boolean, and string values on the integer, boolean, and string stacks. The person who implements the interpreter can create additional stacks for additional types. Dynamic creation of new stacks, as programs run, has been explored but is not part of the basic Push interpreter concept.
Now lets look at how Push programs are executed.
To execute a Push program it is first pushed onto the exec stack and then, while the exec stack isn’t empty and a pre-defined step limit hasn’t yet been reached, the top item is popped and processed.
If that popped item is an instruction, then it is executed by popping the inputs that it requires, performing the instruction, and pushing any outputs onto the stacks of the appropriate types. If the stacks don’t contain all of the needed inputs, then the instruction has no effect at all.
If the popped item is a literal, such as a number or a string of characters, then it is pushed onto the appropriate stack.
Finally, if the popped item is a parenthesized list of items, which we also call a code block, then each of the items that it contains is pushed individually back onto the exec stack, last first, so that the first item ends up on top.
Here’s how this works with the example Push interpreter state that we saw previously. First the integer_mult instruction is popped and processed, which causes the top two integers to be popped and multiplied, and their result to be pushed back onto the integer stack.
Next, boolean_and is processed, causing the top two boolean values to be popped and the result of and-ing them with each other to be pushed. True and false is false.
Next we have a list, which is a code block, which is unwrapped and its contents are pushed individually back on the exec stack.
Then the literal 3 is pushed onto the integer stack.
Then string_dup pops and then pushes two copies of the string on top of the string stack.
Then integer_add pops the top two integers and pushes their sum.
And then the exec stack is empty so execution stops, and the results of the program that was executed can be taken from the resulting data stacks. Often we take the top items of stacks indicated by the specification of the problem we are trying to solve, but in principle one could take any or all of the items remaining on stacks as execution results.
Previously we started in the middle of a program execution, with all of the stacks already populated with data. When we want to execute a full program in an initially empty interpreter, we start by pushing it onto the exec stack and then proceed as we did before. In this case we will find that 1 plus 2 is 3.
Here we’ll see a few examples of programs and their results without the visual display of the interpreter, starting again with the addition of 1 and 2.
And here is a boolean computation using or and not, which leaves false on the boolean stack.
Here we see an integer less than or equal comparison instruction, which pops two integers and pushes a boolean value indicating whether the deeper one, which comes first in this program, is less than or equal to the shallower one, which it is in this case, so the value left on the boolean stack is true.
Here we see how that boolean value can be used to cause the execution of one or another block of code, using an exec_if instruction. When exec_if is executed, the two following code blocks will be beneath it on the exec stack. Depending on the value on top of the boolean stack, one or the other will be removed, and the remaining one will be left to be executed as the normal program execution process continues.
Which in this case leaves “yes” on the string stack and 1 on the integer stack.
We generally provide a standard set of stack manipulation instructions for every type, for example to duplicate the top item on the stack, to test the top two items for equality, to push the current depth of the stack onto the integer stack, and so forth. Details of these instructions can be found in Push-related publications and interpreter source code.
Here we see some examples of integer instructions, for arithmetic, comparisons, conversion from strings, and random number generation.
And here are some example boolean functions.
And some example string instructions.
Exec instructions implement control structures such as conditionals and loops. Here are just a few examples of exec instructions in existing Push implementations.
A few other features of Push are relevant when using Push for evolving programs. I will run through most of these quickly, expanding briefly only on the final two.
Input instructions are often provided that allow a program to push copies of program inputs on demand.
Similarly, print instructions are often provided to send output to a write-only stack that functions like a console or file.
Some implementations include instructions that create associations between names or tags and data items, allowing for non-stack data storage.
A scheme for creating local environments, similar to those created by function definitions in other programming languages, has been developed and implemented in some Push implementations. Within these environments, non-local effects can only be produced by using explicit return instructions. This scheme involves the addition of stacks for environments and for values to be returned from those environments.
Every Push implementation must allow users to specify certain limits, for example on the number of steps to be executed. When the step limit is exceeded, execution terminates and the reason for termination is recorded in the interpreter state, so that the person or system that initiated execution can take appropriate action. Some implementations may also support limits on wall-clock time, on stack depths, or on data item sizes, and they may provide options for how those limits are handled.
Push programs can be nested, using parentheses, but it can be useful to generate and vary them in a flat, linear form, which we call genomes. I’ll say more about this in a moment.
Finally, Push’s flexible syntax facilitates unusually straightforward forms of automatic program simplification. I’ll say more about this in a moment as well.
It can be useful in some cases to generate and vary linear representations of Push programs, without nesting, and to convert them into regular, nested Push programs only in order to run them. We call these linear representations genomes, because of the way that they are intended to be used in genetic programming systems.
One reason to work with linear representations of programs is that it facilitates uniform variation, which may make it easier to explore the space of programs.
By uniform variation we mean that all genetic material that a child inherits is approximately equally likely to be varied, and also that all parts of both parents are approximately equally likely to appear in children, and to appear in a range of combinations. These features are facilitated by the use of linear genome representations, and they may help evolution and other methods to search the space of programs.
Another reason to use linear genomes is that, by doing so, we can make it more like likely that there will be structure where it matters, ensuring, for example that there are code blocks in the bodies of loops and after conditional branches. We can do this by adding the parentheses during translation from genomes to Push programs.
What we do is to specify, for each instruction, whether it should be followed by code blocks, and if so how many. During translation we open those blocks, which are implicitly specified by the positions of those instructions, by inserting opening parentheses.
Two methods have been developed for specifying where code blocks end. In one, we annotate instructions and literals with epigenetic markers, that specify how many blocks should be closed at each location. In the other method, close symbols are included in genomes. These are replaced by closing parentheses when genomes are translated to Push programs. In either case, specifications for unmatched closing parentheses are ignored, and closing parentheses are added at the end if necessary to close any open blocks.
Finally, I will briefly describe one form of automatic program simplification that is straightforward to implement for Push programs.
This is a random hill-climbing process in which we repeatedly perform two steps.
The first step is to make the program simpler by removing one or more program elements, which might be instructions or literals or pairs of parentheses.
The second step is to test the simpler program, and to keep it if it is just as good as the original program, or to revert the simplifications if they damaged the program’s performance.
Even though this process is random, tests show that in often reduces the size of evolved programs dramatically, and that it does so reasonably reliably.
Other tests have shown that the simplified programs are in some cases more general than the original, unsimplified programs, in the sense that they are more likely to work correctly for inputs that were not used for testing during program evolution. The loss of generalization from simplification appears to happen less frequently.
This method can be applied either to Push programs themselves or to linear genomes for Push programs.
Here’s just one example showing what we often see from this form of automatic simplification. The evolved program, for a benchmark software synthesis problem called Replace Space with Newline, has size 231, which counts instructions, literals, and pairs of parentheses. The automatic simplification process produced an equivalent program of size 11.
The Push programming language supports the evolution of expressive programs that may use arbitrary data types and control structures, possibly to perform multiple tasks.
The core concepts of the language are nonetheless relatively straightforward, which means that Push interpreters, and systems that evolve Push programs, are relatively easy to write in any high level host language.
More information is available at pushlanguage.org.