Next: Primitive Instructions Up: Example Programming Language Previous: Example Programming Language

## Data Structures on Tapes

Table 2: Frequently used implementation-specific symbols, relating to the data structures used by a particular FORTH-inspired programming language (Section A). Not necessary for understanding the basic principles of OOPS.

 Symbol Description ds data stack holding arguments of functions, possibly also edited code dp stack pointer of ds Ds auxiliary data stack Dp stack pointer of Ds cs call stack or runtime stack to handle function calls cp stack pointer of cs current function call's instruction pointer current base pointer into ds right below the current input arguments number of return values expected on top of ds above fns stack of currently available self-made functions fnp stack pointer of fns start address of code of most recent self-made function number of input arguments of most recent self-made function number of return values of most recent self-made function pats stack of search patterns (probability distributions on ) patp stack pointer of pats curp pointer to current search pattern in pats, -th numerator of current search pattern denominator; the current probability of is

Each tape contains various stack-like data structures represented as sequences of integers. For any stack introduced below (here stands for a character string reminiscent of the stack type) there is a (frequently not even mentioned) stack pointer ; , located at address , and initialized by 0. The -th element of is denoted . For simplicity we will often omit tape indices . Each tape has:

1. A data stack ds(r) (or ds for short, omitting the task index) for storing function arguments. (The corresponding stack pointer is ).

2. An auxiliary data stack Ds.

3. A runtime stack or callstack for handling (possibly recursive) functions. Callstack pointer is initialized by 0 for the main'' program. The -th callstack entry ( ) contains 3 variables: an instruction pointer (or simply , omitting task index ) initialized by the start address of the code of some procedure , a pointer pointing into ds right below the values which are considered input arguments of , and the number of return values expected on top of ds once has returned. refers to the topmost entry containing the current instruction pointer .

4. A stack fns of entries describing self-made functions. The entry for function fn contains 3 integer variables: the start address of fn's code, the number of input arguments expected by fn on top of ds, and the number of output values to be returned.

5. A stack pats of search patterns. stands for a probability distribution on search options (next instruction candidates). It is represented by integers ( ) and sum[i] (for efficiency reasons). Once hits the current search address , the history-dependent probability of the -th possible next instruction (a candidate value for ) is given by , where is another tape-represented variable ( ) indicating the current search pattern.

6. A binary quoteflag determining whether the instructions pointed to by ip will get executed or just quoted, that is, pushed onto ds.

7. A variable holding the index of this tape's task.

8. A stack of integer arrays, each having a name, an address, and a size (not used in this paper, but implemented and mentioned for the sake of completeness).

9. Additional problem-specific dynamic data structures for problem-specific data, e.g., to represent changes of the environment. An example environment for the Towers of Hanoi problem is described in Section 6.

Next: Primitive Instructions Up: Example Programming Language Previous: Example Programming Language
Juergen Schmidhuber 2004-04-15

Back to OOPS main page