L(ID:7225/l::009)Polish notation language Related languages
References: in [ACM] CACM 4(01) (Jan 1961) view details Introduction The use of an algorithmic programming language such as ALGOL requires the conversion of programs written in this language into programs in the language of the computer on which the programs are to be executed. While this conversion may be made directly, the conversion is often performed in two or more steps. Typically, translation is made to an intermediate language form, such as a symbolic assembly language, which is then processed further by an assembler or loader; another use of an intermediate language is with an interpreter used on the machine. The use of intermediate language forms in the algorithmic language conversion permits disentangling the process, the postponement of some necessary functions to other programs such as assemblers, loaders, and interpreters, the editing when desired in the intermediate form, and considerable overall simplification of the conversion. The purpose of this note is the description of a target language which is designed with the sole aim of simplifying the task of translation as much as possible. It may be used as an intermediate language in translation. The number of instruction types is relatively small. The language is machine-oriented to the extent that it has minimum parenthesis structure. This means that the commands, unlike those of .ALGOL, do not have recursively defined constituents. Each command may if desired be related directly to a complex of instructions on most current machines. Problems of efficiency, optimization and target execution time do not enter into consideration. For convenience we shall call this language L. The language may be considered to describe an addressless computer, since all commands, other than fetch instructions, may be specified by the operation alone--the operands are automatically at the top of a pushdown list. If the language L were to be implemented in hardware, the commands of L would be the instruction set of the resulting computer. While the language is designed to simplify the mechanical translation of a problem-oriented language, it may, if desired, be used directly as a symbolic language for hand coding. Since the types of tasks that make the mechanical translation of a problem-oriented language cumbersome and involved are in a direct use of the target language done by the programmer, the language has advantages in such use. In hand programming the difficulties are met by the training, experience and ingenuity of the coder. Use of this language in hand coding should tend to reduce much of the delay and debugging usually necessary in the use of ~ symbolic language. A corollary to this is that the structure of the language can also point out direction which improvements in machine hardware can take to facilitate both the translation of problem-oriented languages and the use of machines with hand coding in a symbolic language. A last application of the language is to the design and construction of a universal translator or translator generator. The first type of program would use as input ALGOL programs and the characteristics of a particular machine to produce programs in the language of that machine, while the second would from the characteristics of a machine used as input produce a translator usable on that machine. The use of a machine-independent translator-oriented intermediate language facilitates either type of program because the conversion from ALGOL to L is not dependent on the particular machine language. The conversion of L to machine language M would then alone need to take into account the peculiarities of M. This use of the language is closely related to the use of an UNCOL [5] in that the language provides a universal intermediate language between problem-oriented languages and a class of machines. While we have in view primarily the translation of ALGOL, the use of the language as target language equally well facilitates the translation from any other bracket-structure language such as COBOL or FORTRAN. The description of the language is followed by a discussion of how the language may be used in ALGOL translation. A particular advantage here is the relatively easy implementation of recursive procedures. The full discussion of all problems involved in the translation of procedures is, however, outside the scope of this paper In the design of this language I wish to acknowledge the inspiration of conversations with I. H. Bottenbruch. Extract: Structure Underlying the Language Structure Underlying the Language The language described results from an examination of the translation process for the ALGOL language based on the methods of Samelson and Bauer [1] and methods derived from them [2, 3]. In the course of translation it is necessary to employ in the target program a list h of generated labels and a list H of generated variables. The first is needed to handle the decomposition of bracket structure and the second to handle temporary storage requirements. The list L has elements l, l2, ? ? ? , lr, ? ? ? ? At any point in a program written in L, where a label is required, one is supplied from this list. The first one available is used, and each one is used as the label of at most one L-command. The list H is a pushdown list. Of the variables in the list, a certain set, ~1, ? ? ? , ~h are in use at any given time. New material that requires storage is added to the end of the list, i.e., is assigned to ~h+~ and following. Information is used and removed in last-in first-out fashion, so that the information assigned to ~ is always recalled before that assigned to ~h-1 ? After information is removed, ~h is available for reuse. For most ALGOL features, the variable allocations from the list H may be made at translation time; this may be called a static use of the list. However, this makes the handling of features such as function calls, nested procedure calls, and especially the implementation of recursive procedures difficult. It is more convenient and sometimes actually necessary to postpone the allocations to the time when the program is executed on the machine; this constitutes a dynamic use of the list. In this case the actual level of the list h is not available to the translator; therefore it places, instead, instructions for its manipulations into the target program. The actual level then is determined only at execution time. It follows that the counter h will not be an explicit constituent of the language L. Extract: Commands of L Commands of L The commands of L are of two types: (1) those without arguments, which are denoted simply by capital letters, such as V, B, G, or C, or by arithmetic, Boolean, or relational symbols, such as +, ×, V, and <, and (2) those with arguments. Each of the latter will be denoted by a capital letter followed by an identifier. In the course of translation the identifier arises from the handling of an ALGOL identifier. In this note it is convenient to let the identifier in L be the same as that from which it is derived in ALGOL. As an intermediate language, L must be related to both the source language (ALGOL) and also the final target language (machine language). To do the latter, each L-command may be considered to be equivalent to a complex of instructions performable on conventional machines. The complex consists of three parts: (1) an initial operation on a counter h, (2) a set of machine operations which may be described in augmented ALGOL, and (3) a final operation on the counter h. The three parts must be considered to be executed in the order mentioned. The operations (1) and (3) may each or both be stalls (no operation). To discuss the effect of the execution of the commands of L we use ALGOL notation. By itself, however, ALGOL does not suffice. To allow the equivalent of indirect addressing, the values of variables are permitted to be the usual things that ALGOL permits, and also names (that is, identifiers) of other variables and labels. This extension then uses two new operations: (1) V ~-- W. The variable name wis assigned as value to V. (2) C(V). The name of the variable which is the value of V. The operation (1) is in the augmented ALGOL a complete statement which can always be carried out. The operation (2) has meaning only when the value of V is actually a variable name or label as the ALGOL structure may demand. It can be used in any expression in place of the corresponding variable name or label. We illustrate the uses and meaning of (2). W := C(V) The value of the variable whose name is the value of V is assigned as value to W. in [ACM] JACM 9(4) October 1962 view details A second indefinite list of (internally) generated labels is used to provide an indirect jump list, thus eliminating the problems attendant to forward references (that is, transfer of control to a real or implicit label that has not yet been encountered in the source code). In addition, Dr. Grau has defined the assignment of the value "name" in assignments, and a "name function" C(x) which produces the name assigned to x. These extensions provide for indirect addressing from the top of the list 0, and are important in implementing "name calls" and "value calls" occurring in ALGOL. It is not clear that the use of this or any other intermediate language simplifies the translation process for most machines, except in the case noted by the author, where interpretation is to be used. In general, intermediate languages such as assemblers and the like are resorted to because they usually precede the compiler and provide the illusion that they offer mechanisms that are too difficult to implement in the compiler directly. Methods of handling library routines and forward references are usually the attractive features of using such assemblers. However, neither the proposed language or other assembly languages assist with the non-trivial techniques problems associated with segmentation of programs, handling declarations and the like. One of the uses of an intermediate language in translation is to provide a more tractable form for analysis to produce more efficient object codes. For this purpose one of the tree forms or list forms (Newell Simon and Shaw's) would appear more suitable for such manipulation. The efficacy of the language as an intermediate language for translation is of necessity a function of the properties of the target machine. Certainly the notation is ideal for those machines, present and planned, that implement implicit pointer controlled storage (either lists or stacks). The paper is highly recommended to those interested in a more formal motivation for some of the features to be found in machines such as the B5000 and KDF.9. in ACM Computing Reviews 5(04) July-August 1964 view details in ACM Computing Reviews 5(04) July-August 1964 view details |