366 THE PDP-11 FAMILY
the PDP-11/20 instructions provided only single-bit shifts.)
The first disk-based operating system, DOS, was designed for a minimum standard system that included 8 Kwords (16 Kbytes) of memory. After allowing typically 2 Kwords for the resident parts of the monitor, only 5 K to 6 K remained for other use. Consequently, size constraints played a major role in the FORTRAN system design and implementation.
There were not many competitors at the time, but at least one, the IBM 1130, offered a disk-based operating system and FORTRAN system. To meet this competition, an important goal was to deliver the PDP-l1 FORTRAN system to the market as quickly as possible, even at the cost of performance, if necessary.
Neither Compiler nor Interpreter, but Threaded Code
The fundamental design strategy to be determined was the structure of the executing code, the "run-time environment" [DEC, 1974b; DEC, 1974c].
We were leery of a compiler that generated direct machine code primarily because of the size of compiled code. Much of the compiled code would necessarily consist of calls to floating-point and other support routines, and on the PDP- 11, each subroutine call required two words of memory, not counting argument transmission.
An interpreter would easily solve the space problem, but this had its own disadvantages. The basic interpreter loop overhead was a concern, but not crucial at that stage in our deliberations. However, a disadvantage of interpreters is that they must be "always present" even though not all of the capabilities are being used. For example, routines for complex arithmetic are part of the interpreter even though the particular program in use does not perform complex arithmetic. Further, we wanted to maintain the traditional FORTRAN features of independent compilation and linking of routines, and easy writing of routines in assembler for inclusion in the program.
The solution was threaded code [Bell, J., 1973]. Threaded code is a kind of combination of an interpreter and compiled code with most of the best features of each. On the PDP-11 it works in the following way.
The "compiled code" consists simply of a sequence of service routine addresses. A single register (we used R4) is chosen to contain a pointer to the next address in the sequence to be invoked. Each service routine completes by transferring control to the next routine in the sequence and simultaneously advancing the pointer.
To illustrate, consider a service routine whose purpose is to perform floating-point addition of two real values found in a stack (we used R6, the hardware stack pointer, for the value stack) and leave the result on the top of the stack in place of the parameters. The service routine would look like the following.*
The JMP instruction with deferred autoincrement addressing mode provides just the
*The brackets << and >> are used in examples in place of code to indicate the purpose of code that is too bulky and/or not relevant for the example.
In the PDP-l1 MACRO assembler language [DEC, 1976], identifiers may consist of up to six characters from among the letters, numerals, "." and "$". Identifiers created by the FORTRAN compiler include either a period or dollar sign to assure that they are distinct from FORTRAN language identifiers.
In the PDP-11 MACRO assembler language, a colon follows a label and separates the label from assembler instructions.