IBM 7094 Cheat Sheet

Russ Cox
rsc@swtch.com
November 2000; updated January 2007 (sic)

The IBM 7094 was a 1960s-era mainframe. Tony Van Vleck has documented its use in the CTSS system. Ken Thompson was working on an IBM 7094 running CTSS when he wrote his regular expression compiler, described in:

Ken Thompson, “Regular expression search algorithm,” Communications of the ACM 11(6) (June 1968), pp. 419–422. http://doi.acm.org/10.1145/363347.363387

Thompson's paper describes an algorithm that translates a regular expression into IBM 7094 machine code. This web page describes the IBM 7094 and its instructions only as far as needed to understand the paper. Elsewhere on this site you can find a C-based reimplementation of Thompson's approach.

Machine state

Memory (M[addr]): 32,768 36-bit words in main core. Word-addressed.

38-bit Accumulator (AC): 35-bit magnitude, sign bit, extra bit for unsigned words, carry bit.

Seven 15-bit index registers (XR[index]): usually hold (word-addressed) pointers. Index ranges from 1 to 7; there is no XR[0].

15-bit instruction counter (IC): aka instruction pointer, program counter, word-addressed.

Instruction format

36-bit instructions: op addr, index, decr

35 21
address
20 18
index
17 3
decrement
2 0
op

Many instruction encodings omit decr, instead using bits 17–3 as additional opcode bits. Bit 0 is actually called S, the sign bit.

Instructions

ACL addr

add and carry logical word: AC <- AC + M[addr]

AXC addr, index

address to index complement: XR[index] <- 215 - addr
(note that addr, not M[addr], is being used.)

AXC **, index

** is just a 0 to the assembler, but by convention it denotes a value that is being manipulated at run-time (i.e., in self-modifying code) by instructions such as PAC, PCA, and SCA.

CAL addr, index

clear and add, logical (unsigned): AC <- 0; AC <- AC + M[addr+XR[index]]
(If index is missing, the +XR[index] is omitted.)

CLA addr, index

clear and add (signed): AC <- 0; AC <- AC + M[addr+XR[index]]
(If index is missing, the +XR[index] is omitted.)

LAC addr, index

load complement of address in index: XR[index] <- 215 - M[addr]

PAC , index

place complement of address in index: XR[index] <- 215 - AC<35:21>

PCA , index

place complement of index in address: AC <- 0; AC<35:21> <- 215 - XR[index]

SCA addr, index

store complement of index in address: M[addr]<35:21> <- 215 - XR[index]

SCA addr, 0

score complement of zero in address: M[addr]<35:21> <- 215 - 0

the machine description does not explicitly discuss this possibility for a SCA instruction, but Thompson's implementation requires that it behave this way.

SLW addr, index

store logical word: M[addr+XR[index]] <- AC

TRA label, index

transfer (branch, jump): IC <- label+XR[index]
(If index is missing, the +XR[index] is omitted.)

TSX label, index

transfer and set index (subroutine call): XR[index] = 215 - IC; IC <- label

TXH label, index, decr

transfer on index high: if(decr < XR[index]) IC <- label

TXL label, index, decr

transfer on index low: if(decr >= XR[index]) IC <- label

TXI label, index, decr

transfer with index incremented: XR[index] = XR[index] + decr; IC <- label

TXI *+1, index, decr

* indicates the current instruction and *+1 the next instruction, so this is simply an increment/decrement instruction: XR[index] = XR[index] + decr.

Primary sources

The descriptions on this web page are based on the full description of the machine state and instruction set in these page scans of Appendix 1 of an IBM 7094 manual: 1 2 3 4 5 6 7.

I regret that I do not remember where I obtained these images. I downloaded them from a web site in November 2000. The file names (gr000426.jpg, etc.) are original, but web searches for those names in 2007 do not turn up any hits. I would like to give proper credit. If someone does know the source of these images, please email me.

Historical note

LISP originated on the IBM 709, the precursor to the IBM 7090 and 7094: the address and decrement fields of the instruction word are the origin of LISP's CAR and CDR. Jack Harper has documented the IBM 7090/7094 in greater detail as part of documenting early LISP implementations.

Copyright © 2007 Russ Cox. All Rights Reserved.
https://swtch.com/~rsc/regexp/