Previous Contents Next

Another Example: The DEC PDP-8

Chapter 11: Another Example: The DEC PDP-8

Unlike the previous example, this is a 'real' computer - albeit an old one. The DEC PDP-8 was one of the first 'minicomputers' - machines substantially smaller than the usual 'mainframe' of the time, and dates from the 1960s. Such machines were typically not very powerful even by the standards of the day, though they were cheap (again by the standards of the day - we would regard them as outrageously expensive).

The PDP-8 was small and cheap enough that a company could dedicate one to a particular task. The PDP-8 ('programmable data processor') was very successful, and went through many versions. The PDP-8 made DEC (Digital Equipment Company) very successful. At one time, it was the second largest computer company in the world (after IBM), though it later declined dramatically. It was purchased by Compaq in the late 1990s, and Compaq is now in turn part of Hewlett-Packard.

11.1. Informal Description

The PDP-8 was a simple machine. It essentially (at least in the version we are concerned with) had only eight instructions. However, one of these (the operate instruction) was actually a collection of simple operations that did not require memory access. We will only actually specify six of the instructions - leaving out the operate and IO instructions. Words in the PDP-8 were only 12 bits long, meaning the memory address space was only 4096 12-bit words. Instructions were all 12 bits long as well. There was a single register - the accumulator, and a single-bit link register (carry bit, essentially) and a program counter. The six instructions are as follows.

A picture of the PDP-8 is shown in fig 1. The PDP-8 is on the right, alongside a later PDP-11 - note the wood grain effect cabinet! (The computers are in the Deutsches Museum, Munich, but I can't blame them for the dodgy image quality.) The PDP-11 was also highly successful, and also had many versions: the one in the picture looks like a fairly early model.

Fig.1. PDP-8 and PDP-11

You can find out more about the PDP-8, and see some more pictures, here.

Note that because we have omitted the operate group of instructions, we are actually missing quite a lot of functionality - for example, the link register (which will typically contain a carry bit) is pretty useless at the moment. We will choose not to implement any more instructions here however.

Notice that there is one instruction that is fairly obviously missing - return from subroutine. This is actually done by making an indirect jump via the first word of the currently-executing subroutine. To see how this works, we need to look at memory addressing.

11.1.1. Structure of Instructions

All PDP-8 instructions are only 12 bits long; and memory addresses are 12 bits long as well. Given that, how do we manage to store a memory address within an instruction, along with an opcode as well? Instructions are actually broken down into four fields.

11.1.2. Addressing Modes

In common with a lot of machines, the memory of the PDP-8 is logically divided into pages. These pages are 128 words long in the PDP-8 - it is not a coincidence that this is exactly the number of words that can be addressed by the seven bit address field. There are 32 such pages in the PDP-8 (12 - 7 = 5, so there are five extra address bits which can be used to address 32 pages), and the first page - called page zero is 'special'. There are four page-based addressing modes.

11.2. Formal Description

We will now look at the formal description of the PDP-8 in Maude. You can find the code here but note that you will need the BINARY module to get it to work. We will now look at each module in turn.

11.2.1. PDP8-WORD

The first module defines the different length words needed and basic operations.

fmod PDP8-WORD is

    protecting BINARY .
    sorts MachineWord OpCode Address .
    subsort MachineWord < Bits .
    subsort OpCode < Bits .
    subsort Address < Bits .

    *** Operators to extract the various
    *** instruction fields
    op opcode : MachineWord -> OpCode .
    op addr : MachineWord -> Address .
    op pagebit : MachineWord -> Bool .
    op indir : MachineWord -> Bool .

    *** Operators for 12-bit addition, 
    *** and the 13th bit of 12-bit addition
    op _+_ : MachineWord MachineWord -> MachineWord .
    op _+13_ : MachineWord MachineWord -> Bit .
    *** AND operator - note we have only *declared*
    *** this operator, not *defined* it. (If you
    *** have done the exercises from Chapter 8, you
    *** will have defined an AND operator that you
    *** can use.)
    op _AND_ : MachineWord MachineWord -> MachineWord .

    vars X Y : MachineWord .
    vars a b c d e f g h i j k l : Bit .
    mb (a b c d e f g h i
        j k l) : MachineWord .       *** 12 bits
    mb (a b c) : OpCode .            *** 3 bits
    mb (a b c d e f g) : Address  .  *** 7 bits

    *** Opcode is always most significant 3 bits
    eq opcode(Y) = bits(Y,11,9) .

    *** Address is always least significant 7 bits
    eq addr(Y) = bits(Y,6,0) .

    *** extract page bit
    ceq pagebit(Y) = true if bits(Y,8,8) == 1 .
    ceq pagebit(Y) = false if bits(Y,8,8) == 0 .

    *** extract indirection bit
    ceq indir(Y) = true if bits(Y,7,7) == 1 .
    ceq indir(Y) = false if bits(Y,7,7) == 0 .

    *** 12-bit addition
    eq X + Y = bits(X ++ Y, 11, 0) .

    *** 13th bit of addition - used to set L flag
    eq X +13 Y = bits(X ++ Y, 12, 12) .

We need three different length words - 12-bit words for data and addresses, three-bit words for opcodes, and seven-bit words for instruction address fields. There are also two one bit fields in instructions (indirection and page bits). However (a) we already have a BIT sort; and (b) it is actually more convenient in this case to use Booleans. These three word lengths are defined using appropriate membership axioms. There is a group of operators to extract fields from instructions (opcode, addr, pagebit and indir); and operations for 12-bit addition. The first one (_+_) computes a 12-bit result, and the second (_+13_) computes the corresponding carry bit. Finally, we have the _AND_ operator, but no definition. This is left out because it was an exercise from an earlier chapter. As a further exercise, you may wish to modify the PDP-8 specification to include a version of your solution to that earlier exercise.

11.2.2. MEM

The memory module is very similar to the one we saw earlier.

fmod MEM is

	protecting PDP8-WORD .
	sort Mem .
	op _[_] : Mem MachineWord -> MachineWord .
	op _[_/_] : Mem MachineWord MachineWord -> Mem .
	var M : Mem .
	vars A I J : MachineWord .

	eq M[A / I][I] = A .
	eq M[A / I][J] = M[J] [owise] .

11.2.3. MEM-OP

Although the MEM module defines basic memory access operations, it does not define the memory addressing modes we saw above. That is done by the next module.

fmod MEM-OP is

    protecting MEM .

    *** Operators for memory addressing,
    *** reading and writing
    op maddr : Mem MachineWord -> MachineWord .
    op mval : Mem MachineWord -> MachineWord .
    op Mw : Mem MachineWord MachineWord -> Mem .

    var M : Mem .
    vars PC VAL : MachineWord .
    ceq maddr(M,PC) = (0 0 0 0 0 addr(M[PC]))
        if pagebit(M[PC]) == false and
                         indir(M[PC]) == false .
    ceq maddr(M,PC) = (bits(PC,11,7) addr(M[PC]))
        if pagebit(M[PC]) == true and
                         indir(M[PC]) == false .
    ceq maddr(M,PC) = M[(0 0 0 0 0 addr(M[PC]))]
        if pagebit(M[PC]) == false and
                         indir(M[PC]) == true .
    ceq maddr(M,PC) = M[(bits(PC,11,7) addr(M[PC]))]
        if pagebit(M[PC]) == true and
                         indir(M[PC]) == true .
    eq mval(M,PC) = M[maddr(M,PC)] .
    eq Mw(M,PC,VAL) = M[VAL / maddr(M,PC)] .

There are three operators defined here: maddr, which computes a memory address; mval which is used to look up a word in memory (and uses maddr); and Mw which is used to write a word to memory (and also uses maddr). Here we should point out that maddr is only actually needed within the MEM-OP module, and ideally we would like to make it hidden - not visible outside (like private in Java and C#). However, we do not have a mechanism for that in Maude.

11.2.4. PDP8-STATE

The next module defines the PDP-8 state, and operators to extract the various parts. There are four state elements: a memory; a program counter; the accumulator; and the link register.

fmod PDP8-STATE is

    protecting MEM-OP .
    sorts PDP8State .

    *** operator to construct a PDP-8 state from
    *** component parts
    op (_,_,_,_) : MachineWord MachineWord Bit
        Mem -> PDP8State .

    *** operators to extract fields from a
    *** PDP-8 state
    op a_ : PDP8State -> MachineWord .
    op pc_ : PDP8State -> MachineWord .
    op l_ : PDP8State -> Bit .
    op mem_ : PDP8State -> Mem .
    var M : Mem .
    vars A PC : MachineWord .
    var L : Bit .
    eq a(A,PC,L,M) = A .
    eq pc(A,PC,L,M) = PC .
    eq l(A,PC,L,M) = L .
    eq mem(A,PC,L,M) = M .

11.2.5. PDP8

The final module defines the iterated map function PDP8 and the next-state function next (as well as an auxilliary function skip).

fmod PDP8 is

    protecting PDP8-STATE .

    *** State and Next-State functions
    op PDP8 : MachineInt PDP8State -> PDP8State .
    op next : PDP8State -> PDP8State .
    *** Constants
    ops ONE TWO : -> MachineWord .

    *** Ancilliary function used in conditional
    *** instruction
    op skip : Mem MachineWord -> MachineWord .

    vars A PC : MachineWord .
    var L : Bit .
    var M : Mem .
    var T : MachineInt .
    *** Define constants
    eq ONE = (0 0 0 0 0 0 0 0 0 0 0 1) .
    eq TWO = (0 0 0 0 0 0 0 0 0 0 1 0) .

    *** Define the State function
    eq PDP8(0,(A,PC,L,M)) = (A,PC,L,M) .
    eq PDP8(T,(A,PC,L,M)) =
        next(PDP8(T - 1,(A,PC,L,M))) [owise] .

    *** Define the ancilliary skip function
    eq skip(M,PC) = if mval(M,PC) ==
                      (1 1 1 1 1 1 1 1 1 1 1 1) then
                     PC + TWO else PC + ONE fi .

    *** Now we do the various cases of the Next-State
    *** function

    *** AND
    ceq next((A,PC,L,M)) =
            (A AND mval(M,PC),PC + ONE,L,M)
        if opcode(M[PC]) == 0 0 0 .

    *** TAD
    ceq next((A,PC,L,M)) =
            (A + mval(M,PC),PC + ONE, A +13 mval(M,PC),M)
        if opcode(M[PC]) == 0 0 1 .

    *** ISZ
    ceq next((A,PC,L,M)) =
            (A, skip(M,PC), L, Mw(M,PC,mval(M,PC) + ONE))
        if opcode(M[PC]) == 0 1 0 .

    *** DCA
    ceq next((A,PC,L,M)) =
            (0 0 0 0 0 0 0 0 0 0 0 0,PC + ONE, L,
        if opcode(M[PC]) == 0 1 1 .
    *** JSR
    ceq next((A,PC,L,M)) =
            (A, mval(M,PC) + 1, L, Mw(M,PC,PC + ONE))
        if opcode(M[PC]) == 1 0 0 .
    *** JMP
    ceq next((A,PC,L,M)) = (A, mval(M,PC), L, M)
        if opcode(M[PC]) == 1 0 1 .

11.3. Some Exercises

There are no example programs for the PDP-8. Write a module containing one, and run it. Also, because have omitted the last two instructions, the PDP8 module has no defined behaviour for opcode values of 1 1 0 and 1 1 1. In a real machine, attempting to run undefined instructions will typically result in some kind of exception handling behaviour. In the case of a simple machine like the PDP-8, this might be to jump to the top-most word of memory. Add an equation or equations to the PDP8 module to get it to do that.

Previous Contents Next