The Peculiar Case of a Self-Referential Computer Instruction (DEC PDP-7, 1964)

Or, how to lift Kurt Gödel’s hat by −0.

A recent discussion on the Retro Computing Forum turned my interest towards the DEC PDP-7 in general and it’s peculiar lack of a dedicated instruction for two’s complement subtraction (or, that is, subtraction at all) in the absence of a two’s complement negate instruction. Therefore, you had to do something like this, in order to achieve a subtraction:

ONE,  01       /a constant (1)
      lac B    /load subtrahend
      cma      /1's complement
      tad ONE  /add 1, now 2's complement
      tad A    /-B + A => AC

Now, Will Cooke (user @bdk), who had dug quite deeply into PDP-7 code in the context of the B language and the origins of UNIX, pointed out a common shortcut to this:

(…) the LAW (Load Accumulator With) instruction was used as something of a trick to subtract a constant. The opcode for LAW is:

76xxxx = 111 11x xxx xxx xxx xxx

The entire binary representation of that instruction is loaded into the accumulator. So if the instruction was, say,

111 111 111 111 111 111

which is a valid LAW instruction, the accumulator would then hold:

AC = 111 111 111 111 111 111

Which is -1 in two’s complement.
Follow that with

TAD B

and AC would then hold B-1
Any negative constant up to -8192 (…) could be “added” to AC to perform an effective subtraction.
That trick was used a lot in the early UNIX code.

Now, how does this work?

On the PDP-1, with which I’m much more familiar, there was an instruction “LAW-N” for loading negative values in one’s complement. Like the PDP-7, the PDP-1 was an 18-bit machine and in most terms the predecessor to the PDP-7, especially the PDP-1D timesharing version. (The PDP-7 is actually much a cost reduced — at least in its basic configuration —, but faster, because later, version of the PDP-1D. Then, computer speeds were dictated mostly by core memory cycle times, which improved considerably in the early 1960s. A typical PDP instruction took one memory cycle, if this involves memory access, add another one, if there’s indirect address lookup, add yet onother one.)
So “LAW N” loads an unsigned (positive) 12-bit value N, which is directly encoded in the operand part of the instruction, into the acumulator. This is restricted to 12 bits, since the instruction code takes the first 5 bits of the instruction, followed by the sixth bit (bit 5 in DEC nomenclature) indicating indirect addressing or other modifications (the defer bit or i-bit), leaving 12 bits for the operand. If the i-bit is set, LAW loads the one’s complement instead. Thus, “LAW i 0” or just “LAW i” loads negative zero or 0777777, which is -1 in two’s complement.

Now, the PDP-7 lacks such a simple inversion as provided by the PDP-1’s “LAW-N” instruction. Instead, we are meant to perform some obscure arithmetics in order to achieve the same. Quoting the PDP-7 Users Handbook (Digital Equipment Corporation, Maynard, MA, 1965, F-75, pp. 37/38):

(Note: all values are octal.)

Mnemonic    Octal    Machine             Operation
 Symbol     Code     Cycles              Executed
--------  --------  --------             ---------
  LAW      76XXXX      1       Load Accumulator With.  The AC is loaded
                               with the entire instruction word contained
                               in the MB. [MB: Memory Buffer; N.L.]
                               MB => AC
    		

(…) As used in these examples, only bits 5–17 of the LAW instruction are regarded as the addresses, characters [i.e. constant operands; N.L.], and counts, although the entire word is contained in AC. (…)

So the instruction loads the entire memory buffer containing the instruction into the accumulator. Normally, only the operand part is used for any other instructions, performing much as on the PDP-1, but things are a bit different, if we were to add to this. And things become even quirkier, if we want to load a negative number:

To initialze a core memory location with a negative number, where the complete word (bits 0-17) is to be regarded, it is necessary to take the 1’s complement of the number and then subtract the octal code 760000. [The opcode of LAW; N.L.] For example, if the desired count is 755, memory location Y is loaded with -755 as follows. The 1’s complement of 000755 is 777022, which can be represented as the sum of 760000 and 17023. Since 760000 is the operation code for LAW, the resulting program sequence is used:

LAW    17023
DAC    Y

In actual practice this operation is seldom used, since the PDP-7 Symbolic Assembler has defined the special character LAM to load negative numbers for counting or masking purposes. The character LAM is a special case of the LAW instruction, equal to LAW 17777.

So, in essence, loading a negative value N is equalent to

LAW 17777 + N

and, if N is zero, we load -0 in one’s complement, which is -1 in two’s complement. — This isn’t much dissimilar from the PDP-1, but for entirely unrelated reasons. (On the PDP-7, this happens to be the value in MB anyway.)

Now have a look at the instruction code:

LAW 17777

= 0760000 + 017777

= 0777777

= %111 111 111 111 111 111

= -0[1’s complement]

This is an instruction, which not only encodes itself, but operationally also loads itself! In assembler, we could just write “-0”, as well.

Take that, Gödel! ;-)

By which we may also prove that a PDP-7 program is consistent and free of errors, as long as it solely consists of “load -0” instructions…

Norbert Landsteiner,
Vienna, 2019-07-13