ALCOR(ID:360/alc005)
ALCOR-Gruppe ALGOL
For ALgol COnverteR - one of Sammet's four true subsets of ALGOL, defined by the ALCOR Group (ALCOR-Gruppe), which was a consortium of manufactures formed to build an ALGOL machine after the ALGOL meeting in Copenhagen in 1958.
The ALCOR (ALgol COnverteR) joint project was a very early conceptual design for the interpretation of ALGOL 60. The European group devised a high level language machine architecture which was emulated on various machines. The conceptual machine had two stacks which were used for expression parsing and evaluation. One stack held pending operations, while the other stack held intermediate results. Variables and return addresses were statically allocated in program memory.
People:
Structures:
Related languages
| ALGOL 60 | => | ALCOR | Subset | |
| ALCOR | => | Illinois ALCOR | Implementation of | |
| ALCOR | => | Subset Algol 60 | Based on |
References:
Introduction
The European ALGOL situation is a complicated one, made up of the influence of workers from about 25 institutions in ten countries. A brief account of the work done in all these places must emphasize certain developments and forget about others. However, even if in this way I run the risk of doing injustice to valuable work in one place or another, either from ignorance or because of the point of view I am going to present, I feel justified in attempting the present task because, after all, there is a great underlying unity of purpose in the European ALGOL effort. Differences of opinion that do exist concern the proper means of achieving the goal. About the goal itself there is hardly any disagreement. The plan of presentation of this paper is as follows: First I will try to describe the work done in certain distinguishable groups of centers, covering both historical development and the current emphasis within each group. When I have in this way covered the complete field I will try to single out the underlying basic points of view. This will bring me to my conclusion.
Extract: The Central European Group (ALCOR)
The Central European Group (ALCOR)
The first group, both historically and with respect to the number of centers involved, is the central European one. It evolved around Zurich and Mainz and contains the roots of both ALGOL itself and of the whole idea of an algorithmic language. In fact, Rutishauser of Zurich is sometimes referred to as the "grandfather of automatic programming" in view of his work in this direction from about 1950.(1) Again the suggestion of a cross-Atlantic agreement in this field goes back to this group; of the four European members of the first ALGOL committee three came from these two places, namely Rutishauser from Ziirich and Bauer and Samelson from Mainz. The fourth was Bottenbruch from Darmstadt, a center which also belongs to the central European group.(2) It is, I think, worthwhile to notice that these four all come from universities, carrying a heavy load of mathematics and numerical analysis with them. Also, the machines they had available at the time when this work was begun were of moderate size and were used primarily for teaching and research.
The meaning of the central European group cannot be understood, however, unless one knows about the idea of a more local, and far more rigid, collaboration which developed simultaneously with the international ALGOL deliberations. This idea again originated at Mainz and goes as follows: When implementing the common language on different computers it is likely that the details of the language will not be treated exactly alike. Consequently a direct interchange of programs will not work. In order to achieve strict interchangeability it is necessary to make the different translators essentially alike, not only with respect to the language they process, but also in their inner workings. This, then, is the idea of the so-called ALCOR group of computation centers: Within the group all members will make use of the translation algorithm developed in Mainz by Bauer and Samelson(3) and will have the actual matrix, which controls this algorithm, supplied from Mainz.
In this manner complete uniformity of translation is assured.
The ALCOR group (ALCOR stands for Algol COnverteR) at present consists of the following centers:
Institut fur Angewandte Mathematik, Universitat, Mainz.
Institut fur Praktische Mathematik, Technische Hochschule, Darmstadt.
Zentral-Laboratorium, Siemens und Halske, Miinchen.
Institut fur Angewandte Mathematik, Universitat, Bonn.
Rechenzentrum der Technischen Hochschule, Munchen.
Institut fur Angewandte Mathematik, Eidgenossische Technische Hochschule, Zurich.
Institut fur Schwachstromtechnik, Technische Hochschule, Wien.
Telefunken GmbH., Backnang.
Standard Elektrik Lorenz, Stuttgart-Zuffenhausen.
Zuse KG, Bad Hersfeld.
Regnecentralen, Copenhagen.
Oak Ridge National Laboratory, Oak Ridge, Tennessee.
The ALCOR group was established in 1959 with the expectation that working translators would be completed within each of the centers within a year or so. However, the development of ALGOL 60(6) naturally caused some delay in the whole plan and the status of these centers with respect to the completion of actual compilers is as follows:
Since the end of 1958 a translator for a subset of ALGOL for the machine Zuse 222 has been running. The subset excludes procedures.
May 1961 saw the completion of an extended system conforming to the so-called ALCOR specifications. These include most of ALGOL 60, with the exception of recursive procedures and own.
2. SIEMENS UND HALSKE, MUNCHEN
In November 1960 a translator for a modest subset of ALGOL for the Siemens 2002 was completed. The subset excludes procedures, arrays of variable size, and - own. A translator for the complete ALCOR specificstions for the same machine is well underway.
3. TECHNISCHE HOCHSCHULE, MUNCHEN
Since February 1959 a translator for a small subset of ALGOL for the machine PERM has been working. By September 1961 a translator for a larger subset was completed. Work on an even more complete system is in progress.
4. ZURICH
Since July I959 a translator for a small subset of ALGOL for the machine ERMETH has been working. During 1960 this was extended to include the complete ALCOR subset. This has, as far as I know, been working for some time.
The work in Copenhagen will be described below. Oak Ridge falls outside the scope of this report. As to the remaining centers, I regret to say that up-to-date information has not been received.
This successful construction of translators within the ALCOR group has nowhere been considered an experiment or a goal in itself, but has been the basic means of communication with the computer. Thus, at Mainz the teaching of the use of the machine and of numerical analysis has for several years been based exclusively on ALGOL. Some 400 people have taken courses in ALGOL, and all programs for the machine are written in this language. In fact, only one or two people in the center know the machine code of the Zuse 222.
In this context it is also of interest that the Mainz translator for the Zuse 222 already has been distributed to eight other installations having this machine and that several dozen more are expecting it.
As the last field of activity of the central European group, the Taschenbuch project should be mentioned. This project aims at the publication of a four-volume handbook of tested algorithms from the field of numerical analysis. The algorithms will all be written in ALGOL. In compiling this collection the collaboration of outstanding workers from all over the world has been sought. Also, it is intended that only algorithms which have been run successfully on at least two different computers will be included. Thus, hopefully, the handbook will present an all-round collection of algorithms which are sound both theoretically and practically.
Summarizing, we see that the central European group has been busy in a wide field of practical implementation and use of ALGOL. Their translators have initially been modest; often quite heavy restrictions of the language have been tolerated. In this way the actual work of constructing the translators has often been kept very low. In fact, figures - the range from 1/6 to $5 man years are quoted. These figures of course do not include the general advisors of the group. At the same time the group has been very active in the international work of defining the language and is unquestionably responsible for a great deal of the basic characteristics of the language. Extract: The Dutch Group
The Dutch Group
All other European groups came into the ALGOL work when this was already well underway in central Europe. These groups include a Dutch group, a Scandinavian group, and some additional computation centers which do not fit into any grouping.
Speaking of a Dutch group is perhaps going too far, since this would consist only of two centers: the Mathematical Center in Amsterdam and the Dr. Neher Laboratory of the Dutch Postal and Telecommunications Services in Leidschendam. These two centers, although keeping in close touch with each other's developments, do not have any formal arrangements between them. Even so, there is so great a similarity in the background and approach of these centers that it is convenient to pool them.
Whereas the central European group is dominated by people with a background of applied mathematics and numerical analysis, the Dutch group takes its direction from people who have a taste for logic and formal analysis and who, in addition, have been directly concerned with the design of machines. Thus, van der Poel, at Leidschendam, is known for his analysis of the simplest possible computers and his contributions to the design of the ZEBRA, while the Mathematical Center at Amsterdam has been the cradle of both the ARMAC and the Electrologica X1.
These characteristics have left their mark both on ALGOL 60 and on the translators designed by the groups. Both groups were very active in the work leading up to ALGOL 60, and van Wijngaarden from Amsterdam sat on the final thirteen-man committee.(6) In this work the Dutch would urge generality and removal of arbitrary restrictions in the language and also contributed several original features to the language.
In the field of translator construction the group at Amsterdam has been singularly successful. In keeping with their general outlook they have strived to produce a translator which conforms absolutely with the official definition of the ALGOL 60 language, with as few restrictions as possible. This has brought about a new attitude towards the problem of processor constructions, the primary focus being the running program, while the actual translation process, the transformation of the input string, becomes a relatively minor matter.(4, 5)
A system designed along these lines was constructed at Amsterdam by two people, Dijkstra and Zonneveld, and was first tested in June 1960, i.e., about 5 months after the language was defined. This is not only the first successful system that will handle the full generality of ALGOL 60 procedures, but probably remains the only one which will handle recursive procedures. The only restriction is dynamic arrays.
At the Dr. Neher Laboratory an ALGOL system which goes to even higher degrees of conforming to the letter of the ALGOL 60-report is underway.
To most people who have worked with implementation of ALGOL 60, the idea of a system that handles the complete language is likely to provoke the question: What about the efficiency? This is indeed one of the most freq;ent objections raised against ALGOL 60. It is too general, and therefore-inefficient and difficult to implement, people will say. In view of this reaction it is interesting to analyze the attitude and practical experience of the Amsterdam group.
First, on the question of attitude, I want to cite some reflections made by Dijkstra(4). Dijkstra says that the approach taken will clearly cause some slowing down of the running program. However, as a scientific institution, the Mathematical center in Amsterdam prefers to work on a programming technique that will gain in importance in the immediate future. And there are good reasons to believe that the trend of machine design will be such that a proportionally greater number of machines will come into existence for which the cost of a very general approach is not excessive. As a second point Dijkstra considers that the increased flexibility and the removal of arbitrary restraints to be taken into account in will be found more and more valuable as time goes on. Indeed, for the utilization of the rapidly increasing machine capacity these points may well turn out to be decisive.
On the practical side it should perhaps be said first of all that the computer at the Mathematical Center in Amsterdam, the Electrologica X1, happens to be rather well suited to the general approach taken. Even so, it is significant that the ALGOL system does not remain an academic exercise. On the contrary, the use of it has been taught to a great number of people and it is being used extensively for solving a wide class of practical problems.
Extract: The Scandinavian Group
The Scandinavian Group
The Scandinavian group consists of three centers in Sweden, namely Matematikmaskinnamnden in Stockholm, FACIT in Gothenburg, and Svenska Aeroplan Aktiebolaget in Linkoping, and one center in Denmark, namely Regnecentralen in Copenhagen. The latter is my own institution.
Of these institutions one is a machine manufacturer and service center, one is a user, while the remaining two are combined service centers, machine designing and building groups, and research institutions. It may seem strange that these rather different backgrounds should provide an incentive to close collaboration, and probably the close contact between our groups is due mainly to a general positive wish to share our results with any interested group. In 1954 the group at Stockholm very generously put the design of their machine BESK at the disposal of all of us. Like the Dutch group we came into the work only after the preliminary specifications of ALGOL had been settled, but early enough to become quite heavily engaged in the work of establishing ALGOL 60.
Throughout this work our attitude has been that we would be willing to accept any feature in the language on which it would be possible to agree. In fact, we have felt that the language would in any case, be so much better than anything we could think up ourselves, and since we needed a language at the time ALGOL was first announced, we accepted it with glee. The fact that in addition ALGOL seemed to have a fair chance of becoming a widely adopted standard, of course, added to our satisfaction.
With this attitude I believe it is only natural that we should want to help further the development in whatever area we could be most useful, and our work in trying to organize and facilitate free discussion and the interchange of ideas is one fairly obvious response to this desire.
This work was started in March 1959 and was initially planned to cover only the communication within the ALCOR group. However, by June of the same year we had already agreed to act as a general clearing house for communications from any interested person in Europe. As some of you know, we have carried out this assignment through the medium of a series of duplicated notes known as the ALGOL Bulletin.
These are circulated free of charge to anyone who is interested in getting them. The material in the Bulletin consists entirely of the contributions from the readers. So far, in fact, no material submitted has been rejected. At the same time a considerable amount of work on implementation has been going on, although so far with rather less success than in central Europe or in Holland. In fact, the first Scandinavian translators in Copenhagen and Gothenburg have only just started running. The one in Copenhagen has a power about equal to that of the ALCOR specifications, i.e., it will not handle recursive procedures or own arrays(7).
The one in Gothenburg is somewhat more limited.
Extract: Independent Centers
Independent Centers
Of projects falling outside the three groups I have described so far, I would like to mention developments at Zeiss, Jena, Germany, where they are working on a translator for the Zeiss-Rechen-Automat ZRA 1, and at English Electric, Kidsgrove, England, where a translator for a new machine, the KDF 9, is being developed. At this point I would also like to make clear that since this report covers only Europe the developments in Japan and Asian Soviet Union are not touched. Extract: General Trends
General Trends
Having now described the European ALGOL situation in a geographical and historical manner I would finally like to try to find some of the underlying trends and points of view. I think it is right to say, first of all, that throughout Europe ALGOL has been taken very seriously. People have put a great deal of thought, work, and faith into the whole idea. However, underneath this common general faith we can discern at least two different attitudes. These can perhaps be expressed as follows: in the one view ALGOL is seen as the final expression of existing trends and needs within the fields of numerical analysis and machine design. Where ALGOL goes further than these it is regarded with suspicion or rejected altogether. In particular, where ALGOL forces an inconvenient use of present machines it is restricted in the actual implementations.
In the other view ALGOL is seen as an independent construction in its own right. Where it provides new mechanisnk for which no immediate use is apparent, this is understood as just a temporary state of affairs, the conviction being that these features will turn out to be important as soon as the learn to use them. Again, if ALGOL forces an inconvenient use of present machines, this is thought to be the fault of the machines. Indeed, it is felt that future machine design will be heavily influenced by ALGOL.
If you ask for my opinion on these two attitudes, I must say that I think that they are both right and useful. Unquestionably there is a big job to be done in working out the best algorithms of numerical analysis in a common language like ALGOL, and for this purpose people probably can do without the most general features of the language, at least to start with. At the same time I feel that there is an urgent need for radically new impulses in the logical design of machines. Throughout the past decade machines have been designed according to roughly the same principles--or lack of principles. The machine coding aspect has always been in the foreground in spite of the fact that the inconveniences of present-day machine code are obvious and widely recognized.
Previous languages, such as FORTRAN, have not brought about a change here, basically because these languages have themselves been designed with the computer in mind. Thus, they have only tended to perpetuate the present machine designs. This is of course fine, if one feels that it is right to spend, first, a great effort in building a machine which in a sense no one will use, and then another great effort in writing a system of 20,000 or 50,000 instructions necessaryto work with the thing. I feel that there is something utterly wrong here, and I am gratified to see that apparently the only incentive to changing this situation is corning from the ALGOL effort.
Extract: Conclusion
Conclusion
In conclusion I think it is fair to say that within a significant part of the European computation centers the ALGOL effort has had a profound effect. It has inspired wide interest in the fields of computer languages and translation. It has furthered the contact between these computation centers. It has convinced a great many people that a common language is both desirable and possible. It has inspired new thought on the machine design problem. Finally, it has led to the completion, in many places, of processors of a high degree of generality and usefulness.
in Proceedings of the 1961 Computer Applications Symposium, Armour Research Foundation, Illinois Institute of Technology, Chicago, Illinois view details
in er, 4(2) April 1962 view details
in [ACM] CACM 6(10) (Oct 1963) view details
in ACM Computing Reviews 5(03) May-June 1964 view details
The I.T.C, code was not produced by the ALCGR group. It just happened that a majority of computers for which ALGOL translators have been provided in the ALCOa group are equipped with teletype machines using the existing I.T.C. code. It was obvious that this code had to be modified only slightly in order to be usable for ALGOL. This was done already in 1959 in a meeting in Copenhagen. Since this time, the arbitrary arrangement of symbols and lack of any form of parity check was never found to be of practical importance. It was important, however, that this existing code allowed work with ALGOL and free exchange of programs. The fact that efforts in Great Britain have not yet established a generally accepted ALGOL code of systematic form, justifies the approach of the ALCOR group. Unless by international agreements a better 5-track code is provided, the use of the I.T.C. ALCOL code can still be advocated.
F. L. Bauer
Technische Hochschule
Munich, Germany
in [ACM] CACM 7(07) July 1964 view details
in ACM Computing Reviews 5(03) May-June 1964 view details
These comments refer to the 5-track paper tape representation described in [1]. We find it hard to believe that a group of computer users could produce such a code. Even harder to believe is the fact that anyone would want to start from the I.T.C. code as a suitable code for any form of computer input. The arbitrary arrangement of symbols and lack of any form of parity checking militates against common sense.
In Great Britain most computers using paper tape employ codes specifically designed for computers and radically different from the I.T.C. code. We think it is significant that no group using such a code is a member of the ALCOR group. That we have not agreed among ourselves on a standard code is unfortunate; however, any of these codes is preferable, for computer work, to the I.T.C. code.
A representation of ALGOL, based on an existing computer code but otherwise in the general spirit of the ALCOR group, has recently been proposed by Gerard and Sambles [2]. We give in Table 1 a variant of the Ferranti 5-hole code (with which we are most famihar) designed specifically for ALGOL. The printed version looks like ALGOL and achieves with 5-hole tape results that are similar to the 7- and 8-hole codes now being introduced. In the Ferranti code all the numerals and some other frequently used characters have an odd number of holes, hole 5 being used as a parity digit. The partiy checking may then be done by program or by hardware (for instance the Ferranti Pegasus allows "direct" and "checked" input).
The nonfeed characters, _ and [, can be used to synthesize other characters, such as begin, >=, =< and ~. The symbols × and $ could be conveniently represented by * and **, as in FORTRAN. String quotes could be represented by .4 and >, re- spectively, a convention already in use with some ALGOL systems. The position of the feed hole should probably be placed between holes 3 and 4 for some measure of compatibility with 7- and 8-hole tape codes. The cost of the proposed code is not much; a total of £5 ($15) above the normal cost of a teleprinter set has been quoted.
We suggest that in the future one should not waste one's time trying to adapt completely unsuitable codes for purposes far removed from their original intentions, but rather concentrate on designing a code that is generally acceptable to users and computers.
REFERENCES :
1. ALCOR group representation of ALGOL symbols. Comm. ACM 6 (Oct. 1963), 597-599.
2. GERARD, J. M. AND SAMBLES, A. A hardware representation for ALGOL 60 using creed teleprinter equipment. Comput. J. 5 (1962-63), 338-340.
P. A. SAMET
P. J. TAYLOR
Computation Laboratory
The University
Southampton, England External link: Online copy
in [ACM] CACM 7(07) July 1964 view details
in [ACM] CACM 7(07) July 1964 view details
in [ACM] CACM 7(07) July 1964 view details
in [ACM] CACM 7(07) July 1964 view details
Conclusions
The main advantage of a non-conventional architecture for the
compilation of ALGOL 60 appears to be the production of
extremely compact object code. This is achieved with the
B5500 by a very short address length within an instruction.
Because of the dynamic storage allocation of ALGOL 60,
access to simple variables is always by a small offset from an
environmental pointer. Hence an address length within an instruction
of only 9 bits is adequate. Anything in excess of
9 bits is likely to be wasted. On the other hand, several index
registers or their equivalent are necessary for environment
control and array accessing. Such registers must be capable of
being updated rapidly for procedure entry and exit, and for
access to name parameters.
Access to array elements is usually via an array word which
can be addressed in the same way as a simple variable. A short
address length may preclude some array access optimisation,
for instance if 'a' is a global array of fixed size a[200] could be
accessed by a single instruction provided the address field was
large enough. In fact the B5500 does not allow array accessing
optimisation because the storage protection system depends
upon access via the array word (descriptor). The optimisation
produced by the ALCOR compilers (Grau, 1967), could be
done on a machine with a short address length, but not the
B5500.
Array bound checking is an area where special hardware can
be used to great advantage. Unfortunately the hardware on the
B5500 does not deal with the general value of the lower bound,
so that explicit code must be generated by the compiler to
subtract the value of this lower bound if it is non-zero. Options
to do bound checking on other machines tend to be very
expensive in processor time. The 1108, although having no
built-in hardware for array accessing, has a convenient instruction
for bound checking. With this instruction, a single test
can be made to see if the operand lies within the range
defined by two registers.
Apart from the production of compact code from ALGOL 60,
it is clear that in many scientific fields non-conventional
machines can have other substantial advantages. Array bound
checking has already been mentioned, but other examples lie
outside the scope of this paper, for instance distinction between
data and program and the ability to share the available core
store between processes. The majority of these advantages are
in the field of operating system design, and so are not considered
here. Such advantages are likely to have a substantial effect
upon the performance of the compiling system itself, and the
easy way in which such systems can be developed.
in The Computer Journal 15(1) February 1972 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