Extended ALGOL(ID:548/ext001)An extension of ALGOL 60, used to write the ESPOL compiler on Burroughs B5500, B6500, B6700. Places Hardware: Related languages
References: During the past year I have had the opportunity of working extensively with the Burroughs B5500 installed at the University of Denver. In the Burroughs i/o manual for the B5500, the preface points out that "... the formulation of this language was restricted to areas which are machine independent. Implementation of machine-dependent elements was recognized to be the responsibility of the individual computer manufacturer." Hence, any ALGOL implementation must be designed for the machine on which it is to operate, with the compiler including whatever unique routines may be required for communication with the processor, for i/o device utilization, for data editing, and for diagnostics. That few computers in the North American market utilize ALGOL bespeaks a seeming lack of willingness to exercise a real opportunity fox development of programming capabilities. Those who have experience with the Burroughs Extended ALGOL for the B5500 will appreciate its wide flexibility. Personally, I have used it for list processing, development of a perpetual in- ventory control system in business, and scientific and mathemati- cal programming including building the compiler of an electrical engineering circuit analysis language. Because of the thoroughness of the design of the ALGOL compiler in our equipment, I have found no region in which any limitation (other than my own lack of knowledge) exists. There is not, as Guier (quoted by Adams in the article cited above) stated "... the major implementation prob- lem ... of inventing methods for circumventing language limita- tions to allow the fullest use of the capabilities of the hardware." Perhaps I'm spoiled by having the opportunity to work with an effective ALGOL implementation. In fact, when Daniel McCracken spoke last spring at the Pikes Peak Chapter of ACM on his con- cepts of an "ideal" universal programming language, I could find not one feature mentioned which was not included in a thoroughly proven ALGOL implementation. Likewise, at the University of Pennsylvania in June, where an advanced digital computer pro- gramming course was given, several hours were devoted to an exposition of an over-the-horizon language with improved capa- bilities, the first of whose compilers was not, at that time, due until mid-1966. in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details Extendible Compilers -- Basic Concepts Many attempts (starting with McIlroy [McI1 60]) have been made to embed macro features in compiler systems. One approach was to retain the macro syntax form but add a number of built-in features which are compiler-like. The SET system [Ben 64a] included a skeleton compiler with input-output, symbol manipulation, table handling, and list processing features. These built-in routines were combined with translation time operations (action operators) in the attempt to build a TWS. A more successful approach has been to use the structured syntax of high level languages as a basis for extension. Many existing compilers (including PL/I [IBM 66]) incorporate simple forms of macro expansion, the first probably being JOVIAL [Shaw 63]. The most primitive form is pure text replacement without parameter substitution. For example, in B5500 ALGOL one could define a macro with the statement: DEFINE LOOP 1 = FOR I ~ 1 STEP 1 UNTIL N and later write statements like LOOP 1 N DO A[I] ~ 0 which would be expanded into FOR I ~-- 1 STEP 1 UNTIL N DO A [I] ~-- 0. The next step is to allow a macro definition with parameters. This facility has been included in the AED-0 compiler [Ross 66], among others. In AED-0 one might define a macro with the statement: DEFINE MACRO LOOP (P1, P2) TOBE FOR P1 ~-- 1 STEP 1 UNTIL P2 DO ENDMACRO. In this case, one could get the same result as above with the shorter statement LOOP(I, N) A[I] ~-- O. These two simple macro forms would form a useful addition to any high level language, and one might imagine developing mechanisms which parallel more sophisticated macro techniques. Although AED-0 does permit arbitrary strings as parameters, and nested definitions, features like conditional assembly do not seem to have been widely used in high level languages. One reason for this is that compilers normally depend heavily on the structure of the text; the next two sections describe the complexities that arise in trying to extend compilers with macro techniques. in [ACM] CACM 11(02) (February 1968) view details The Extended ALGOL for the Burroughs B5500 [...] is quite powerful and has added many useful features to ALGOL. Among the major ones are the following: 1. The ability to access a partial word by giving the beginning and ending bits. 2. A TIME function which can yield either the current date, or various elapsed times. 3. A concatenate expression which provides an efficient method of forming a primary (or Boolean primary) from selected bits of two or more primaries (or Boolean primaries). 4. A FILL statement which permits assignment of specified values to one row of an array. 5. A DOUBLE statement which causes assignment of the double-length result of Operations on double-length variables. 6. STREAM procedures which manipulate words, characters, and bits. 7. Edit and move statements. 8. Specific hardware and efficiency-oriented input/output statements. 9. An ALPHAbetic data type. 10. A DEFINE declaration to permit use of a single identifier for a longer legal program string. ll. SORT and MERGE statements. This language appears to have a great many facilities which are useful in business data processing and in character-handling applications, e.g., compiler writing. It is definitely a multipurpose language and has apparently been used to write its own compiler. in [ACM] CACM 11(02) (February 1968) view details in [ACM] CACM 11(02) (February 1968) view details B6700 Extended ALGOL as a Systems Programming Language The object of B6700 Extended ALGOL is to allow the programmer access to all machine and operating system facilities within the constraint that his program may not adversely effect other programs not created by the current execution of his program. The flexibility of the language is illustrated by the fact that all B6700 compilers, including the Extended ALGOL compiler itself, are written in Extended ALGOL. The Extended ALGOL compiler compiles large programs at a rate in excess of 4000 card images per minute thus proving that it is possible for a compiler implemented in a high level language to be both reasonably fast and to generate reasonably efficient code. The claim that the code generated is efficient is supported by noting that the compiler, which runs at reasonable speed (and is therefore reasonably efficient), is an ALGOL program. Certain extensions have been made to the ALGOL 60 language to facilitate its use as a systems programming language which, by the way, makes it a more powerful user language. These include, among many others: 1. Bit manipulstion facilities IF X.[5:2] = 3 THEN X.[9:I] := I; The above statement tests the two bits beginning at bit number five of the current value stored in the variable X against the value 3. If equal, then bit 9 of the value of X is turned on. 2. X := Z & Y.[31:20:15]; The value of X is replaced by the bit pattern at Z which is modified beginning at the 31st bit by the 15 bits beginning at bit 20 of the variable Y. Recursion The ALGOL language allows full recursion. If efficiently implemented, this provides a very powerful tool for the systems programmer. For example, in B6700 FORTRAN the following subscripted reference to the array X is allowed: A = B + X(B + SQRT(X(I))) This (possibly useful) extension to the FORTRAN language occurred due to laziness on the part of the implementor of the FORTRAN compiler. Subscripts are encountered frequently in the compilation of arithmetic expressions. Since the implementor was coding the expression routine which must, of course, compile generalized arithmetic expressions when he reached the point in the algorithm where he must call the subscript evaluation routine, he elected to call himself recursively rather than go to the trouble of coding still another specialized expression routine. 3. High Level Macros (Defines) The define capability is provided primarily for documentation and maintainability. DEFINE STATUS = [5:2]#, TESTPASSED = [9:1]#; A define indicates to the compiler that when the defined word is encountered in a subsequent statement, a direct textual substitution of the text appearing between the equal sign (in the DEFINE statement) and the pound sign should be made for the tokens parsed by the compiler. With the above DEFINE the following statement produces identical code to that produced by the first example under "Bit manipulation facilities" IF X.STATUS = 3 THEN X.TESTPASSED : = I; Similarly, a DEFINE may be "passed" parameters at compile time. If the following DEFINE, as well as the two above, has been encountered during the compilation process, DEFINE TEST (Z) = IF Z.STATUS = 3 THEN Z.TESTPASSED := l#; then the subsequent appearance of the statement TEST(X); will again produce identical code to that of the first example. 4. Inter-Program Communication While the ALGOL 60 language specification does not allow separately compiled procedures the EXTERNAL declaration for procedures in I%700 Extended ALGOL allows this feature. The system allows procedures to be explicitly "bound" to a host program prior to execution, implicitly bound at execution time, or even to be non-existant assuming that the procedure is not to be called during a given execution. While itself an important (and necessary) addition to the language as far as effective systems programming is concerned, EXTERNAL procedures provide an even more useful extension to the language when coupled with the multi-tasking facilities described below. Possibly the most useful extension made to ALGOL from the standpoint of its use as a systems programming language is the incorporation of Inter-Program Communication (IPC) facilities. Software EVENTs are included which may be CAUSEd WAITed upon or tested to see if they have HAPPENED. Both hardware and software INTERRUPTs (similar to PL/I on-conditions) are allowed which may be ENABLEd and DISABLEd. Any given procedure may be invoked via a normal procedure call as a coroutine partner, as an asynchronous process, or any combination of the three in any given program. Asynchronous processes and coroutines are assigned TASK identifiers by which they may be monitored and controlled through interrogation and assignment of their task attributes. Task attributes include as a subset those familiar in the PL/I language. Some of the additional attributes include: COREESTIMATE Estimated core storage requirement of the task (used for system scheduling purposes). MAXPROCTIME Maximum processor time to be allowed before the task is automatically terminated by the system. STATUS Current status of the task: Scheduled, active, temporarily suspended, terminated. HISTORY Reflects cause of termination of a task: Operator terminated. arithmetic fault, etc. EXCEPTIONTASK Identifier of the task to be notified of changes of status of this task. NAME By assignment to the NAME attribute of an inactive task and the subsequent activation of that task 8 program may refer to any program or procedure known to the system (compilers, user programs, etc.). By appropriate manipulation of task attributes the programmer may activate as a dependent, asynchronous process any procedure known to him as well as any program known to the system (subject to security constraints) including compilers, utilities, and other user programs. A measure of the relative conciseness of B6700 Extended ALGOL is reflected in the size of some of the B6700 compilers. The Extended ALGOL compiler is roughly 15,000 source statements in length; FORTRAN IV, level H requires 12,000 card images while a full CODASYL 68 COBOL is implemented in 25,000 statements. 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 The stack mechanism for this machine is designed explicitly for ALGOL. Unfortunately only two registers are available for the top of the stack and hence the stack instructions are not necessarily very fast. The special instructions for procedure call, array access, name call, etc. ensure that no more instructions are executed on this machine than with conventional ones even though it is a zero address computer. The real advantage of the B5500 is that it has very compact instructions (12 bits) and a short address length (10 bits). This allows B5500 ALGOL programs to be half the size (in bits) of their conventional counterparts. The space required for data, is, of course, unaffected. 'Man or boy' does not work on the B5500 due to a restriction on the stack size. Extract: Conclusion Conclusions The main advantage of a non-conventional architecture for the compilation of ALGOL 60 appears to be the production of extremely compact object code. This is achieved with the B5500 by a very short address length within an instruction. Because of the dynamic storage allocation of ALGOL 60, access to simple variables is always by a small offset from an environmental pointer. Hence an address length within an instruction of only 9 bits is adequate. Anything in excess of 9 bits is likely to be wasted. On the other hand, several index registers or their equivalent are necessary for environment control and array accessing. Such registers must be capable of being updated rapidly for procedure entry and exit, and for access to name parameters. Access to array elements is usually via an array word which can be addressed in the same way as a simple variable. A short address length may preclude some array access optimisation, for instance if 'a' is a global array of fixed size a[200] could be accessed by a single instruction provided the address field was large enough. In fact the B5500 does not allow array accessing optimisation because the storage protection system depends upon access via the array word (descriptor). The optimisation produced by the ALCOR compilers (Grau, 1967), could be done on a machine with a short address length, but not the B5500. Array bound checking is an area where special hardware can be used to great advantage. Unfortunately the hardware on the B5500 does not deal with the general value of the lower bound, so that explicit code must be generated by the compiler to subtract the value of this lower bound if it is non-zero. Options to do bound checking on other machines tend to be very expensive in processor time. The 1108, although having no built-in hardware for array accessing, has a convenient instruction for bound checking. With this instruction, a single test can be made to see if the operand lies within the range defined by two registers. Apart from the production of compact code from ALGOL 60, it is clear that in many scientific fields non-conventional machines can have other substantial advantages. Array bound checking has already been mentioned, but other examples lie outside the scope of this paper, for instance distinction between data and program and the ability to share the available core store between processes. The majority of these advantages are in the field of operating system design, and so are not considered here. Such advantages are likely to have a substantial effect upon the performance of the compiling system itself, and the easy way in which such systems can be developed. in The Computer Journal 15(1) February 1972 view details in ACM Computing Reviews 15(04) April 1974 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 ACM Computing Reviews 15(04) April 1974 view details in ACM Computing Reviews 15(04) April 1974 view details in SIGPLAN Notices 13(11) Nov 1978 view details |