Emulating π-WAM in Dogelog Player

We are currently setting sail to give Dogelog Player a more janus faced backend. Until now we had only one code compilation idea that realizes our Prolog VM. With π-WAM we add a second Prolog VM to the same Prolog system, with the aim to use it for specialized tasks.

The Machine

The concept of a π-WAM embraces a fusion of a processs (π) calculus a Warren Abstract Machine (WAM). Optimized for speed the π-WAM is very primitive and currently only supports the ‘$SEQ’/2 control construct, plus rudimentary 32-bit integer arithmethic and between/3.

The machine itself is a variant of Hack by Nisan and Schocken. While Hack has A and C instructions, we always combine an A and C instruction into a combo. A π-WAM AC instruction has an action field, an object field from A and a relative jump field from C:

INSTR = (ACT, OBJ, REL)

By simply setting REL = 0 the π-WAM will go from the present instruction to the next instruction. Otherwise when REL > 0 or REL < 0 we can let any action continue at relatively computed new program adress. Using relative jumps means also code blocks can be moved around.

The Compiler

The compiler capitalizes that code blocks are relocatable. We adopt a continuation passing style compilation and pass a code block as a continuation to the compilation. The compilation is written in Prolog itself. Given a goal GOAL and a code block CODE, we can use the notation:

CODE’ := [[ GOAL | CODE ]]

To indicate that CODE’ resulted from compiling GOAL with a continuation CODE. The compiler uses Prolog lists to repesent code blocks, and utilizes Prolog DCG to emit code blocks. The rudimentary 32-bit integer arithmethic maps straight away to Hack ALU and conditional jumps.

[[ (GOAL, GOAL2) | CODE ]] := [[ GOAL | [[ GOAL2 | CODE ]] ]]

The above equation shows how we compile $SEQ/2, one could say its just the associativity law. A major challenge was between/3, but we viewed it as Logical Loops as described by Schimpf, so that we implement it without any choice points and basically as a for loop.

The Emulator

To test the compiler, we deviced an emulator that will execute an abstract π-WAM, again written in Prolog itself. We made a further refinement of the instruction set, again inspired by Hack, and let the action field itself be structured into function, mode and condition as follows:

ACT = (FUN, MODE, COND)

The π-WAM does not only do without choice points, it has also no stack and no trail. The later two are both superflous since for the rudimentary 32-bit integer arithmethic the compiler will simply allocate more registers and registers are also used as Prolog variables and just overwritten.

sys_run(PC, CODE, ACCU, STATE) :-
   nth0(PC, CODE, INSTR),
   INSTR = (ACT, OBJ, REL),
   ACT = (FUN, MODE, COND),
   sys_run_get(MODE, OBJ, STATE, VALUE),
   sys_run_fun(FUN, ACCU, VALUE, ACCU2),
   sys_run_set(MODE, OBJ, STATE, ACCU2, STATE2),
   sys_run_jump(COND, ACCU2, REL, REL2),
   PC2 is PC+1+REL2,
   sys_run(PC2, CODE, ACCU2, STATE2).

The above shows the emulator main routine. The parameters are program counter, code block, accumulator and state, i.e. the array of registers. No single fetch and execution logic dispatch as in the usual WAM is found. The execution logic is distributed across get, fun, set and jump.

The Results

The emulator dispatches π-WAM in/1 and out/1 commands to the usual Prolog read and write predicates. This can be used to test the emulator beyond running a statically given goal. Here is a simple utility that computes the square of a given number:

As unorthodox as our machine may sound, it shares many threats with the famous Intel 4004 from 1971. The first commerical CPU developed for electronic calculators, but we want to show more. Here is a backtracking example with two between/3, giving an idea what the π-WAM can do:

Conclusions

Optimized for speed the π-WAM is very primitive. The compiler capitalizes that code blocks are relocatable. The emulator dispatches π-WAM in/1 and out/1 commands to the usual Prolog read and write predicates. We could demonstrate a is/2 example and a between/3 example.

See also:

The Elements of Computing Systems https://mitpress.mit.edu/9780262539807/the-elements-of-computing-systems/