Initial User-Defined Programs: Examples

The user can declare initial, possibly recursive programs by composing the tokens described above. Programs are sequentially written into $q$, starting with $q_1$ at address 1. To declare a new token (program) we write decl(m, n, NAME, body), where NAME is the textual name of the code. Textual names are of interest only for the user, since the system immediately translates any new name into the smallest integer $> n_Q$ which gets associated with the topmost unused code address; then $n_Q$ is incremented. Argument $m$ denotes the code's number of expected arguments on top of the data stack ds; $n$ denotes the number of return values; body is a string of names of previously defined instructions, and possibly one new name to allow for cross-recursion. Once the interpreter comes across a user-defined token, it simply calls the code in $q$ starting with that body's first token; once the code is executed, the interpreter returns to the address of the next token, using the callstack $cs$. All of this is quite similar to the case of self-made functions defined by the system itself -- compare instruction def in section A.2.2.

Here are some samples of user-defined tokens or programs composed from the primitive instructions defined above. Declarations omit parantheses for argument lists of instructions.

1. decl(0, 1, C999, c5 c5 mul c5 c4 c2 mul mul mul dec ret) declares C999(), a program without arguments, computing constant 999 and returning it on top of data stack ds.

2. decl(2, 1, TESTEXP, by2 by2 dec c3 by2 mul mul up mul ret) declares TESTEXP (x,y), which pops two values $x,y$ from ds and returns $[6x (4y - 1)]^2$.

3. decl(1, 1, FAC, up c1 ex rt0 del up dec FAC mul ret) declares a recursive function FAC(n) which returns 1 if $n=0$, otherwise returns $n \times$ FAC(n-1).

4. decl(1, 1, FAC2, c1 c1 def up c1 ex rt0 del up dec topf dof mul ret) declares FAC2(n), which defines self-made recursive code functionally equivalent to FAC(n), which calls itself by calling the most recent self-made function even before it is completely defined. That is, FAC2(n) not only computes FAC(n) but also makes a new FAC-like function.

5. The following declarations are useful for defining and executing recursive procedures (without return values) that expect as many inputs as currently found on stack ds, and call themselves on decreasing problem sizes. defnp first pushes onto auxiliary stack Ds the number of return values (namely, zero), then measures the number $m$ of inputs on ds and pushes it onto Ds, then quotes (that is, pushes onto ds) the begin of the definition of a procedure that returns if its topmost input $n$ is 0 and otherwise decrements $n$. callp quotes a call of the most recently defined function / procedure. Both defnp and callp also quote code for making a fresh copy of the inputs of the most recently defined code, expected on top of ds. endnp quotes the code for returning, grabs from Ds the numbers of in and out values, and uses bsf to call the code generated so far on stack ds above the input parameters, applying this code (possibly located deep in $ds$) to a copy of the inputs pushed onto the top of $ds$.

   decl(-1,-1,defnp, c0 toD pushdp dec toD qot def up rt0 dec intpf cpn qot ret)

   decl(-1,-1,calltp, qot topf dof intpf cpn qot ret)

   decl(-1,-1,endnp,qot ret qot fromD cpnb fromD up delD fromD ex bsf ret)

6. Since our entire language is based on integer sequences, there is no obvious distinction between data and programs. The following illustrative example demonstrates that this makes functional programming very easy:

   decl(-1, -1, TAILREC, qot c1 c1 def up qot c2 outb qot ex rt0 del up dec topf dof qot c3 outb qot ret qot c1 outb c3 bsjmp) declares a tail recursion scheme TAILREC with a functional argument. Suppose the data stack ds holds three values $n$, val, and codenum above the current base pointer. Then TAILREC will create a function that returns val if $n=0$, else applies the 2-argument function represented by codenum, where the arguments are $n$ and the result of calling the 2-argument function itself on the value $n-1$.

   For example, the following code fragment uses TAILREC to implement yet another version of FAC(n): (qot c1 mul qot TAILREC ret). Assuming $n$ on ds, it first quotes the constant c1 (the return value for the terminal case $n=0$) and the function mul, then applies TAILREC.

The primitives of Section A collectively embody a universal programming language, computationally as powerful as the one of [14] or FORTH or ADA or C. In fact, a small fraction of the primitives would already be sufficient to achive this universality. Higher-level programming languages can be incrementally built based on the initial low-level FORTH-like language.

To fully understand a given program, one may need to know which instruction has got which number. For the sake of completeness, and to permit precise re-implementation, we include the full list here:

1: 1toD, 2: 2toD, 3: mvdsk, 4: xAD, 5: xSA, 6: bsf, 7: boostq, 8: add, 9: mul, 10: powr, 11: sub, 12: div, 13: inc, 14: dec, 15: by2, 16: getq, 17: insq, 18: findb, 19: incQ, 20: decQ, 21: pupat, 22: setpat, 23: insn, 24: mvn, 25: deln, 26: intpf, 27: def, 28: topf, 29: dof, 30: oldf, 31: bsjmp, 32: ret, 33: rt0, 34: neg, 35: eq, 36: grt, 37: clear, 38: del, 39: up, 40: ex, 41: jmp1, 42: outn, 43: inn, 44: cpn, 45: xmn, 46: outb, 47: inb, 48: cpnb, 49: xmnb, 50: ip2ds, 51: pip, 52: pushdp, 53: dp2ds, 54: toD, 55: fromD, 56: delD, 57: tsk, 58: c0, 59: c1, 60: c2, 61: c3, 62: c4, 63: c5, 64: exec, 65: qot, 66: nop, 67: fak, 68: fak2, 69: c999, 70: testexp, 71: defnp, 72: calltp, 73: endnp.

Back to OOPS main page