Table of Contents for Programming Languages: a survey

Languages for automated programming

The Push3 genetic programming target language

PUSH3 is a stack language. Its instruction set is divided by stack. The stacks are are BOOLEAN, CODE, EXEC, FLOAT, INTEGER, NAME.

The following is quoted or paraphrased from http://faculty.hampshire.edu/lspector/push3-description.html

Note about the EXEC stack: "Code queued for execution. The EXEC stack maintains the execution state of the Push interpreter. Instructions that specifically manipulate the EXEC stack can be used to implement various kinds of control structures. The CODE stack can also be used in this way, but manipulations to the EXEC stack are "live" in the sense that they are manipulating the actual execution state of the interpreter, not just code that might later be executed."

Note about the NAME stack: "For creating bindings between symbolic identifiers and values of various types; that is, for implementing (global) variables and defined instructions. Bindings are created with DEFINE instructions. Any identifier that is not a known Push instruction or a known literal of any other type is considered a NAME and will be pushed onto the NAME stack when encountered, unless it has a definition (in which case its associated value will be pushed on the EXEC stack when it is encountered. The NAME.QUOTE instruction can be used to get a name that already has a definition onto the NAME stack."

Note about the CODE stack: "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."

Instructions common to all stacks:

• =: push TRUE if the top two items on tis stack are equal
• DUP
• FLUSH: empties the stack
• POP
• ROT
• SHOVE: inserts the top element of the stack "deep" in the stack, at the position indexed by the top INTEGER (for the INTEGER stack, the top element is the index and the next element is the one to be inserted)
• STACKDEPTH: Pushes the depth of this stack onto the INTEGER stack
• SWAP
• YANK: Removes an indexed item from "deep" in the stack and pushes it on top of the stack. The index is taken from the INTEGER stack.
• YANKDUP: Pushes a copy of an indexed item "deep" in the stack onto the top of the stack, without removing the deep item. The index is taken from the INTEGER stack.

Instructions common to all stacks but NAME:

• DEFINE: Defines the name on top of the NAME stack as an instruction that will push the top item of the current stack onto the EXEC stack.

Instructions common to all stacks but EXEC:

• RAND: Pushes a random element of the type that goes in this stack.
  • For CODE more detail is needed: Pushes a newly-generated random program onto the CODE stack. The limit for the size of the expression is taken from the INTEGER stack; to ensure that it is in the appropriate range this is taken modulo the value of the MAX-POINTS-IN-RANDOM-EXPRESSIONS parameter and the absolute value of the result is used.
  • For FLOAT and INTEGER the random value will be between MIN-RANDOM-{FLOAT/INTEGER} and less than or equal to MAX-RANDOM-{FLOAT/INTEGER} (inclusive)

Instructions common to INTEGER and FLOAT (these are also the only operations available for the INTEGER stack):

• +, -, *, /, %, min, max
• comparison ops <, >
• FROMBOOLEAN
• each of INTEGER and FLOAT also has a conversion op from the other

Instructions only for FLOAT:

• SIN, COS, TAN

Instructions only for BOOLEAN:

• AND, OR, NOT
• FROMFLOAT, FROMINTEGER

Instructions only for NAME:

• QUOTE: Sets a flag indicating that the next name encountered will be pushed onto the NAME stack (and not have its associated value pushed onto the EXEC stack), regardless of whether or not it has a definition. Upon encountering such a name and pushing it onto the NAME stack the flag will be cleared (whether or not the pushed name had a definition). (actually, this is also available in EXEC)
• RANDBOUNDNAME: Pushes a randomly selected NAME that already has a definition.

Instructions for both EXEC and CODE (descriptions here given for the EXEC stack:

• DO*COUNT: An iteration instruction that performs a loop (the body of which is taken from the EXEC stack) the number of times indicated by the INTEGER argument, pushing an index (which runs from zero to one less than the number of iterations) onto the INTEGER stack prior to each execution of the loop body. This is similar to CODE.DO*COUNT except that it takes its code argument from the EXEC stack. This should be implemented as a macro that expands into a call to EXEC.DO*RANGE. EXEC.DO*COUNT takes a single INTEGER argument (the number of times that the loop will be executed) and a single EXEC argument (the body of the loop). If the provided INTEGER argument is negative or zero then this becomes a NOOP. Otherwise it expands into: ( 0 <1 - IntegerArg?> EXEC.DO*RANGE <ExecArg?> )
• DO*RANGE: An iteration instruction that executes the top item on the EXEC stack a number of times that depends on the top two integers, while also pushing the loop counter onto the INTEGER stack for possible access during the execution of the body of the loop. This is similar to CODE.DO*COUNT except that it takes its code argument from the EXEC stack. The top integer is the "destination index" and the second integer is the "current index." First the code and the integer arguments are saved locally and popped. Then the integers are compared. If the integers are equal then the current index is pushed onto the INTEGER stack and the code (which is the "body" of the loop) is pushed onto the EXEC stack for subsequent execution. If the integers are not equal then the current index will still be pushed onto the INTEGER stack but two items will be pushed onto the EXEC stack -- first a recursive call to EXEC.DO*RANGE (with the same code and destination index, but with a current index that has been either incremented or decremented by 1 to be closer to the destination index) and then the body code. Note that the range is inclusive of both endpoints; a call with integer arguments 3 and 5 will cause its body to be executed 3 times, with the loop counter having the values 3, 4, and 5. Note also that one can specify a loop that "counts down" by providing a destination index that is less than the specified current index.
• DO*TIMES: Like EXEC.DO*COUNT but does not push the loop counter. This should be implemented as a macro that expands into EXEC.DO*RANGE, similarly to the implementation of EXEC.DO*COUNT, except that a call to INTEGER.POP should be tacked on to the front of the loop body code in the call to EXEC.DO*RANGE. This call to INTEGER.POP will remove the loop counter, which will have been pushed by EXEC.DO*RANGE, prior to the execution of the loop body.
• IF: If the top item of the BOOLEAN stack is TRUE then this removes the second item on the EXEC stack, leaving the first item to be executed. If it is false then it removes the first item, leaving the second to be executed. This is similar to CODE.IF except that it operates on the EXEC stack. This acts as a NOOP unless there are at least two items on the EXEC stack and one item on the BOOLEAN stack.

Instructions only for EXEC:

• K: The Push implementation of the "K combinator". Removes the second item on the EXEC stack.
• S: The Push implementation of the "S combinator". Pops 3 items from the EXEC stack, which we will call A, B, and C (with A being the first one popped). Then pushes a list containing B and C back onto the EXEC stack, followed by another instance of C, followed by another instance of A.
• Y: The Push implementation of the "Y combinator". Inserts beneath the top item of the EXEC stack a new item of the form "( EXEC.Y <TopItem?> )".

Instructions only for CODE (you might think, why can't i execute these in EXEC? but note that ALL instrutions can be IN the EXEC stack; these are operations that execute ON the CODE stack):

• APPEND: Pushes the result of appending the top two pieces of code. If one of the pieces of code is a single instruction or literal (that is, something not surrounded by parentheses) then it is surrounded by parentheses first.
• ATOM: Pushes TRUE onto the BOOLEAN stack if the top piece of code is a single instruction or a literal, and FALSE otherwise (that is, if it is something surrounded by parentheses).
• CAR: Pushes the first item of the list on top of the CODE stack. For example, if the top piece of code is "( A B )" then this pushes "A" (after popping the argument). If the code on top of the stack is not a list then this has no effect. The name derives from the similar Lisp function; a more generic name would be "FIRST".
• CDR: Pushes a version of the list from the top of the CODE stack without its first element. For example, if the top piece of code is "( A B )" then this pushes "( B )" (after popping the argument). If the code on top of the stack is not a list then this pushes the empty list ("( )"). The name derives from the similar Lisp function; a more generic name would be "REST".
• CONS: Pushes the result of "consing" (in the Lisp sense) the second stack item onto the first stack item (which is coerced to a list if necessary). For example, if the top piece of code is "( A B )" and the second piece of code is "X" then this pushes "( X A B )" (after popping the argument).
• CONTAINER: Pushes the "container" of the second CODE stack item within the first CODE stack item onto the CODE stack. If second item contains the first anywhere (i.e. in any nested list) then the container is the smallest sub-list that contains but is not equal to the first instance. For example, if the top piece of code is "( B ( C ( A ) ) ( D ( A ) ) )" and the second piece of code is "( A )" then this pushes ( C ( A ) ). Pushes an empty list if there is no such container.
• CONTAINS: Pushes TRUE on the BOOLEAN stack if the second CODE stack item contains the first CODE stack item anywhere (e.g. in a sub-list).
• DEFINITION: Pushes the definition associated with the top NAME on the NAME stack (if any) onto the CODE stack. This extracts the definition for inspection/manipulation, rather than for immediate execution (although it may then be executed with a call to CODE.DO or a similar instruction).
• DISCREPANCY: Pushes a measure of the discrepancy between the top two CODE stack items onto the INTEGER stack. This will be zero if the top two items are equivalent, and will be higher the 'more different' the items are from one another. The calculation is as follows: 1. Construct a list of all of the unique items in both of the lists (where uniqueness is determined by equalp). Sub-lists and atoms all count as items; 2. Initialize the result to zero; 3. For each unique item increment the result by the difference between the number of occurrences of the item in the two pieces of code; 4. Push the result.
• DO: Recursively invokes the interpreter on the program on top of the CODE stack. After evaluation the CODE stack is popped; normally this pops the program that was just executed, but if the expression itself manipulates the stack then this final pop may end up popping something else.
• DO*: Like CODE.DO but pops the stack before, rather than after, the recursive execution.
• EXTRACT: Pushes the sub-expression of the top item of the CODE stack that is indexed by the top item of the INTEGER stack. The indexing here counts "points," where each parenthesized expression and each literal/instruction is considered a point, and it proceeds in depth first order. The entire piece of code is at index 0; if it is a list then the first item in the list is at index 1, etc. The integer used as the index is taken modulo the number of points in the overall expression (and its absolute value is taken in case it is negative) to ensure that it is within the meaningful range.
• FROMBOOLEAN: Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack.
• FROMFLOAT: Pops the FLOAT stack and pushes the popped item onto the CODE stack.
• FROMINTEGER: Pops the INTEGER stack and pushes the popped integer onto the CODE stack.
• FROMNAME: Pops the NAME stack and pushes the popped item onto the CODE stack.
• INSERT: Pushes the result of inserting the second item of the CODE stack into the first item, at the position indexed by the top item of the INTEGER stack (and replacing whatever was there formerly). The indexing is computed as in CODE.EXTRACT.
• INSTRUCTIONS: Pushes a list of all active instructions in the interpreter's current configuration.
• LENGTH: Pushes the length of the top item on the CODE stack onto the INTEGER stack. If the top item is not a list then this pushes a 1. If the top item is a list then this pushes the number of items in the top level of the list; that is, nested lists contribute only 1 to this count, no matter what they contain.
• LIST: Pushes a list of the top two items of the CODE stack onto the CODE stack.
• MEMBER: Pushes TRUE onto the BOOLEAN stack if the second item of the CODE stack is a member of the first item (which is coerced to a list if necessary). Pushes FALSE onto the BOOLEAN stack otherwise.
• NOOP: Does nothing.
• NTH: Pushes the nth element of the expression on top of the CODE stack (which is coerced to a list first if necessary). If the expression is an empty list then the result is an empty list. N is taken from the INTEGER stack and is taken modulo the length of the expression into which it is indexing.
• NTHCDR: Pushes the nth "CDR" (in the Lisp sense) of the expression on top of the CODE stack (which is coerced to a list first if necessary). If the expression is an empty list then the result is an empty list. N is taken from the INTEGER stack and is taken modulo the length of the expression into which it is indexing. A "CDR" of a list is the list without its first element.
• NULL: Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise.
• POSITION: Pushes onto the INTEGER stack the position of the second item on the CODE stack within the first item (which is coerced to a list if necessary). Pushes -1 if no match is found.
• QUOTE: Specifies that the next expression submitted for execution will instead be pushed literally onto the CODE stack. This can be implemented by moving the top item on the EXEC stack onto the CODE stack.
• SIZE: Pushes the number of "points" in the top piece of CODE onto the INTEGER stack. Each instruction, literal, and pair of parentheses counts as a point.
• SUBST: Pushes the result of substituting the third item on the code stack for the second item in the first item. As of this writing this is implemented only in the Lisp implementation, within which it relies on the Lisp "subst" function. As such, there are several problematic possibilities; for example "dotted-lists" can result in certain cases with empty-list arguments. If any of these problematic possibilities occurs the stack is left unchanged.

Links:

• http://faculty.hampshire.edu/lspector/push3-description.html

Links

• http://cswww.essex.ac.uk/staff/poli/gp-field-guide/index.html