Each PADO program is constructed as an arbitrary directed graph of nodes. As an arbitrary directed graph of N nodes, each node can have as many as N outgoing arcs. These arcs indicate possible flows of control in the program. In a PADO program each node has two main parts: an action and a branch-decision. Each program has an argument stack (see section 3.2). All PADO actions pop their inputs from this argument stack and push their result back onto the argument stack. These actions are the equivalent of GP's terminals and non-terminals. For example, the action ``6'' simply pushes 6 onto the argument stack. The action ``Write'' pops arg1 and arg2 off the stack and writes arg1 into Memory[arg2] after pushing Memory[arg2] onto the argument stack.
Evaluating a GP tree is effectively a post-order traversal of the tree. This traversal requires an argument stack which is taken care of, in most traditional GP implementations, by the activation records stack for recursive function calls. Because there are many arcs coming into a particular node in the PADO language, we evaluate a part of the graph (indeed, the whole graph) as a chronological, not structural, post-order traversal of the graph. In other words, to see where the arguments to a particular node come from in PADO, we have to look to the previous nodes in time rather than the previous nodes in the structure (as per standard GP).
In stack-based GP the programs are written in Postfix Notation instead of tree form [Keith and Martin 1994; Perkis 1994]. If you maintain arity constraints through crossover (so that no function is executed before its arguments have been computed) then stack-GP is tree-GP. In contrast, If PADO's argument stack is empty when an argument request comes, a 0 is returned. So arity requirements are not considered in the construction or recombination of PADO programs. We mention these details because the argument stack mentioned in this section is not in itself a departure from GP, but, like stack-based GP, is simply an easier way of telling the same story.
After the action at node i is executed, an arc is taken to a new node. The branch-decision function at the current node makes this decision. Each node has its own branch-decision function that may use the stack top, the action type (e.g., ``constant'', ``ADD'', etc.) of the previously executed node, the memory, and constants to pick an arc. The next section will provide further branch-decision details.
Several special nodes are shown in Figure 3.1.
Node q is the start node. It is always the first node to be
executed when a program begins. Node X is the stop node.
When this node is reached, its action is executed and then the program
halts. When a program halts or is halted at the time-threshold, its
response is considered to be the current value residing in some
particular memory location (e.g., response = Memory[0]). If a program
halts sooner than a pre-set time threshold, it is started again at its
start node (without erasing its memory or stack) to give it a chance
to revise its confidence value. Node A executes the private
ADF program (starting at 
) as its action. When (and if) the
ADF reaches its stop node ( 
), control is returned to the
calling program node that then executes its branch-decision function
as normal. Node 
executes Library program number 91 in a
similar manner.
For the purposes of this chapter the programs' nodes have been limited to two outgoing arcs each. It is still possible for any node to have as many as N incoming arcs. This outgoing arc limit was fixed largely to make the special actions of the SMART operators (section 3.4.3) easier to understand. Though the following will not be justified here, we claim that there is a qualitative difference between programs with a maximum fanout of one (already a superset of GP-trees) and programs with a maximum fanout of two. Further, we claim that there is only a quantitative difference between programs with a maximum fanout of two and programs with higher maximum fanouts.