First Push

Program Structure

PUSH 3 is a programming language created for use in genetic programming. Detailed description of it is available here. I will just briefly re-iterate the concepts crucial to further development of this blog.

Push has a very simple grammar:

program ::= instruction | literal | ( program* )

In other words:

• an instruction is a Push program
• a literal is a Push program
• a parenthesized sequence of zero or more Push programs is a Push program

I have picked FParsec library to parse this simple grammar, since I did not need to convert it any further and could simply code this “intuitive” description.

Here literals are simply constants. Push has types: BOOLEAN, FLOAT, and INTEGER types. I have also added a LITERAL type (a quoted string) for convenience.

Instructions are case sensitive and are of the form:

instruction ::= <type_name>.<operation>

E. g.: INTEGER.+, FLOAT.DUP, etc.

Stacks

Push is a stack based language. Literals of every type get their own stack and operations manipulate data on these stacks. For instance, INTEGER.+ will add two numbers on the integer stack.

Every operation, unless specified otherwise, removes its arguments from the stack and pushes the result on top of a stack.

For binary operations, the argument on top of the stack is treated as the right-hand argument.

Push interpreter evaluates the program recursively, using a special kind of stack called EXEC. This is not strictly necessary, it is just an implementation of recursion, managed by Push itself. To quote the Push 3.0 website, this is what program execution looks like:

To execute program P:
Push P onto the EXEC stack
  LOOP until the EXEC stack is empty:
     If the first item on the EXEC stack is a single instruction 
         then pop it and execute it.
     Else if the first item on the EXEC stack is a literal 
         then pop it and push it onto the appropriate stack.
     Else (the first item must be a list) pop it and push all of the
         items that it contains back onto the EXEC stack,
         in reverse order (so that the item that was first
         in the list ends up on top).




Robustness

Push is robust. Its programs always succeed if they are syntactically correct. If an operation does not find necessary arguments on the stack it leaves the state of execution as it was before the operation was invoked. Essentially it becomes a NOOP.

EXEC and CODE Stacks

CODE stack is used to push pieces of Push code for evaluation. EXEC stack is used to manage execution of a program. By default, the entire program is pushed to the CODE stack before the start of execution.

Examples

Here are some examples of Push programs:

a. (2 3 INTEGER.+)


Leaves “5” on top of integer stack.

b. ( 5 1.23 INTEGER.+ ( 4 ) INTEGER.- 5.67 FLOAT.* )

FLOAT STACK: ( 6.9741 )
INTEGER STACK: ( 1 )

Here is the order of execution:

1. 5 pushed to INTEGER stack
2. 1.23 pushed to FLOAT stack
3. INTEGER.+ – no effect on anything
4. 4 pushed to INTEGER stack
5. INTEGER.- – 4 and 5 yanked from INTEGER stack 5 – 4 = 1 pushed back (top of the stack is the right-hand argument)
6. 5.67 pushed to FLOAT
7. FLOAT.* 1.23 * 5.67 = 6.9741 pushed back to the FLOAT stack instead of the two yanked arguments.

More examples on the Push 3 site.