In the 1960's, people sometimes described the computer industry as consisting of IBM and the BUNCH, where the latter term is an acronym for the other players in the computer industry of the era,
In the late 1960's, the BUNCH grew to include General Electric and Xerox, both of which sold some very interesting mainframes, so instead of talking about IBM and the BUNCH, people talked about Snow White and the Seven Dwarves. IBM, as Snow White, was, of course, untouchable, while the dwarves, while large companies in their own right, were hardly more than bit players in the computer industry.
All of these groupings omitted the most dynamic companies of the 1960's, the minicomputer makers. Companies like Digital Equipment Corporation, Hewlett Packard, Data General, and Motorola all began making small computers in this decade, and these computers, particularly DEC's PDP-11, were the major influence on the birth of microcomputers in the 1970's. From the point of view of the computer industry in the 1960's, however, these minicomputer makers seemed totally irrelevant!
This bit of history is relevant because it serves to introduce the Burroughs product line. The Burroughs 5000 and its successors were the most innovative new computers of the early 1960's. While no modern microprocessors (with the possible exception of the Rockwell AAMP) follow the design philosophy of these machines, the experience writing compilers for Algol on Burroughs machines shaped the style of memory use and addressing that dominates our thinking about procedure calling and activation records to this day.
The Burroughs architecture was not a low level architecture, but rather, a mid-level one. The machine language was at a high enough level that Burroughs did not use an assembly language; instead, they used dialects of Algol (the common ancestor of C, Pascal and Ada) for all their system programming.
Here is a summary of some aspects of the Burroughs architecture, ommitting all details of instruction coding and oversimplifing many issues:
Versions of push immediate were available for short (one syllable) and long constants.
The push and pop instructions allowed the contents of local or global variables to be referenced. The displacement x used in these instrucitons was limited to 1 syllable, so no procedure could have more than 64 local variables, and no program could have more than 64 global variables! Arrays and records were referenced using pointers, so this limitation was not too serious.
Arithmetic instructions operated exclusively on operands on the stack! This was an RPN machine!
Unconditional branch; d is a signed 12 bit displacement.
Conditional branches; d is a signed 12 bit displacement.
Simple calls cannot pass parameters. The simple return cannot return a result from a function.
To pass parameters, first push the mark, then push each parameter, and finally use a parameterized call, with n equal to the number of parameters passed. The called procedure or function can address the parameters as local variables.
To return a result, a function pushes it on the stack and then does a function return. This saves the parameter, pops the activation record off the stack, and then puts the parameter on the stack top.
| Free | | Space | | | <---- SP |----------| | | \ |Temporary | \ | Stuff| | | | | |----------| | | | | Current |Local | | Activation | Variables| | Record | | | |----------| | | | | |Parameters| / | | / <-- FP |----------| ---+o Old FP | A stack | | Old PC | mark | |----------| | | | \ | | | > Previous Activation Record -->| | / |----------| | Old FP | An older | Old PC | stack mark |----------|
Why are we interested in the B 5000? First, UNISYS still makes the descendants of this machine, and it is the machine from which much of our standard terminology about activation records is derived. Second, the B 5000 instruction set is at a much higher level than the instruction set on which we have focused up until this point.
Consider the following simple function:
integer function multiply(x,y)
if x = 0
return 0
else
return multiply(y,x-1)+y
Note first that the B 5000 had no assembly language! A B 5000 programmer
would write something very similar to the above in Burroughs Algol, and
would never see the actual machine instructions. As a result, there was
no official symbolic instruction format for the B 5000 machine language,
so we'll be informal here:
multiply:
-- assume the caller the parameters above the mark
-- x is therefore local variable 0
-- y is therefore local variable 1
Push Local 0 -- get x
Branch Not Equal else
Push Immediate 0
Function Return
else:
Push Mark -- setup to push parameters to call
Push Local 1 -- get y
Push Local 0 -- get x
Push Immediate 1
Subtract -- we're passing x-1
Parameterized Call multiply, 2 -- the call
Push Local 1 -- get y again
Add -- we're returning multiply(y,x-1)+y
Function Return
Note that the program makes no mention of registers! All you do is
mention the variables, parameters, etc! From a programmer's perspective,
this seems very civilized compared to the RISC architectures we've been
exploring.
On the other hand, implementing such a stack architecture is expensive! Large amounts of hardware must be dedicated to doing things at run-time which we know how to do before run-time, using compilers or hand assembly methods. As a result, for just about any fixed choice of technology, If you fix the dollar cost you're willing to spend on the CPU, the stack CPU will run slower. If, instead, you fix the speed you demand, the stack CPU will cost more.
It is not hard to compose a set of macros that make a machine like the Hawk look like the B 5000! This will form the basis of the next extended example we will undertake.