ML/I(ID:295/mli001)Early macro translating system. Related languages
Samples: References: in [ACM] CACM 10(10) (Oct 1967) view details Charles Hootline, Cambridge University None of the panel members have mentioned microgenerators, and at Cambridge one of our graduate students, a chap called Peter Brown, has implemented a completely general purpose microgenerator called ML-1 which isn't oriented to any particular language but is rather just a straight processor. You describe your micro environment it it, take in one input string and outputs another string. We've had very considerable success with this general purpose microgenerator in implementing very quickly and readily special purpose languages. In particular we have used it to implement a systems writing language and then having decided what features we wanted in our language, using this general purpose microgenerator, we are now producing a compiler for this language, actually using the Brooker-Morris compiler on our Atlas computer. This microgenerator itself is implemented on our PDP-7 and on our Atlas computer and it is in fact written in terms of micros which is a part of the language itself, so when you transfer it from one machine to another one only has to recode the few very basic micros, and this is in fact how it was transferred from the PDP where it was originally written onto the Atlas computer. Now during the summer it is going to be put on the 1108 at the National Engineering Laboratory in Scotland and also on some ICT range of machines. I believe IBM did look into this in England but they decided, I believe, not to use this now. I'd be most interested to hear the panel' s comments on microgenerators because I feel they really are an essential part of any general purpose language system. in Proceedings of the 4th Annual ACM IEEE Design Automation Conference archive view details in Proceedings of the 4th Annual ACM IEEE Design Automation Conference archive view details There are at least three internationally accepted machineindependent high-level languages in which algorithms involving purely numerical manipulations can be encoded. Efficient compilers for these languages are widely available and it is rare that one is forced to resort to machine code for encoding numerical algorithms. The situation in this field, though not perfect, is therefore reasonably satisfactory. However, for algorithms involving a good deal of non-numerical manipulations and in particular for software, the situation is much less satisfactory. (The term 'software' is used here to mean compilers, assemblers, etc.-not the languages they compile.) It is possible to use some existing high-level languages for software writing or to use other tools, such as syntax directed compilers, but the resultant object code is normally large and inefficient. Non-numeric features are often treated interpretively. Hence these methods, though very suitable if one wants to get something working quickly, are not suitable for production software. There do exist some honourable exceptions to this, i.e. machineindependent high-level languages with non-numerical facilities and efficient compilers. These are sometimes extensions of well-known languages, such as Burroughs' extended ALGOL. However, these languages are not widely accepted and compilers often only exist for one machine or range of machines. Hence the advantages of machine-independence are largely lost. There is, in fact, a much more fundamental disadvantage in using predefined high-level languages for software writing over and above the fact that compilers tend to be inefficient. However general a language might be, it will never contain quite the right facilities needed for describing a particular piece of software. For example very few high-level languages provide an efficient way of implementing a dynamic stack in which data of varying types is freely intermixed. The basic problem is that for numeric working there is a fairly standard set of possible operations, data types and aggregates, whereas for non-numeric working there is a huge range of possible operations, data types and aggregates and it is not possible to represent these efficiently in terms of a few primitives. Hence when writing software in a predefined high-level language one is forced to adapt the design of the software to fit the facilities that happen to be available in the language, i.e., one tailors the software to the software-writing language. Because of the disadvantages described above, production software is still largely written in assembly language or in other machine-dependent languages suitable for software writing, such as PL360 (Wirth, 1968). If it becomes necessary to implement the software on a new machine, it needs to be re-coded, which is a most undesirable task. Extract: A DLIMP A DLIMP The purpose of this discussion is to describe a method of software implementation which uses a machineindependent high-level language but surmounts the problems described above. The method uses the ML/I macro processor (Brown, 1966, 1967) and is called a DLIMP, which stands for Descriptive Language Implemented by Macro Processor. Assume, therefore, that it is required to implement some software S on several different machines or. alternatively, some software S is to be implemented on one machine and it is thought it may be necessary to implement it on other machines, as yet undefined, at some time in the future. The first step of the implementation process is to separate the logic of S into its machine-independent part and its machine-dependent part. Typically the latter might include 110, hashing algorithms, data type conversion, routines dependent on individual character representations, etc., i.e., routines where the very logic is dependent on the object machine. Of course, the word 'machine-independent' is a rather loosely used (and much abused) term, and the above division must be made in a somewhat ad hoe manner. Moreover a distinction must be made between theory and practice. In theory if some software is expressed as a ~ u r i mna~ch ine it is machine-independent. However, this is not much use in practice. This paper is concerned with software that is machine-independent in practice and hence there is an added requirement of efficiency in the use of machines. The technique to be described below is only applicable if S is reasonably machine-independent. It is inapplicable if the machine-dependent part of S is as large as or larger than its machine-independent part, in which case S, by its very nature, needs to be largely rewritten for each object machine. Extract: The descriptive language The descriptive language After the logic of S has been separated out into its two parts, the next step of the implementation process is to design a descriptive language for the machineindependent part of S. This will be represented as DL(S). DL(S) is a machine-independent language with semantics designed especially for describing S and with syntax designed to be translatable by ML/I into the assembly language of any machine and preferably also into any suitable high-level language. Loosely speaking, DL(S) is a collection of machine-independent ML/I macros corresponding to all the primitive operations used in S. Note that both the operations and the data types in DL(S) are specially tailored to S. Thus if S involved a dictionary facility, DL(S) would contain operations for manipulating the exact type of dictionary used in S. Alternatively if S involved list processing, DL(S) might contain list data together with suitable operations for manipulating it. The designing of DL(S) would probably be concurrent with the last stages of the designing of S and would proceed incrementally, until a comprehensive and wellrounded set of macros for the description of S was accumulated. DL(S) would be an aid to the documentation of S and, in isolating the primitives needed, should be a help in the design of S. If one uses flowcharts, the macros in DL(S) would probably mirror the operations one writes in the boxes of a fairly detailed flow-chart. Extract: Reasons for using ML/I Reasons for using ML/I Almost any general-purpose macro processor can be used to perform a DLIMP but it is claimed that ML/I has considerable advantages because : (a) it allows freedom of notation in writing macro calls and sophisticated macros can be built up relatively easily (e.g. arithmetic expressions, ALGOL-like IF statements); (b) it allows macro calls within macro calls (e.g. a constant macro within an arithmetic expression macro within an IF macro); (c) it does not require any trip character to precede a macro call. Of these (c) is probably the most important. It means that ML/I is capable of performing systematic editing and it is unnecessary to specify in the descriptive language what is a macro and what is not. This is decided only when a mapping is made. The following example illustrates the advantages of this. In DL(ML/I) identifiers of up to six characters are used for program labels. In most mappings these were copied without alteration into the object program, i.e. they were not treated as macros. However, the PLAN assembler used on the ICL 1900 Series mapping only allowed five character labels, and so it was necessary to change all six character labels to five. It was possible to do this by including, within the mapping macros for PLAN, macros to scan for all six character labels and generate macros to replace them by five character labels, checking each for uniqueness. No messy hand editing was needed. Examples like this arose on nearly every mapping. In the PL/I mapping, for instance, it was necessary to map a series of data declarations into an array with an initial value and to replace references to the data accordingly. This facility in ML/I for systematic editing (i.e. editing involving commands to replace systematically one piece of text by another throughout a document) is the main reason why mappings have avoided most of the unforeseen difficulties that normally plague exercises in machine-independence because of the arbitrary differences between machines and between various compilers and assemblers. in The Computer Journal 12(4) 1969 view details in Halpern, Mark I and Shaw Christopher J (eds) "Annual Review in Automatic Programming" (6) 1969 Pergamon Press, Oxford view details Introduction The mobility of a program is a measure of the ease with which it can be implemented on a new machine. A user of a highly mobile program suffers minimum disruption of his work when his computer is upgraded or he moves to a new installation. Because his program is mobile, only a small amount of effort is required to get it running on the new machine before he can continue using it. Applications programs written in high level languages such as FORTRAN, ALGOL or COBOL have reasonable mobility, provided that the author has taken some pains to avoid local idiosyncrasies. For systems software, however, the picture is much grimmer. There have been many attempts to devise high level languages for compiler writing (Feldman and Gries, 1968) and a few to use such languages for the production of operating systems (Glaser, Couleur and Oliver, 1965). Unfortunately, none of these attempts has yet met with widespread success. A FORTRAN user requires a large programming system, consisting of the compiler and associated runtime routines. The mobility of his programs is determined by the number of installations which support this system. One can therefore argue that the mobility of a program is completely dependent upon the mobility of the programming system on which it rests. In this paper, I shall discuss a technique which I believe is fundamental to the improvement of programming system mobility. The background and general concepts from which the technique was derived are presented in Section 2, while the remainder of the paper is concerned with a specific system which has been designed and built using this technique. Section 3 describes the basic bootstrap on which the system rests, and Section 4 discusses the implementation of the common macro processor. The advantages and disadvantages of the approach are presented in the Section 5. Extract: General approach General approach The technique rests on the fact that it is possible to identify two components of any program: the basic operations and the algorithm which coordinates these operations. Given a particular task, it is possible to define a set of basic operations and data types needed to perform the task. These operations and data types define an abstract machine-a hypothetical computer which is ideally suited to this particular task. The program to perform the task is then written for this abstract machine. To run the program on a real machine, it is necessary to realise the abstract machine in some way. The abstract machine is an embodiment of the basic operations required to perform a particular task. Theoretically, it has no connection with any real machine, but practically we must always keep a wary eye on reality when designing an abstract machine. Many abstract machines can be formulated for a given task. The trick is to choose one of the right ones. ., Three considerations must be kept in mind- 1) The ease and efficiency with which the algorithm for accomplishing the task can be programmed in the language of the abstract machine. 2) The ease and efficiency with which the simulation of the abstract machine can be carried out on machines available currently and in the forseeable future. 3) The tools at hand for the realisation of the abstract machine. Balancing these three considerations is very much an engineering task. If one is stressed at the expense of the others, there will be trouble. An early attempt to use the abstract machine concept was the UNCOL proposal (SHARE, 1958). UNCOL was to be a UNiversal Computer Oriented Language which would reduce the number of translators for n languages and m machines from n x m to n + m. Effectively, the UNCOL proposal created a single abstract machine. In view of the three considerations mentioned above, it is easy to see why this attempt was unsuccessful-try to design an abstract machine which comes close to satisfying condition 1 above for FORTRAN, LISP (McCarthy, 1960) and SNOBOL (Griswold, Poage and Polonsky, 1969) simultaneously! The mobile programming system circumvents this difficulty by allowing a multiplicity of abstract machines. It does not attempt to solve the n x rn translator problem. The advantage of the mobile programming system lies in the fact that it reduces the specification of an algorithm to the specification of its basic operations, thus drastically reducing the amount of effort needed to implement it. One way to carry out the realisation of an abstract machine is to devise for it an assembly language whose statements can be expressed as macros acceptable to the real machine's assembler. This approach was suggested by McIlroy (1960) and used in the implementation of L6 (Knowlton, 1966) and SNOBOL (Griswold, et al., 1969). Unfortunately, the assemblers for different machines may reauire auite different invut formats. and their macro processors often vary widely in power. The ease of transferring a program written in this way thus depends critically on the existence of a suitable assembly language for the target machine. Recent developments in language-independent macro processing (Strachey, 1965, Waite, 1967, Brown, 1967) suggest that it is possible to make available a common macro processor. If the assembly language statements for the abstract machine are acceptable to this macro processor, then the realisation does-not depend upon the macro capabilities of the target machine, but rather on the availability of the common macro processor. An example of this approach is the implementation of WISP (Wilkes, 1964). There the WISP compiler is the common macro processor, and is itself built up by bootstrapping from simpler macro processors. in The Computer Journal 13(1) January 1970 view details in [ACM] CACM 15(12) 1972 view details in Computers & Automation 21(6B), 30 Aug 1972 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 Computers & Automation 21(6B), 30 Aug 1972 view details in Machine Oriented Higher Level Languages (van der Poel, Maarsen, editors) North Holland 1974 view details in The Computer Journal 28(1) January 1985 view details Resources
|