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
$cs[cp].ip$	current function call's instruction pointer $ip(r) := cs[cp](r).ip$
$cs[cp].base$	current base pointer into ds right below the current input arguments
$cs[cp].out$	number of return values expected on top of ds above $cs[cp].base$
fns	stack of currently available self-made functions
fnp	stack pointer of fns
$fns[fnp].code$	start address of code of most recent self-made function
$fns[fnp].in$	number of input arguments of most recent self-made function
$fns[fnp].out$	number of return values of most recent self-made function
pats	stack of search patterns (probability distributions on $Q$)
patp	stack pointer of pats
curp	pointer to current search pattern in pats, $0 \leq curp \leq patp$
$p[curp][i]$	$i$-th numerator of current search pattern
$sum[curp]$	denominator; the current probability of $Q_i$ is $p[curp][i] / sum[curp]$

Each tape $r$ contains various stack-like data structures represented as sequences of integers. For any stack $Xs(r)$ introduced below (here $X$ stands for a character string reminiscent of the stack type) there is a (frequently not even mentioned) stack pointer $Xp(r)$; $0 \leq Xp(r) \leq maxXp$, located at address $a_{Xp}$, and initialized by 0. The $n$-th element of $Xs(r)$ is denoted $Xs[n](r)$. For simplicity we will often omit tape indices $r$. 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 $dp: 0 \leq dp \leq maxdp$).

2. An auxiliary data stack Ds.

3. A runtime stack or callstack $cs$ for handling (possibly recursive) functions. Callstack pointer $cp$ is initialized by 0 for the ``main'' program. The $k$-th callstack entry ( $k = 0, \ldots, cp$) contains 3 variables: an instruction pointer $cs[k](r).ip$ (or simply $cs[k].ip$, omitting task index $r$) initialized by the start address of the code of some procedure $f$, a pointer $cs[k].base$ pointing into ds right below the values which are considered input arguments of $f$, and the number $cs[k].out$ of return values $ds[cs[k].base+1], \ldots, ds[dp]$ expected on top of ds once $f$ has returned. $cs[cp]$ refers to the topmost entry containing the current instruction pointer $ip(r) := cs[cp](r).ip$.

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. $pats[i]$ stands for a probability distribution on search options (next instruction candidates). It is represented by $n_Q+1$ integers $p[i][n]$ ( $1 \leq n \leq n_Q$) and sum[i] (for efficiency reasons). Once $ip(r)$ hits the current search address $l(q)+1$, the history-dependent probability of the $n$-th possible next instruction $Q_n$ (a candidate value for $q_{ip(r)}$) is given by $p[curp][n] / sum[curp]$, where $curp$ is another tape-represented variable ( $0 \leq curp \leq patp$) 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 $r$ 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.

Back to OOPS main page