OOPS Prerequisites: Multitasking & Prefix Tracking Through Method ``Try''

The Turing machine-based setups for HSEARCH and LSEARCH assume potentially infinite storage. Hence they may largely ignore questions of storage management. In any practical system, however, we have to efficiently reuse limited storage. This, and multitasking, is what the present subsection is about. The recursive method Try below allocates time to program prefixes, each being tested on multiple tasks simultaneously, such that the sum of the runtimes of any given prefix, tested on all tasks, does not exceed the total search time multiplied by the prefix probability (the product of the tape-dependent probabilities of its previously selected components in $Q$). Try tracks effects of tested program prefixes, such as storage modifications (including probability changes) and partially solved task sets, to reset conditions for subsequent tests of alternative prefix continuations in an optimally efficient fashion (at most as expensive as the prefix tests themselves). Optimal backtracking requires that any prolongation of some prefix by some token gets immediately executed. To allow for efficient undoing of state changes, we use global Boolean variables $mark_i(r)$ (initially FALSE) for all possible state components $s_i(r)$. We initialize time $t_0 := 0;$ probability $P := 1$; q-pointer $qp := a_{frozen}$ and state $s(r)$ (including $ip(r)$ and $p(r)$) with task-specific information for all task names $r$ in a ring $R_0$ of tasks. Here the expression ``ring'' indicates that the tasks are ordered in cyclic fashion; $\mid R \mid$ denotes the number of tasks in ring $R$. Given a global search time limit $T$, we Try to solve all tasks in $R_0$, by using existing code in $q= q_{1:qp}$ and / or by discovering an appropriate prolongation of $q$:

Method 2.1 (returns TRUE or FALSE; $r_0 \in R_0$)   .

1. Make an empty stack $\cal S$; set local variables $r := r_0; R := R_0; t:= t_0;$ Done$:=$ FALSE.

WHILE $\mid R \mid > 0$ and $t \leq PT$ and instruction pointer valid ( $-l(s(r)) \leq ip(r) \leq qp$) and instruction valid ( $1 \leq z(ip(r))(r) \leq n_Q$) and no halt condition (e.g., error such as division by 0) encountered (evaluate conditions in this order until first satisfied, if any) DO:

If possible, interpret / execute token $z(ip(r))(r)$ according to the rules of the given programming language (this may modify $s(r)$ including instruction pointer $ip(r)$ and distribution $p(r)$, but not $q$), continually increasing $t$ by the consumed time. Whenever the execution changes some state component $s_i(r)$ whose $mark_i(r)=$ FALSE, set $mark_i(r) :=$ TRUE and save the previous value $\hat{s}_i(r)$ by pushing the triple $(i, r, \hat{s}_i(r))$ onto $\cal S$. Remove $r$ from $R$ if solved. IF $\mid R \mid > 0$, set $r$ equal to the next task in ring $R$. ELSE set Done $:=$ TRUE; $a_{frozen} := qp$ (all tasks solved; new code frozen, if any).

2. Use $\cal S$ to efficiently reset only the modified $mark_i(k)$ to FALSE (but do not pop $\cal S$ yet).

3. IF $ip(r)=qp+1$ (this means an online request for prolongation of the current prefix through a new token): WHILE Done $=$ FALSE and there is some yet untested token $Z \in Q$ (untried since $t_0$ as value for $q_{qp+1}$), set $q_{qp+1}:=Z$ and Done $:=$ Try ( $qp+1, r, R, t, P * p(r)(Z)$), where $p(r)(Z)$ is $Z$'s probability according to current $p(r)$.

4. Use $\cal S$ to efficiently restore only those $s_i(k)$ changed since $t_0$, thus also restoring instruction pointer $ip(r_0)$ and original search distribution $p(r_0)$. Return the value of Done.

It is important that instructions whose runtimes are not known in advance can be interrupted by Try at any time. Essentially, Try conducts a depth-first search in program space, where the branches of the search tree are program prefixes, and backtracking is triggered once the sum of the runtimes of the current prefix on all current tasks exceeds the prefix probability multiplied by the total time limit. A successful Try will solve all tasks, possibly increasing $a_{frozen}$. In any case Try will completely restore all states of all tasks. Tracking / undoing effects of prefixes essentially does not cost more than their execution. So the $n$ in Def. 2.1 of $n$-bias-optimality is not greatly affected by backtracking: ignoring hardware-specific overhead, we lose at most a factor 2. An efficient iterative (non-recursive) version of Try for a broad variety of initial programming languages was implemented in C.

Back to OOPS home page