Example Initial Programming Language

``If it isn't 100 times smaller than 'C' it isn't FORTH.'' (CHARLES MOORE)

The efficient search and backtracking mechanism described in Section 4.1 is designed for a broad variety of possible programming languages, possibly list-oriented such as LISP, or based on matrix operations for recurrent neural network-like parallel architectures. Many other alternatives are possible.

A given language is represented by $Q$, the set of initial tokens. Each token corresponds to a primitive instruction. Primitive instructions are computer programs that manipulate tape contents, to be composed by OOPS such that more complex programs result. In principle, each ``primitive'' could actually be large and time-consuming software--compare Section 4.5.

For each instruction there is a unique number between 1 and $n_Q$, such that all such numbers are associated with exactly one instruction. Initial knowledge or bias is introduced by writing appropriate primitives and adding them to $Q$. Step 1 of procedure Try (see Section 4.1) translates any instruction number back into the corresponding executable code (in our particular implementation: a pointer to a $C$-function). If the presently executed instruction does not directly affect instruction pointer $ip(r)$, e.g., through a conditional jump, or the call of a function, or the return from a function call, then $ip(r)$ is simply incremented.

Given some choice of programming language / initial primitives, we typically have to write a new interpreter from scratch, instead of using an existing one. Why? Because procedure Try (Section 4.1) needs total control over all (usually hidden and inaccessible) aspects of storage management, including garbage collection etc. Otherwise the storage clean-up in the wake of executed and tested prefixes could become suboptimal.

For the experiments (Section 6) we wrote (in $C$) an interpreter for an example, stack-based, universal programming language inspired by FORTH [36] whose disciples praise its beauty and the compactness of its programs. Our main motivation for this choice is the desire to combine universality and simplicity.

The appendix (Section A) describes the details. Data structures on tapes (Section A.1) can be manipulated by primitive instructions listed in Sections A.2.1, A.2.2, A.2.3. Section A.3 shows how the user may compose complex programs from primitive ones, and insert them into total code $q$. Once the user has declared his programs, $n_Q$ will remain fixed.

Back to OOPS main page