Push 2.0 Programming Language Description

Lee Spector, Chris Perry, and Jon Klein
School of Cognitive Science
Hampshire College

November, 2003 - April, 2004 (see document version history)

This document is under collaborative construction. Send comments/updates to lspector@hampshire.edu.

Overview
Push Concepts
Simple Examples
Configuration
Random Code Generation
Implementation Notes
Push2 vs. Push1
Under Discussion
Type/Instruction Catalog
Acknowledgments
Document Version History

Overview

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 Concepts

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:

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

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:

EVALPUSH-LIMIT: This is the maximum allowed number of "executions" in a single top-level call to the interpreter. The execution of a single Push instruction counts as one execution, as does the processing of a single literal, as does the descent into one layer of parentheses (that is, the processing of the "(" counts as one execution). When this limit is exceeded the interpreter aborts immediately, leaving its stacks in the states they were in prior to the abort (so they may still be examined by a calling program). Whether or not this counts as an "abnormal" termination is up to the calling program.
MAX-POINTS-IN-PROGRAM: This is the maximum size of an item on the CODE stack, expressed as a number of points. A point is an instruction, a literal, or a pair of parentheses. Any instruction that would cause this limit to be exceeded should instead act as a NOOP, leaving all stacks in the states that they were in before the execution of the instruction.

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).

Simple Examples

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:

Operations on integers and on floating point numbers can be interleaved; all instructions take their arguments from the appropriate stacks and push their results onto the appropriate stacks.
The call to INTEGER.+ does nothing because there are not two integers on the INTEGER stack when it is executed.
The call to INTEGER.- subtracts 4 (which is on top of the stack) from 5 (which is second on the stack), not the other way around.
The parentheses in "( 4 )" have no effect on the results; parentheses serve mainly to group pieces of code for handling by code-manipulation instructions.

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)

Configuration

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:

<parameter name> <value>
type <type name>
instruction <instruction name>
constant <type name> <constant name>

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:

MIN-RANDOM-INTEGER: The minimum INTEGER that will be produced as an ephemeral random INTEGER constant or from a call to INTEGER.RAND.
MAX-RANDOM-INTEGER: The maximum INTEGER that will be produced as an ephemeral random INTEGER constant or from a call to INTEGER.RAND.
MIN-RANDOM-FLOAT: The minimum FLOAT that will be produced as an ephemeral random FLOAT constant or from a call to FLOAT.RAND.
MAX-RANDOM-FLOAT: The maximum FLOAT that will be produced as an ephemeral random FLOAT constant or from a call to FLOAT.RAND.
MAX-POINTS-IN-RANDOM-EXPRESSIONS: The maximum number of points in an expression produced by the CODE.RAND instruction.
MAX-POINTS-IN-PROGRAM: The maximum number of points that can occur in any program on the CODE stack. Instructions that would violate this limit act as NOOPs (they do nothing).
EVALPUSH-LIMIT: The maximum number of points that will be executed in a single top-level call to the interpreter.
NEW-ERC-NAME-PROBABILITY: The probability that the selection of the ephemeral
random NAME constant for inclusion in randomly generated code will produce a new name (rather than a name that was previously generated).
RANDOM-SEED: A seed for the random number generator; 0 <= RANDOM-SEED <= 30081.

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.

Random Code Generation

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

Implementation Notes

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 vs. Push1

Push2 differs from Push1 mainly in the following ways:

Changes to the language per se:

The instruction overloading scheme in Push1 was dropped. It was deemed to be overly complex and unnecessary.
The "TYPE" data type, which was used primarily to support instruction overloading, was dropped.
Conversions between data types, which were previously handled by a CONVERT instruction in conjunction with the TYPE type, are now handled by conversion instructions for each appropriate type/type pair.
Type names are now integrated into instruction identifiers (like "INTEGER.POP") rather than occurring as type literals.
A few artifacts of the Lisp derivation of Push1 have been dropped; for example the Boolean literals are now TRUE and FALSE, rather than T and NIL.
A few names have been changed for clarity or consistency (e.g. PULL was replaced with YANK to better reflect that it is the inverse of the SHOVE, which we didn't want to name PUSH as that might imply pushing onto the top of the stack).

Refinements to our implementations and their interfaces:

Template-like mechanisms simplify the implementation of instructions for multiple data types (now that there is no overloading).
A configuration file system was developed to simplify the specification of a particular set of types/instructions/parameters for a particular run. This system is intended to support libraries of types and instructions, and to work for all Push2 implementations (including our current Lisp and C++ implementations).
A test file system was also added to help ensure that the various implementations behave in the same ways.

Rejected alternative names for Push2:

push-- ("push minus minus", on account of the removal of OOP-like features)
p (streamlined push... "programming with p" sounds pretty funny!)
shove (push with more oomph)
TAP (Type Ascribed Push, "what's on tap?")
Qush (incrementing the first letter)
plush
pints (Push, No Type Stack)
Push 2: With A Vengeance
Push II: The Empire Strikes Back
A few more from Maarten Keijzer:
- Push.DUP (two pushes, does not neccessarity mean an improvement)
- Push.INC (not in the standard function set, and afaik push isn't incorporated)
- Push.PUSH (maybe push needs to be pushed a bit more, but one can overdo it)

Under Discussion

Following are a couple of items that are currently under discussion for possible inclusion in future versions of Push:

Standardized entries in the type/instruction catalog for other types that we commonly use (point/vector, child, unitaryMatrix, ...?).
Various ideas for dynamic generation of new types from Push code.
Exceptions as first class entities (with their own stack, etc.), allowing for the explicit handling of stack underflows, divisions by zero, etc. (Suggested by Maarten Keijzer.)
Environments (containing stack states, variable binding states, perhaps more) as first class entities, along with associated instructions that allow for the execution of code within specified environments. This might allow for the "safe" execution of arbitrary code fragments (which would be executed in a fresh environment and would not be able to affect the the environment of the remainder of the code). Ideas for this range from minimal extensions (e.g. "DO&" which executes in a fresh environment, plus a mechanism to get the results back to the calling environment) to a full-fledged ENVIRONMENT type with a stack, etc. (Suggested by Maarten Keijzer.)
Control of various meta-linguistic features from Push code.

Type/Instruction Catalog

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).

Type BOOLEAN

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.

Instructions

BOOLEAN.=: Pushes TRUE if the top two BOOLEANs are equal, or FALSE otherwise.
BOOLEAN.AND: Pushes the logical AND of the top two BOOLEANs.
BOOLEAN.DUP: Duplicates the top item on the BOOLEAN stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!).
BOOLEAN.FROMFLOAT: Pushes FALSE if the top FLOAT is 0.0, or TRUE otherwise.
BOOLEAN.FROMINTEGER: Pushes FALSE if the top INTEGER is 0, or TRUE otherwise.
BOOLEAN.GET: Pushes the current BOOLEAN binding of the NAME that is on top of the NAME stack onto the BOOLEAN stack. If there is no such binding then this acts as a NOOP.
BOOLEAN.NOT: Pushes the logical NOT of the top BOOLEAN.
BOOLEAN.OR: Pushes the logical OR of the top two BOOLEANs.
BOOLEAN.POP: Pops the BOOLEAN stack.
BOOLEAN.RAND: Pushes a random BOOLEAN.
BOOLEAN.SET: Binds the top BOOLEAN to the NAME on top of the NAME stack.
BOOLEAN.SHOVE: Inserts the top BOOLEAN "deep" in the stack, at the position indexed by the top INTEGER.
BOOLEAN.STACKDEPTH: Pushes the stack depth onto the INTEGER stack.
BOOLEAN.SWAP: Swaps the top two BOOLEANs.
BOOLEAN.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.
BOOLEAN.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.

Type CODE

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.

Instructions

CODE.=: Pushes TRUE if the top two pieces of CODE are equal, or FALSE otherwise.
CODE.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.
CODE.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).
CODE.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".
CODE.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".
CODE.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).
CODE.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.
CODE.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).
CODE.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.
CODE.DO: Recursively invokes the interpreter on the program on top of the CODE stack. After evaluation the 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.
CODE.DO*: Like CODE.DO but pops the stack before, rather than after, the recursive execution.
CODE.DO*COUNT: Pops the CODE stack (saving the popped program) and the INTEGER stack (saving the popped number) and then recursively invokes the interpreter on the popped program the number of times indicated by the popped number. If the popped number is less than or equal to zero then no recursive interpretations will be performed. Prior to each recursive interpretation a "loop counter," which starts at 0, is pushed onto the INTEGER stack. For example, if the popped number is 4 then the popped program will be interpreted 4 times, with 0 pushed onto the INTEGER stack prior to the first interpretation, 1 prior to the second interpretation, 2 prior to the third interpretation, and 4 prior to the fourth (and final) interpretation.
CODE.DO*TIMES: Like DO*COUNT but does not push the loop counter (ever).
CODE.DUP: Duplicates the top item on the CODE stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!).
CODE.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.
CODE.FROMBOOLEAN: Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack.
CODE.FROMINTEGER: Pops the INTEGER stack and pushes the popped integer onto the CODE stack.
CODE.FROMFLOAT: Pops the FLOAT stack and pushes the popped item onto the CODE stack.
CODE.FROMNAME: Pops the NAME stack and pushes the popped item onto the CODE stack.
CODE.GET: Pushes the current CODE binding of the NAME that is on top of the NAME stack onto the CODE stack. If there is no such binding then this acts as a NOOP.
CODE.IF: If the top item of the BOOLEAN stack is TRUE this recursively executes the second item of the CODE stack; otherwise it recursively executes the first item of the CODE stack. Either way both elements of the CODE stack (and the BOOLEAN value upon which the decision was made)
are popped.
CODE.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.
CODE.INSTRUCTIONS: Pushes a list of all active instructions in the interpreter's current configuration.
CODE.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.
CODE.LIST: Pushes a list of the top two items of the CODE stack onto the CODE stack.
CODE.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.
CODE.NOOP: Does nothing.
CODE.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.
CODE.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.
CODE.NULL: Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise.
CODE.POP: Pops the CODE stack.
CODE.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.
CODE.QUOTE: Specifies that the next expression submitted for execution will instead be pushed literally onto the CODE stack.
CODE.RAND: 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.
CODE.SET: Binds the top piece of CODE to the NAME on top of the NAME stack.
CODE.SHOVE: Inserts the top piece of CODE "deep" in the stack, at the position indexed by the top INTEGER.
CODE.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.
CODE.STACKDEPTH: Pushes the stack depth onto the INTEGER stack.
CODE.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.
CODE.SWAP: Swaps the top two pieces of CODE.
CODE.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.
CODE.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.

Type FLOAT

Description Floating-point numbers (that is, numbers with decimal points).

Instructions

FLOAT.%: Pushes the second stack item modulo the top stack item. If the top item is zero this acts as a NOOP. The modulus is computed as the remainder of the quotient, where the quotient has first been truncated toward negative infinity. (This is taken from the definition for the generic MOD function in Common Lisp, which is described for example at http://www.lispworks.com/reference/HyperSpec/Body/f_mod_r.htm.)
FLOAT.*: Pushes the product of the top two items.
FLOAT.+: Pushes the sum of the top two items.
FLOAT.-: Pushes the difference of the top two items; that is, the second item minus the top item.
FLOAT./: Pushes the quotient of the top two items; that is, the second item divided by the top item. If the top item is zero this acts as a NOOP.
FLOAT.<: Pushes TRUE onto the BOOLEAN stack if the second item is less than the top item, or FALSE otherwise.
FLOAT.=: Pushes TRUE onto the BOOLEAN stack if the top two items are equal, or FALSE otherwise.
FLOAT.>: Pushes TRUE onto the BOOLEAN stack if the second item is greater than the top item, or FALSE otherwise.
FLOAT.COS: Pushes the cosine of the top item.
FLOAT.DUP: Duplicates the top item on the FLOAT stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!).
FLOAT.FROMBOOLEAN: Pushes 1.0 if the top BOOLEAN is TRUE, or 0.0 if the top BOOLEAN is FALSE.
FLOAT.FROMINTEGER: Pushes a floating point version of the top INTEGER.
FLOAT.GET: Pushes the current FLOAT binding of the NAME that is on top of the NAME stack onto the FLOAT stack. If there is no such binding then this acts as a NOOP.
FLOAT.MAX: Pushes the maximum of the top two items.
FLOAT.MIN: Pushes the minimum of the top two items.
FLOAT.POP: Pops the FLOAT stack.
FLOAT.RAND: Pushes a newly generated random FLOAT that is greater than or equal to MIN-RANDOM-FLOAT and less than or equal to MAX-RANDOM-FLOAT.
FLOAT.SET: Binds the top FLOAT to the NAME on top of the NAME stack.
FLOAT.SHOVE: Inserts the top FLOAT "deep" in the stack, at the position indexed by the top INTEGER.
FLOAT.SIN: Pushes the sine of the top item.
FLOAT.STACKDEPTH: Pushes the stack depth onto the INTEGER stack.
FLOAT.SWAP: Swaps the top two BOOLEANs.
FLOAT.TAN: Pushes the tangent of the top item.
FLOAT.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.
FLOAT.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.

Type INTEGER

Description Integer numbers (that is, numbers without decimal points).

Instructions

INTEGER.%: Pushes the second stack item modulo the top stack item. If the top item is zero this acts as a NOOP. The modulus is computed as the remainder of the quotient, where the quotient has first been truncated toward negative infinity. (This is taken from the definition for the generic MOD function in Common Lisp, which is described for example at http://www.lispworks.com/reference/HyperSpec/Body/f_mod_r.htm.)
INTEGER.*: Pushes the product of the top two items.
INTEGER.+: Pushes the sum of the top two items.
INTEGER.-: Pushes the difference of the top two items; that is, the second item minus the top item.
INTEGER./: Pushes the quotient of the top two items; that is, the second item divided by the top item. If the top item is zero this acts as a NOOP.
INTEGER.<: Pushes TRUE onto the BOOLEAN stack if the second item is less than the top item, or FALSE otherwise.
INTEGER.=: Pushes TRUE onto the BOOLEAN stack if the top two items are equal, or FALSE otherwise.
INTEGER.>: Pushes TRUE onto the BOOLEAN stack if the second item is greater than the top item, or FALSE otherwise.
INTEGER.DUP: Duplicates the top item on the INTEGER stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!).
INTEGER.FROMBOOLEAN: Pushes 1 if the top BOOLEAN is TRUE, or 0 if the top BOOLEAN is FALSE.
INTEGER.FROMFLOAT: Pushes the result of truncating the top FLOAT.
INTEGER.GET: Pushes the current INTEGER binding of the NAME that is on top of the NAME stack onto the INTEGER stack. If there is no such binding then this acts as a NOOP.
INTEGER.MAX: Pushes the maximum of the top two items.
INTEGER.MIN: Pushes the minimum of the top two items.
INTEGER.POP: Pops the INTEGER stack.
INTEGER.RAND: Pushes a newly generated random INTEGER that is greater than or equal to MIN-RANDOM-INTEGER and less than or equal to MAX-RANDOM-INTEGER.
INTEGER.SET: Binds the top INTEGER to the NAME on top of the NAME stack.
INTEGER.SHOVE: Inserts the second INTEGER "deep" in the stack, at the position indexed by the top INTEGER. The index position is calculated after the index is removed.
INTEGER.STACKDEPTH: Pushes the stack depth onto the INTEGER stack (thereby increasing it!).
INTEGER.SWAP: Swaps the top two INTEGERs.
INTEGER.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, and the indexing is done after the index is removed.
INTEGER.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, and the indexing is done after the index is removed.

Type NAME

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).

Instructions

NAME.=: Pushes TRUE if the top two NAMEs are equal, or FALSE otherwise.
NAME.DUP: Duplicates the top item on the NAME stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!).
NAME.GET: Pushes the current NAME binding of the NAME that is on top of the NAME stack onto the NAME stack. If there is no such binding then this acts as a NOOP.
NAME.POP: Pops the NAME stack.
NAME.RAND: Pushes a newly generated random NAME.
NAME.RANDBOUNDNAME: Pushes a randomly selected NAME that already has a binding (for some type).
NAME.SET: Binds the second NAME to the NAME on top of the NAME stack. That is, the NAME on top acts as the "variable name," and the second NAME is the value of that variable (for the NAME type).
NAME.SHOVE: Inserts the top NAME "deep" in the stack, at the position indexed by the top INTEGER.
NAME.STACKDEPTH: Pushes the stack depth onto the INTEGER stack.
NAME.SWAP: Swaps the top two NAMEs.
NAME.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.
NAME.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.

Acknowledgments

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.

Document Version History

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.

[end]

Type	BOOLEAN
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.
Instructions	BOOLEAN.=: Pushes TRUE if the top two BOOLEANs are equal, or FALSE otherwise. BOOLEAN.AND: Pushes the logical AND of the top two BOOLEANs. BOOLEAN.DUP: Duplicates the top item on the BOOLEAN stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!). BOOLEAN.FROMFLOAT: Pushes FALSE if the top FLOAT is 0.0, or TRUE otherwise. BOOLEAN.FROMINTEGER: Pushes FALSE if the top INTEGER is 0, or TRUE otherwise. BOOLEAN.GET: Pushes the current BOOLEAN binding of the NAME that is on top of the NAME stack onto the BOOLEAN stack. If there is no such binding then this acts as a NOOP. BOOLEAN.NOT: Pushes the logical NOT of the top BOOLEAN. BOOLEAN.OR: Pushes the logical OR of the top two BOOLEANs. BOOLEAN.POP: Pops the BOOLEAN stack. BOOLEAN.RAND: Pushes a random BOOLEAN. BOOLEAN.SET: Binds the top BOOLEAN to the NAME on top of the NAME stack. BOOLEAN.SHOVE: Inserts the top BOOLEAN "deep" in the stack, at the position indexed by the top INTEGER. BOOLEAN.STACKDEPTH: Pushes the stack depth onto the INTEGER stack. BOOLEAN.SWAP: Swaps the top two BOOLEANs. BOOLEAN.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. BOOLEAN.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.

Type	CODE
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.
Instructions	CODE.=: Pushes TRUE if the top two pieces of CODE are equal, or FALSE otherwise. CODE.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. CODE.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). CODE.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". CODE.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". CODE.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). CODE.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. CODE.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). CODE.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. CODE.DO: Recursively invokes the interpreter on the program on top of the CODE stack. After evaluation the 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. CODE.DO: Like CODE.DO but pops the stack before, rather than after, the recursive execution. CODE.DOCOUNT: Pops the CODE stack (saving the popped program) and the INTEGER stack (saving the popped number) and then recursively invokes the interpreter on the popped program the number of times indicated by the popped number. If the popped number is less than or equal to zero then no recursive interpretations will be performed. Prior to each recursive interpretation a "loop counter," which starts at 0, is pushed onto the INTEGER stack. For example, if the popped number is 4 then the popped program will be interpreted 4 times, with 0 pushed onto the INTEGER stack prior to the first interpretation, 1 prior to the second interpretation, 2 prior to the third interpretation, and 4 prior to the fourth (and final) interpretation. CODE.DOTIMES: Like DOCOUNT but does not push the loop counter (ever). CODE.DUP: Duplicates the top item on the CODE stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!). CODE.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. CODE.FROMBOOLEAN: Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack. CODE.FROMINTEGER: Pops the INTEGER stack and pushes the popped integer onto the CODE stack. CODE.FROMFLOAT: Pops the FLOAT stack and pushes the popped item onto the CODE stack. CODE.FROMNAME: Pops the NAME stack and pushes the popped item onto the CODE stack. CODE.GET: Pushes the current CODE binding of the NAME that is on top of the NAME stack onto the CODE stack. If there is no such binding then this acts as a NOOP. CODE.IF: If the top item of the BOOLEAN stack is TRUE this recursively executes the second item of the CODE stack; otherwise it recursively executes the first item of the CODE stack. Either way both elements of the CODE stack (and the BOOLEAN value upon which the decision was made) are popped. CODE.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. CODE.INSTRUCTIONS: Pushes a list of all active instructions in the interpreter's current configuration. CODE.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. CODE.LIST: Pushes a list of the top two items of the CODE stack onto the CODE stack. CODE.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. CODE.NOOP: Does nothing. CODE.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. CODE.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. CODE.NULL: Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise. CODE.POP: Pops the CODE stack. CODE.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. CODE.QUOTE: Specifies that the next expression submitted for execution will instead be pushed literally onto the CODE stack. CODE.RAND: 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. CODE.SET: Binds the top piece of CODE to the NAME on top of the NAME stack. CODE.SHOVE: Inserts the top piece of CODE "deep" in the stack, at the position indexed by the top INTEGER. CODE.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. CODE.STACKDEPTH: Pushes the stack depth onto the INTEGER stack. CODE.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. CODE.SWAP: Swaps the top two pieces of CODE. CODE.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. CODE.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.

Type	FLOAT
Description	Floating-point numbers (that is, numbers with decimal points).
Instructions	FLOAT.%: Pushes the second stack item modulo the top stack item. If the top item is zero this acts as a NOOP. The modulus is computed as the remainder of the quotient, where the quotient has first been truncated toward negative infinity. (This is taken from the definition for the generic MOD function in Common Lisp, which is described for example at http://www.lispworks.com/reference/HyperSpec/Body/f_mod_r.htm.) FLOAT.*: Pushes the product of the top two items. FLOAT.+: Pushes the sum of the top two items. FLOAT.-: Pushes the difference of the top two items; that is, the second item minus the top item. FLOAT./: Pushes the quotient of the top two items; that is, the second item divided by the top item. If the top item is zero this acts as a NOOP. FLOAT.<: Pushes TRUE onto the BOOLEAN stack if the second item is less than the top item, or FALSE otherwise. FLOAT.=: Pushes TRUE onto the BOOLEAN stack if the top two items are equal, or FALSE otherwise. FLOAT.>: Pushes TRUE onto the BOOLEAN stack if the second item is greater than the top item, or FALSE otherwise. FLOAT.COS: Pushes the cosine of the top item. FLOAT.DUP: Duplicates the top item on the FLOAT stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!). FLOAT.FROMBOOLEAN: Pushes 1.0 if the top BOOLEAN is TRUE, or 0.0 if the top BOOLEAN is FALSE. FLOAT.FROMINTEGER: Pushes a floating point version of the top INTEGER. FLOAT.GET: Pushes the current FLOAT binding of the NAME that is on top of the NAME stack onto the FLOAT stack. If there is no such binding then this acts as a NOOP. FLOAT.MAX: Pushes the maximum of the top two items. FLOAT.MIN: Pushes the minimum of the top two items. FLOAT.POP: Pops the FLOAT stack. FLOAT.RAND: Pushes a newly generated random FLOAT that is greater than or equal to MIN-RANDOM-FLOAT and less than or equal to MAX-RANDOM-FLOAT. FLOAT.SET: Binds the top FLOAT to the NAME on top of the NAME stack. FLOAT.SHOVE: Inserts the top FLOAT "deep" in the stack, at the position indexed by the top INTEGER. FLOAT.SIN: Pushes the sine of the top item. FLOAT.STACKDEPTH: Pushes the stack depth onto the INTEGER stack. FLOAT.SWAP: Swaps the top two BOOLEANs. FLOAT.TAN: Pushes the tangent of the top item. FLOAT.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. FLOAT.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.

Type	INTEGER
Description	Integer numbers (that is, numbers without decimal points).
Instructions	INTEGER.%: Pushes the second stack item modulo the top stack item. If the top item is zero this acts as a NOOP. The modulus is computed as the remainder of the quotient, where the quotient has first been truncated toward negative infinity. (This is taken from the definition for the generic MOD function in Common Lisp, which is described for example at http://www.lispworks.com/reference/HyperSpec/Body/f_mod_r.htm.) INTEGER.*: Pushes the product of the top two items. INTEGER.+: Pushes the sum of the top two items. INTEGER.-: Pushes the difference of the top two items; that is, the second item minus the top item. INTEGER./: Pushes the quotient of the top two items; that is, the second item divided by the top item. If the top item is zero this acts as a NOOP. INTEGER.<: Pushes TRUE onto the BOOLEAN stack if the second item is less than the top item, or FALSE otherwise. INTEGER.=: Pushes TRUE onto the BOOLEAN stack if the top two items are equal, or FALSE otherwise. INTEGER.>: Pushes TRUE onto the BOOLEAN stack if the second item is greater than the top item, or FALSE otherwise. INTEGER.DUP: Duplicates the top item on the INTEGER stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!). INTEGER.FROMBOOLEAN: Pushes 1 if the top BOOLEAN is TRUE, or 0 if the top BOOLEAN is FALSE. INTEGER.FROMFLOAT: Pushes the result of truncating the top FLOAT. INTEGER.GET: Pushes the current INTEGER binding of the NAME that is on top of the NAME stack onto the INTEGER stack. If there is no such binding then this acts as a NOOP. INTEGER.MAX: Pushes the maximum of the top two items. INTEGER.MIN: Pushes the minimum of the top two items. INTEGER.POP: Pops the INTEGER stack. INTEGER.RAND: Pushes a newly generated random INTEGER that is greater than or equal to MIN-RANDOM-INTEGER and less than or equal to MAX-RANDOM-INTEGER. INTEGER.SET: Binds the top INTEGER to the NAME on top of the NAME stack. INTEGER.SHOVE: Inserts the second INTEGER "deep" in the stack, at the position indexed by the top INTEGER. The index position is calculated after the index is removed. INTEGER.STACKDEPTH: Pushes the stack depth onto the INTEGER stack (thereby increasing it!). INTEGER.SWAP: Swaps the top two INTEGERs. INTEGER.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, and the indexing is done after the index is removed. INTEGER.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, and the indexing is done after the index is removed.

Type	NAME
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).
Instructions	NAME.=: Pushes TRUE if the top two NAMEs are equal, or FALSE otherwise. NAME.DUP: Duplicates the top item on the NAME stack. Does not pop its argument (which, if it did, would negate the effect of the duplication!). NAME.GET: Pushes the current NAME binding of the NAME that is on top of the NAME stack onto the NAME stack. If there is no such binding then this acts as a NOOP. NAME.POP: Pops the NAME stack. NAME.RAND: Pushes a newly generated random NAME. NAME.RANDBOUNDNAME: Pushes a randomly selected NAME that already has a binding (for some type). NAME.SET: Binds the second NAME to the NAME on top of the NAME stack. That is, the NAME on top acts as the "variable name," and the second NAME is the value of that variable (for the NAME type). NAME.SHOVE: Inserts the top NAME "deep" in the stack, at the position indexed by the top INTEGER. NAME.STACKDEPTH: Pushes the stack depth onto the INTEGER stack. NAME.SWAP: Swaps the top two NAMEs. NAME.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. NAME.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.