From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
Subject: Re: MINIMUM instruction set
Date: Wed, 11 Nov 1992 14:43:04 GMT
Organization: University of Iowa, Iowa City, IA, USA

From article <1992Nov10.235849.19192@fcom.cc.utah.edu>, by val@news.ccutah.edu (Val Kartchner):
> I've heard that it is possible to implement all programming languages with
> seven instructions.

What is an instruction?  Ignoring I/O, the following CISC instruction does
the job:

	DB <op1> <op2> <op3>
		Decrement <op1> by <op2> and branch to <op3> if the result
		is less than zero.  All operand fields address memory.

This can be modified to a tighter form:

        DAB <op1> <op2>
		Decrement <op1> by the value in the accumulator, leaving the
		result in both the accumulator and <op1>; branch to <op2>
		if the result is negative.

		To load the accumulator, first zero it, then decrement
		something by it.

		To zero the accumulator, decrement the same location twice
		in a row (leaving both AC and the location zeroed).

		To add, first negate then subtract.

		To negate, subtract from zero.

		To store, first zero the destination memory location and
		negate the value to be stored, then store it.

Further modifications are possible.  For example, if the program counter
is memory-mapped, then this instruction can be reduced to a one address
instruction:

	DA <op1>
		Decrement <op1> by the value in the accumulator, leaving
		the result in the accumulator and <op1>.

		To branch, decrement the program counter by the negated
		relative address of the destination.

		Conditional branches are tricky.

Even though the above approaches all reduce the instruction set to a single
instruction, the instruction is complex -- these are not RISC machines.

An alternate approach to this is the "move machine" or Ultimate RISC.  Here,
the CPU has one instruction set and no ALU or accumulator.

	MOV <op1> <op2>
		Move <op1> to <op2>.

		To do arithmetic, add a memory mapped accumulator and a
		memory mapped ALU.  The only essential operations are
		load and store accumulator, subtract from accumulator,
		and inspect sign of accumulator

		To branch, make the program counter memory mapped and
		move the destination address to it.

		To do a conditional branch, move the sign of the accumulator
		to the accumulator, subtract the destination address
		(producing one of two addresses), and move that to the
		program counter.

The 7 or 8 instruction minimum you suggest could come from the DEC PDP-8,
a machine that had only a 3 bit op-code field (see alt.sys.pdp8 for more
than you ever wanted to know about that system), or it could come from
my Minimal CISC, a stack machine with the following instructions:

	NOP     Do nothing.
	S1	Shift a 1 into the stack top,
	S0	Shift a 0 into the stack top,
			A sequence of S1 and S0 instructions will shift
			any constant into the word on the stack top.
	DUP	Duplicate the stack top.
	POP	Store the value in the stack top in the memory location
			pointed to by the value below it on the stack,
			then pop both values from the stack.
	FETCH	Replace the value on the stack top by the memory location
			it points to.
	SUB	Subtract the top element of the stack from the element
			below it, popping both and pushing the difference.
	BRNEG	Branch to the address on the stack top if the value below
			it is negative.  Always pop both whether or not
			the branch is taken.

Note that these instructions have no operand field, so each instruction
is exactly 3 bits.  They can be packed 5 to a 16 bit word, for example.
Branches are always to a word boundary, so NOP instructions are frequently
needed to pad out to a word boundary.

					Doug Jones
					jones@cs.uiowa.edu