Sue(ID:573/sue001)System language, used to write an OS for the IBM 360. Cross between Pascal and XPL. Allows type checked separate compilation of internal procedures using a program library. Holt et al University of Toronto 1971-1976 Structures: Related languages
References: in [ACM] SIGPLAN Notices 6(10) October 1971 Proceedings of the SIGPLAN symposium on Languages for system implementation 1971, Lafayette, Indiana, United States; October, 1971 view details in [ACM] SIGPLAN Notices 6(10) October 1971 Proceedings of the SIGPLAN symposium on Languages for system implementation 1971, Lafayette, Indiana, United States; October, 1971 view details in [ACM] SIGPLAN Notices 6(10) October 1971 Proceedings of the SIGPLAN symposium on Languages for system implementation 1971, Lafayette, Indiana, United States; October, 1971 view details in Computers & Automation 21(6B), 30 Aug 1972 view details in [AFIPS] Proceedings of the 1972 Fall Joint Computer Conference FJCC 41 view details Introduction Project SUE was established two years ago to design and build an extensible timesharing operating system for the IBM System/360 series of computers that would be flexible, efficient, reliable, and (above all) understandable [Atwood et al. 1972; Sevcik et al. 1972]. We started with the conviction that a suitable language and compiler would be vital to this task so we designed and implemented the SUE System Language [Clark and Homing 1971, 1972]. The System Language has, of course, had a major impact on the operating system we are creating. It has helped to structure the system and to reduce our total programming effort; we expect the final system to be more reliable and more understandable because of its use. However, this paper is primarily concerned with the converse effect: the implications of the operating systems project for the language. Out of our experience we have developed some rather strong opinions about many aspects of language design in this context - not all in agreement with current "folk wisdom". Most of our discussion follows from and illustrates two central principles: 1. The main function of a language is communication between people and it is essential that this communication be clear, convenient, and unambiguous. [Cf. Hill 1972] As systems grow larger, this communication becomes more crucial. [Cf. Conway 1968]. 2. The importance of high-level languages in the construction of systems comes at least as much from the errors and "clevernesses" that they prevent as from the powerful operations that they make convenient. [Cf. Wirth 1971a]. Extract: Intent Intent: The primary consideration in the design of a system programming language should be to facilitate the clearest possible statement of the programmer's intentions. A language which is even moderately successful in this respect will naturally play a major role in all phases of a project from design to documentation and maintenance. It will, in fact, blur the distinctions and lower the communications barriers between the various phases. Within Project SUE, we have found that the System Language serves as our language of design, as well as of programming; the programming task is now a natural continuation of the design task. An immediate consequence of this principle is that when programmers are concerned with communicating algorithms, rather than sequences of machine instructions, the language should be algorithmic, rather than machine-oriented. From our experience with Project SUE, we feel that at least 95% of an operating system can and should be stated in algorithmic terms; correspondingly, the language should be nearly machine-independent, and machine dependent statements should be easily isolated. (Although the System Language was originally designed for the IBM System/36O , the production of a compatible compiler for the DEC PDP-11 encountered no major difficulties). Our regrets involve those machine-dependent features (e.g. , bit (n) as a data type), that we included in the System Language, rather than any that we omitted. We have also found that only a small amount of explicit application-dependence is needed. The innermost layer of the operating system requires a few occurrences of peculiar machine instructions (e.g., Load Program Status Word) and data structures (e.g., New Program Status Word). Other layers require access to system primitives (e.g., inter-process communication) provided by this layer; syntactically, these are procedure calls, but they are implemented as supervisor call operations (SVCs). With these two exceptions, the System Language differs from a general-purpose language mainly in the features (e.g., floating point) that we could dispense with. Figure 1 shows the listing of a typical segment from our operating system (part of the timer manager); the reader should note the low degree of machine- and application-dependence. Extract: Structure Structure: Structure is vital for the creation of coherent, understandable systems. We distinguish four types of structure affected by our choice of language: control structure, data structure, visual structure, and programming structure. It should no longer be necessary to argue the disadvantages of undisciplined control constructs such as GoTo. [Dijkstra 1968; Wulf 1971a, 1972; Mills 1972]. However, it is not sufficient to merely delete these constructs from the language. They must be replaced by disciplined constructs that are both clear and efficient. A formally adequate minimal] set, such as while plus sequential execution [Ashcroft and Manna 1971] is not very useful in practice, since programs get longer [Knuth and Floyd 1971], to the detriment of both clarity and efficiency. We have found that each of the following constructs contributes to the construction of well-structured, readable programs: selection, provided by if then else and case; iteration, both bounded (do with controlled variable) and unbounded (cycle); procedure call; exit and return, to escape from iterations and procedures; and block structure, to delimit the scope of names. Taken together, these also seem to be quite sufficient for practical use. Most algorithms in our operating system are straightforward, once the data structure has been designed. Thus we rely heavily on the data-structuring capabilities of the language, and its ability to communicate the intended information content of the data (rather than the collection of bits which will represent it). Fortunately, this has been nicely handled in the language Pascal [Wirth 1971a], which we adopted as our model. Readability is one of our major concerns, and the layout of programs on the page is one of its major determinants. Good programmers use such "paragraphing" techniques as indenting subsidiary structures (e.g., the bodies of loops), aligning matching brackets (e.g., begin and end), and judiciously inserting spaces and blank lines, all with the intent of making their programs both more attractive and (since visual structure matches control structure) more readable. Simple rules can be given for paragraphing, and consistency in their use is more important then the particular rules chosen [Gordon 1973]. Our compilers automatically paragraph all programs, thus ensuring consistency and removing from the programmers the chore of keeping their programs properly paragraphed. They also use the lower-case letters available on our line printers (BUT NOT OUR KEYPUNCHES) to further enhance readability. Finally, we structure the programming process itself. Project SUE has adopted a "top-down" programming methodology [Dijkstra 1970; Mills 1972; Wirth 1971b3. At each stage we have a complete algorithm, generally stated in terms of operations to be defined in later stages. These definitions may take the form of either procedure declarations or macro declarations, since procedure and macro calls are syntactically identical. Either form preserves in the source program the conceptual structure that guided its construction; the trade-off is one of space and time efficiency. We have also adopted the very useful guideline that each refinement (procedure or macro body) must fit on one page [Mills 1971]. Decision-making: Some languages present the programmer with many ways (generally not equivalent) to express the same algorithm; it is also common to require him to make decisions about the internal representation and processing~ of his data. We do not view such ,flexibilities" as virtues. Every decision requires time and presents an opportunity for error. Our approach is to reduce the number of alternatives facing the programmer, to restrict his decision-making to items that really matter, and to attempt to explicitly record as many of his decisions as possible within the program -- rather than hoping he will remember to include them in comments or external documentation. The crucial decisions in our operating system have largely been associated with data structures. It is not uncommon for a project member to spend several weeks preparing the declarations for a module, and then to write the executable code in a few hours. The data structures introduced in Pascal [Wirth 1971a] largely free the programmer from decisions about machine representation, and facilitate the statement of design decisions about the information structure. This trend was strengthened by our decision to ban all "mystery numbers" (i.e., integer constants greater than two) outside of constant declarations. Extract: Redundancy Redundancy: All error-checking is based on the availability of redundant information. The conciseness of high-level languages is obtained by the elimination of redundancy, yet they allow more extensive error detection than low-level languages. There is a distinction between useless (unchecked) redundancy, which can only introduce errors, and useful redundancy, which serves to detect them. Traditionally, high-level languages have two major error-screening mechanisms: syntactic redundancy and mandatory declaration. If the programming style is to use long, dissimilar identifiers, these two mechanisms can catch most keypunching errors, but few "logical" errors. Careful type-checking - - particularly in a language with many data types -- detects another class of errors. Assertions [SIGPLAN/SIGACT 1972] can be checked at compile-time (given an adequate theorem-prover) or at run-time (as in Project SUE). Selection by name, rather than position, allows additional checking. The development of effective forms of redundancy that will not excessively burden the programmer is an area of continuing research. Some attempts at reducing the redundancy of languages seem to be misguided. Allowing keywords to be used as identifiers and allowing terse abbreviations of keywords not only detracts from readability, it increases the opportunities for undetected error. Both "typeless" languages (e.g. BLISS [Wulf 1971b], and BCPL [Richards 1909] and languages with automatic type conversion (e.g., PL/I [Hopkins 1971]) defeat type-checking, which has been the most useful single screen for "logical" errors within Project SUE. Some forms of redundancy present in many languages are not very effective in error detection, because they are uncheckable or merely involve duplication (inviting duplication of errors). For example, common or external statements permit the separate compilation of cooperating modules, provided that these statements 8re identical in both; typically, these are long statements whose accuracy cannot be checked by the compiler, and any error will have serious consequences. The mechanism for separate compilation in the System Language is much more complex [Clark and Horning 1971], but it has the virtue that only a single identifier need be duplicated to permit sharing of variables and complete type-checking. We expect this to be a major advantage during system integration. Although assembly languages are highly redundant, they do not facilitate error-checking. In fact, beyond checking that every symbol is declared, there is very little inter-statement checking that even the most conscientious assembler can perform, since every sequence of valid instructions must be accepted as a valid program. This lack of useful redundancy is a serious handicap to the use of even the most powerful macro-assemblers in systems programming. By contrast, we have found that by the time a System Language program is accepted by the compiler it is generally free of logical errors; "debugging" is replaced by "verification". Efficiency: It is, of course, important that operating systems be efficient. Although high-level languages reduce the cost of programming, ease the tasks of documentation, maintenance, and modification, and increase reliability, system programmers have traditionally been willing to sacrifice everything for the "efficiency" of assembly language. We believe that this is a serious mistake. Empirical studies show that typical programs spend over half of their time executing less than 4% of their code [Knuth 1971; Alexander 1972]. (Furthermore, the author of a program seldom knows where the crucial 4% is). A poor choice of algorithm or data structure can slow a program down by orders of magnitude, which no amount of "fine tuning" or "bit twiddling" can recover. Thus, for efficiency, it is important that the system automatically collect performance data and that decisions be easily reversible and their impact on the program localized [Corbato 1969]. The immense inertia of large assembly language programs makes it excessively difficult to abandon basic data structures or algorithms, even if deficiencies are detected. Programmers have limited short-term memories, and can optimize effectively only over small stretches ( a few pages) of code. Furthermore, crucial decisions (e.g., register allocation) are bound as the code is written, making optimization over complete programs difficult. Thus, although assembly language programmers often produce code which is locally better than compiler output, there is reason to doubt that they consistently produce globally superior code. We believe strongly in the "no surprise" rule: No language construct should have consequences that surprise the programmer, either in its effect or in its resource consumption. Programmers who are not surprised are far less prone to producing inefficient~ code. Fortunately, we have found that the criteria of clarity and efficiency do not generally conflict. One exception on the System/360 is the procedure call construct, which is surprisingly expensive for a block-structured language, due to clumsy machine architecture [Dijkstra 1972]. Finally, we observe in practice ( and suspect that someone could prove) that the efficiency of the code produced by a compiler has an inverse relation to the size of the language it must deal with. Although the System Language as originally described [Clark and Horning 1971] was of modest size, we now feel that it should have been smaller. Our programmers work quite effectively within an "official subset," and we have dropped all plans to implement the full language. Extract: Conclusion Conclusion: Many of the points we have made were brought to our attention by the problems of scale and complexity involved in constructing an operating system. Yet they also seem to apply to the construction of smaller programs. We expect that good languages for writing operating systems will come to look more and more like good languages for "applications programming," as both kinds of languages improve. in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details Extract: Introduction Introduction There are several areas where traditional high-level languages are notably less efficient than hand-coding. Two of these areas are accessing array elements and calling procedures. Although in the former case much research has been done to improve the efficiency (resulting in the ALCOR and FORTRAN H2 compilers), little work has been published on calling procedures. In many scientific computations procedures are not called very frequently but this is not true in non-numeric work. Since modularisation by means of procedures is one of the most powerful programming tools in structuring complex problems, an inefficient calling mechanism can be very detrimental. In recent years there has been an increased use of high-level languages as assembler replacements ? the so-called 'System Implementation Languages'. Such languages must achieve a high degree of object code efficiency if their use is to become more widespread. The purpose of this paper is to compare the procedure calling mechanism of traditional high-level languages with both system implementation languages and machine-code. Extract: Ackermann's function Ackermann's function In view of the paper by Sundblad [1], a reasonable test case for study seemed to be the evaluation of Ackermann's function. This function has the advantage of being very short and not requiring large integer values for typical cases, yet being complex enough to be a significant test. The figures given in Sundblad's paper also provided a basis for comparison before many values had been obtained. Following Sundblad, we calculate Ackermann (3,n) for increasing n, in accordance with the complete program listing below. Three figures are determined from the test, the average execution time per call, the number of instructions executed per call and the amount of stack space required for each call. Although the average time per call can be determined from running the program, the other two figures cannot be found so easily and indeed, in many cases the figures are not available. [1]Y. Sundblad, The Ackermann function. A theoretical, computational and formula manipulative study. BIT 11 (1971), 107119. Extract: Acknowledgements Acknowledgements This work has been inspired by the International Federation for Information Processing Working Group 2.4. The desire of the group to obtain information on the performance of system implementation languages has led to tests such as this. It would not have been possible to write this paper without the active help of the following persons in running the test: ? Mr. L. Ammeraal (Mini-ALGOL 68), Dr R. Backhouse (B5500), Dr J. G. P. Barnes (RTL/2), Dr D. A. Bell (PL516), Dr H. Boom (Cyber 73 ALGOL 68), Mr P. Klint (C-UNIX), Mr R. Conradi (MARY, CYBER 74, 1108, CDC3300), Mr W. Findlay (PASCAL 1906A & machine code), Mr W. B. Foulkes (PASCAL 370/158). Professor G. Goos (B6700), Mr. V. Hath-way (BCPL MOD 1), Mr M. Healey (PL/I OPT), Professor J. J. Horning (Sue 11), Mr B. Jones (ALGOL 60, Dclft 370/165), Dr M. MeKeag (PASCAL & ALGOL 60, 1906S), Mr Z. Mocsi (R10), Dr J. Palme (DEC10 SIMULA & machine code), Mr M.J. Parsons (PALGOL), Dr M. Richards (BCPL), Professor J. S. Rohl (Manchester 1900 ALGOL), Mr P. D. Stephens (IMP), Dr P. Wetherall (ALGOL 68-R), Professor N. Wirth (PASCAL), Professor D. B. Wortman (370/165 machine code) and Professor W. A. Wulf (Bliss 10, Bliss 11 & machine code). Extract: Results of tests (altered to include authors where known)
Program listing begin integer i, j, k, k1; real t1, t2; integer procedure Ackermann(m, n); value m, n; integer m, n; Ackermann := if m = 0 then n + l else if n = 0 then Ackermann(m -1,1) else Ackermann(m - 1, Ackermann(m, n - 1)); k:= 16; k1 := 1; for i := 1 step 1 until 6 do begin t1 := cputime; j : = Ackermann(3, i); t2 := cputime; if j = A;-3 then outtext(1, 'WRONG VALUE'); outreal(1, t2 ? t1); comment Now output time per call; outreal(1, 3 x (t2 - t1)/(512 x k1 - 15 x k + 9x i + 37))); k1 := 4 x k1; k := 2 x k end end Extract: Properties of the algorithm Properties of the algorithm To determine the execution characteristics of the test one needs the following properties of the algorithm (which can be easily proved by induction). The number of executions of each leg of the algorithm in calculating Ackermann (3, n) is: first leg: (64x4|n- 72x2|n + 6xn + 26)/3 second leg: ( 24 x 2 | n - 3 x n - 12)/3 third leg: (64x4|n- 72x2|n + 6xn + 23)/3 total no. of calls = (128 x4|n- 120x2|n + 9xn + 37)/3 Hence for large n, the average number of instructions per call is half the number of instructions in the first and third legs. Both legs contain the procedure entry and exit overheads and the third leg includes two unsuccessful tests for equality with zero. So the number of instructions executed per call can be found by examining the machine code produced by the compiler. Unfortunately this is not always easy and sometimes almost impossible. To provide an approximate comparative value, an estimate has been made from the time using a Gibson mix value [2] to extrapolate from a similar machine. In a few cases, the instructions executed arc known but the time has not been measured. In these cases, an estimate for the time is given based upon published instruction times. The amount of stack space required by the program is determined by the maximum depth of procedure calls. This is given by Sundblad as Ackermann(3, n) - 1 = 2 | (n + 3) - 4 and occurs when the third leg is being evaluated at all but the last of those levels. Hence the amount of stack space required doubles when n is increased by one. For a more detailed discussion on the storage requirements and the definition of the 'maximum depth of recursion' see [5]. To measure this space, Sundblad observed the maximum value of 11 for which Ackermann (3, n) could be calculated using 26K words of store (which he called the 'capability'). Although this measurement is easy to take, it only provides a rough estimate of the space needed per call. Examination of the machine code of the third leg of the algorithm gives the precise value. In fact, the number of words per call is the difference in the address of 4m in the inner call to the address of the parameter in the routine. It is not easy to calculate this value from the code, and so a post-mortem print may be the easiest way to find the value. Rather than give the capability, the number of words per call is listed with the results. If only the capability is known, bounds can be given for the number of words per call by assuming that between 3K and 10K words are needed out of the 26K store for the program and run-time system. Extract: Notes on the results and Factors influencing the execution speed Notes on the results Estimates of missing values are included in the table in brackets and have been calculated in the manner described above. The program listing in all cases has followed the coding given very closely. The only exceptions are 1) the machine code examples, 2) the PASCAL and SUE systems which have no conditional expressions, and 3) PL516 which follows the hardware of the machine in not supporting recursion (stacking is performed by subroutines). Factors influencing the execution speed Factors influencing the call of a recursive procedure vary from inherent problems with the architecture of the machine to purely software problems on the design of the procedure calling mechanism. Against each of the results above is a sequence of letters and digits which describes the principle characteristics governing the execution performance. Recursion. On most modern machines with a few base registers and indexing facilities, the basic overhead of recursion is very small indeed. A few minicomputers do not have adequate base registers or addressing facilities to support recursion. The Honeywell DDP5l6 is of this type, hence with the high-level assembler PL516 stacking must be performed explicitly. On some machines, although the addressing logic is available an additional time penalty occurs by addressing via pointers. On the Modular 1 implementation of CORAL 66, recursion is an option. In fact the code produced with recursion is more efficient than that without recursion. The reason for this is that the short address length of the Modular 1 means that base registers must be loaded to access the variables of another procedure. This is a larger overhead than that incurred using a single stack register which only needs to he incremented and decremented by a small amount. Without recursion, the number of instructions is increased to 19.5 (30% more). Storage allocation. In order to execute this program, a stack storage scheme is necessary. It is sometimes possible on conventional hardware to use an area in the store as stack without performing an explicit software check for stack overflow. One can then rely upon a hardware address violation which should permit the output of a suitable diagnostic. Such systems are marked by an N, whereas C denotes a software stack overflow check. Languages such as ALGOL 68, PL/I and SIMULA require more than a simple stack and hence must perform an overflow check in a manner which allows a recovery to perform some garbage collection. Systems like this arc marked with an H. PASCAL permits additional storage apart from the stack but without garbage collection. Although no garbage collection is involved, PASCAL is marked with an H. Only SIMULA requires an actual garbage collection during the execution of this test. The method used to administer the stack is partly a matter of language design and partly a matter of implementation. For instance, although ALGOL 68 requires a heap, the ALGOL 68-R implementation will run a stack only if the program does not require the heap. The difference, shown above, is that an additional subroutine is called on procedure entry to check that adequate stack space is available. Complete display. Block structured languages in general require a base pointer for every block whose variables can be accessed at the relevant part of the program. This facility is marked with a D. Languages such as BCPL and Burroughs B5500 ALGOL restrict access to local and global identifiers only, permitting a significant economy in pointers. These languages are marked with an L. The actual method of implementing the display can vary independently of the language. For instance, ALGOL W and IMP have every base pointer in a register, the PASCAL implementations above backchain the display (from the local procedure) and ALGOL 68-R keeps a copy in core of the full display in the local block. In almost all cases, there will be small variations in the calling overhead depending upon the relevant positions (in the display) of the call and the procedure. Dynamic stack storage. In ALGOL 60, the sizes of arrays are not, in general, known until program execution. This facility, implemented with second order working store, requires a small overhead on the administration of stack storage even when no arrays are being used, as in this test. Languages requiring such storage are marked with a 2 whereas systems allowing only storage whose size can be determined at compile time are marked with a W. PALGOL and RTL/2 are LW languages and hence require only one stack pointer (and one pointer for static storage depending upon the addressing structure). Parameter handling. The most expensive mechanism is marked with a T which denotes a 'thunk' that is required to implement the ALGOL 60 call by name [4]. A thunk can be avoided with this test by performing all parameter checking at compile time and using only the value mechanism (V). The KDF9, B5500 and Atlas ALGOL compilers all use the value mechanism. The use of the thunk mechanism by the other ALGOL 60 compilers is caused by the problem of handling the call of formal procedures whose parameters cannot be specified [3]. With value parameters, the ICL 1900 ALGOL compiler uses a simplified thunk mechanism but the Manchester ALGOL compiler uses the value mechanism. The PL/I systems use call by address which is marked with an A. With recursion, the addresses of parameters are dynamic and in consequence this method is less efficient than call by value. Open code or subroutines. Systems which handle this test entirely by open code are marked with an O, whereas the use of subroutines is marked with an R. The PL/I optimising compiler generates a subroutine call, but it is not invoked unless insufficient stack space is given (which did not happen in this case). Extract: Conclusion Conclusion. Ackermann's function provides a simple method of comparing the efficiency of the procedure calling mechanism of a language permitting recursion. The results show a very wide variation in performance even for languages containing no inherent complications. Additional instructions required in ALGOL 68, PL/I and PASCAL to check for stack overflow are quite insignificant compared to the hundreds of extra instructions executed by the inefficient implementations of ALGOL 60. There is no doubt that 'System Implementation Languages' give very much better results on this test without reducing the facilities to the programmer. Machine independence seems to be realised in this case without any measurable cost as BCPL shows. Does Ackermann s function represent a good test for a system implementation language? Unfortunately no statistical information is available to the author on the use of procedures in operating systems and compilers etc. Hence it is not known if, for instance, two parameters is typical. The large amount of stack space used is certainly not typical and can result in pathological situations. For instance, stack space is claimed in 64 word units under George 3 on a 1906A, but is not released. Hence during the first part of the algorithm when the stack is being increased a large operating system overhead occurs. During the second part when the stack is rarely increased beyond its previous maximum, there is no significant overhead. The computational part of testing for the equality with zero, jumping and adding or subtracting one seems very typical of non-numeric work. On the 360 computer, the fact that the the algorithm is very short ( <4K bytes) results in a small saving, but on the IMP compiler which can take advantage of this the speed was only the increased by 3%. From the better figures produced by system implementation languages, the code for Ackermann is roughly divided as follows: instructions subroutine entry and exit 2 stacking return address 1 setting up environment 3 checking for stack overflow 2 (if check made) restoring old environment 3 (on procedure exit) setting parameters 2x1=2 body of Ackermann 8 Total 21 in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details Separate compilation of program units is a practical necessity. Its basic goals are to permit the separation of large programs into simpler, more manageable parts, and to create libraries of program units. Separate compilation helps to reduce compilation costs and to simplify the development and management of program corrections and modifications. For large projects involving several programmers, separate compilation permits program texts to be separated physically in a way that reflects the division of work and responsibilities. Once the common interface between two parts has been agreed upon and recorded, the two parts can be developed and compiled separately. The fact that the common interface is a physically separate text guarantees that separate recompilation of either part does not invalidate the common interface. The physical separation of program texts may be viewed as a support facility for the structured programming concept of refinement. It may also be used to conceal the text of a subprogram body from users who are only allowed to call the subprogram. Such concealment may be justified either for reasons of confidentiality or in order to prevent the user from inferring implicit properties or making assumptions regarding the functioning of the subprogram. Finally this physical separation facilitates the construction of libraries and reusable software components. It is appropriate at this stage to introduce the distinction between independent and separate compilation (following J.J. Horning). Independent compilation has been achieved by most assembly languages and also by languages such as Fortran and PL/1. Compilation of individual modules is performed independently in the sense that the modules have no way of sharing knowledge of properties defined in other modules. Independent compilation is usually achieved with a lower level of compile-time checking of consistency between units than is possible within a single compilation unit. In consequence, independent compilation came into disrepute and was rejected by safety-minded early typed language definitions such as Algol 68 and Pascal. Fast compilation of the complete program was often advocated by promoters of these languages as a safe alternative to independent compilation. However, fast compilation has its limits, and it fails to answer the needs of confidentiality and libraries. Separate compilation, on the other hand, reconciles type-checking safety and the pragmatic reasons for compiling in parts. It is based on the use of a program library which contains a record of previous compilations of the units that form a program. It has been developed in the language Sue and in later languages such as Lis, Jossle, Mesa and later extensions of Pascal and Algol 68. We next discuss its properties in terms of what is provided in Ada. When a program unit is submitted to the compiler, the compiler also has access to the program library and is therefore able to perform the same level of checking (in particular type checking) whether a program is compiled in many parts or as a whole. It is the existence of the program library that makes the compilation separate but not independent. Using the general information available in the program library, the compiler will be able to assist the user in organizing recompilations. In particular, it will be able to display information about the current state of the compilation of a program that is divided into several compilation units: which separate program units have been compiled, and which need to be recompiled because of prior recompilations. It is thus for reasons of safety and utility that Ada offers a powerful facility for separate compilation. Two additional criteria have been followed in this design, namely simplicity of use and simplicity of implementation. Separate compilation being a user-oriented facility, it should be simple to understand and use. Consequently it should not introduce other concepts than those required by the nature of separate compilation. Scope rules and the general form of separately compiled program units should be similar to those of other program units. In addition, separate compilation should be implementable simply and efficiently. The additional work required for separate compilation should stay within reasonable limits, since one of the goals is to save overall compilation and recompilation time. in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details |