Editing Burroughs Large Systems (section)

=== Procedures ===
Procedures can be invoked in four ways – normal, call, process, and run.

The '''normal''' invocation invokes a procedure in the normal way any language invokes a routine, by suspending the calling routine until the invoked procedure returns.

The '''call''' mechanism invokes a procedure as a coroutine. Coroutines are partner tasks established as synchronous entities operating in their own stack at the same lexical level as the initiating process. Control is explicitly passed between the initiating process and the coroutine by means of a '''CONTINUE''' instruction. 

The '''process''' mechanism invokes a procedure as an asynchronous task with a separate stack set up starting at the lexical level of the processed procedure. As an asynchronous task, there is no control over exactly when control will be passed between the tasks, unlike coroutines. The processed procedure still has access to the enclosing environment and this is a very efficient IPC (Inter Process Communication) mechanism. Since two or more tasks now have access to common variables, the tasks must be synchronized to prevent race conditions, which is handled by the EVENT data type, where processes can WAIT on one, or more, events until it is caused by another cooperating process. EVENTs also allow for mutual exclusion synchronization through the PROCURE and LIBERATE functions. If for any reason the child task dies, the calling task can continue – however, if the parent process dies, then all child processes are automatically terminated. On a machine with more than one processor, the processes may run simultaneously. This EVENT mechanism is a basic enabler for multiprocessing in addition to multitasking.

==== Run invocation type ====

The last invocation type is '''run'''. This runs a procedure as an independent task which can continue on after the originating process terminates. For this reason, the child process cannot access variables in the parent's environment, and all parameters passed to the invoked procedure must be call-by-value.

Thus, Burroughs Extended ALGOL had some of the multi-processing and synchronization features of later languages like [[Ada (programming language)|Ada]].  It made use of the support for asynchronous processes that was built into the hardware.

==== Inline procedures ====

One last possibility is that in NEWP a procedure may be declared '''INLINE''', that is when the compiler sees a reference to it [[inline expansion|the code for the procedure is generated inline]] to save the overhead of a procedure call; this is best done for small pieces of code. Inline functions are similar to [[parameterized macro]]s such as [[C (programming language)|C]] #defines, except you don't get the problems with parameters that you can with macros.  

==== Asynchronous calls ====

In the example program only normal calls are used, so all the information will be on a single stack. For asynchronous calls, a separate stack is initiated for each asynchronous process so that the processes share data but run asynchronously.

==== Display registers ====

A stack hardware optimization is the provision of D (or "display") registers. The D registers correspond to scope in source programs, that is nesting in the source. These are registers that point to the start of each called stack frame. These registers are updated automatically as procedures are entered and exited and are not accessible by any software other than the MCP. There are 32 D registers, which is what limits operations to 32 levels of lexical nesting.

Consider how we would access a lexical level 2 (D[2]) global variable from lexical level 5 (D[5]). Suppose the variable is 6 words away from the base of lexical level 2. It is thus represented by the address couple (2, 6). If we don't have D registers, we have to look at the control word at the base of the D[5] frame, which points to the frame containing the D[4] environment. We then look at the control word at the base of this environment to find the D[3] environment, and continue in this fashion until we have followed all the links back to the required lexical level. This is not the same path as the return path back through the procedures which have been called in order to get to this point. (The architecture keeps both the data stack and the call stack in the same structure, but uses control words to tell them apart.)

As you can see, this is quite inefficient just to access a variable. With D registers, the D[2] register points at the base of the lexical level 2 environment, and all we need to do to generate the address of the variable is to add its offset from the stack frame base to the frame base address in the D register. (There is an efficient linked list search operator LLLU, which could search the stack in the above fashion, but the D register approach is still going to be faster.) With D registers, access to entities in outer and global environments is just as efficient as local variable access.

 D Tag Data                — Address couple, Comments
 register

 | 0        | ''n''          | (4, 1) The integer ''n'' (declared on entry to a block, not a procedure)
 |-----------------------|
 | D[4]==>3 | '''MSCW'''       | (4, 0) The Mark Stack Control Word containing the link to D[3].
 |=======================|
 | 0        | ''r2''         | (3, 5) The real ''r2''
 |-----------------------|
 | 0        | ''r1''         | (3, 4) The real ''r1''
 |-----------------------|
 | 1        | ''p2''         | (3, 3) A SIRW reference to ''g'' at (2,6)
 |-----------------------|
 | 0        | ''p1''         | (3, 2) The parameter ''p1'' from value of ''f'' 
 |-----------------------|
 | 3        | '''RCW'''        | (3, 1) A return control word
 |-----------------------|
 | D[3]==>3 | '''MSCW'''       | (3, 0) The Mark Stack Control Word containing the link to D[2].
 |=======================|
 | 1        | ''a''          | (2, 7) The array ''a''  ======>[ten word memory block]
 |-----------------------|
 | 0        | ''g''          | (2, 6) The real ''g'' 
 |-----------------------|
 | 0        | ''f''          | (2, 5) The real ''f'' 
 |-----------------------|
 | 0        | ''k''          | (2, 4) The integer ''k'' 
 |-----------------------|
 | 0        | ''j''          | (2, 3) The integer ''j'' 
 |-----------------------|
 | 0        | ''i''          | (2, 2) The integer ''i''
 |-----------------------|
 | 3        | '''RCW'''        | (2, 1) A return control word
 |-----------------------|
 | D[2]==>3 | '''MSCW'''       | (2, 0) The Mark Stack Control Word containing the link to the previous stack frame.
 |=======================| — Stack bottom

If we had invoked the procedure p as a coroutine, or a process instruction, the D[3] environment would have become a separate D[3]-based stack. This means that asynchronous processes still have access to the D[2] environment as implied in ALGOL program code. Taking this one step further, a totally different program could call another program's code, creating a D[3] stack frame pointing to another process' D[2] environment on top of its own process stack. At an instant the whole address space from the code's execution environment changes, making the D[2] environment on the own process stack not directly addressable and instead make the D[2] environment in another process stack directly addressable. This is how library calls are implemented. At such a cross-stack call, the calling code and called code could even originate from programs written in different source languages and be compiled by different compilers.

The D[1] and D[0] environments do not occur in the current process's stack. The D[1] environment is the code segment dictionary, which is shared by all processes running the same code. The D[0] environment represents entities exported by the operating system.

Stack frames actually don't even have to exist in a process stack. This feature was used early on for file I/O optimization, the FIB (file information block) was linked into the display registers at D[1] during I/O operations. In the early nineties, this ability was implemented as a language feature as STRUCTURE BLOCKs and – combined with library technology - as CONNECTION BLOCKs. The ability to link a data structure into the display register address scope implemented object orientation. Thus, the B6500 actually used a form of object orientation long before the term was ever used.

On other systems, the compiler might build its symbol table in a similar manner, but eventually the storage requirements would be collated and the machine code would be written to use flat memory addresses of 16-bits or 32-bits or even 64-bits. These addresses might contain anything so that a write to the wrong address could damage anything. Instead, the two-part address scheme was implemented by the hardware. At each lexical level, variables were placed at displacements up from the base of the level's stack, typically occupying one word - double precision or complex variables would occupy two. Arrays were ''not'' stored in this area, only a one word descriptor for the array was. Thus, at each lexical level the total storage requirement was not great: dozens, hundreds or a few thousand in extreme cases, certainly not a count requiring 32-bits or more. And indeed, this was reflected in the form of the VALC instruction (value call) that loaded an operand onto the stack. This op-code was two bits long and the rest of the byte's bits were concatenated with the following byte to give a fourteen-bit addressing field. The code being executed would be at some lexical level, say six: this meant that only lexical levels zero to six were valid, and so just three bits were needed to specify the lexical level desired. The address part of the VALC operation thus reserved just three bits for that purpose, with the remainder being available for referring to entities at that and lower levels. A deeply nested procedure (thus at a high lexical level) would have fewer bits available to identify entities: for level sixteen upwards five bits would be needed to specify the choice of levels 0–31 thus leaving nine bits to identify no more than the first 512 entities of any lexical level. This is much more compact than addressing entities by their literal memory address in a 32-bit addressing space. Further, only the VALC opcode loaded data: opcodes for ADD, MULT and so forth did no addressing, working entirely on the top elements of the stack.

Much more important is that this method meant that many errors possible on systems employing flat addressing could not occur because they were simply unspeakable even at the machine code level. A task had no way to corrupt memory in use by another task, because it had no way to develop its address. Offsets from a specified D-register would be checked by the hardware against the stack frame bound: rogue values would be trapped. Similarly, within a task, an array descriptor contained information on the array's bounds, and so any indexing operation was checked by the hardware: put another way, each array formed its own address space. In any case, the tagging of all memory words provided a second level of protection: a misdirected assignment of a value could only go to a data-holding location, not to one holding a pointer or an array descriptor, etc. and certainly not to a location holding machine code.

====Array storage====
Arrays were not stored contiguous in memory with other variables, they were each granted their own address space, which was located via the descriptor. The access mechanism was to calculate on the stack the index variable (which therefore had the full integer range potential, not just fourteen bits) and use it as the offset into the array's address space, with bound checking provided by the hardware. By default, should an array's length exceed 1,024 words, the array would be segmented, and the index be converted into a segment index and an offset into the indexed segment. There was, however, the option to prevent segmentation by specifying the array as LONG in the declaration.  In ALGOL's case, a multidimensional array would employ multiple levels of such addressing. For a reference to A[i,j], the first index would be into an array of descriptors, one descriptor for each of the rows of A, which row would then be indexed with j as for a single-dimensional array, and so on for higher dimensions. Hardware checking against the known bounds of all the array's indices would prevent erroneous indexing.

FORTRAN however regards all multidimensional arrays as being equivalent to a single-dimensional array of the same size, and for a multidimensional array simple integer arithmetic is used to calculate the offset where element A[i,j,k] would be found in that single sequence. The single-dimensional equivalent array, possibly segmented if large enough, would then be accessed in the same manner as a single-dimensional array in ALGOL. Although accessing outside this array would be prevented, a wrong value for one index combined with a suitably wrong value for another index might not result in a bounds violation of the single sequence array; in other words, the indices were not checked individually.

Because an array's storage was not bounded on each side by storage for other items, it was easy for the system to "resize" an array - though changing the number of dimensions was precluded because compilers required all references to have the same number of dimensions. In ALGOL's case, this enabled the development of "ragged" arrays, rather than the usual fixed rectangular (or higher dimension) arrays. Thus in two dimensions, a ragged array would have rows that were of different sizes. For instance, given a large array A[100,100] of mostly-zero values, a sparse array representation that was declared as SA[100,0] could have each row resized to have exactly enough elements to hold only the non-zero values of A along that row.

Because arrays larger than 1024 words were generally segmented but smaller arrays were not, on a system that was short of real memory, increasing the declared size of a collection of scratchpad arrays from 1,000 to say 1,050 could mean that the program would run with far less "thrashing" as only the smaller individual segments in use were needed in memory. Actual storage for an array segment would be allocated at run time only if an element in that segment were accessed, and all elements of a created segment would be initialised to zero. Not initialising an array to zero at the start therefore was encouraged by this, normally an unwise omission.

Array equivalencing is also supported.  The ARRAY declaration requested allocation of 48-bit data words which could be used to store any bit pattern but the general operational practice was that each allocated word was considered to be a REAL operand.  The declaration of:

   ARRAY A [0:99]

requested the allocation of 100 words of type REAL data space in memory.  The programmer could also specify that the memory might be referred to as character oriented data by the following equivalence declaration:

   EBCDIC ARRAY EA [0] = A [*];

or as hexadecimal data via the equivalence declaration:

   HEX ARRAY HA [0] = A [*];

or as ASCII data via the equivalence declaration:

   ASCII ARRAY AA [0] = A[*];

The capability to request data type specific arrays without equivalencing is also supported, e.g.

   EBCDIC ARRAY MY_EA [0:99]

requested that the system allocated a 100 character array.  Given that the architecture is word based, the actual space allocated is the requested number of characters rounded up to the next whole word boundary.

The Data Descriptor generated at compilation time indicated the data type usage for which the array was intended.  If an array equivalence declaration was made a copy descriptor indicating that particular usage type was generated but pointed back to the original, or MOM, descriptor.  Thus, indexing the correct location in memory was always guaranteed.

BOOLEAN arrays are also supported and may be used as a bit vector.  INTEGER arrays may also be requested.

The immediately preceding discussion uses the ALGOL syntax implementation to describe ARRAY declarations, but the same functionality is supported in COBOL and FORTRAN.