The B Programming Language
This document describes the implementation of B on the PDP-7 and PDP-11. The compilers seem to be lost, but there is enough code left to reconstruct how (almost) everything worked.
The implementation of the threaded code (the B interpreter) can be found in bilib for the PDP-11, which I have disassembled and somewhat commented, and bi.s for the PDP-7, which survived in source form.
The standard library is in libb for the PDP-11, which I have partially disassembled and commented. It is mostly wrappers around syscalls. Interestingly printn and printf actually contain compiled B code, so check it out to see how the threaded code looks like. bl.s contains the (much smaller) equivalent for the PDP-7.
Threaded code
B is implemented in threaded code on the PDP-7 and PDP-11. The way it is implemented differs a bit however. This is because a word on the PDP-7 is 18 bits but an address is only 13 bits wide. On the PDP-11 a word and address are both 16 bits.
For the PDP-7 this means a B instruction word can have rather the same format as a native PDP-7 instruction: 4 bits opcode and 13 bits address (PDP-7 instructions have an additional indirection bit, this is unused by B). The opcode bits are used to index a dispatch table, The address portion of a word then contains an address or any address sized number.
On the PDP-11 all B opcodes are stored as the address of the subroutine that handles it. If an address is needed, it is stored in the following word.
The threaded program counter is word 17 on the PDP-7 (an auto-increment location) and the register r3 on the PDP-11. As an implementation detail, r2 points to the MQ register of the KE-11 extended arithmetic unit.
Word addresses
This only concerns the PDP-11.
The B runtime expects word addresses
but the linker can only generate byte addresses for global variables.
To work around this the runtime has to patch the addresses
of all global addresses at runtime before calling into B code (main).
The way this is done is -- according to Steve Johnson --
a marvellous hack by Dennis Ritchie.
The first instruction in each object file jumps to the end of the file
and there calls a subroutine chain,
whose job it is to patch all the addresses of that object file.
After the return it falls off the end of the file and into the next one,
which does its patching the same way.
The B program has to be linked such that there is a runtime file
to begin the chain (to fall into the first B object file)
and one to end the chain (to catch the last B object file).
To see how this looks, check printf.s and printn.s,
which are compiled and disassembled B files.
They do not make use of the chain mechanism because they are not
linked to the proper place in the chain,
but the code is there nonetheless.
The code for chain is missing unfortunately but its purpose is clear.
Stack
All values are stored on a stack, which grows upwards. Two pointers, sp and dp, are used to address it. sp is the stack pointer and points to the next free word. dp is the display pointer for the current function's stack frame. Both are regular words on the PDP-7 and r5 and r4 resp. on the PDP-11.
In the decision how values are actually stored on the stack, the PDP-7 and PDP-11 differ quite a bit.
On the PDP-7 all values are stored as lvalues (i.e. their addresses) on the stack. For values that don't logically have an lvalue (i.e. constants and temporary results) the lvalue word points to the next word on the stack where the actual rvalue is stored. All others (i.e. lvalues of variables) also have this second word but don't point to or use it.
On the PDP-11 every value is stored with only one word and it is the compilers job to push lvalue and rvalues as needed. To do that, some more threaded instructions are introduced. This also means that the unary & operator cannot be implemented at runtime anymore.
Main functions
In the tables below
the name is that of the PDP-7 function that implements it.
An 'x' means it is implemented,
a '-' means it should be implemented but isn't,
a blank means it's not part of the language.
These are the main instruction of B. They have either an address-sized argument or specify a secondary function code.
The former is the case for all instruction but b, n and u. On the PDP-7 the address is stored in the instruction word. On the PDP-11 the address is stored in the next word.
For the b, n, and u instructions, the address field contains a secondary code on the PDP-7 (see table below). On the PDP-11 all b, n, u instructions are distinct functions.
name code PDP-7 description
autop a 040000 push automatic variable
binop b 100000 binary operator (see table below)
consop c 140000 push address sized constant
ifop f 200000 jump if stack value is zero
etcop n 240000 misc. function (see table below)
setop s 300000 set stack pointer
traop t 340000 jump
unaop u 400000 unary operator (see table below)
extop x 440000 push external variable
aryop y 500000 define automatic vector
z switch statement
As an example, consider the expression 'a + 3' where 'a' is an automatic variable at stack location 4. On the PDP-7, this can be compiled to:
a 4
c 3
b 14
On the PDP-11 it looks like this:
a; 4
c; 3
b14
PDP-11 specific instructions
As explained above, there are different functions to push lvalues and rvalues on the PDP-11. Also there are variants to pop the last value and ignore it.
auto ext const action
a x c push rvalue
ia ix ic pop; push rvalue
va vx push lvalue
iva ivx pop; push lvalue
Binary Operators
The function prefix is 'b'.
op name code PDP-7 PDP-11
= basg 1 x x
| bor 2 x x
& band 3 x x
== beq 4 x x
!= bne 5 x x
<= ble 6 x x
< blt 7 x x
>= bge 10 x x
> bgt 11 x x
>> brsh 12 - x
<< blsh 13 - x
+ badd 14 x x
- bmin 15 x x
% bmod 16 x x
* bmul 17 x x
/ bdiv 20 x x
=| 102 x
=& 103 x
=== 104 -
=!= 105 -
=<= 106 -
=< 107 -
=>= 110 -
=> 111 -
=>> 112 x
=<< 113 x
=+ 114 x
=- 115 x
=% 116 x
=* 117 x
=/ 120 x
Unary operators
The function prefix is 'u'
op name code PDP-7 PDP-11
& uadr 1 x
- umin 2 x x
* uind 3 x x
! unot 4 x x
++x 5 x
--x 6 x
x++ 7 x
x-- 10 x
Miscellaneous functions
The function prefix is 'n'
name code PDP-7 PDP-11 description
mcall 1 x x call function without arguments
mark 2 x x mark stack location for pushing arguments
call 3 x x return to mark, call function with arguments
vector 4 x x address vector
litrl 5 x put next instruction word on stack
goto 6 x x go to address
retrn 7 x x return from function with value
escp 10 x escape to machine code two words after instruction
11 x return from function without value