next up previous
Next: Looking Inside a PADO Up: The Language Previous: The Language

Looking Inside a PADO Program

 

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 tex2html_wrap_inline859 ) as its action. When (and if) the ADF reaches its stop node ( tex2html_wrap_inline861 ), control is returned to the calling program node that then executes its branch-decision function as normal. Node tex2html_wrap_inline863 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.



next up previous
Next: Looking Inside a PADO Up: The Language Previous: The Language



Eric Teller
Tue Oct 29 17:04:55 EST 1996