🚀 go-pugleaf

This will probably get buried in the Alpha discussions, but . . .

> So here is a challenge: design a machine that uses no more than 4 bits
> per instruction (including operand fields), is Turing complete, not
> terribly inefficient and which can be built using far less hardware
> than current microprocessors. The latter would make it suitable for
> massively parallel systems.

( This is a modification of Doug Jones' (jones@herky.cs.uiowa.edu) work )

Note that this processor is possible, but would work the blazes out of a
compiler or assembly programmer. Also, I am positive that a good FORTH
hacker could come up with a more complete (and faster) set of macros.

Notation:  X = top word on stack
           Y = second word on stack

Opcodes:

NOP     0000    No op
ZERO    0001    X := X << 1           (zero fill)
ONE     0010    X := (X << 1) + 1     (ones fill)
DUP     0011    push(X)        (duplicate top word on stack)
STORE   0100    M[X] := Y; pop; pop;
LOAD    0101    X := M[X];
ADD     0110    Y := Y+X; pop;
BNEG    0111    if (X<0) then PC := Y; endif; pop; pop;
SWAP    1000    exch(X,Y)      (exchange top two words on stack)
OR      1001    Y := Y | X; pop;
PUSHZ   1010    push(0)
NOT     1011    X := !X;       (or ~X)
AND     1100    Y := Y & X; pop;
POP     1101    pop(X)         (removes top word on stack)
BZERO   1110    if (X=0) then PC := Y; endif; pop; pop;
BPOS    1111    if (X>0) then PC := Y; endif; pop; pop;


Macros:

NOT allows one's complement with the macro NOT;PUSHZ;ONE;ADD;
    this allows SUB (Y-X) to be done by NOT;PUSHZ;ONE;ADD;ADD;
CALL,BRA,JMP can be done using {push address};PUSHZ;BZERO;
INCR = PUSHZ;ONE;ADD;
DECR = PUSHZ;NOT;ADD;
XOR can be simulated (using $00) by (X|Y) & !(X&Y)
    PUSHZ;STORE;DUP;PUSHZ;LOAD;AND;NOT;SWAP;PUSHZ;LOAD;OR;AND;
if (X==Y) then {}
    NOT;PUSHZ;ONE;ADD;ADD;{push address};SWAP;BZERO;
if (X>Y) then {}
    NOT;PUSHZ;ONE;ADD;ADD;{push address};SWAP;BNEG;
if (X<Y) then {}
    NOT;PUSHZ;ONE;ADD;ADD;{push address};SWAP;BPOS;

simple loop - do {} until (--x == 0);
        {push count}
    label1: loop statements
        more statements (leaving count on top of stack)
        PUSHZ;NOT;ADD;DUP;
        {push address of label1}
        SWAP;BPOS;

simple loop -  do while (x-- >0) {};
        {push count}
    label1: DUP;
        {push end}
        SWAP;BZERO;
        statements (leaving count on top of stack)
        PUSHZ;NOT;ADD;
        {push label1}
        PUSHZ;BZERO;
    end: POP;

simple multiply by addition - (uses $00)
        PUSHZ;STORE;        (store X)
        PUSHZ;SWAP;DUP;     ( Y Y 0 . . .)
        {push end}
        SWAP;BZERO;         ( Y was zero )
    label1: SWAP;
        PUSHZ;LOAD;ADD;     ( add X to sum )
        SWAP;PUSHZ;NOT;ADD; ( decriment Y )
        DUP;{push label1}
        SWAP;BPOS;
    end: POP;               (remove Y)
        (leaves result on stack)

division (with remainder) could be done similarly using subtraction and
a counter.

(I'm not positive about this code)
killer multiply by bit test and add - (uses $00-$02)
        PUSHZ;STORE;                (store X $00)
        DUP;PUSHZ;ONE;ZERO;STORE;   (store Y $02)
        PUSHZ;ONE;DUP;DUP;STORE;    (store test bit $01)
        AND;                        (test bit with Y)
        PUSHZ;SWAP;                 (start with zero sum)
        {push label2}
        SWAP;BZERO;                 (if zero, nothing)
        POP;PUSHZ;LOAD;             (pop zero,load X)
    label2:
        PUSHZ;DUP;LOAD;ZERO;SWAP;STORE;
                (left shift X)
        PUSHZ;ONE;ZERO;LOAD;        (load Y)
        PUSHZ;ONE;DUP;DUP;LOAD;ZERO;SWAP;STORE;LOAD;AND;
                (load test bit, rotate, store, test)
        {push label3}
        SWAP;BZERO;                 (if zero, nothing)
        PUSHZ;LOAD;ADD;             (add shifted X)
    label3:{push label2};
        PUSHZ;ONE;LOAD;             (load test bit)
        BPOS;                       (loop until test bit is MSB)
        (leaves result on stack)


Possible Deletions:

POP could be done by
    PUSHZ;ONE;BZERO  |  PUSHZ;BNEG;  |  PUSHZ;BPOS;
BNEG could be eliminated by exclusion and good code
    !(BZERO | BPOS) == BNEG
SWAP could be done (using $00 and $01) by
    PUSHZ;STORE;PUSHZ;ONE;STORE;PUSHZ;LOAD;PUSHZ;ONE;LOAD
    but SWAP is far too useful
DUP could be done (using $00) by
    PUSHZ;STORE;PUSHZ;LOAD;PUSHZ;LOAD;
    but DUP is also too useful


Possible Additions: (to make life easier)
    MULT (useful, faster, but more difficult hardware)
    SUB  (could be useful for compares and divides)
    PUSHPC
    LSR


Implementation:

BPOS means high bit clear, and non zero
BNEG mean high bit set

If the word size is N bits, it takes N instructions, in the worst case,
to push an N bit constant.  101010... is the worst case.
 
Instructions are packed 2 per byte, and labels must be word aligned.
NOP instructions are used to align labels to a word boundary.

Right shift doesn't exist.
Arrays with arbitrary indices are difficult, but vector operations on
arrays are very friendly. Procedure calls are either inline or
absolutely addressed with either caller or callee cleanup. Routines can
handle an RTS by using a PUSHZ;BZERO;, but calling routines will have to
have their own addresses compiled in (no easy access to PC). Returned
values will have to be stored in memory or on the top of the stack.