Burroughs B5000: Mark Stack and Recursive Procedure Linkage

The Burroughs B5000 made procedure linkage part of the processor’s storage model. Its hardware operated on a stack that held both operands and control information, providing processor-level support for calls and activation state rather than leaving all return bookkeeping to software conventions. The A and B registers acted as the top of that stack; the S register addressed its memory-backed continuation. Calls through Program Reference Table (PRT) descriptors entered program segments, while Return and Exit operations restored saved control state.

This article follows one narrow part of that design: how the B5000 marked a stack boundary, staged parameters and temporary values, and supported nested, including recursive, subroutines. It uses Burroughs’ 1963 Operational Characteristics of the Processors for the B 5000 as the authority for the implemented processor behavior. R. S. Barton’s 1961 paper explains the design motivation in more abstract terms, but Barton explicitly simplifies the actual machine for exposition; his model should not be mistaken for a complete B5000 instruction manual.

The operand stack was partly in registers

In Word Mode, B5000 program words were 48 bits, divided into four 12-bit syllables. The syllables included operators, literals, and calls that referenced operands or descriptors. Arithmetic and expression evaluation used a stack rather than requiring each intermediate result to have a permanently assigned memory address.

The stack was not just a block of memory manipulated by software. Burroughs describes its physical implementation as the A and B registers plus the memory area addressed by S. A new operand normally entered A. If A was occupied, its value moved into B. If B was also occupied, the processor advanced S and pushed B into the memory stack before making room. Empty/full flip-flops let the processor avoid unnecessary memory transfers when either register had no value. An operation consumed operands from the top and placed its result back into the stack.

This arrangement gave common short expressions a fast path through registers while preserving a memory-backed stack for deeper evaluation. The important point is not that the entire stack lived in A and B; it did not. Rather, the processor maintained the boundary between its register-resident top and the continuation in memory. Program code could express a sequence of operations without explicitly storing and reloading every temporary result.

PRT descriptors separated a call from a fixed address

Each program had a PRT, a relocatable table of up to 1,024 words addressed relative to the R register. The table held descriptors for data areas and program segments, along with scalar values used by the program. A program call syllable referred to a descriptor entry rather than embedding a machine-wide absolute address in the syllable.

A Program Descriptor described a program segment, including its location and whether it was present in core memory; it also identified the segment’s operating mode and could indicate that the segment required parameters. When a call referenced a segment that was not present, the processor signaled a presence interrupt instead of silently treating the missing code as resident. The system software could then resolve the missing segment. The call mechanism therefore combined control transfer with the machine’s segment-residency model.

The B5000 manual distinguishes Program Level from Sub-Program Level. At the Sub-Program Level, call syllables could address a limited range of stack locations, the subroutine segment, and the PRT. That allowed a procedure to refer to its parameters and working storage through the current linkage state, rather than assuming that every call used the same global addresses.

Mark Stack established a boundary for procedure state

The Mark Stack operation prepared a well-defined region of the stack for a subroutine’s arguments and local working storage. Burroughs documents it as a set of processor actions, not as a high-level-language keyword:

The current A and B register contents are pushed onto the memory stack.
The processor saves the prior F and R register values and the Mark Stack and Program Level state in a Mark Stack control word. When required, the outer mark is retained in the PRT at the location relative to R specified by the manual.
The current stack position S is copied to F, making F the frame reference used by subroutine addressing.
The operation establishes Sub-Program Level state and transfers control according to the address supplied in A; the exact emitted sequence depends on the program’s linkage path.

The order matters because the mark is a boundary, not a claim that every local variable has been allocated at call time. After the mark, the documented call sequence can place parameter values in known stack positions and enter a target segment through its Program Descriptor. The frame reference gives the callee a stable way to locate those parameters even as the stack changes during evaluation.

Burroughs’ model also distinguishes the parameter area from temporary working storage. The manual describes parameter references on one side of F and subroutine temporary storage on the other, while S continues to track the active extent of stack storage. A subroutine can therefore use stack-relative addressing for its inputs and for intermediate values without confusing those two regions.

Return control words made nested calls unwindable

When a call syllable entered a program segment, the processor placed a Return Control Word on the stack. That word preserved the control information needed to resume the caller, including program-location and relevant register state. A Mark Stack Control Word preserved the outer linkage state, such as the earlier F and R values and the mark/program-level settings.

On a normal subroutine exit, a Return or Exit operation used the Return Control Word to restore the caller’s registers and instruction position. The processor then consulted the Mark Stack Control Word to restore the previous frame and program-level state; where marks were nested, the manual describes restoring successive saved contexts until the appropriate outer boundary was reached. This makes a nested call a stack discipline: each deeper activation adds control state, and leaving it removes that activation in reverse order.

The mechanism also explains how recursion fit the design. A recursive procedure could be active more than once because each entry had its own saved return and stack-relative state. The B5000 manual explicitly says subroutines could call themselves and that the nesting mechanism supported recursive procedures. This is not an assertion of unlimited recursion: memory, stack limits, and the rest of the system still bound practical depth. It means the linkage model was not restricted to one statically allocated frame per procedure name.

A conceptual trace, not B5000 source code

The following sequence summarizes roles, not a compilable instruction stream or a complete compiler calling convention:

Phase	Processor mechanism	State kept distinct
Evaluate an expression	Operands move through A and B; additional stack words spill through S.	Expression temporaries and control state share an ordered stack.
Establish a subroutine boundary	Mark Stack saves outer linkage state and establishes F.	Caller context versus the new subroutine’s frame.
Stage arguments	Values are placed in the documented parameter area; call syllables refer through the PRT.	Parameters versus callee temporaries.
Enter the segment	A Program Descriptor supplies segment information; the processor creates return state.	Current callee location versus saved caller return.
Return or exit	Control words restore the saved registers and outer mark state.	Inner activation is removed before its caller resumes.

The table deliberately avoids presenting a fabricated Algol example as machine code. Burroughs’ manual is precise about the processor’s control words and registers, but a real compiled procedure also depends on the compiler’s data layout and the exact call form. Barton’s earlier paper is useful for understanding the motivation: expression evaluation as a Polish-string stack and generalized subroutine linkage. It presents an abstracted control organization and notes that details are simplified.

Why this was a compiler-oriented architecture

Burroughs’ processor manual says that highly efficient machine code was generated by problem-oriented language compilers integrated with the programming system. Its description of the stack, PRT, descriptors, subroutine levels, and automatic entry/exit is therefore best read as an attempt to make compiler output directly useful to the hardware. It did not merely add a stack instruction to a conventional register architecture: operand evaluation, procedure activation, segment references, and saved control state fit a common machine model.

That approach has limits and should not be retrofitted with modern terms too casually. A B5000 Mark Stack Control Word is not a modern ABI stack-frame record, and Program Descriptors are not the same thing as contemporary virtual-memory page tables. The manual documents a specific machine with its own syllable formats, registers, segment organization, and system software. Likewise, the 1961 design paper’s simplified stack model is evidence of the design rationale, not proof that every production detail matched the paper’s abstraction.

The historical lesson is concrete: recursion and procedure calls become easier to compile when the processor itself maintains a disciplined activation stack and saves the control state needed to unwind it. On the B5000, the A/B registers accelerated the top of that stack; S tracked its memory-backed continuation; F and Mark Stack control words delimited procedure state; and descriptors connected calls to relocatable code segments. Together these mechanisms made nested procedures a first-class part of the computer’s organization.

Related:

Sources: