Introduction

On my PDP-8 Assembly Language Studio page I describe why the mid-1960’s PDP-8 minicomputer from Digital Equipment Corporation had an extremely minimal instruction set.

With a 12-bit address space, the earliest models of the PDP-8 were limited to 4,096 12-bit words of hand-threaded magnetic core random access memory (RAM).

Modern software emulators exist for the constrained architecture of the PDP-8. These emulators provide an interesting sandbox for experimenting with resource constrained algorithms.

This article describe an implementation of John Conway’s Life cellular automaton which was invented while PDP-8 minicomputers were still popular as a lower cost alternative to time-shared mainframes.

Why constrain yourself, you may ask? Perhaps we can take a tiny bit of inspiration from this famous quotation:

  • “We choose to go to the moon in this decade and do the other things. Not because they are easy, but because they are hard.” — John F. Kennedy

Our Algorithm

This implementation of Conway’s Life, along with a complete PDP-8 emulation environment for running it, are available on GitHub: https://github.com/rrutt/PDP8.

The algorithm implemented by our Conway.pal program is described in Chapter 17 of Michael Abrash’s Graphics Programming Black Book. In particular, see Listing 17.5

We don’t have enough memory available to implement the more advanced algorithms defined in Chapter 18 of Michael Abrash’s book. In fact, we are so tight on memory that we have to pack two generations of the cell grid into one array. We use the right (“low”) 6 bits of each cell word to store the “live neighbor count” in the rightmost 4 bits, and the “live or dead” bit as the 5th bit from the right, for the current generation. We store the same information for the “next generation” in the left (“high”) 6 bits of each cell word.

Prior to processing a generation, the 6 bits from the left half-word (the “next generation”) are “cloned” to the right 6 bits (the “current generation”) of each grid cell. The right half-word is then used to update the terminal display for the cell grid.

With this storage format, a dead cell with no live neighbors contains all zero bits. These cells are quickly bypassed in the cell scanning loop, as suggested by Michael Abrash. This improves the performance of our algorithm compared to a more naive approach.

When the cell-scanning loop encounters a non-zero word, it evaluates the “neighbor count” and “live or dead” bit in the right half-word. The automaton rules are applied to these two values and a the logic branches to one of three options:

  • The cell remains live or dead, so the memory word is left unchanged and the next cell is scanned.
  • A dead cell is “born”; the “live bit” in the left half-word is turned on and the “live neighbor count” is incremented in the left half-word of all neighboring cells.
  • A live cell “dies”; the “live bit” in the left half-word is turned off and the “live neighbor count” is decremented in the left half-word of all neighboring cells.

Here is the terminal display for the transition of a “glider” as it is processed from Generation 4 to Generation 5:

Conway_Glider_display4

Conway_Glider_display5

Here are the corresponding memory display images for the same transition:

Conway_Gliger_debug_4a

In this first image, Generation 4 has just been computed in the left half-words. based on Generation 3’s state in the right half-words. Memory address 2032 contains octal 2103. The left half 21 octal is 010001 binary, or 0 ignored sign bit, 1 “live bit”, 0001 “neighbor count”.

Conway_Gliger_debug_4b

In this second image, the left “next generation” half-words have been cloned to the right “current generation” half-words.

Conway_Gliger_debug_5a

In this third image, Generation 5 has been computed in the left half-words. Memory address 2032 now contains octal 0221. The right half 21 octal is the prior Generation 4 value. The left half 02 octal is 000010 binary, or 0 ignored sign bit, 0 “dead bit”, 0010 “neighbor count” (2 live neighbors).

Conway_Gliger_debug_5b

In this last image, the left “next generation” half-words have again been cloned to the right “current generation” half-words.

Grid Cell Wrap-Around

When running in a limited grid space, most implementations of Conway’s Life implemented a wrap-around geometry. Our implementation uses these wrap-around rules for processing “live neighbor counts”:

  • The neighbor to the right of the right-most cell in a row is the left-most cell in the next row. This “spiral wrap” effect results automatically when the neighbor-cell offsets are applied to the “linearized” two-dimensional grid cell array.
  • The neighbor to the top of the top-most cell in a column is the bottom-most cell in the same column. This requires special wrap rows of extra cells to be allocated before and after the main grid cell array. These wrap row cells never have their “live bit” set; they only contain “neighbor cell count” values. At the end of each generation processing iteration, these wrap row neighbor counts, which may be negative, are added to the corresponding cells in the main grid array. The wrap row cells are then cleared prior to processing the next generation.
  • Two extra special wrap cells are also provided for the “northwest” (upper left) and “southeast” (lower right) corners of the cell grid. These are required to handle the special logic for the “spiral wrap” effect of the right-to-left wrap rule.

Understanding the PDP-8 Assembly Language Source Code

The following sections provide insight into the primitive but powerful world of PDP-8 Assembly Language source code.

One note on the PAL source: The “rest of the line is a comment” symbol is a single slash (/). However, a pair of slashes are used here to allow NotePad++ to be set to C# color-coding conventions.

The PDP-8 Assembly Language source code is available from GitHub as Conway.pal with a formatted assembler listing at Conway.lst

Defining symbolic constants

Our source code starts with some assembler symbol definitions. These symbols will be expanded directly into the matching bit patterns as part of machine instructions defined later in our source code. Here are the decimal constants for the size of our grid. The PAL assembler can do addition and subtraction of assembly-time symbolic constants, but not multiplication. Thus, we need to pre-compute the value for numCells as the product of numRows and numCols.

// Assembly-time Constants.
//
// Grid Size.
//
// Grid dimensions for use with PDP-8 emulator debug memory display.
numRows=12d
numCols=8d
numCells=96d

To avoid adding run-time increment and decrement logic to key portions of our code, we have the assembler pre-compute “plus one” and “minus one” values:

numColP1=numCols+1
numColM1=numCols-1
numCellM1=numCells-1

We also supply some ASCII character codes:

//
// ASCII Character Codes.
//
asciiEsc=27d // Escape
asciiSpace=32d // Space (Blank)
asciiCR=13d // Carriage Return
asciiLF=10d // Line Feed

Here are two octal constants to increment or decrement the “live neighbor count” values that we store in the left half-word of our grid array of 12-bit words.

incrNbrCount=0100 // Increment neighber count in high half word.
decrNbrCount=-incrNbrCount // Decrement neighber count in high half word.

Defining memory constants

PDP-8 instructions only contain 7 bits of the 12-bit address space. 7 bits can only address 128 12-bit words (128 = 0200 octal). This requires the memory to be treated as 32 separate “pages” of 128 words each.

Each memory instruction also contains one more bit to indicate whether the address is on the same page as the instruction or on the first page of memory. This means the first page of PDP-8 memory, defined as all addresses less than 0200 octal, is always directly addressable from any other page, and can be treated as a set of memory-based registers. We use this portion of memory to define global constant values that will later be loaded or added into the single accumulator register (AC). Here are our definitions:

//
// Bit Masks.
//
mNbrCount, 0017 // Right 4 bits to store 0 thru 8 as Neighbor Count.
mCellOnLo, 0020 // Cell marked "on" in lo half (5th bit from right).
mCellOnHi, 2000 // Cell marked "on" in hi half.
mCellOffHi, 5777 // Clear "on" bit in hi half.
mLoHalf, 0077 // Right 6 bits.
mHiHalf, 7700 // Left 6 bits.
mRandBits, 0017 // Right 4 bits for random # (0 to 15).
mLoOctalDigit, 0007 // Right-most octal digit.
//
// Memory Constants.
//
cMinusOne, -1
cMinusTwo, -2
cMinusThree, -3
cNumCols, numCols
cNumCells, numCells
//
// String and Character Constants.
//
szClrScreen, . // VT-100 Clear Screen.
  asciiEsc;'[2J'
  0
szCrsrHome, . // VT-100 Cursor Home.
  asciiEsc;'[0;0H'
  0
szSeed, . // Random seed display message.
  '  Seed: '
  0
szGeneration, . // Generation display message.
  '  Generation: '
  0
szNewLine, . // Carriage-Return/Line-Feed combination.
  asciiCR;asciiLF
  0
charSpace, asciiSpace
charZero, '0'
charStar, '*'
//
// Neighbor Cell Offsets.
//
cellOffsets, . // Base address to load into auto-index register.
coNW, -numColP1
coN, -numCols
coNE, -numColM1
coE, +1
coSE, numColP1
coS, numCols
coSW, numColM1
coW, -1
coSelf, 0 // Terminate loop.

Indirect addressing pointers

Each memory instruction contains yet another bit to indicate if the directly referenced 7-bit address, interpreted as on the first memory page or the instruction’s memory page, is the “final destination”, or if it contains the full 12-bit address of the desired destination.

The first memory page also provides a useful area to store indirect addressing pointers to support this feature. Here are address pointers to our grid array:

//
// Array Pointers.
//
pNWWrapCell, NWWrapCell // Extra "northwest" wrap cell.
pTopWrapRow, CellBuffer-1 // Preceding address for auto-indexing to top wrap row.
pGridCells, CellBuffer+numColM1 // Preceding address for actual cell grid (after top wrap row).
pBotWrapRow, CellBuffer+numCols+numCellM1 // Preceding address for bottom wrap row (after top wrap row and grid).
pSEWrapCell, CellBuffer+numCols+numCells+numCols // Extra "southeast" wrap cell (after top wrap row, cell grid, and bottom wrap row.)
//
pNWPairCell, NWWrapCell+numCells // Pair for "northwest" wrap cell (just before top pair row).
pTopPairRow, CellBuffer+numCellM1 // Preceding address for pair for top wrap row (just after NW pair).
pBotPairRow, CellBuffer+numColM1 // Preceding address for pair for bottom wrap row (same as grid).
pSEPairCell, CellBuffer+numCols+numCols // Pair for "southwest" wrap cell (just after bottom pair row).

The actual memory addresses referenced by these indirect-addressing pointers are define at the end of our source code at base address 2007 octal:

//
// Cell Array Pages.
//
*2007 // Could be *2000, but *2007 aligns better in the PDP-8 emulator debug display.
NWWrapCell, 0 // Extra "northwest" wrap cell.
CellBuffer, 0 // Array of top wrap row, cell grid, bottom wrap row, and "southeast" wrap cell.

Subroutine pointers

The limited instruction set of the PDP-8 includes support for “jump to and then return” subroutines. The “jump to subroutine” (JMS) instruction stores the return address (the instruction after the JMS instruction) at the targeted destination, and then sets the program counter to resume execution at the instruction after the subroutine entry point address. Later, the subroutine returns by performing an indirect-addressing jump to its own entry point address.

Due to the 7-bit local addressing default, subroutines are usually written to fit on a single 128-word page. As a result, most subroutine calls occur across pages. To keep this simple, we define a vector of subroutine address pointers on the first page of memory (the “register” area):

//
// Subroutine Pointers.
//
SkipIfChar, srSkipIfChar
GetChar, srGetChar
PutChar, srPutChar
PutString, srPutString
PutNewLine, srPutNewLine
PutOctal, srPutOctal
SetRand, srSetRand
GetRand, srGetRand
EmuMUY, srEmuMUY
ClrGeneration, srClrGeneration
LoadSeed, srLoadSeed
ShowSeedAndGeneration, srShowSeedAndGeneration
ClrWrap, srClrWrap
ClrGrid, srClrGrid
RandomizeGrid, srRandomizeGrid
InitGrid, srInitGrid
ShowGrid, srShowGrid
ProcessGeneration, srProcessGeneration
CloneGrid, srCloneGrid
CloneCell, srCloneCell
CellBorn, srCellBorn
CellDied, srCellDied
CellNeighbors, srCellNeighbors
ProcWrap, srProcWrap

Global variables

We also use the first page “register” area to define global mutable variables that can be directly addressed by any instruction:

//
// Global Variables.
//
gGeneration, 0
gSeed, 0

Main entry point and loop

By convention, most PDP-8 programs start at the first instruction word of the second page of memory, at octal address 0200. Here is our main loop:

It consists mostly of indirect subroutine invocations (JMS I) and branching/looping jump instructions (JMP).

//
// Main Code Page.
//
*0200
Main, cla cll // Clear AC and Link.
  tls / Wake Up Printer (terminal display)
  jms i LoadSeed
  jms i ClrGeneration  
  jms i ShowSeedAndGeneration
  jms i ClrWrap
  jms i ClrGrid
  jms i InitGrid 
  jms i CloneGrid
  jms i ShowGrid
  jms i SkipIfChar
    jmp MainLoop
  jmp MainPause
MainLoop, jms i ProcessGeneration
  jms i CloneGrid
  jms i ShowGrid
  jms i SkipIfChar
    jmp MainLoop
MainPause, hlt // Halt.
  jmp MainLoop // Resume loop if user continues via front-panel.

End, cla cll // Clear AC and Link.
  hlt // Halt.
  jmp Main // Restart if user continues via front panel.

A simple subroutine

Here is our first subroutine that reads the toggle switch settings from the front panel of the PDP-8 computer as a value to store in the gSeed global variable location on the first page of memory. Notice how the entry point word is reserved with a 0 value to allow room to receive the return address from the caller’s JMS instruction. Also note how the subroutine returns using an indirect jump (JMP I) to the entry point word.

// Subroutine: Load Seed from Switch Register.
// Parameter: Switch Register.
// Updates: Global value gSeed.
//
srLoadSeed, 0
  cla cll // Clear AC and Link.
  osr // Or the Switch Register bits into AC.
  dca gSeed // Save random seed.
  jmp i srLoadSeed // Return

A subroutine with a parameter

One basic way to pass a single parameter to a subroutine is to load the value into the accumulator register (AC) before calling the subroutine. Another way, which is especially handy for passing constant parameter values, is to store the parameter in the word after the calling JMS instruction:

  jms i CellNeighbors // Increment cell neighbor counts
    incrNbrCount

Here is the subroutine that can increment or decrement “live neighbor” counts for all grid cells surrounding a cell that was just “born” or has just “died”. Notice how the return address value is incremented to “skip-return” past the parameter value word by using an ISZ incrementing instruction. Also note the declaration of some “local variables” on the same memory page after the jmp CNLoop looping instruction.

// Subroutine: Cell Neighbor count update.
// Parameter: AC contains address of cell, word after call contains increment or decrement constant.
// Registers: air7
//
srCellNeighbors, 0
  dca CNCellAddr
  tad i srCellNeighbors // Load increment or decrement.
  dca CNIncrDecr
  isz srCellNeighbors // Prepare for skip-return.
  tad cellOffsets // Load index register with address before neighbor cell offsets list.
  dca air7
CNLoop, tad i air7 // Load offset to a neighbor cell.
  sna // Skip if non-zero
    jmp i srCellNeighbors // Else, return if offset was zero.
  tad CNCellAddr // Load address of current cell.
  dca CNNbrAddr // And save as neighbor cell address.
  tad i CNNbrAddr // Load neighbor cell current state.
  tad CNIncrDecr // And increment or decrement that cell's neighbor count (hi half word).
  dca i CNNbrAddr // And store back to grid cell.
  jmp CNLoop
CNCellAddr, 0
CNNbrAddr, 0
CNIncrDecr, 0

Branching

A typical construct to allow conditional brancing in low-level machine instructions is to implement a conditional skip rather than a conditional jump. This avoids having to hold a memory value comparison address and a jump destination address in the same instruction. In this sequence of instructions, the SkipIfChar subroutine has been written to return to either the next address (the normal return point) or the next address plus one, depending on whether a keyboard character has been pressed. If no character has been pressed, the jmp MainLoop executes. Otherwise, that instruction is skipped and the jmp MainPause occurs.

  jms i SkipIfChar
    jmp MainLoop
  jmp MainPause

Here is the SkipIfChar subroutine. Notice how the isz srSkipIfChar return address increment only occurs in one code path.

// Subroutine: Skip If Character ready.
// Check for keyboard character. 
// Skip-return if present, returning the character in the AC. 
// Else just return.
// 
srSkipIfChar, 0
  ksf // Is Keyboard Flag Raised?
    jmp i srSkipIfChar // No, just return.
  krb // Yes - Read Character to AC.
  isz srSkipIfChar // Increment return address.
  jmp i srSkipIfChar // Return to "skip" address.

Further Information

Thanks to the impressive power of modern computers, Conway’s life continues to attract active research and experimentation. Check out the LifeWiki at ConwayLife.com for a vast repository of information.

Advertisements