Formules(ID:2706/for035)Compiler for Zuse Z4=Formulas Heinz Rutishauser, Konrad Zuse automatic coding compiler for Zuse Z4. Used a "superplan" to construct "plans" (plans were the Zuse/Rutishauser word for programs) Bemer 1957 said that it had features not available in US autocodes Places People: Related languages
References: The language of communication will be our own-mathematical notation as far as possible and then English when we run out of concise symbolism. Present logical language is weak, and I imagine that even the commercial people had better brush up on their Boolean algebra. The area of loop control and recursive operations is still not well handled in existing mathematical notation, but computers are forcing the development. As an example, note the "Replace" operator (<==) of K. Zuse. Although the ultimate in language does not exist yet, we can console ourselves meanwhile with compatible (as against common) language. There is much current evidence that existing algebraic languages are all mappable into one another by pre-processors, although these may be of varying and perhaps prohibitive complexity. The Germans, in particular, are concerned that such mappability be guaranteed before they make heavy coding investments for the many machines they will be operating. Extract: Summary Let me elaborate these points with examples. UNICODE is expected to require about fifteen man-years. Most modern assembly systems must take from six to ten man-years. SCAT expects to absorb twelve people for most of a year. The initial writing of the 704 FORTRAN required about twenty-five man-years. Split among many different machines, IBM's Applied Programming Department has over a hundred and twenty programmers. Sperry Rand probably has more than this, and for utility and automatic coding systems only! Add to these the number of customer programmers also engaged in writing similar systems, and you will see that the total is overwhelming. Perhaps five to six man-years are being expended to write the Alodel 2 FORTRAN for the 704, trimming bugs and getting better documentation for incorporation into the even larger supervisory systems of various installations. If available, more could undoubtedly be expended to bring the original system up to the limit of what we can now conceive. Maintenance is a very sizable portion of the entire effort going into a system. Certainly, all of us have a few skeletons in the closet when it comes to adapting old systems to new machines. Hardly anything more than the flow charts is reusable in writing 709 FORTRAN; changes in the characteristics of instructions, and tricky coding, have done for the rest. This is true of every effort I am familiar with, not just IBM's. What am I leading up to? Simply that the day of diverse development of automatic coding systems is either out or, if not, should be. The list of systems collected here illustrates a vast amount of duplication and incomplete conception. A computer manufacturer should produce both the product and the means to use the product, but this should be done with the full co-operation of responsible users. There is a gratifying trend toward such unification in such organizations as SHARE, USE, GUIDE, DUO, etc. The PACT group was a shining example in its day. Many other coding systems, such as FLAIR, PRINT, FORTRAN, and USE, have been done as the result of partial co-operation. FORTRAN for the 705 seems to me to be an ideally balanced project, the burden being carried equally by IBM and its customers. Finally, let me make a recommendation to all computer installations. There seems to be a reasonably sharp distinction between people who program and use computers as a tool and those who are programmers and live to make things easy for the other people. If you have the latter at your installation, do not waste them on production and do not waste them on a private effort in automatic coding in a day when that type of project is so complex. Offer them in a cooperative venture with your manufacturer (they still remain your employees) and give him the benefit of the practical experience in your problems. You will get your investment back many times over in ease of programming and the guarantee that your problems have been considered. Extract: IT, FORTRANSIT, SAP, SOAP, SOHIO The IT language is also showing up in future plans for many different computers. Case Institute, having just completed an intermediate symbolic assembly to accept IT output, is starting to write an IT processor for UNIVAC. This is expected to be working by late summer of 1958. One of the original programmers at Carnegie Tech spent the last summer at Ramo-Wooldridge to write IT for the 1103A. This project is complete except for input-output and may be expected to be operational by December, 1957. IT is also being done for the IBM 705-1, 2 by Standard Oil of Ohio, with no expected completion date known yet. It is interesting to note that Sohio is also participating in the 705 FORTRAN effort and will undoubtedly serve as the basic source of FORTRAN-to- IT-to-FORTRAN translational information. A graduate student at the University of Michigan is producing SAP output for IT (rather than SOAP) so that IT will run on the 704; this, however, is only for experience; it would be much more profitable to write a pre-processor from IT to FORTRAN (the reverse of FOR TRANSIT) and utilize the power of FORTRAN for free. in "Proceedings of the Fourth Annual Computer Applications Symposium" , Armour Research Foundation, Illinois Institute of Technology, Chicago, Illinois 1957 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 |