We describe a form of routine proposed for compiler output for Atlas. The information is principally in relocatable binary, but there is sufficient symbolic content to allow very flexible communication between independently compiled routines.
A compiler which treats a whole program as a unit can obviously produce its output in the form of binary words exactly as they are to be stored for execution. There is no need in this case for any intermediate form of storage. However, experience in using automatic programming languages has shown the enormous advantage of allowing the programmer to split up his program into more-or-less independent routines, to limit the scope of certain identifiers.
There is a considerable difference between the processing which has to be carried out inside each routine and that which links routines together. We emphasize this difference by using the word compiler or assembler to designate the processor for individual routines, and loader for that which links them together before initiating execution. We thus distinguish compile time, load time, and execute time.
An appreciable part of the work of a compiler consists of the treatment of cross-references of one sort or another: identifiers and statement numbers, both of which play a very important part in automatic programming languages. The processing of cross-references is roughly proportional to the square of the size of the program or routine being compiled, and so it is advantageous to keep the routines small. If a large program can be broken up into ten routines of one-tenth the size, compiling time will be considerably reduced. In general, a loader does not need to be such a sophisticated processor as a compiler, and cross-references between routines can be dealt with in a simpler way, giving a net gain.
With the technique of independently compiled routines, alterations to a program do not require the whole program to be re-compiled: only the relevant routines. Consequently, programmers are not discouraged from making corrections in source language, rather than in binary.
It is not appropriate in this paper to give a description of Atlas, or of the Supervisor, which controls input/output and the scheduling of jobs. We refer readers to papers by Kilburn, Howarth, Payne, and Sumner (1961) for a description of the Manchester University Atlas Operating System. The operating system for the Harwell Atlas will be basically the same, with trivial variations, mainly concerned with a layout more appropriate for cards.
The main addition is a Local Operating System, which we call HARTRAN, to control the processing of individual programs. It is entered from the Supervisor to process a document with the appropriate COMPILER heading. (It is important not to confuse the meanings of the heading COMPILER and a compiler.) Processing consists of compiling or assembling routines in source language, and loading all routines if execution of the job is requested. (The execution request will be deleted if serious errors are discovered while processing.) After processing the document containing the program, the Local Operating System returns control to the Supervisor, which will, if necessary, begin execution of the object program.
In the HARTRAN system. a program can consist of a number of routines, each of which may be written in any source language for which a compiler exists, whichever is most convenient for the particular problem. For example, most routines of the program can be written in an automatic programming language such as FORTRAN, but some tricky inner loops can be made into separate routines, and written in a language closer to the basic machine language, such as ASP (Atlas Symbolic Programming). The routines are processed independently by the appropriate compiler into a standard target language. The loader converts all routines from this target language into the object program. It would be very convenient if compilers for other automatic programming languages envisaged for Atlas, e.g. Atlas Autocode, and Nebula. could also give their output in this standard target language.
The target language which we here describe has been designed for communication between the various parts of HARTRAN, but there is no fundamental reason why it should not be used in other operating systems. It has the advantage that routines are principally in relocatable binary (thus reducing the amount of work to be done on loading), but have sufficient symbolic content to allow very flexible communication between independently compiled routines. We call it BAS: Binary and Arbitrarily Symbolic. It is more general than the BSS form used by FORTRAN II (I.B.M. 1958) and more compact than the LSS form proposed by McCarthy and Corbato (1960).
In Part I of this paper we describe in general terms the facilities available in the BAS language, without going into too much detail. The details are given in Part 2, to show how the various features of BAS are implemented. The description will mainly be limited to BAS, but at some points the full power of the arrangements cannot be appreciated without reference to the wider context (HARTRAN). In particular, we will refer to loader control directives. These always occur between routines and allow the loading process to be modified in various ways. The conventions adopted for HARTRAN will be mentioned at appropriate points. It would, of course, be extremely convenient if other compilers giving output in BAS used the same conventions, but this is not strictly necessary if intercommunication with routines compiled in the HARTRAN system is not required.
The loader provides facilities for symbolic cross-referencing between BAS routines:
A symbol is a name with an associated meaning. Names which can be used for this purpose are limited by the Atlas word length: they must be represented by one word of 48 bits, i.e. eight 6-bit characters. Words in which the more-significant half (high half) is all zero bits are not permitted as names in BAS; they are used for special purposes. Apart from these, any word can be used as an identifier, in any code suitable for the compiler.
The convention in the HARTRAN system is that characters are represented by the Atlas internal code using the inner set only. The null character is excluded; thus it is impossible that a special name should be generated accidentally. Normal names consist of up to eight characters of which the first is a letter and the others letters or digits. These are left-adjusted and filled out with spaces, to make exactly eight characters. The name of eight spaces is used in HARTRAN to designate the main routine of a chapter (see next section). Cross-references wholly inside a routine are dealt with by the compiler and converted to a relocatable binary form, in which instruction addresses are worked out relative to the origin of the routine, and need to have the routine origin added to them on loading.
Cross-references between routines have to be treated specially by the compiler, and a record made of the names of routines and public arrays which are used. These are called external location symbols. Every BA routine has a name by which other routines can refer to it, and it can use external location symbols which it expects to be defined elsewhere. The names of routines, and public arrays are valid (i.e. have a meaning) throughout the loading process, unless changed by special directives. A routine can also define other symbols for subsidiary entry points to itself.
Symbols can also be defined by loader control directives, and names changed.
The main store of the Atlas includes the core store and the magnetic drums. The one-level store technique (Kilburn and Sumner. 1962; Fotheringham, 1961) allows this all to be directly accessible, providing automatic transfers of information between the drums and core in blocks of 512 words each. Ampex magnetic tape is the principal auxiliary storage medium, allowing transfers of 512-word blocks. (IBM tape is only used for input/output.) Thus the division of the main store into 512-word blocks is important when auxiliary transfers are concerned.
The theoretical maximum size of the main store of Atlas is about a million words (220); actual sizes are not as large as this. But however large the main store of a computer, one can always find a job for which the program requires more space than is directly accessible. In such cases, auxiliary storage has to be used to back up the main store. Whether the associated two-level storage problem is solved automatically or by the programmer, the program has to be split up into number of parts which occupy the main store at different times. Naturally, for a computer with as large a main store as Atlas, we expect most jobs not to require such treatment. However, the organization surrounding BAS has been designed so that it can cope with larger problems. We intend to use the simplest method of treating the two-level problem, and require the programmer to divide a large program into distinct sections, only one of which can be in the main store at one time. We call these sections chapters.
Chapters are indicated by loader control directives; each consists of a number of BAS routines. There is no provision for a BAS routine to spread over from one chapter to another: each BAS routine is in a unique chapter, and must not refer to routines in other chapters. Control is passed from one chapter to another by the chapter changing routine, which will be in the library, and automatically provided when it is needed. Each chapter has a unique entry point (corresponding to the name of eight spaces) where it is entered after having been read into the main store.
Each chapter will be assigned storage starting at a block origin, and will be compact so as to make chapter changing as fast as possible. Storage is assigned for successive routines and arrays in the chapter without leaving any gaps. This means that all routines and arrays in the chapter must be able to start at any location. Arrays which do not fulfil this requirement are stored separately, as will be described in the next section. Routines which are required for several chapters can, at the programmers' option, be made Global, and stored outside the chapter. They are then not affected by chapter changes.
A powerful new feature in BAS is the arrangement for assigning storage for arrays at load time. A routine which uses an array carries with it the name of the array, and the length of storage required for it. The loader examines the array name to see whether storage has already been assigned; if not, it automatically assigns the requisite number of words in the appropriate part of the store. This method of storage assignment is based on the fact that it does not usually matter where the array is stored, provided that all routines which refer to arrays with the same name are told that it is stored in the same place. There are two situations which require special consideration:
There is also a common region used to implement the COMMON feature in FORTRAN.
Any routine can have private arrays, which are assigned storage in the same region as the routine, and whose names are not made available to other routines.
Normally, arrays are stored in the chapter region, and are available to all routines in the same chapter. Such arrays are called public arrays, and their names and origins are public symbols. The range of validity of a public symbol is the chapter in which it occurs - in just the same way as a routine name is valid throughout the chapter.
Arrays needed for communication between chapters are called global arrays. They must be defined by a loader control directive, before any routine which uses them (usually at the head of the chapter). Storage for them is arranged in the global region where they are accessible from all chapters. Their names and origins are global symbols and valid throughout the job.
Any array can be specified by routines which use it as a block array. This means that it is to be used for auxiliary transfers, and must occupy an exact number of Atlas blocks. (Its length will, if necessary, be made up to the next multiple of 512.) Unless an array is specified as a block array in the first routine which uses it, it will not be given separate blocks of storage. Block arrays are not stored in the chapter, since the program is expected to look after transfers concerning them explicitly. The common region is available for use by any routine, and can be regarded as an array whose length is not predetermined. Each routine which uses this common array will refer to it by a special name, and specify the length it requires. The loader will determine the maximum of all these lengths.
As a consequence of the BAS method of assigning storage for arrays at load time. the way is made clear for array sizes to be parametric in source language. One no longer has to compile routines with array storage assigned for the maximum size possible, or to re-compile when only the sizes of arrays are changed. The length of an array in the BAS form can depend on the values of parameters, which are supplied at load time by means of loader control directives. The same compiled routine can be used on different occasions with different parameter values giving different amounts of storage for arrays.
Parameters can be used in any routine, both for dimensions of arrays and in place of (integer) constants in arithmetic statements. Multi-dimensional arrays are allowed to involve parameters: a matrix with M rows and N columns needs M × N storage cells. and the loader can work this out, given values of M and N.
Parameters are represented by symbols, with names of the same form as routine and array names. The difference is that the meaning of the name is a pure number, as opposed to a location. (It has no relation whatsoever to the arrangement of information in the store.) This is a rather subtle distinction which is relevant in the context of relocatable routines.
All Symbolic cross-references in BAS are converted by referring to a symbol table, that is, a list of all currently defined symbols. We have defined a symbol as a name with an associated meaning. The name of the symbol occupies one word and its meaning another word. The meaning of a symbol consists of a numerical value (24 bits) with some additional information (length, 21 bits and mode, 3 bits) which indicates its nature. This additional information is used to distinguish types of symbol in at least three contexts: during assembly, in the BAS form, and during loading.
The length distinguishes array names from others. A positive integer in this position records the number of words of storage assigned for the array. Zero or negative integers have different meanings according to the context. The mode distinguishes whether the name represents a number or a location; whether or not it is a block array name; and whether or not its range of validity is restricted (to this routine or chapter).
Each routine of the program is converted to BAS form by the appropriate compiler, or read in in BAS. The BAS loader is a subroutine of the local operating system, which is entered after each routine has been obtained in BAS. It accumulates loaded routines, and information about them. The standard assignment of storage for an object program is illustrated in Fig. 1.
| Standard Origin | Current limit | Name of region |
|---|---|---|
| 0000 000 |
Last Routine Next location |
Global Region |
| 1000 000 |
Last Routine Next location |
Chapter Region |
| 2000 000 |
Last Block |
Block Region |
| 3000 000 |
Maximum Length |
Common Region |
Locations of standard origins are given in octal; the first four digits give the Atlas block number. The regions are deliberately well spaced: the standard origins should be suitable for any Atlas configuration. Blocks 0 and 1 will probably be reserved for special purposes. Blocks 34008 and above are not used, for the convenience of the Supervisor. Locations 40000008 and above constitute the special stores of Atlas (i.e. the private and fixed stores).
The loader records the values of six numbers to mark its current limits of storage assignment. For the global and chapter regions it keeps the location after the end of the last routine loaded in the region, and the next available location in the region. (These are not necessarily the same, because of array assignments.) For the other regions, it keeps the end of the last assigned block array, and the maximum length of the common array requested for routines already loaded.
The loader also records information connected with symbols in two tables which will now be described.
The Loader Symbol Table is a list of symbols whose meanings are known to the loader. In this table, the length position acts as a three-way switch. A positive (non-zero) length indicates an array for which storage has been assigned. A negative length indicates a routine (different numbers may be used to distinguish different versions of routines with the same name). A zero length indicates an array for which storage has not yet been assigned, but whose mode is known (i.e. global or not). The mode distinguishes public from global symbols, i.e. definitions restricted to the chapter or not.
The Forward Reference Table is a list of forward references to routines, i.e. uses of names whose meanings are not yet known. Each entry in this table consists of the name (one word) followed by an indefinite number of half words giving the absolute locations into which the value of the symbol is to be added. (A negative number terminates each entry.) There may be any number of entries for each routine.
A BAS routine consists of the following sections:
The routine heading is in a symbolic form, for ease of recognition and manipulation. The remainder is in a standard binary form, with the tables occupying locations following the last location required by the routine itself. They will eventually be over-written when the next routine is loaded. Each routine is processed as follows.
(1) Routine heading
This is the first part of the routine met by the Local Operating System when the routine is read in in BAS, and its most important purpose is to indicate to the local system that a routine in BAS follows. The local system then enters the BAS loader to process the routine. The routine heading is in a suitable format for recognition by the local system. Routines are normally loaded into the chapter region, immediately after the preceding routine or array. A loader control directive can change this and cause particular routines to be put in the global region. Accordingly, when the loader is entered, the Loader Symbol Table is scanned to find which region to use. The next available location in the appropriate region is taken as origin for the present routine and preserved for relocation.
The routine heading also gives information to the BAS loader about the routine as a whole: (i) its name; (ii) a version number; (iii) the entry point; (iv) the location after the end of the routine (not counting tables); (v) the origin of the parameter use table. The origin of the routine is added to these last three numbers to give absolute locations. The name, version number. and entry point arc entered in the Loader Symbol Table, In order that all jobs start with a standard store, the loader clears all registers from the end of the last routine loaded to the end of this routine, before actually loading it. Then the end of the current routine is preserved for similar use after the next routine. By this means the tables for each routine are cleared after they have been processed. The origin of the parameter use table is preserved for later processing.
(2) Relocation
The routine, followed by all its tables, is then loaded into the store, starting at the assigned relocation origin. Selected words in the routine are relocated by adding the relocation origin to their addresses. (It is the responsibility of the assembler to specify which words are to be relocated.) The tables are loaded into storage immediately following the routine. They will eventually be cleared before the next routine is loaded into the same region. All of the binary part of a BAS routine is loaded before any further processing takes place.
Because the format of relocatable binary information may be essentially different on cards and paper tape, different versions of this section of the loader will have to be written for different formats. It will be a subroutine of the loader, so changing it will not be difficult.
In a BAS routine, any address can be adjusted on loading by adding to it the product of any number of parameters and a specified constant, and/or the value of any array or routine name which is valid. The adjustments are specified in the various tables, which are now processed.
(3) The Parameter Use Table
This defines parametric expressions which must be evaluated by the loader, and added to half-words in the routine or its tables. Each entry defines the product of an arbitrary number of symbols, which may be parameters or internal symbols defined in terms of parameters {private parameters). The routine symbol table contains an entry for each private parameter. This is the first table to be processed, because it may be necessary for it to make changes to other tables before they themselves arc processed. For example, the size of an array may involve parameters. This size must be calculated and inserted in the External Reference Table.
The first few words of each entry in the Parameter Use Table contain the names of symbols whose values must be multiplied together. To find the value of each symbol, the Routine and the Loader Symbol Tables are searched (in that order, to deal with private parameters correctly). Each symbol must have been previously defined and must be numeric. A word with zero high half terminates the list of names. The current product is multiplied by the low half to give the value to be used. This value is added to the locations specified in successive half-words, which may be in the routine or its tables. All these locations must be positive: negative numbers are used to mark the end of each entry, and the end of the whole table (lowest bit 0 or 1).
(4) The External Reference Table
This is a list of external location symbols which the routine uses. Associated with each name is the length of storage required. A length greater than zero indicates an array, and the appropriate space is assigned automatically when the array is first met. The length might depend on the values of parameters: the Parameter Use Table can make adjustments before this table is processed. By convention. zero length indicates a subroutine or, more strictly, information which will be loaded independently. No space is assigned until the routine is loaded: forward references to it are listed in the Forward Reference Table.
Each entry in the External Reference Table refers to one symbol whose name, length, and mode are specified. Names of the special type (zero high half) are used to indicate the common array (zero low half) or private arrays (non-zero low half). For the common array, the current maximum length of common is adjusted if necessary. The origin of this array is always available and is added to the specified half-words in the standard way (as for the Parameter Use Table). Private arrays are assigned storage as described below (iii) in the chapter or global region, and the origin added to the specified half-words (but not recorded in the Loader Symbol Table).
If the name is not special, it is compared with names in the loader symbol table to find whether it has already been met. If a coincidence is found, the entry in the Loader Symbol Table is examined to see whether storage has been assigned (non-zero length). If a coincidence is not found, flow proceeds as for zero length in the Loader Symbol Table. Subsequent action depends on whether the length in the External Reference Table (ERT) is zero or non-zero (it cannot be negative), and whether the length in the Loader Symbol Table (LST) is zero or non-zero. There are thus four possible cases:
(i) Zero length in ERT, zero length or no entry in LST. This is a forward reference to a routine which will be loaded later. The remainder of the entry in the ERT is copied across to the Forward Reference Table.
(ii) Zero length in ERT, non-zero length in LST. This is a backward reference to a routine which has already been loaded. The value of the symbol is obtained from the LST, and added to the specified half-words in the routine.
(iii) Non-zero length in ERT, zero length or no entry in LST. This is the first reference to a particular array name, and storage must now be assigned, in the appropriate region of the main store, as indicated by the mode. If this is a block or global array, storage is assigned in the appropriate region, otherwise in the chapter region.
Assignment of storage for an array in the chapter region consists of taking the next available location for this region as the value of the array name, and then incrementing this next available location by the array length.
Assignment of storage for a global but not block array consists of taking the next available location for global arrays as the origin of the present array, and then incrementing this next available location by the array length.
Assignment of storage for a block array is slightly more complicated. The next available block is forced to a block origin, and then taken as the origin. Finally, it is incremented by the length of the array.
When storage has been assigned, the value of the symbol is entered in the LST with the appropriate length and mode, and added to the specified half-words in the routine.
(iv) Non-zero length in ERT, non-zero length in LST. This is a backward reference to an array for which storage has already been assigned. The modes and lengths must be checked for compatibility: if the assigned mode (in LST) indicates that the array is in the chapter, the requested mode (in ERT) must not be block or global; if the assigned mode is global but not block, the requested mode must not be block; if the assigned length is positive, the requested length must be less than or equal to this. If these rules are violated, the current routine is asking for something different from the original assignment for the array, and the loader is not expected to cope with it. Errors on loading will cause a request for execution of the job to be deleted.
After checking, the value of the symbol is added to the specified half-words, as in processing the Parameter Use Table. Negative numbers indicate the end of each entry, and of the whole table.
(5) The Routine Symbol Table
This is a list of symbols defined in this routine. It is stored between the routine and the Parameter Use Table for convenience in searching while processing the latter. The Parameter Use Table and the External Reference Table can make adjustments to it. In the Routine Symbol Table, the mode distinguishes internal from external symbols, i.e. definitions restricted to this routine or not. There is no action for internal symbols. Entries for external symbols are simply copied into the Loader Symbol Table.
This table ends just before the Parameter Use Table begins, at a position already known to the loader. Processing of the BAS routine is then finished. and the loader returns to the local operating system to continue input of the job.
The end of each chapter must be indicated by a loader control directive recognized by the local system. The loader then completes the previous chapter by filling in forward references and supplying missing routines from the library. The remainder of the last Atlas block containing the chapter is cleared. The loader symbol table is revised for a new chapter by removing all symbols referring to locations in the chapter region. The value of the all-blank symbol is recorded as the chapter entry point. Other symbols might be recorded for diagnostic purposes.
If this is a multi-chapter job, the chapter is written on tape, and its position (with the chapter number) preserved for the chapter change routine. The next available location and end of last routine counts are reset, and loading of the next chapter begun.
If this is the last chapter of the job, the loader passes information about the job to the supervisor. This includes the amounts of storage needed for the various regions, and the entry point of the job. The local system exits to the supervisor, which may initiate execution of the job.
One problem which is left completely untreated in BAS is the two-level storage problem concerning B-registers. The presumption is that routines use the B-registers independently, and each routine must take care to restore to their original values any B-registers which it might have changed, before relinquishing control. The decision to adopt this approach was based on examination of a number of routines, comparing the number of B-registers needed with the number of instructions executed. It was found that in most routines a loss of only a few per cent is entailed, and this is tolerable.
However, since assignment of B-registers is quite independent of storage allocation, there is no reason why there could not be a more sophisticated loader for Atlas which carries out B-relativization, in addition to the storage allocation as in BAS.
It will be noted that the external references are adjusted explicitly. instead of using an indirect addressing technique. This method is more appropriate to the Atlas hardware, as there is no basic indirect addressing, and extracode indirect addressing is not sufficiently general. If BAS is developed for another computer which does have indirect addressing, a form of routine closer to BSS (1.B.M., 1958) would be appropriate.
We think that routines in the BAS form will be very convenient to use, since they have all the good features of BSS routines, which we know are convenient. The form of routine proposed for FORTRAN IV STRETCH (IBM 7030), described by Herzing and Larner (1961), has features like our public arrays, but nothing corresponding to parameters. We therefore consider that BAS routines represent a significant advance in compiler target languages.
FOTHERINGHAM, J. (1961). "Dynamic Storage Allocation in the Atlas Computer, including an Automatic Use of a Backing Store." Comm. A.C.M. Vol. 4. p. 435.
HERZING, W. P., and LARNER, R. A. (1961). "A Semi-Automatic Storage Allocation System at Loading Time," Comm. A.C.M. Vol. 4, p. 446.
IBM (1958). Reference Manual FORTRAN II, Form C28-6000-1.
KILBURN, T., HOWARTH, D. J., PAYNE, R. B., and SUMNER, F. M. (1961). "The Manchester University Atlas Operating System" The Computer Journal, Vol. 4, p. 222.
KILBURN, T., and SUMNER, F. H. (1962). To be published.
MCCARTHY, J., and CORBATO, F. J. (1960). '"Linking Segment Subprograms," Share Secretary Distribution No. 64C-1511.
We will describe the features currently proposed for HARTRAN, in order to indicate the possible action. The format could be different in other local operating systems, but the facilities would be similar.
* DEFINE X = Y, I = 50, J = I + 3
This directive creates new symbols in the Loader Symbol Table (LST). There can be as many definitions as will go on each DEFINE card. Each new name comes before an = sign; the value and mode are obtained by working out the expression on the right-hand side (in which all symbols must have been previously defined). A new entry is made in the LST. No other entries are changed.
* RENAME U/V, I/ J
This allows the names of symbols in the LST to be changed. The new name comes before a / sign; the old name comes after the slash. There can be as many changes as will go on each RENAME card.
In case there are any forward references using the old names, the Forward Reference Table (FRT) is processed whenever a RENAME card is met. The name in each entry is compared with names in the LST, and if a coincidence is found, the forward reference is filled in. Otherwise, the name is compared with the old names on the RENAME card, and changed if necessary. The entry is then moved to compress the FRT.
When the FRT has been processed, each old name on the RENAME card is compared with names in the LST. When a coincidence is found, the entry in the LST is changed. No new entries are created.
* GLOBAL A,B
This specifies that routines or arrays A and B are to be assigned storage in the global region. An entry for each is made in the LST with length zero and mode global.
* CHAPTER N
The chapter number N may be a decimal integer, or a parameter. The previous chapter (if there was one) is completed and the current chapter number noted. Then loading of the chapter can begin. The chapter is terminated by another CHAPTER or an ENTER directive.
* ENTER N
The number N defines the chapter to be entered. It may be a decimal integer, or parameter. or blank (meaning the last chapter loaded).
This directive marks the end of the program part of the job: the data follows immediately.
