METAPLAN(ID:6199/met017)Semantics-directed compilerfor META Programming LANguage Semantics directed compiler Related languages
References: METAPLAN METAPLAN stands for META Programming LANguage, and denotes a computer-independent language at the compiler level. METAPLAN statements are of two types: declarative and imperative. Declarative statements declare data of several kinds, including: data in tabular form, whole word and partial word data, and programmable switches. Imperative statements specify the program flow, moving and testing of the data, and arithmetic operations. A typical imperative statement is: IF F(A) PLUS 5 EQ G(B) GOTO L In this example, F and G are previously declared fields. Let's assume the F field is the 3rd to the 6th bits of the argument (in this case, A), and that the G field is the last 15 bits of the second word following the argument (in this case, B). Optimum code is generated to load the contents of A, isolate the 3 bits of the F field, add 5, and compare the result with the last 15 bits of the word at B+2. What actually happens here is that IF, PLUS, EQ and GOTO are procedure calls, each with an argument. The four calls together constitute a many-to-many macro, many procedure calls producing many instructions in the object code. Those of you who have dealt with the problem of generating optimum code in this kind of situation will recognize that treating IF, PLUS and EQ as unrelated one-to-many macros, and generating code from each in turn, would not in general produce optimum code. The many-to-many macro, however, gives the translator the ability to look ahead to future requirements (or back) and thus hold shift operations to a minimum, take advantage of particular computer commands which load and store address fields, etc. Furthermore, the actual code to be generated by the procedures is expressed in assembly language, whereas in a conventional compiler it is hidden within the compiler program itself. What we have here is a way of exhibiting the semantic content of a compiler statement, just as recently developed syntax-directed techniques have made it possible to exhibit the syntax of the compiler language. METAPLAN is essentially a semantics-directed compiler. It seems likely that semantics-directed compilation techniques will have an impact on the compiler technology of the next few years comparable to the impact that syntax-directed techniques have had in the last few years. By combining syntax-directed and semantics directed techniques, implementors can adapt an existing compiler or meta-assembler to a new computer in weeks, rather than coding an entirely new program over a period of months. In fact, the bulk of the task consists in programming I/O routines and a loader for the new computer, The introduction of the many-to-many macro, and the resulting development of METAPLAN and the concept of the semantics-directed compiler, have brought the meta-assembly program to its current state of evolution. Abstract: A generalized assembler called a "meta-assembler" is described. The meta-assembler is defined and factors which contributed to its evolution are presented. How a meta-assembler is made to function as an assembly program is described. Finally, the implication of meta-assemblers on compiler design is discussed. Extract: METAPLAN Introduction A meta-assembly program is a machine-independent assembly program. It is machine independent in the sense that both the assembly language which it is to accept (the source language) and the machine code which it is to generate (the object language) are supplied as part of the program to be assembled. That is, both the source language and the object language are input parameters to the meta-assembler. The name meta-assembler was coined by analogy with the word meta-language. A meta-language describes a language; a meta-assembler describes an assembler. The term is not directly related to the term meta-compiler, which has recently come into use. A meta-assembler is probably more closely allied to what has recently been called a macro expander. Meta-assembly is a proven technique. Several metaassembly programs have been implemented and are operating on many different computers. They have been used to create assembly programs for these computers and for a number of other computers, some with characteristics very different from those of the base computers. The meta-assembly process is briefly described here, and a few remarks are offered on existing meta-assembly programs together with developments that distinguish each from its predecessors. The paper concludes with a brief description of METAPLAN, a computer-independent systems programming language based upon the metaassembly technique, which is translated by way of metaassembly programs. in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details METAPLAN (Ferguson [Fer 66]) The article by Ferguson is taken from the ACM Programming Language Conference, San Dimas, California, 1965, and contains a good introduction to meta-assemblers. The basic ideas arose from observing that all assemblers have many features in common. By building procedures for handling such things as symbol tables, location counters and macros, one could speed up the writing of particular assemblers. To construct an assembler for a particular machine one would specify word size, number representations, and the like. Output for each machine would be programmed using format statements and could easily include relocation or symbolic debugging information. While such a system seems feasible and quite useful for writing assemblers, it is not obvious how one would extend it to a TWS. The use of a meta-assembler as a TWS is based on the previously mentioned assumption that the compiler is a special case of the macro assembler. Discussions of this assumption sound like a reincarnation of the macro versus high level language debate. The macro assembler side is on the defensive, is outnumbered, and therefore has been the most vehement in argument. The whole situation is further complicated by a lack of agreement on what an assembler is (cf. discussion following the paper [Fer 66]). An example will suffice for our purposes. Fergnson describes how a recta-assembler would handle the compiler-like statement: 1F F(A) PLUS 5 EQ G(B) GO TO L. He would have IF, PLUS, EQ, and GO TO be defined as (prefix) operators using a scheme called many-many macro. The many-many macro has features for using and updating state information during text replacement. This attacks the main problem in the more general use of macros--the effective use of global properties (state information) in the assembly process. The many-many macro is probably flexible enough to implement any known compiler; the real question is whether the many-many macro is a good way of doing it. The answer to this depends on the mechanisms for recording and using state information, and these are not discussed in the paper. Extract: PLASMA PLASMA (Graham and Ingerman [GraM 65]) The meta-assembler effort of Graham and Ingerman concentrates mainly on the problems of substitution and binding. They are much less concerned with syntax than Halpern (next discussion), because they assume a syntaxdirected front end (presumably [Ing 66]) for a compiler written in their system. The basic input to their meta-assembler is a "line" which is a list of lists. The first list is a generalized label consisting of a symbol, the number of higher levels at which it is active, and the number of lower levels at which it is active. The second list contains the operation, and the third contains the operands. The input is converted into a tree, and substitutions are made on the basis of the tree structure. By allowing substitutions by symbolic or numeric value, they combine the text replacement with assembly functions. The authors are continuing their work at RCA, Cherry Hill, and will presumably report on it again. Their current efforts involve even more elaborate substitution processes. They have not, as yet, put forth specific suggestions on how their system might be used as the basis for a compiler. in [ACM] CACM 11(02) (February 1968) view details in Halpern, Mark I and Shaw Christopher J (eds) "Annual Review in Automatic Programming" (6) 1969 Pergamon Press, Oxford view details |