Sequentielle Formelübersetzung(ID:2808/bau001)High-level algbraic compiler=Sequential Formula Translation High-level algbraic compiler from Dresden, built by Bauer and Samelson on Boehm's work, incorporating the library functionality of Gill et al, avoiding the outer->inner parsing of Bracketed Terms People: Related languages
References: in Elektron. Rechenanlagen 1 (1959 ) view details in [ACM] CACM 3(03) March 1960 view details in ACM Computing Reviews, January-December 1960 view details in Elektr. Rechen. 3(4) (1961) view details in ACM Computing Reviews 3(04) July-August 1962 view details in Belzer, J. ; A. G. Holzman, A. Kent, (eds) Encyclopedia of Computer Science and Technology, Marcel Dekker, Inc., New York. 1979 view details Introduction In the late 40s and early 50s, there were a few groups in the USA, in England, in Continental Europe and other countries that started to construct computers. To be precise they constructed the computer hardware. The computing machine in the modern sense had to replace desk calculators which were slow, had limited capabilities and lacked automatic performance of complex tasks. In 1936, Alan Turing described the functioning of a computer in a theoretical way with the aim to create a sound basis for a definition of the concept of computable numbers. Turing's computer of 1936 would have been terribly slow if it had been constructed. However, Turing did not construct it at that time. Then Konrad Zuse, John Presper Eckert and John W. Mauchly and a few others constructed computer hardware with relays or even with vacuum tubes and they had to master immense difficulties of engineering nature. Their products were often clumsy since the main problem of the hardware designers was to make their machines function in the first place. Furthermore, they had to make compromises with respect to available technologies. Zuse's first outlines around 1934 ("Vom Formular zur Programmsteuerung") showed for example a machine that used non-erasable storage and thus was much closer to functional programming than his later designs. However, he had to give up this approach and came to the solution of using erasable storage with appropriate writing and reading mechanisms. Extract: How did software arise? Heinz Zemanek has put it this way: "Software started with the translation of algebraic formulas into machine code." Thus, the Plankalkul of Konrad Zuse in 1945, the Formelubersetzung of Heinz Rutishauser and of Corrado Bohm in 1951, the Algebraic interpreter of Alick E. Glennie in 1953, the Programming Program of E. Z. Ljubimskii and Sergej Sergeevich Kamynin in 1954 and of Andrei Ershov in 1955 stood at the beginning of software, soon followed by Remington-Rand's Math-Matic (1955) and IBM's Fortran (1956). All these advances were made before the word 'software' came into wider use in 1960, 1961 or 1962. Now I will describe how we started to construct software in Munich and Zurich in the 50s, we being Klaus Samelson (1918-1980), Heinz Schecher (1922-1984) and myself in Munich and Heinz Rutishauser (1919-1970) in Zurich. Extract: Early Work in Munich and Zurich Early Work in Munich and Zurich In Munich, we were part of a group, under the supervision of the engineer Hans Piloty and the mathematician Robert Sauer, that constructed a computer. Our specific task was, to see to it that the computer under construction could perlorm the calculations it was intended for. Our group started in 1952, well-informed about the von Neumann report. Our first challenge was the ESDAC book of Wilkes-Wheeler-Gill, published in 1951. We learned from this book that we had to develop tools to make the programming job easier and more reliable. Only as a first step we decided to consider the subroutine technique advocated by Maurice V. Wilkes. We also were aware of Rutishauser's publication 'Uber automatische Rechenplanfertigung bei programmgesteuerten Rechenanlageri in ZAMM 1951, where the idea to use the computer in order to write its own program was exemplified. For this reason first personal contact to Rutishauser was established in November 1952. Apart from our daily work of fabricating subroutines for Sauer and checking the engineers' design, we started modestly to think about such simple tools as a supervisory program, while Rutishauser wrote a program for his relay computer Z4 performing the automatic generation for his relay of a linear sequence of machine instructions from a loop. In accordance with Rutishauser, we were convinced that 'automatic programming' was the direction we had to follow. Rutishauser knew that he could not use the Z4 for the realization of his 1951 ideas. Piloty's PERM in Munich was slightly ahead in time compared to Speiser's ERMETH in Zurich, so we aimed at constructing a practicable tool for 'automatic programming' as soon as our Munich machine was ready; in the meantime we followed closely the development in 'automatic programming' in the USA and in other countries, but we were not satisfied with the idea of constructing a 'compiler' that simply piled up prefabricated subroutines. Under the influence of Wilhelm Britzelmayr, our logic professor in Munich, we became more linguistically-oriented (when FORTRAN appeared in 1956, we were dissatisfied). Nevertheless, we now knew that we had to look for a better solution. We had several ideas how to achieve this aim. The PERM machine was ready for tests in 1955 (it was completely usable in 1956), so we could actually proceed. Extract: The Kellerprinzip The Kellerprinzip In 1955, when STANISLAUS was under construction, Samelson and I discussed how we would proceed with translating arithmetical formulas into machine code and suddenly we came to the conclusion that besides the 'Zahlkeller', that was used in Polish notation to postpone the intermediate results, we had to use an 'Op-I'l'alioiiskcllcr' in a similar way for postponing operations when dealing with pa-renlheses or implicit precedence. Soon, we found out that the functional principle we had discovered (we called it Kellerprinzip) "postpone operations that you can not yet evaluate and evaluate Iliem as soon as possible" was not only suitable for the evaluation or translation of parenthesized formulas, but for any constructs that show a parenthesized, interlocked structure.' Samelson in particular used the Kellerprinzip to make storage allocation efficient and when we designed step by step the programming language that we wauled lo use for 'automatic programming,' we structured the language accordingly. It became known as Chomsky-2-language. Rutishauser in particular showed how to use the Kellerprinzip in parameter transfer, bringing the spirit of the Lambda notation of formal logic into programming. Our efforts finally led in 1958 to ALGOL and made ALGOL a well-structured, very safe programming language. As usual, when freed from the restrictions hardware implies, more elegant, more flexible, more versatile solutions can be obtained. in "History of computing: software issues" Hashagen, Ulf; Keil-Slawik, Reinhard; Norberg, Arthur L. eds Proceedings of the international conference on History of computing: software issues 2002, Paderborn, Germany April 05 - 07, 2000 Springer 2002 view details Britzlmayr and Angstl The idea of what I later called the stack principle came into my mind before I became seriously acquainted with what was dubbed program-controlled calculators at that time. In the academic year 1948-1949 I was sitting in a class of Wilhelm Britzlmayr's, logician and honorary professor at the Ludwig-Maximilians-Universitat in Munich (his regular occupation was director of a bank). One day he spoke on the syntactic aspects (but this terminology was not used at that time) of the parentheses-free notation that was advocated by Jan Lukasiewicz [1]. Something stirred my interest, and thus I was not completely lost when on June 27, 1949 in Britzlmayr's seminar a man by the name of Kon-rad Zuse, while giving a survey of his Plankalkul [4], used the checking of the well-formedness of a propositional formula written in parentheses-free notation as an example for a Plankalkul program (a Rechenplan, as he called it). The discussion between Zuse and Britzlmayr brought to light that it was an algorithm Zuse had learned from his colleague Hans Lohmeyer, a mathematician working, like Zuse, at Henschel-Flugzeug-Werke in Berlin. The algorithm originated in 1943 from the Berlin logician Karl Schroter [3], based on the 1938 work by the Viennese logician Karl Menger [2]. While Zuse wanted to sell his Plankalkul, Britzlmayr was interested only in the algorithm as such, and most of the discussion took place in two different jargons, which was rather confusing. Extract: Influence by Shannon I did not like [Angstl's] solution with the wooden apparatus, and influenced by the 1949 paper by Claude Shannon [6], The Synthesis of Two-Terminal Switching Circuits, I started to look for a relay realization for the formula, which was to be typed in directly. At the same time, this allowed a direct evaluation of the propositional formula for true or false instantiations of the variables; the test for well-formedness turned out to be a byproduct of such a formula-programmed relay calculator for parentheses-free propositional formulas. Around the turn of the year 1950/51, during a stay in Davos, Switzerland, I made the wiring diagram for the relay calculator; in honor of the Polish school of logic I dubbed it STANISLAUS Extract: sequential formula translation A Software Patent for the Stack The Stack Principle In 1955, Samelson and I had quite a different motivation with respect to the STANISLAUS design. In February 1952, I had visited Heinz Rutis-hauser in Zurich and had seen the Z4 working; since the fall of 1953, I had had close contact with him, mainly in questions of numerical mathematics, which was my main duty under Sauer and also the field where I hoped to obtain my habilitation. Naturally, I did not neglect to take notice of Rutishauser's germinative publication [9] [10] of 1951, Uber automatische Rechenplanfertigung bei programmgesteuerten Rechen-maschinen, dealing for the first time with the translation of a mathematical formula language into machine programs by a Superplan in Rutishauser's terminology, a "programming program", as Andrei Ershov called it later. Samelson and I both had in mind to realize this Formel-ubersetzung for the PERM. When in mid-1955 we had time to start it and could expect a speedy finish to the construction of the PERM, it soon came to our attention that STANISLAUS solved a similar, but simplified task. Its "cellar" contained stored intermediate yes-no values; in the case of arithmetic formulas this would be a "number cellar". [...] The translation algorithm turns out to be superior to Rutishauser's method [9] inasmuch as it avoids the Rutishauser Springprozession; the effort is only proportional to the length of the formula and not, as with Rutishauser, to the square of the length. In Rutishauser's terminology it amounts to the decomposition of the parenthesis mountain from the first pair of peaks in the first chain of peaks, so it was sequential. Correspondingly, in the publication the method was characterized as "sequential formula translation". Extract: Recursion and the cellar principle Hardware Stacks We gave a report on our results to Sauer and Piloty. Piloty remarked that the German Research Council (Deutsche Forschungsgemeinschaft) had a tendency to make sure that patents were obtained for the projects it supported; he urged us to examine whether this would be possible in our case. We agreed, and he offered the prospect of providing the successor machine of the PERM with a number cellar and operation cellar in hardware. This must have been in the summer or fall of 1955. For the patent application we had to disguise our method as hardware, and for this purpose had to become engineers. The elaboration of the patent application therefore brought a lot of work and was fun, too; on the other hand it meant that publication of our results was paralyzed. Samelson therefore reported at the Dresden meeting at the end of November 1955 [13] with great caution. Both Rutishauser and Heinz Billing in Gottingen, who was building the G3 computer, were in on the secret The German patent application [14, in the following partly reprinted] was finally filed March 30, 1957 (Auslegeschrift 109472019, Kl.42m), the U.S.-American one [15] March 28, 1958 within the priority time limit. A Software Patent for the Stack While the U.S.-American application contained an abundance of and and or gates, the German patent law allowed quite functional descriptions of methods, thus the German application stayed free of drawings for electrical circuits; it was possible to design from it immediately a program with programmed cellar structures, later called stacks. Our patent can therefore be considered as an early case of a software patent The actual writing of a machine program for the PERM, which in the meantime was operating, was delegated in mid-1957 to the assistants Manfred Paul and Peter Graeff; the program was ready for tests after a few months. At first, an interpreting machine program was written; then the transition to a generating translator (a compiler) meant simply, instead of immediately executing say (as above) inserting into the program the corresponding instruction The hardware stacks, the building of which Piloty had suggested, were not realized in Munich, since the PERM II project was not supported by the German Research Council. Billing, however, equipped his G3 computer with the hardware for a number stack. thus particularly well suited for efficient translation, which was a main concern of the impoverished European side. In Zurich, Samelson had particularly stressed the point that the block structure of storage allocation (Cellar Principle of State Transition and Storage Allocation, [30]), following so naturally from the cellar principle and becoming so typical in the later development, became the dominant organization principle of the programming language. Storage allocation with complete parentheses structure should be organized in a dynamic stack, which without further complications allowed mastery of recursive definitions. The compromise that was achieved in a struggle with the U.S.-American side did not reflect this issue in the published report; thus, later the implementation of recursive situations was reinvented by some people not present at the Zurich meeting. Extract: arrival of Algol The Preliminary ALGOL Report The goals attempted by the ZMD group, to create a language widely following mathematical notation, readable without much ado, and suitable for publications and for mechanical translation, had been largely reached. The publication was completed in 1959 in the first issue of the new journal Numerische Mathematik of Springer-Verlag under the title Report on the Algorithmic Language ALGOL Extract: Mainz 22 and algol 58 When in 1958 I moved from Munich to Mainz, with Samelson soon following me, the ZMD group was widened to the ZMMD group. Emphasis was on finishing compilers for ALGOL 58. The common basis was the method of a stack automaton developed in Munich, which was extended without any difficulty to a full algorithmic language including statements, declarations, block structure, indexed variables, and so on. It was published in 1959 in the newly founded journal Elektronische Rechenanlagen [..] and in 1960 in Communications of the ACM [...]. Manfred Paul, who had done most of the preparatory work, finished a compiler for the Mainz Z22 towards the end of 1958. Soon afterwards, H.R.Schwarz and P.Lauchli followed in Zurich for the ERMETH and G.SeegmuIler in Munich for the PERM. Extract: ICIP, BNF, stack notation ICIP Conference A lot of work was caused by the preparations for ALGOL 60. At the International Conference on Information Processing (ICIP), arranged in Paris, |une 15-20, 1959 by UNESCO, John Backus [24] made a famous proposal for the formal description of the syntax. The Backus notation (Backus Normal Form), soon generally accepted, allowed one to attach in an elegant way the semantics of the programming language to the syntax of a context-free language. Manfred Paul, in his 1962 dissertation, clarified how from this description the transition matrix for the stack automaton could be derived formally. Extract: British hostility and absence, ZMD excellence The Zurich Meeting In the summer of 1957, Bottenbruch became initiated in the Munich Sequential Formula Translator method [16], and at the Zurich meeting the ZMD group not only presented a draft [17] for the language, which at first was called International Algebraic Language, but also had a completed compiler design in the bag. Some U.S.-American delegates had experience with working compilers (Backus with FORTRAN, Perlis with IT, Katz with MATH-MATIC). An open discussion of the technical problems of programming language translation into machine code was left out, as there would not have been enough time. Technically speaking, the state of the art within the ZMD group was far more advanced: FORTRAN used the method of parentheses completion, introduced by P.B.Sheridan [18] and discussed as early as 1952 by Corrado Boehm [11] in his Zurich dissertation, a method that like Rutishauser's required an effort proportional to n2; IT [12] used pure comparison of neighboring operators, enforcing an oppressive limitation to operator precedence grammars. This situation led from time to time to a paralysis of the discussion, which was basically oriented towards progress. On the whole, ALGOL, as it was called in the publication [19b], was an incarnation of the cellar principle […] Christopher Strachey, who—inadvertently—had not been invited to the Zurich meeting, went into the trouble of criticizing ALGOL 58 and produced not only considerable stir, but also a lot of public attention. Thus, it was not too difficult to convince the International Federation for Information Processing, founded in Paris, to organize a conference for the "final ALGOL", later called ALGOL 60. The preparations were this time much more intensive; a European pre-conference was held in November 1959 in Paris; it nominated seven European delegates, who met again in December 1959 in Mainz. The U.S.-American side nominated its delegates in November 1959. This time, representatives from Great Britain, France, the Netherlands, and Denmark, besides representatives from the U.S.A., Germany, and Switzerland, were invited. Extract: Paris Conference Paris, 1960 The ALGOL conference took place in Paris, January 11-16, 1960 under the patronage of the newly founded IFIP. It led to consolidations and completions of the Preliminary Report. Characteristically, the introduction to the report [25a, b] says "The present report represents the union of the committee's concepts and the intersection of its agreements". In this way, contradictions could remain here and there and solutions were omitted. What made me particularly angry was that Samelson, who in 1958 regarding the question of the block structure could not win against Alan Perlis, in 1960, when acceptance of recursion was no longer an issue, was given no credit for the block structure; the editor Peter Naur, who was not present in Zurich, was not aware of this. In the short period of six days we also did not succeed in formalizing, next to the syntax which now was formalized in BNF (Backus Normal Form), the semantics as well; it was still explained rather verbally, leading later to exegetic quarrels. Heinz Zemanek tried, with the IFIP Technical Committee 2 Working Conference Formal Language Description Language, held in 1964 in Baden near Vienna, to compensate for this lack. Peter Landin [29] gave a complete formal description of ALGOL 60, but it lacked the blessing of the authorities. Extract: The ALCOR Group The ALCOR Group After the ICIP Congress, June 1959 in Paris and particularly after the publication of the ALGOL 60 report, the ZMMD group decided to widen its membership and invited interested institutions in Europe and North America to participate in the efforts for propagation of ALGOL through the construction of ALGOL compilers for various different machine configurations; the documents of the previous ZMMD group were made available for this purpose. The offer was accepted by scientific institutions (among the first were Regnecentralen Copenhagen, Bonn University, Zemanek's Mailiifterl group in Vienna, Oak Ridge National Laboratory, Neber Laboratory Leidschendam) as well as by some computer companies (Siemens and Halske AG for the 2002, Telefunken for the TR4, Standard Elektrik Lorenz AG, IBM Germany). The resulting multitude of concrete implementations was unavoidable because of the differences in the machines involved, but it was useful in its scientific aspects. For example, Albert A. Grau, Oak Ridge, introduced the concept of syntactic states and described the compiler as a system of mutually recursive subprograms [31]. Peter Lucas in Vienna went his own way [32] in generating, like Paul in Mainz [33,34], the compiler from the syntax in BNF. Jurgen Eickel and Manfred Paul, in 1964, studied the parsing and ambiguity problem for Chomsky languages in general [39]. Extract: Algol 58 and the death of Algol After my return to Munich in 1963, the build-up of computer science there became my main obligation, leaving less time to be spent on the further development of ALGOL. The way it went became more and more of a nightmare, leading to ALGOL 68 and to the ruin of the ALGOL idea. One after another, people left the IFIP Working Group 2.1 on ALGOL: Peter Naur, Niklaus Wirth, Tony Hoare, Edsger Dijkstra, Brian Randall, Gerhard Seegmiiller, Wlad Turski, Mike Woodger, Hans Bekic, and Fraser Duncan. in Software Pioneers: Contributions to Software Engineering, Bonn, 28-29. 6. 2001 eds Broy, Manfred and Denert, Ernst Springer 2002 view details |