🚀 go-pugleaf

> 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.

I proposed an idea that might help in my Computer Architecture News paper
entitled "the Minimal CISC" (June 1988).  In that paper, I proposed a
not-too inefficient machine using only 3 bits per instruction (operand
fields included).  Here's a 4 bit per instruction improvement that's not
half bad (you can do quite a bit better if you let some 4 bit instructions
interpret the next nibble as a 4 bit operand:

Notation:  X = top word on stack
           Y = word under top word on stack
	   push(t) -- push word with value T on stack
	   pop -- pop one word off stack

NOP	0000 No op                                \
ZERO    0001 X := X << 1                           \
ONE     0010 X := (X << 1) + 1                      | This much is exactly
DUP     0011 push(X) (duplicates top word on stack) \ my minimal CISC
STORE   0100 M[Y] := X; pop; pop;                   / instruction set.
LOAD    0101 X := M[X];                             |
SUB     0110 Y := Y-X; pop;                        /
BNEG    0111 if Y<0 then PC := X; endif; pop; pop;/
ZZERO	0000 X := X << 2;                         \
OONE    0001 X := (X << 2) + 3;                    \
PUSHZ   0010 push(0);                               |
NEG     0011 X := -X;                               \
AND     0100 Y := Y & X; pop;                       /
CALL    0101 swap(PC,X);                            |
BZERO   0110 if Y=0 then PC := X; endif; pop; pop; /
BPOS    0111 if Y>0 then PC := X; endif; pop; pop;/

PUSHZ = DUP;DUP;SUB, but we add it for fast pushing of small constants;
ZZERO = ZERO;ZERO, but we add it for faster pushing of constants;
OONE  = ONE;ONE, but we add it for the same reason.
NEG is added so that ADD can be done by the macro NEG;SUB;
NEG allows one's complement with the macro NEG;PUSHZ;ONE;SUB;
Unconditional branch is done with PUSHZ;{push address};BZERO;

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.

				Doug Jones
				jones@herky.cs.uiowa.edu