ALGOL 58(ID:17/alg018)Algorithmic LanguageThe release name for the International Algebraic Language The language is suitable for expressing a large class of numerical processor in a form sufficiently concise for direct automatic translation into the language of programmed automatic computers. The algorithmic language has three different kinds of representations - reference, hardware, and publication, and the development described is in terms of the language are represented by a given set of symbols and it is only in the choice of symbols that the other two representations may differ. Structure and content must be the same for all representations. People: Related languages
References: in Goodman, Richard (ed) "Annual Review in Automatic Programming "(1) 1960 Pergamon Press, Oxford view details in [ACM] CACM 1(12) (Dec 1958) view details in Proc. Int. Conf. Information Processing, Oldenbourg, München, 1960 view details in Proc. Int. Conf. Information Processing, Oldenbourg, München, 1960 view details in Proc. Int. Conf. Information Processing, Oldenbourg, München, 1960 view details in ER 1(2) May 1959 view details in ER 1(2) May 1959 view details Most of the papers are written in a style and manner which seem to have become universally accepted for papers on computer programming, at least in the English-speaking world and probably in others. This style insists on a liberal dosage of impressively detailed flow charts which, considering the well-known and understandable reluctance of programmers to read their own programs much less those of others, one suspects most readers hastily skip over, willingly granting their authenticity. The flow charts are invariably accompanied by long lists of special instructions described in the private patois of the author, who seems blissfully unaware or unconcerned that his specially constructed vocabulary of acronyms may present;. rough going to the reader from the inlying provinces. Finally, the style demands long and wearisome descriptions of basic concepts (e.g., subroutine; symbolic instruction, etc.) long since familiar to the average reader, some indication of difficulties as yet to be surmounted (e.g., automatic storage allocation; easier debugging; et al). Nevertheless, the volume does give some idea of the status of automatic programming systems in Great Britain in early 1959. It also contains a concise description of the 709 SHARE operating system, and another brief account of FLOW-MATIC and MATH-MATIC. There are two interesting appendices worthy of mention. Appendix One consists of reprints of two papers by the late A. M. Turing, "On Computable Numbers with an Application to the Entscheidungsproblem", in which the "Turing machine" was conceived, and a brief corrective note on the same subject. Appendix Two contains the "Preliminary Report of ~ ACM-GAMM Committee on an International Algebraic Language", since published elsewhere. The reviewer cannot suppress the question of whether this sort of material (Appendices excepted), so soon obsolescent or obsolete and so difficult to present adequately in short papers, deserves the effort and expense required to reproduce it between the bound hard covers of a handsome book. in ACM Computing Reviews 2(03) May-June 1961 view details Until quite recently, large scale computers have been mainly an American phenomenon. Smaller computers were almost worldwide right from the beginning. An active computer organization GAMM had been set up in Europe, and in 1957 a number of members of this organization were actively interested in the design of Algebraic compilers for a number of machines. They decided to try to reach agreement on a common language for various machines, and made considerable progress toward the design of such a language. There are many obvious advantages to having generally accepted computer independent problem oriented languages. It was clear that a really international effort in this direction could only be achieved with United States participation. The President of GAMM wrote a letter to John Carr who was then President of the ACM, suggesting that representatives of ACM and of GAMM meet together for the purpose of specifying an international language for the description of computing procedures. The ACM up to that time had served as a forum for the presentation of ideas in all aspects of the computer field. It had never engaged in actual design of languages or systems. In response to the letter from GAMM, Dr. Carr appointed Dr. Perlis as chairman of a committee on programming languages. The committee set out to specify an Algebraic compiler language that would represent the American proposal at a meeting with representatives of GAMM at which an attempt would be made to reach agreement on an internationally accepted language. The ACM committee consisted of representatives of the major computer manufacturers, and representatives of several Universities and research agencies that had done work in the compiler field. Probably the most active member of the committee was John Backus of IBM. He was probably the only member of the committee whose position permitted him to spend full time on the language design project, and a good part of the "American Proposal" was based on his work. The ACM committee had a number of meetings without any very great sense of urgency. Subcommittees worked on various parts of the language and reported back to the full committee, and in general there was little argument or disagreement. There is after all very general agreement about the really basic elements of an Algebraic language. Much of the language is determined by the desirability of remaining as close as possible to Mathematical notation. This is tempered by experience in the use of computers and in the design of compilers which indicates some compromises between the demands of desirable notation and those of practical implementation. At one meeting of the committee Dr. Bauer, one of the leaders of the GAMM effort, presented a report on the proposed European language. Among other things they proposed that English language key words, like begin, end, for, do, be used as a world-wide standard. Of course this is something the American committee would never have proposed, but it seemed quite reasonable to go along with the Europeans in this matter. Although some of the notations seemed strange, there were very few basic disagreements between what GAMM was proposing, and what the ACM committee was developing. Dr. Bauer remarked that the GAMM organization felt somewhat like the Russians who were meeting with constant rebuffs in an effort to set up a summit meeting. With such wide areas of agreement why couldn't the ACM-GAMM meeting take place? Although there is quite general agreement about the basic elements of an Algebraic language, there is quite considerable disagreement about how far such a language should go, and about how some of the more advanced and more difficult concepts should be specified in the language. Manipulation of strings of symbols, direct handling of vectors, matrices, and multiple precision quantities, ways to specify segmentation of problems, and the allocation and sharing of storage; these were some of the topics which could lead to long and lively discussion. The ACM language committee decided that it was unreasonable to expect to reach an agreement on an international language embodying features of this kind at that time. It was decided to set up two subcommittees. One would deal with the specification of a language which included those features on which it was reasonable to expect a wide range of agreement. The other was to work toward the future, toward the specification of a language that would really represent the most advanced thinking in the computer field. The short-range committee was to set up a meeting in Europe with representatives of GAMM. Volunteers for work on this committee would have to arrange for the trip to Europe and back, and were therefore limited to those who worked for an organization that would be willing to sponsor such a trip. The ACM was asked to underwrite the trip for Dr. Perlis. The meeting of the ACM and GAMM subcommittees was held in Zurich in the spring of 1958, and the result was a Preliminary report on an International Algebraic Language, which has since become popularly known as Algol 58. in [AFIPS JCC 25] Proceedings of the 1964 Spring Joint Computer Conference SJCC 1964 view details in [AFIPS JCC 25] Proceedings of the 1964 Spring Joint Computer Conference SJCC 1964 view details There was a tremendous number of ideas floating around at the time. Around that rime, Al Perlis had come through RAND and talked about how to really do all this. He stimulated a lot of people to at least think about it if not do something about it. I got deeper and deeper into the whole mystique of language design and compiler construction, and began to follow the first international effort?IAL?rather closely. RAND, SDC and some other organizations decided that the International Algebraic Language, which was eventually called ALGOL 58, was something of interest. Even though it had some flaws and ambiguities in it, at least it looked like a reasonable improvement over FORTRAN. From it came JOVIAL at SDC. [...] ALGOL 58 came along and excited a lot of people, but neither ALGOL 58 nor ALGOL 60 was really accepted in this country, because by that time FORTRAN was really rolling down the road. SHARE had promoted, or helped promote FORTRAN II rather heavily and then along came FORTRAN III which in retrospect was a rather idiotic attempt. [...] So FORTRAN III was born and it allowed you to do much of what JOVIAL did, dropping into assembly language by adding a statement that allowed you to pop in and out of assembly from FORTRAN, which everybody knew was a disaster. [...] I have the strong recollection that FORTRAN III actually saw the light of day, but it died. [13] It just didn't have it?there were people who were much closer to FORTRAN because I had begun to move away from FORTRAN per se and pursue other language oriented things. I was looking at the SDC's JOVIAL. I was trying to build some small compilers for open shop languages at RAND at the time and then I got involved in the SHARE ALGOL effort in '58-'59. [...] Well, there was a letter written by, I believe it was Rudishauser, to possibly Al Perlis through the ACM[15], and said the world was going off in a thousand different directions with this language stuff. Maybe we ought to get together, the Europeans and the Americans, and design one internationally based language that we would all agree upon, and maybe we will solve some of the world's nastier problems, particularly in program communications, if we have a common source language. We may end up getting real power in the world of commonality, usability, and things like that. [...] I have to back up. I just remembered something. There was another effort going on in SHARE called UNCOL: Universal Computer Oriented Language, which I got my fingers into. As a result of that, the ACM appointed a group, and I don't know whether Perlis was the chairman of the group, but I believe he was. I know John Backus was a member of the group. And I am trying to remember who the others were. Joe Wegstein may well have been a member. I know he was on ALGOL 60. I don't know whether he was on '58. Anyway, the group met in Zurich and sat down and designed a language. What they came back with was ALGOL '58. And they had done it very, very swiftly. Everyone came with their own ideas; there was an awful lot of argument and compromise. But it wasn't a terribly bad language. It had some ambiguities and some holes, e.g., they completely left the I/O out, so that was up to the implementer to decide how he had to do it on his local computer. It may not have been a full quantum improvement over FORTRAN, but it was an improvement. It incorporated an awful lot of things which you couldn't express or only expressed with great difficulty in FORTRAN. In IAL or ALGOL it was reasonably straight forward. [...] There were a lot of us, including me, who sat around and looked at ALGOL and realized that it had a lot of faults. There are notational things that could be cleaned up. There are things that they forgot to put in which could be easily added. There are ambiguities that really had to be straightened out. It didn't have any I/O. And it is not all that easy to get common implementation because there are these vagaries of interpretation about what certain things meant. And I can't remember whether ALGOL 58 was a block structured language or not, but there were some misunderstandings about the scope of variables and all the other things that you run into when you start putting together rather complex language structures. After some early and some aborted attempts to implement ALGOL 58, which is when I got really involved with ALGOL through SHARE. We decided that ALGOL was a good thing and that SHARE was going to implement ALGOL 58, or at least convince IBM to help us. We would help specify how it was to be done, and IBM would do the implementation. Bob Bemer, Julian Green and several other people at IBM were building something called XTRAN, which was a tool that would help them implement almost any language, but in particular ALGOL. Things go to the point where it was clearly understood that ALGOL had to be cleaned up. And so the [original] group [that produced IAL] was to reconvene in late '59 or early '60. Their report came out in early '60, which is why it was called ALGOL 60, although they actually met in '59. Perlis was the chairman of the group that went to Paris to clean up IAL. That is when the name ALGOL was invented. [16] The earlier effort was designated ALGOL 58 because the new one was designated '60. I know Joe Wegstein was there. I know Julian Green was there. I know John Backus was there because that is when Backus Normal Form (before it became Backus Naur Form) was invented. I don't know whether it is apocryphal or what but the story goes that John finally figured out [how to represent the syntax of a programming language in a formal notation] on the plane over to Paris. I don't quite believe that, knowing John. He works very long and hard and maybe he had an of inspiration [on the plane] but the [representation problem] had been brewing as a result of '58. And the difficulties they had trying to get a syntax description pushed him into working that problem very hard. There were thirteen people [at the Paris meeting] in all. Seven from Europe and six from the United States, but I can't remember any of the rest of the six. The seventh U.S. representative was killed in an automobile accident just before he was supposed to go. I can't remember who that was [William Turanski]. [...] They [the U.S. committee] came back and Julian Green showed up at the SHARE meeting in March following the ALGOL 60 meeting, and he quietly presented me [as Chairman of the SHARE ALGOL Committee] with a draft copy of the report written in Backus NORMAL FORM. I looked at the thing and had a hemorrhage, because we had all been working very hard on the supposition that they were going to go away and fix ALGOL 58 and make it useful and wonderful and clean and beautiful and unambiguous. What they had done was gone away and thrown ALGOL 58 out the window and started clean again. They came up with a whole new completely incompatible language. People who had implemented ALGOL 58 in any shape or form really had thrown their money away because that was no longer going to be the international language, ALGOL 60 was. The compatibility was just not there. I got very, very upset. I wrote Dr. Perlis, who was then at Carnegie Tech, a rather harsh and nasty letter about dereliction of duty and a few odd things like that. I'm sure there is a copy of it somewhere in RAND. I couldn't get it [mailed] out of the building first time I tried. There was a lady who controlled all outgoing mail from the RAND Corporation. Her primary job was to see that no classified information was sent out without proper protection and was going to the recipient who knew how to handle it. She was also the guardian of the corporate morals, ethics and language and my letter was rather harsh. I had gone to Paul Armer and said, "I am going to send this very nasty letter. Be warned. Apparently, he saw it and said, "If that is what you want to say, okay, that is what you want to say." The next morning when I came in the letter hadn't gone out. We had a minor battle inside RAND convincing them I had every right to say what I was saying, both as a member of the RAND Corporation staff and representing my chairmanship of the SHARE ALGOL Committee. Finally, it got out the door. And I will never forget Perlis' answer scribbled on the bottom of my original letter that said in essence, "Go away, you bother me or you don't bother me." But I think that was the death knell for ALGOL 60 and for the concept of ALGOL in this country. MAPSTONE: Maybe the death knell of any kind of universal language. BERNSTEIN: The basic problem was you can't get thirteen guys together and in six days invent the world. And it wasn't the right flavor of people. The mix was all wrong. I have yet to be able to plow through the wondrous and glorious [latest] ALGOL report. But it is probably a major improvement. It is far more consistent, has far fewer ambiguities, and many well be one of the most powerful and delightful programming languages in the world. If you could only understand the description. It is a terribly, terribly complex thing and you must spend many hours studying it in order to get any appreciation out of it. But it was done by a fairly small group over a long period of time who really honed and worked the problem. Julian Green, Joe Wegstein and I had a rather uproarious session which I didn't find very uproarious. I got rather upset when I heard the stories of how ALGOL 60 was created. It was like putting a piece of legislation through Congress rather than a bunch of scientists getting together and saying, "What's best? What's cleanest? What's purest? What really is scientifically or technologically the best possible thing, the apotheosis of our skill and our knowledge." Instead, what they did was barter as in, "If you will let me put this in, I will let you put that in. No, no. I am not going to vote for your thing if you are going to argue with me about that thing." Joe Wegstein was sitting there telling me that when things got out of order he would slam his hand down on the table and bring everybody to silence by shaking them up. It doesn't sound to me the way you design a language. You go away and the think about it for a while. Think through the problems: What is the objective of the whole thing? Who are we trying to get to use it? How would you like them to be able to use it? Are there any implementation aspects that you might take into account? Can this thing be implemented at all on the existing computer? Must it wait for the next generation? Things like that. That wasn't the kind of considerations that they made. Now they may have had all those considerations in the back of their mind. And maybe I am being over-critical, but I believe they blew it. They just destroyed whatever first, good step they had taken by not going after ALGOL 58, as impotent as it may have been in their two year further down the pike view of the world. Who cared if it didn't have "own" variables. Nobody really understood what they were all about anyway. They probably represent one tenth of one percent of the utility of a true language. The decision that all procedures had to be recursive was an interesting concept, but not something you lay on the world before they are thoroughly and completely educated in the value and use and the need, and where you may or may not want to get into things like that. And they just came out with all this beautiful, gorgeous?not terribly pragmatic?inconsistent language. And then they did other wondrous and glorious things. They said, we will have the publication language and we leave to the implementer the hardware representation. And that is where we had great fun in SHARE. I must have spent sixty or seventy hours sitting in on arguments, chairing a committee, trying to satisfy all the diverse points of view about a SHARE hardware representation for ALGOL 60. Up to this time SHARE had a resolution which blessed the whole thing. And it was subsequent to that that I became completely disenchanted with the whole thing. The deeper I got into it, the angrier I got, and finally introduced a resolution that SHARE withdraw its original resolution and castigate the idiots who had done that, rather soundly. It didn't get that strongly worded, but we withdrew our original commendation at ACM and the [other] parties involved were going off on various crusade to create an ALGOL international language. MAPSTONE: What was the SHARE resolution? BERNSTEIN: I think it ended up just withdrawing SHARE's original resolution. It said: We no longer bless it, we don't care. SHARE no longer has any interest in ALGOL?particularly ALGOL 60. MAPSTONE: But the language did go on, and is still extant today? BERNSTEIN: ALGOL 60: yes, people still talk about it. It may be used in a few universities. MAPSTONE: Is there not a language called ALGOL which is in use today? BERNSTEIN: Yes. In fact, there is still some ALGOL 60 compilers around. How much of ALGOL 60 they really cover is not clear to me. SHARE actually did eventually, after I gave up, produce [a compiler]. This was a SHARE effort. We decided that we didn't have much of a chance to convince IBM [to implement ALGOL]. IBM was completely antithetical to ALGOL by this time. They had gotten turned off and put most of their interest in FORTRAN. We had essentially been told was that IBM was not going to implement an ALGOL processor as an IBM supported language. They said, "If you guys want to do something, build your own compiler with blessings. We'll even help you." Julian Green and Rex Franciotti were two guys that I interfaced with from IBM, who were trying to build certain pieces of the ALGOL compiler for us. I had given up on trying to keep a cooperative effort going. I had worked rather hard building one piece with a guy at Lockheed in Sunnyvale. We would get together occasionally and check out code to get this and that going. And then somebody would turn up and hadn't done their job, so by that time I got sick and tired of the whole thing and said, "To hell with you guys." I thought that the whole business of trying to get a cooperative ALGOL compiler produced was an abortion. But some people stuck by it, particularly people at Oak Ridge and I can't remember where the other guy was from. I guess he was at Rocketdyne and had a certain personal dedication to the whole thing. Marjorie Lisky and he eventually put together an operable ALGOL compiler which she offered to distribute through SHARE. I don't know how many people took her up on that and I don't know if it ever really worked. It took umpteen thousand passes and probably worked reasonably well. It created at least one social upset. As a result of Julian Green and Marjorie Lisky working so closely together on ALGOL, both divorced their spouses and married each other. MAPSTONE: Well, that means they worked well together. in [AFIPS JCC 25] Proceedings of the 1964 Spring Joint Computer Conference SJCC 1964 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 MAD was developed at the University of Michigan in 195960 for the IBM 704. It was very widely used on the IBM 7090 and 7094, the Philco 2000, and UNIVAC 1100 computers during the 1960s for the purpose of teaching programming to college students. Michigan published a reference manual, but most students learned MAD from the MAD PRIMER, written by Elliott Organick of the University of Houston and distributed by Ulrichs Book Store of Ann Arbor, Michigan. Organick also wrote a more widely used FORTRAN PRIMER. The MAD compiler for the UNIVAC 1100 computers called RALPH was developed at the University of Maryland. The name RALPH is an acronym of sorts: Reentrant Algorithmic Language Processor with H just for the H of it. (The explanation of the acronym is supplied by George Baltz, formerly at the University of Maryland.) The RALPH processor could compile either FORTRAN or MAD, depending on the option selected. MAD is perhaps most famous for the line printer picture of Alfred E. Neumann which was printed when an attempted compilation had too many errors. Underneath the picture it printed the caption: See this man about your program--He might want to publish it. He never worries--but from the looks of your program, you should. MAD faded from the scene in the 1970s. A very simple MAD program follows: INTEGER A START A = 1 WHENEVER A .G. 0 PRINT COMMENT $ A GTR 0$ OTHERWISE PRINT COMMENT $A LEQ 0$ END OF CONDITIONAL PRINT COMMENT $ END $ END OF PROGRAM The WHENEVER OTHERWISE END OF CONDITIONAL is equivalent to an if-else statement External link: Online copy at UNISIS History in Software Pioneers: Contributions to Software Engineering, Bonn, 28-29. 6. 2001 eds Broy, Manfred and Denert, Ernst Springer 2002 view details |