The Humble Programmer
by
Edsger W. Dijkstra
As a result of a long sequence of coincidences I entered the programming profession officially on the first spring morning of 1952 and as far as I have been able to trace, I was the first Dutchman to do so in my country. In retrospect the most amazing thing was the slowness with which, at least in my part of the world, the programming profession emerged, a slowness which is now hard to believe. But I am grateful for two vivid recollections from that period that establish that slowness beyond any doubt.
After having programmed for some three years, I had a discussion with A. van Wijngaarden, who was then my boss at the Mathematical Centre in Amsterdam, a discussion for which I shall remain grateful to him as long as I live. The point was that I was supposed to study theoretical physics at the University of Leiden simultaneously, and as I found the two activities harder and harder to combine, I had to make up my mind, either to stop programming and become a real, respectable theoretical physicist, or to carry my study of physics to a formal completion only, with a minimum of effort, and to become….., yes what? A programmer? But was that a respectable profession? For after all, what was programming? Where was the sound body of knowledge that could support it as an intellectually respectable discipline? I remember quite vividly how I envied my hardware colleagues, who, when asked about their professional competence, could at least point out that they knew everything about vacuum tubes, amplifiers and the rest, whereas I felt that, when faced with that question, I would stand empty-handed. Full of misgivings I knocked on van Wijngaarden’s office door, asking him whether I could “speak to him for a moment”; when I left his office a number of hours later, I was another person. For after having listened to my problems patiently, he agreed that up till that moment there was not much of a programming discipline, but then he went on to explain quietly that automatic computers were here to stay, that we were just at the beginning and could not I be one of the persons called to make programming a respectable discipline in the years to come? This was a turning point in my life and I completed my study of physics formally as quickly as I could. One moral of the above story is, of course, that we must be very careful when we give advice to younger people; sometimes they follow it!
Another two years later, in 1957, I married and Dutch marriage rites require you to state your profession and I stated that I was a programmer. But the municipal authorities of the town of Amsterdam did not accept it on the grounds that there was no such profession. And, believe it or not, but under the heading “profession” my marriage act shows the ridiculous entry “theoretical physicist”!
So much for the slowness with which I saw the programming profession emerge in my own country. Since then I have seen more of the world, and it is my general impression that in other countries, apart from a possible shift of dates, the growth pattern has been very much the same.
Let me try to capture the situation in those old days in a little bit more detail, in the hope of getting a better understanding of the situation today. While we pursue our analysis, we shall see how many common misunderstandings about the true nature of the programming task can be traced back to that now distant past.
The first automatic electronic computers were all unique, single-copy machines and they were all to be found in an environment with the exciting flavour of an experimental laboratory. Once the vision of the automatic computer was there, its realisation was a tremendous challenge to the electronic technology then available, and one thing is certain: we cannot deny the courage of the groups that decided to try and build such a fantastic piece of equipment. For fantastic pieces of equipment they were: in retrospect one can only wonder that those first machines worked at all, at least sometimes. The overwhelming problem was to get and keep the machine in working order. The preoccupation with the physical aspects of automatic computing is still reflected in the names of the older scientific societies in the field, such as the Association for Computing Machinery or the British Computer Society, names in which explicit reference is made to the physical equipment.
What about the poor programmer? Well, to tell the honest truth: he was hardly noticed. For one thing, the first machines were so bulky that you could hardly move them and besides that, they required such extensive maintenance that it was quite natural that the place where people tried to use the machine was the same laboratory where the machine had been developed. Secondly, his somewhat invisible work was without any glamour: you could show the machine to visitors and that was several orders of magnitude more spectacular than some sheets of coding. But most important of all, the programmer himself had a very modest view of his own work: his work derived all its significance from the existence of that wonderful machine. Because that was a unique machine, he knew only too well that his programs had only local significance and also, because it was patently obvious that this machine would have a limited lifetime, he knew that very little of his work would have a lasting value. Finally, there is yet another circumstance that had a profound influence on the programmer’s attitude to his work: on the one hand, besides being unreliable, his machine was usually too slow and its memory was usually too small, i.e. he was faced with a pinching shoe, while on the other hand its usually somewhat queer order code would cater for the most unexpected constructions. And in those days many a clever programmer derived an immense intellectual satisfaction from the cunning tricks by means of which he contrived to squeeze the impossible into the constraints of his equipment.
Two opinions about programming date from those days. I mention them now, I shall return to them later. The one opinion was that a really competent programmer should be puzzle-minded and very fond of clever tricks; the other opinon was that programming was nothing more than optimizing the efficiency of the computational process, in one direction or the other.
The latter opinion was the result of the frequent circumstance that, indeed, the available equipment was a painfully pinching shoe, and in those days one often encountered the naive expectation that, once more powerful machines were available, programming would no longer be a problem, for then the struggle to push the machine to its limits would no longer be necessary and that was all what programming was about, wasn’t it? But in the next decades something completely different happened: more powerful machines became available, not just an order of magnitude more powerful, even several orders of magnitude more powerful. But instead of finding ourselves in the state of eternal bliss of all progamming problems solved, we found ourselves up to our necks in the software crisis! How come?
There is a minor cause: in one or two respects modern machinery is basically more difficult to handle than the old machinery. Firstly, we have got the I/O interrupts, occurring at unpredictable and irreproducible moments; compared with the old sequential machine that pretended to be a fully deterministic automaton, this has been a dramatic change and many a systems programmer’s grey hair bears witness to the fact that we should not talk lightly about the logical problems created by that feature. Secondly, we have got machines equipped with multi-level stores, presenting us problems of management strategy that, in spite of the extensive literature on the subject, still remain rather elusive. So much for the added complication due to structural changes of the actual machines.
But I called this a minor cause; the major cause is… that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming had become an equally gigantic problem. In this sense the electronic industry has not solved a single problem, it has only created them, it has created the problem of using its products. To put it in another way: as the power of available machines grew by a factor of more than a thousand, society’s ambition to apply these machines grew in proportion, and it was the poor programmer who found his job in this exploded field of tension between ends and means. The increased power of the hardware, together with the perhaps even more dramatic increase in its reliability, made solutions feasible that the programmer had not dared to dream about a few years before. And now, a few years later, he had to dream about them and, even worse, he had to transform such dreams into reality! Is it a wonder that we found ourselves in a software crisis? No, certainly not, and as you may guess, it was even predicted well in advance; but the trouble with minor prophets, of course, is that it is only five years later that you really know that they had been right.
Then, in the mid-sixties, something terrible happened: the computers of the so-called third generation made their appearance. The official literature tells us that their price/performance ratio has been one of the major design objectives. But if you take as “performance” the duty cycle of the machine’s various components, little will prevent you from ending up with a design in which the major part of your performance goal is reached by internal housekeeping activities of doubtful necessity. And if your definition of price is the price to be paid for the hardware, little will prevent you from ending up wth a design that is terribly hard to program for: for instance the order code might be such as to enforce, either upon the progrmmer or upon the system, early binding decisions presenting conflicts that really cannot be resolved. And to a large extent these unpleasant possibilities seem to have become reality.
When these machines were announced and their functional specifications became known, quite a few among us must have become quite miserable; at least I was. It was only reasonable to expect that such machines would flood the computing community, and it was therefore all the more important that their design should be as sound as possible. But the design embodied such serious flaws that I felt that with a single stroke the progress of computing science had been retarded by at least ten years: it was then that I had the blackest week in the whole of my professional life. Perhaps the most saddening thing now is that, even after all those years of frustrating experience, still so many people honestly believe that some law of nature tells us that machines have to be that way. They silence their doubts by observing how many of these machines have been sold, and derive from that observation the false sense of security that, after all, the design cannot have been that bad. But upon closer inspection, that line of defense has the same convincing strength as the argument that cigarette smoking must be healthy because so many people do it.
It is in this connection that I regret that it is not customary for scientific journals in the computing area to publish reviews of newly announced computers in much the same way as we review scientific publications: to review machines would be at least as important. And here I have a confession to make: in the early sixties I wrote such a review with the intention of submitting it to the CACM, but in spite of the fact that the few colleagues to whom the text was sent for their advice, urged me all to do so, I did not dare to do it, fearing that the difficulties either for myself or for the editorial board would prove to be too great. This suppression was an act of cowardice on my side for which I blame myself more and more. The difficulties I foresaw were a consequence of the absence of generally accepted criteria, and although I was convinced of the validity of the criteria I had chosen to apply, I feared that my review would be refused or discarded as “a matter of personal taste”. I still think that such reviews would be extremely useful and I am longing to see them appear, for their accepted appearance would be a sure sign of maturity of the computing community.
The reason that I have paid the above attention to the hardware scene is because I have the feeling that one of the most important aspects of any computing tool is its influence on the thinking habits of those that try to use it, and because I have reasons to believe that that influence is many times stronger than is commonly assumed. Let us now switch our attention to the software scene.
Here the diversity has been so large that I must confine myself to a few stepping stones. I am painfully aware of the arbitrariness of my choice and I beg you not to draw any conclusions with regard to my appreciation of the many efforts that will remain unmentioned.
In the beginning there was the EDSAC in Cambridge, England, and I think it quite impressive that right from the start the notion of a subroutine library played a central role in the design of that machine and of the way in which it should be used. It is now nearly 25 years later and the computing scene has changed dramatically, but the notion of basic software is still with us, and the notion of the closed subroutine is still one of the key concepts in programming. We should recognise the closed subroutines as one of the greatest software inventions; it has survived three generations of computers and it will survive a few more, because it caters for the implementation of one of our basic patterns of abstraction. Regrettably enough, its importance has been underestimated in the design of the third generation computers, in which the great number of explicitly named registers of the arithmetic unit implies a large overhead on the subroutine mechanism. But even that did not kill the concept of the subroutine, and we can only pray that the mutation won’t prove to be hereditary.
The second major development on the software scene that I would like to mention is the birth of FORTRAN. At that time this was a project of great temerity and the people responsible for it deserve our great admiration. It would be absolutely unfair to blame them for shortcomings that only became apparent after a decade or so of extensive usage: groups with a successful look-ahead of ten years are quite rare! In retrospect we must rate FORTRAN as a successful coding technique, but with very few effective aids to conception, aids which are now so urgently needed that time has come to consider it out of date. The sooner we can forget that FORTRAN has ever existed, the better, for as a vehicle of thought it is no longer adequate: it wastes our brainpower, is too risky and therefore too expensive to use. FORTRAN’s tragic fate has been its wide acceptance, mentally chaining thousands and thousands of programmers to our past mistakes. I pray daily that more of my fellow-programmers may find the means of freeing themselves from the curse of compatibility.
The third project I would not like to leave unmentioned is LISP, a fascinating enterprise of a completely different nature. With a few very basic principles at its foundation, it has shown a remarkable stability. Besides that, LISP has been the carrier for a considerable number of in a sense our most sophisticated computer applications. LISP has jokingly been described as “the most intelligent way to misuse a computer”. I think that description a great compliment because it transmits the full flavour of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.
The fourth project to be mentioned is ALGOL 60. While up to the present day FORTRAN programmers still tend to understand their programming language in terms of the specific implementation they are working with —hence the prevalence of octal and hexadecimal dumps—, while the definition of LISP is still a curious mixture of what the language means and how the mechanism works, the famous Report on the Algorithmic Language ALGOL 60 is the fruit of a genuine effort to carry abstraction a vital step further and to define a programming language in an implementation-independent way. One could argue that in this respect its authors have been so successful that they have created serious doubts as to whether it could be implemented at all! The report gloriously demonstrated the power of the formal method BNF, now fairly known as Backus-Naur-Form, and the power of carefully phrased English, a least when used by someone as brilliant as Peter Naur. I think that it is fair to say that only very few documents as short as this have had an equally profound influence on the computing community. The ease with which in later years the names ALGOL and ALGOL-like have been used, as an unprotected trade mark, to lend some of its glory to a number of sometimes hardly related younger projects, is a somewhat shocking compliment to its standing. The strength of BNF as a defining device is responsible for what I regard as one of the weaknesses of the language: an over-elaborate and not too systematic syntax could now be crammed into the confines of very few pages. With a device as powerful as BNF, the Report on the Algorithmic Language ALGOL 60 should have been much shorter. Besides that I am getting very doubtful about ALGOL 60′s parameter mechanism: it allows the programmer so much combinatorial freedom, that its confident use requires a strong discipline from the programmer. Besides expensive to implement it seems dangerous to use.
Finally, although the subject is not a pleasant one, I must mention PL/1, a programming language for which the defining documentation is of a frightening size and complexity. Using PL/1 must be like flying a plane with 7000 buttons, switches and handles to manipulate in the cockpit. I absolutely fail to see how we can keep our growing programs firmly within our intellectual grip when by its sheer baroqueness the programming language —our basic tool, mind you!— already escapes our intellectual control. And if I have to describe the influence PL/1 can have on its users, the closest metaphor that comes to my mind is that of a drug. I remember from a symposium on higher level programming language a lecture given in defense of PL/1 by a man who described himself as one of its devoted users. But within a one-hour lecture in praise of PL/1. he managed to ask for the addition of about fifty new “features”, little supposing that the main source of his problems could very well be that it contained already far too many “features”. The speaker displayed all the depressing symptoms of addiction, reduced as he was to the state of mental stagnation in which he could only ask for more, more, more… When FORTRAN has been called an infantile disorder, full PL/1, with its growth characteristics of a dangerous tumor, could turn out to be a fatal disease.
So much for the past. But there is no point in making mistakes unless thereafter we are able to learn from them. As a matter of fact, I think that we have learned so much, that within a few years programming can be an activity vastly different from what it has been up till now, so different that we had better prepare ourselves for the shock. Let me sketch for you one of the posssible futures. At first sight, this vision of programming in perhaps already the near future may strike you as utterly fantastic. Let me therefore also add the considerations that might lead one to the conclusion that this vision could be a very real possibility.
The vision is that, well before the seventies have run to completion, we shall be able to design and implement the kind of systems that are now straining our programming ability, at the expense of only a few percent in man-years of what they cost us now, and that besides that, these systems will be virtually free of bugs. These two improvements go hand in hand. In the latter respect software seems to be different from many other products, where as a rule a higher quality implies a higher price. Those who want really reliable software will discover that they must find means of avoiding the majority of bugs to start with, and as a result the programming process will become cheaper. If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with. In other words: both goals point to the same change.
Such a drastic change in such a short period of time would be a revolution, and to all persons that base their expectations for the future on smooth extrapolation of the recent past —appealing to some unwritten laws of social and cultural inertia— the chance that this drastic change will take place must seem negligible. But we all know that sometimes revolutions do take place! And what are the chances for this one?
There seem to be three major conditions that must be fulfilled. The world at large must recognize the need for the change; secondly the economic need for it must be sufficiently strong; and, thirdly, the change must be technically feasible. Let me discuss these three conditions in the above order.
With respect to the recognition of the need for greater reliability of software, I expect no disagreement anymore. Only a few years ago this was different: to talk about a software crisis was blasphemy. The turning point was the Conference on Software Engineering in Garmisch, October 1968, a conference that created a sensation as there occured the first open admission of the software crisis. And by now it is generally recognized that the design of any large sophisticated system is going to be a very difficult job, and whenever one meets people responsible for such undertakings, one finds them very much concerned about the reliability issue, and rightly so. In short, our first condition seems to be satisfied.
Now for the economic need. Nowadays one often encounters the opinion that in the sixties programming has been an overpaid profession, and that in the coming years programmer salaries may be expected to go down. Usually this opinion is expressed in connection with the recession, but it could be a symptom of something different and quite healthy, viz. that perhaps the programmers of the past decade have not done so good a job as they should have done. Society is getting dissatisfied with the performance of programmers and of their products. But there is another factor of much greater weight. In the present situation it is quite usual that for a specific system, the price to be paid for the development of the software is of the same order of magnitude as the price of the hardware needed, and society more or less accepts that. But hardware manufacturers tell us that in the next decade hardware prices can be expected to drop with a factor of ten. If software development were to continue to be the same clumsy and expensive process as it is now, things would get completely out of balance. You cannot expect society to accept this, and therefore we must learn to program an order of magnitude more effectively. To put it in another way: as long as machines were the largest item on the budget, the programming profession could get away with its clumsy techniques, but that umbrella will fold rapidly. In short, also our second condition seems to be satisfied.
And now the third condition: is it technically feasible? I think it might and I shall give you six arguments in support of that opinion.
A study of program structure had revealed that programs —even alternative programs for the same task and with the same mathematical content— can differ tremendously in their intellectual manageability. A number of rules have been discovered, violation of which will either seriously impair or totally destroy the intellectual manageability of the program. These rules are of two kinds. Those of the first kind are easily imposed mechanically, viz. by a suitably chosen programming language. Examples are the exclusion of goto-statements and of procedures with more than one output parameter. For those of the second kind I at least —but that may be due to lack of competence on my side— see no way of imposing them mechanically, as it seems to need some sort of automatic theorem prover for which I have no existence proof. Therefore, for the time being and perhaps forever, the rules of the second kind present themselves as elements of discipline required from the programmer. Some of the rules I have in mind are so clear that they can be taught and that there never needs to be an argument as to whether a given program violates them or not. Examples are the requirements that no loop should be written down without providing a proof for termination nor without stating the relation whose invariance will not be destroyed by the execution of the repeatable statement.
I now suggest that we confine ourselves to the design and implementation of intellectually manageable programs. If someone fears that this restriction is so severe that we cannot live with it, I can reassure him: the class of intellectually manageable programs is still sufficiently rich to contain many very realistic programs for any problem capable of algorithmic solution. We must not forget that it is not our business to make programs, it is our business to design classes of computations that will display a desired behaviour. The suggestion of confining ourselves to intellectually manageable programs is the basis for the first two of my announced six arguments.
Argument one is that, as the programmer only needs to consider intellectually manageable programs, the alternatives he is choosing between are much, much easier to cope with.
Argument two is that, as soon as we have decided to restrict ourselves to the subset of the intellectually manageable programs, we have achieved, once and for all, a drastic reduction of the solution space to be considered. And this argument is distinct from argument one.
Argument three is based on the constructive approach to the problem of program correctness. Today a usual technique is to make a program and then to test it. But: program testing can be a very effective way to show the presence of bugs, but is hopelessly inadequate for showing their absence. The only effective way to raise the confidence level of a program significantly is to give a convincing proof of its correctness. But one should not first make the program and then prove its correctness, because then the requirement of providing the proof would only increase the poor programmer’s burden. On the contrary: the programmer should let correctness proof and program grow hand in hand. Argument three is essentially based on the following observation. If one first asks oneself what the structure of a convincing proof would be and, having found this, then constructs a program satisfying this proof’s requirements, then these correctness concerns turn out to be a very effective heuristic guidance. By definition this approach is only applicable when we restrict ourselves to intellectually manageable programs, but it provides us with effective means for finding a satisfactory one among these.
Argument four has to do with the way in which the amount of intellectual effort needed to design a program depends on the program length. It has been suggested that there is some kind of law of nature telling us that the amount of intellectual effort needed grows with the square of program length. But, thank goodness, no one has been able to prove this law. And this is because it need not be true. We all know that the only mental tool by means of which a very finite piece of reasoning can cover a myriad cases is called “abstraction”; as a result the effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer. In this connection it might be worth-while to point out that the purpose of abstracting is not to be vague, but to create a new semantic level in which one can be absolutely precise. Of course I have tried to find a fundamental cause that would prevent our abstraction mechanisms from being sufficiently effective. But no matter how hard I tried, I did not find such a cause. As a result I tend to the assumption —up till now not disproved by experience— that by suitable application of our powers of abstraction, the intellectual effort needed to conceive or to understand a program need not grow more than proportional to program length. But a by-product of these investigations may be of much greater practical significance, and is, in fact, the basis of my fourth argument. The by-product was the identification of a number of patterns of abstraction that play a vital role in the whole process of composing programs. Enough is now known about these patterns of abstraction that you could devote a lecture to about each of them. What the familiarity and conscious knowledge of these patterns of abstraction imply dawned upon me when I realized that, had they been common knowledge fifteen years ago, the step from BNF to syntax-directed compilers, for instance, could have taken a few minutes instead of a few years. Therefore I present our recent knowledge of vital abstraction patterns as the fourth argument.
Now for the fifth argument. It has to do with the influence of the tool we are trying to use upon our own thinking habits. I observe a cultural tradition, which in all probability has its roots in the Renaissance, to ignore this influence, to regard the human mind as the supreme and autonomous master of its artefacts. But if I start to analyse the thinking habits of myself and of my fellow human beings, I come, whether I like it or not, to a completely different conclusion, viz. that the tools we are trying to use and the language or notation we are using to express or record our thoughts, are the major factors determining what we can think or express at all! The analysis of the influence that programming languages have on the thinking habits of its users, and the recognition that, by now, brainpower is by far our scarcest resource, they together give us a new collection of yardsticks for comparing the relative merits of various programming languages. The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague. In the case of a well-known conversational programming language I have been told from various sides that as soon as a programming community is equipped with a terminal for it, a specific phenomenon occurs that even has a well-established name: it is called “the one-liners”. It takes one of two different forms: one programmer places a one-line program on the desk of another and either he proudly tells what it does and adds the question “Can you code this in less symbols?” —as if this were of any conceptual relevance!— or he just asks “Guess what it does!”. From this observation we must conclude that this language as a tool is an open invitation for clever tricks; and while exactly this may be the explanation for some of its appeal, viz. to those who like to show how clever they are, I am sorry, but I must regard this as one of the most damning things that can be said about a programming language. Another lesson we should have learned from the recent past is that the development of “richer” or “more powerful” programming languages was a mistake in the sense that these baroque monstrosities, these conglomerations of idiosyncrasies, are really unmanageable, both mechanically and mentally. I see a great future for very systematic and very modest programming languages. When I say “modest”, I mean that, for instance, not only ALGOL 60′s “for clause”, but even FORTRAN’s “DO loop” may find themselves thrown out as being too baroque. I have run a a little programming experiment with really experienced volunteers, but something quite unintended and quite unexpected turned up. None of my volunteers found the obvious and most elegant solution. Upon closer analysis this turned out to have a common source: their notion of repetition was so tightly connected to the idea of an associated controlled variable to be stepped up, that they were mentally blocked from seeing the obvious. Their solutions were less efficient, needlessly hard to understand, and it took them a very long time to find them. It was a revealing, but also shocking experience for me. Finally, in one respect one hopes that tomorrow’s programming languages will differ greatly from what we are used to now: to a much greater extent than hitherto they should invite us to reflect in the structure of what we write down all abstractions needed to cope conceptually with the complexity of what we are designing. So much for the greater adequacy of our future tools, which was the basis of the fifth argument.
As an aside I would like to insert a warning to those who identify the difficulty of the programming task with the struggle against the inadequacies of our current tools, because they might conclude that, once our tools will be much more adequate, programming will no longer be a problem. Programming will remain very difficult, because once we have freed ourselves from the circumstantial cumbersomeness, we will find ourselves free to tackle the problems that are now well beyond our programming capacity.
You can quarrel with my sixth argument, for it is not so easy to collect experimental evidence for its support, a fact that will not prevent me from believing in its validity. Up till now I have not mentioned the word “hierarchy”, but I think that it is fair to say that this is a key concept for all systems embodying a nicely factored solution. I could even go one step further and make an article of faith out of it, viz. that the only problems we can really solve in a satisfactory manner are those that finally admit a nicely factored solution. At first sight this view of human limitations may strike you as a rather depressing view of our predicament, but I don’t feel it that way, on the contrary! The best way to learn to live with our limitations is to know them. By the time that we are sufficiently modest to try factored solutions only, because the other efforts escape our intellectual grip, we shall do our utmost best to avoid all those interfaces impairing our ability to factor the system in a helpful way. And I cannot but expect that this will repeatedly lead to the discovery that an initially untractable problem can be factored after all. Anyone who has seen how the majority of the troubles of the compiling phase called “code generation” can be tracked down to funny properties of the order code, will know a simple example of the kind of things I have in mind. The wider applicability of nicely factored solutions is my sixth and last argument for the technical feasibiilty of the revolution that might take place in the current decade.
In principle I leave it to you to decide for yourself how much weight you are going to give to my considerations, knowing only too well that I can force no one else to share my beliefs. As each serious revolution, it will provoke violent opposition and one can ask oneself where to expect the conservative forces trying to counteract such a development. I don’t expect them primarily in big business, not even in the computer business; I expect them rather in the educational institutions that provide today’s training and in those conservative groups of computer users that think their old programs so important that they don’t think it worth-while to rewrite and improve them. In this connection it is sad to observe that on many a university campus the choice of the central computing facility has too often been determined by the demands of a few established but expensive applications with a disregard of the question how many thousands of “small users” that are willing to write their own programs were going to suffer from this choice. Too often, for instance, high-energy physics seems to have blackmailed the scientific community with the price of its remaining experimental equipment. The easiest answer, of course, is a flat denial of the technical feasibility, but I am afraid that you need pretty strong arguments for that. No reassurance, alas, can be obtained from the remark that the intellectual ceiling of today’s average programmer will prevent the revolution from taking place: with others programming so much more effectively, he is liable to be edged out of the picture anyway.
There may also be political impediments. Even if we know how to educate tomorrow’s professional programmer, it is not certain that the society we are living in will allow us to do so. The first effect of teaching a methodology —rather than disseminating knowledge— is that of enhancing the capacities of the already capable, thus magnifying the difference in intelligence. In a society in which the educational system is used as an instrument for the establishment of a homogenized culture, in which the cream is prevented from rising to the top, the education of competent programmers could be politically impalatable.
Let me conclude. Automatic computers have now been with us for a quarter of a century. They have had a great impact on our society in their capacity of tools, but in that capacity their influence will be but a ripple on the surface of our culture, compared with the much more profound influence they will have in their capacity of intellectual challenge without precedent in the cultural history of mankind. Hierarchical systems seem to have the property that something considered as an undivided entity on one level, is considered as a composite object on the next lower level of greater detail; as a result the natural grain of space or time that is applicable at each level decreases by an order of magnitude when we shift our attention from one level to the next lower one. We understand walls in terms of bricks, bricks in terms of crystals, crystals in terms of molecules etc. As a result the number of levels that can be distinguished meaningfully in a hierarchical system is kind of proportional to the logarithm of the ratio between the largest and the smallest grain, and therefore, unless this ratio is very large, we cannot expect many levels. In computer programming our basic building block has an associated time grain of less than a microsecond, but our program may take hours of computation time. I do not know of any other technology covering a ratio of 1010 or more: the computer, by virtue of its fantastic speed, seems to be the first to provide us with an environment where highly hierarchical artefacts are both possible and necessary. This challenge, viz. the confrontation with the programming task, is so unique that this novel experience can teach us a lot about ourselves. It should deepen our understanding of the processes of design and creation, it should give us better control over the task of organizing our thoughts. If it did not do so, to my taste we should not deserve the computer at all!
It has already taught us a few lessons, and the one I have chosen to stress in this talk is the following. We shall do a much better programming job, provided that we approach the task with a full appreciation of its tremendous difficulty, provided that we stick to modest and elegant programming languages, provided that we respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers.
B is a computer language designed by D. M. Ritchie and K. L.
Thompson, for primarily non-numeric applications such as system
programming. These typically involve complex logical
decision-making, and processing of integers, characters, and bit strings.
On the H6070 TSS system, B programs are usually much easier to
write and understand than assembly language programs, and object
code efficiency is almost as good. Implementation of simple TSS
subsystems is an especially appropriate use for B.
This technical report contains a description of the MH-TSS
(Honeywell 6070) version of B (by S. C. Johnson), and a tutorial
introduction to most of the features of the language (by B. W.
Kernighan).
DMR note, June 1997:
This WWW page is a rendition of
Bell Laboratories Computing Science Technical
Report #8: The Programming Language B, January, 1973.
It was scanned using Adobe OCR software and
the version here was edited by Dennis Ritchie.
It is divided into two sections, each in several formats:
For scholars, the page images are also available:
The document seems to exist only on (partially) original
paper printed on a Teletype model 37 terminal. It uses underlining
for emphasis. You need to look at the PDF scans to verify any
typos I might have introduced in cleaning up the OCR, which was
pretty good except where there was underlining or double-quote
characters; they tended to merge into the line above. I
avoided the urge to redact the original except for a few
obvious mistakes, in particular some missing semicolons
in the syntax for some of the commands.
When this CSTR was issued, which was probably
some months after the papers were written,
the use of B was growing
on the local Honeywell GCOS system.
Its time-sharing facility was
called MH-TSS here, and it was then the main computation
facility at Bell Labs in Murray Hill, NJ.
By this time, use of B in the early Unix system was already pretty
much at an end; early C had already taken over
(see The Development of the
C Language). In fact, by September 1973, the operating system
had already been translated into C and most of the B utilities
converted.
The memos shown here were based on an earlier document,
User’s Reference to B,
by Ken Thompson.
The Unix dialect of B closely followed the Honeywell version
described here–the compiler front-ends were the same,
but of course the Unix system calls were present, and the
GCOS-specific I/O stuff absent. The basic library must
have looked very similar.
Indeed, there were never very many B programs on early Unix.
The compiler itself was written in B, and a few of the utilities,
for example the first /etc/glob, which expanded wild-card
characters for the shell.
This is because no compiler to machine code for the PDP-7 or PDP-11 was
ever built; the Unix B compilers produced interpreted, threaded
code that wasn’t efficient enough to write a whole system in.
On the other hand, B, with a real compiler, flourished in a modest way on the Honeywell
machines, as indicated by this CSTR.
Moreover, it had direct use and even progeny elsewhere, especially
at the University of Waterloo in Ontario.
It apparently lives on today: see
Thinkage Ltd. UW Tools Package,
for example.
A final note of possible historical interest or amusement:
so far as Brian and I can remember, the Tutorial contains the
first instance of a “Hello, world” program.
B is a new computer language designed and implemented at Murray
Hill. It runs and is actively supported and documented on the
H6070 TSS system at Murray Hill.
B is particularly suited for non-numeric computations, typified
by system programming. These usually involve many complex logical decisions, computations on integers and fields of words,
especially characters and bit strings, and no floating point. B
programs for such operations are substantially easier to write
and understand than GMAP programs. The generated code is quite
good. Implementation of simple TSS subsystems is an especially
good use for B.
B is reminiscent of BCPL [2] , for those who can remember. The
original design and implementation are the work of K. L. Thompson
and D. M. Ritchie; their original 6070 version has been substantially improved by S. C. Johnson, who also wrote the runtime
library.
This memo is a tutorial to make learning B as painless as possible. Most of the features of the language are mentioned in passing, but only the most important are stressed. Users who would
like the full story should consult A User’s Reference to B on
MH-TSS, by S. C. Johnson [1], which should be read for details
anyway.
We will assume that the user is familiar with the mysteries of
TSS, such as creating files, text editing, and the like, and has
programmed in some language before.
Throughout, the symbolism (->n) implies that a topic will be
expanded upon in section n of this manual. Appendix E is an
index to the contents.
main( ) {
-- statements --
}
newfunc(arg1, arg2) {
-- statements --
}
fun3(arg) {
-- more statements --
}
All B programs consist of one or more “functions”, which are
similar to the functions and subroutines of a Fortran program, or
the procedures of PL/I.
main
is such a function, and in fact all
B programs must have a
main.
Execution of the program begins at
the first statement of
main,
and usually ends at the last.
main
will usually invoke other functions to perform its job, some coming from the same program, and others from libraries. As in Fortran, one method of communicating data between functions is by
arguments. The parentheses following the function name surround
the argument list; here
main
is a function of no arguments, indicated by ().
The {} enclose the statements of the function.
Functions are totally independent as far as the compiler is concerned, and
main
need not be the first,
although execution starts
with it. This program has two other functions:
newfunc
has two
arguments, and
fun3
has one. Each function consists of one or
more statements which express operations on variables and
transfer of control. Functions may be used recursively at little
cost in time or space (->30).
Most statements contain expressions, which in turn are made up of
operators, names, and constants, with parentheses to alter the
order of evaluation. B has a particularly rich set of operators
and expressions, and relatively few statement types.
The format of B programs is quite free; we will strive for a uniform style as a good programming practice. Statements can be
broken into more than one line at any reasonable point, i.e.,
between names, operators, and constants. Conversely, more than
one statement can occur on one line. Statements are separated by
semicolons. A group of statements may be grouped together and
treated as a single statement by enclosing them in {}; in this
case, no semicolon is used after the ‘}’ . This convention is
used to lump together the statements of a function.
(a) SYSTEM? filsys cf bsource,b/1,100/<br /> (b) SYSTEM? filsys cf bhs,b/6,6/,m/r/<br /> (c) SYSTEM? [create source program with any text editor]<br /> (d) SYSTEM? ./bj (w) bsource bhs<br /> (e) SYSTEM? /bhs<br />
(a) and (b) need only be done once; they create file space for
the source program and the loaded program. (d) compiles the
source program from
bsource,
and after many machinations, creates a program in
bhs.
(e) runs that program. ./bj is more fully
described in [1].
You may from time to time get error messages from the B compilers
These look like either of
ee n<br /> ee name n<br />
where ee is a two-character error message, and
n
is the approximate source line number of the error. (->Appendix A)
main( ) {<br /> auto a, b, c, sum;<br /><br /> a = 1; b = 2; c = 3;<br /> sum = a+b+c;<br /> putnumb(sum);<br />}<br />
This simple program adds three numbers, and prints the sum. It
illustrates the use of variables and constants, declarations, a
bit of arithmetic, and a function call. Let us discuss them in
reverse order.
putnumb
is a library function of one argument, which will print a
number on the terminal (unless some other destination is specified (->28)).
The code for a version of
putnumb
can be found in
(->30). Notice that a function is invoked by naming it, followed
by the argument(s) in parentheses. There is no CALL statement as
in Fortran.
The arithmetic and the assignment statements are much the same as
in Fortran, except for the semicolons. Notice that we can put
several on a line if we want. Conversely, we can split a statement among lines if it seems desirable – the split may be between
any of the operators or variables, but not in the middle of a
variable name.
One major difference between B and Fortran is that B is a
typeless
language: there is no analog in B of the Fortran IJKLMN
convention. Thus a, b, c, and sum are all 36-bit quantities, and
arithmetic operations are integer. This is discussed at length
in the next section (->5).
Variable names have one to eight ascii characters, chosen from
A-Z, a-z, ., _, 0-9, and start with a non-digit. Stylistically,
it’s much better to use only a single case (upper or lower) and
give functions and external variables (->7) names that are unique
in the first six characters. ( Function and external variable
names are used by batch GMAP, which is limited to six character
single-case identifiers. )
The statement “auto …” is a declaration, that is, it defines
the variables to be used within the function. auto in particular
is used to declare local variables, variables which exist only
within their own function
(main
in this case). Variables may be
distributed among auto declarations arbitrarily,
but all declarations must precede executable statements.
All variables must be
declared, as one of auto, extrn (->7), or implicitly as function arguments (->8).
auto
variables are different from Fortran local variables in one
important respect – they appear when the function is entered, and
disappear when it is left. They cannot be initialized at compile
time, and they have no memory from one call to the next.
All arithmetic in B is integer, unless special functions are
written. There is no equivalent of the Fortran IJKLMN convention, no floating point, no data types, no type conversions, and
no type checking. Users of double-precision complex will have to
fend for themselves. (But see ->32 for how to call Fortran
subroutines.)
The arithmetic operators are the usual ‘+’, ‘-’, ‘*’, and ‘/’
(integer division). In addition we have the remainder operator
‘%’:
x = a%b<br />
sets x to the remainder after a is divided by b (both of which
should be positive).
Since B is often used for system programming and bit-manipulation, octal numbers are an important part of the
language. The syntax of B says that any number that begins with
0 is an octal number (and hence can’t have any 8′s or 9′s in it).
Thus 0777 is an octal constant, with decimal value 511.
main( ) {<br /> auto a;<br /> a= 'hi!';<br /> putchar(a);<br /> putchar('*n' );<br />}<br />
This program prints “hi!” on the terminal it illustrates the use
of character constants and variables. A “character” is one to
four ascii characters, enclosed in single quotes. The characters
are stored in a single machine word, right-justified and zero-filled. We used a variable to hold “hi!”, but could have used a
constant directly as well.
The sequence “*n” is B Jargon for “newline character”, which,
when printed, skips the terminal to the beginning of t:e next
line. No output occurs until putchar encounters a “*n” or the
program terminates. Omission of the “*n”, a common error, causes
all output to appear on one line, which is usually not the
desired result. There are several other escapes like “*n” for
representing hard-to-get characters (->Appendix B). Notice that
“*n” is a single character: putchar(‘hi!*n’) prints
four characters (the maximum with a single call).
Since B is a typeless language, arithmetic on characters is quite
legal, and even makes sense sometimes:
c = c+'A'-'a';<br />
converts a single character stored in c to upper case (making use
of the fact that corresponding ascii letters are a fixed distance
apart).
main( ) {<br /> extrn a, b, c;<br /> putchar(a); putchar(b); putchar(c); putchar('!*n');<br />}<br /><br />a 'hell';<br />b 'o, w';<br />c 'orld';<br />
This example illustrates
external variables,
variables which are
rather like Fortran COMMON, in that they exist external to all
functions, and are (potentially) available to all functions. Any
function that wishes to access an external variable must contain
an
extrn
declaration for it. Furthermore, we must define all
external variables outside any function% For our example
variables a, b, and c, this is done in the last three lines.
External storage is static, and always remains in existence, so
it can be initialized. (Conversely,
auto
storage appears
whenever the function is invoked, and disappears when the
function is left.
auto
variables of the same name in different
functions are unrelated. ) Initialization is done as shown: the
initial value appears after the name, as a constant. We have
shown character constants; other forms are also possible. External variables are initialized to zero if not set explicitly.
main( ) {<br /> extrn a,b,c,d;<br /> put2char(a,b) ;<br /> put2char(c,d) ;<br />}<br /><br />put2char(x,y) {<br />putchar(x);<br />putchar(y);<br />}<br /><br />a 'hell'; b 'o, w'; c 'orld'; d '!*n';<br />
This example does the same thing as the last, but uses a separate
(and quite artificial) function of two arguments,
put2char.
The
dummy names x and y refer to the arguments throughout putchar;
they are not declared in an auto statement.
We could equally
well have made a,b,c,d
auto
variables, or have called
put2char
as
put2char( 'hell','o, w');<br /> etc.<br />
Execution of
put2char
terminates when it runs into the closing ‘}’,
as in
main;
control returns to the next statement of
the calling program.
main( ) {<br /> auto c;<br /> c= getchar();<br /> putchar(c);<br />}<br />
getchar
is another library IO function. It fetches one character
from the input line each time it is called, and returns that
character, right adjusted and zero filled, as the value of the
function. The actual
implementation of
getchar
is to read an
entire line, and then
hand out the characters one at a time.
After the ‘*n’ at the
end of the line has been returned, the next
call to getchar will cause an entire new line to be read, and its
first character returned. Input is generally from the terminal (->28).
== equal to (".EQ." to Fortraners)<br /> != not equal to<br /> > greater than<br /> < less than<br /> >= greater than or equal to<br /> <= less than or equal to<br />
These are the relational operators; we will use ‘!=’ (“not equal
to) in the next example. Don’t forget that the equality test is
‘==’; using just one ‘=’ leads to disaster of one sort or another. Note: all comparisons are arithmetic, not logical.
main( ) {<br /> auto c;<br />read:<br /> c= getchar();<br /> putchar(c);<br /> if(c != '*n') goto read;<br />} /* loop if not a newline */<br />
This function reads and writes one line. It illustrates several
new things. First and easiest is the comment, which is anything
enclosed in /*…*/, just as in PL/I.
read
is a label – a name followed by a colon ‘:’, also just as in
PL/I. A statement can have several labels if desired. (Good
programming practice dictates using few labels, so later examples
will strive to get rid of them.) The goto references a label in
the same function.
The
if
statement is one of four conditionals in B. (while (->14),
switch (->26), and “?:” (->16) are the others.) Its general form is
if (expression) statement<br />
The condition to be tested is any expression enclosed in
parentheses. It is followed by a statement. The expression is
evaluated, and if its value is non-zero, the statement is
executed. One of the nice things about B is that the statement
can be made arbitrarily complex (although we’ve used very simple
ones here) by enclosing simple statements in {} (->12)
if(a<b) {<br /> t = a;<br /> a = b;<br /> b = t;<br /> }<br />
As a simple example of compound statements, suppose we want to
ensure that a exceeds b, as part of a sort routine. The interchange of a and be takes three statements in B; they are grouped
together by {} in the example above.
As a general rule in B, anywhere you can use a simple statement,
you can use any compound statement, which is just a number of
simple or compound ones enclosed in {}. Compound statements are
not followed by semicolons.
The ability to replace single statements by complex ones at will
is one thing that makes B much more pleasant to use than Fortran.
Logic which requires several GOTO’s and labels in Fortran can be
done in a simple clear natural way using the compound statements
of B.
read:<br /> c = putchar(getchar());<br /> if (c != '*n') goto read;<br />
Functions which return values (as all do, potentially ->24) can
be used anywhere you might normally use an expression. Thus we
can use
getchar
as the argument of
putchar,
nesting the functions.
getchar
returns exactly the character that
putchar
needs
as an argument.
putchar
also passes its argument back as a
value, so we assign this to c for later reference.
Even better, if c won’t be needed later, we can say
read:<br /> if (putchar(getchar()) != '*n') goto read;<br />
while ((c=getchar()) != '*n') putchar(c);<br />
Avoiding
isgoto‘s
Thisgoto‘s.
the previous one. (The difference? This one doesn’t print the
terminating ‘*n’.) The
while
statement is basically a loop statement, whose general form is
while (expression) statement<br />
As in the
if
statement, the expression and the statement can both
be arbitrarily complicated, although we haven’t seen that yet.
The action of while is
(a) evaluate the expression<br /> (b) if its value is true (i. e., not zero), do the<br /> statement and return to (a)<br />
Our example gets the character and assigns it to c, and tests to
see if it’s a ‘*n’. If it isn’t, it does the statement part of
the
while,
a
putchar,
and then repeats.
Notice that we used an assignment statement “c=getchar()’” within
an expression. This is a handy notational shortcut, usually produces better code, and is sometimes necessary if a statement is
to be compressed. This works because an assignment statement has
a value, just as any other expression does. This also implies
that we can successfully use multiple assignments like
x = y = f(a)+g(b)<br />
As an aside, the extra pair of parentheses in the assignment
statement within the conditional were really necessary: if we had
said
c = getchar() != '*n'<br />
c would be set to 0 or 1 depending on whether the character
fetched was a newline or not. This is because the binding
strength of the assignment operator ‘=’ is lower than the relational operator ‘!=’. (-> Appendix D)
main( ) {<br /> auto c;<br /> while (1) {<br /> while ( (c=getchar()) != ' ')<br /> if (putchar(c) == '*n') exit();<br /> putchar( '*n' );<br /> while ( (c=getchar()) == ' '); /* skip blanks */<br /> if (putchar(c)=='*n') exit(); /* done when newline */<br /> }<br />}<br />
This terse example reads one line from the terminal, and prints
each non-blank string of characters on a separate line: one or
more blanks are converted into a single newline.
Line four fetches a character, and if it is non-blank, prints it,
and uses the library function
exit
to terminate execution if it’s
a newline. Note the use of the assignment within an expression
to save the value of c.
Line seven skips over multiple blanks. It fetches a character,
and if it’s blank, does the statement ‘;’. This is called a null
statement – it really does nothing. Line seven is just a very
tight loop, with all the work done in the expression part of the
while clause.
The slightly odd-looking construction
while(1){<br /> ---<br /> }<br />
is a way to get an infinite loop. “1″ is always non-zero; so the
statement part (compound here!) will always be done. The only
way to get out of the loop is to execute a goto (->11) or break
(->26), or return from the function with a
return
statement
(->24), or terminate execution by
exit.
if (expression) statement else statement2<br />
is the most general form of the
if
- the
else
part is sometimes
useful. The canonical example sets x to the minimum of a and b:
if (a<b) x=a; else x=b;<br />
If’s and else’s can be used to construct logic that branches one
of several ways, and then rejoins, a common programming structure, in this way:
if(---)<br /> { -----<br /> ----- }<br /> else if(---)<br /> { -----<br /> ----- }<br /> else if(----)<br /> { -----<br /> ----- }<br />
etc.
The conditions are tested in order, and exactly one block is executed – the first one whose if is satisfied. When this block is
finished, the next statement executed is the one after the last
“else if” block.
B provides an alternate form of conditional which is often more
concise and efficient. It is called the “conditional expression”
because it is a conditional which actually has a value and can be
used anywhere an expression can. The last example can best be
expressed as
x = a<b ? a : b;<br />
The meaning is: evaluate the expression to the left of ‘?’. If it
is true, evaluate the expression between ‘?’ and ‘:’ and assign
that value to x. If it’s false, evaluate the expression to the
right of ‘:’ and assign its value to x.
auto k;<br /> k = 0;<br /> while (getchar() != '*n') ++k;<br />
B has several interesting unary operators in addition to the
traditional ‘-’. The program above uses the increment operator
‘++’ to count the number of characters in an input line. “++k”
is equivalent to “k=k+1″ but generates better code. ‘++’ man
also be used after a variable, as in
k++<br />
The only difference is this. suppose k is 5. Then
x = ++k<br />
sets k to 6 and then sets x to k, i.e., to 6. But
x = k++<br />
sets x to 5, and then k to 6.
Similarly, the unary decrement operator ‘–’ can be used either
before or after a variable to decrement by one.
c = o;<br /> i = 36;<br /> while ((i = i-9) >= 0) c = c | getchar()<<i;<br />
B has several operators for logical bit-manipulation. The example above illustrates two, the OR ‘|’ , and the left shift <<.
This code packs the next four 9-bit characters from the input
into the single 36-bit word c, by successively left-shifting the
character by i bit positions to the correct position and OR-ing
it into the word.
The other logical operators are AND ‘&’, logical right shift
‘>>’, exclusive OR ‘^’, and 1′s complement ‘~’.
x = ~y&0777<br />
sets x to the last 9 bits of the 1′s complement of y, and
x = x&077<br />
replaces x by its last six bits.
The order of evaluation of unparenthesized expressions is determined by the relative binding strengths of the operators involved
(-> Appendix D).
An unusual feature of B is that the normal binary operators like
‘+’, ‘-’, etc. can be combined with the assignment operator =
to form new assignment operators. For example,
x =- 10<br />
means “x=x-10″. ‘=-’ is an assignment operator. This convention
is a useful notational shorthand, and usually makes it possible
for B to generate better code. But the spaces around the operator are critical! For instance,
x = -10<br />
sets x to -10, while
x =- 10<br />
subtracts 10 from x. When no space is present,
x=-10<br />
also decreases x by 10. This is quite contrary to the experience
of most programmers.
Because assignment operators have lower binding strength than any
other operator, the order of evaluation should be watched
carefully:
x = x<<y|z<br />
means “shift x left y places, then OR in z, and store in x”. But
x =<< y|z<br />
means “shift x left by y|z places”, which is rather different.
The character-packing example can now be written better as
c= 0;<br /> i = 36;<br /> while ((i =- 9) >= 0) c =| getchar()<<i;<br />
A vector is a set of consecutive words, somewhat like a one-dimensional array in Fortran. The declaration
auto v[10];<br />
allocates 11 consecutive words? v[0], v[1], …, v[10] for v.
Reference to the i-th element is made by v[i] ; the [] brackets
indicate subscripting. (There is no Fortran-like ambiguity
between subscripts and function call.)
sum = o;<br /> i = 0;<br /> while (i<=n) sum =+ V[i++];<br />
This code sums the elements of the vector v. Notice the increment
within the subscript – this is common usage in B. Similarly, to
find the first zero element of v,
i = -1;<br /> while (v[++i]);<br />
Vectors can of course be external variables rather than
auto.
We declare v external within the function (don’t mention a size) by
extrn v;<br />
and then outside all functions write
v[10];<br />
External vectors may be initialized just as external simple
variables:
v[10] 'hi!', 1, 2, 3, 0777;<br />
sets v[0] to the character constant ‘hi!’, and V[1] through v[4]
to various numbers. v[5] through v[10] are not initialized.
To understand all the ramifications of vectors, a digression into
addressing is necessary. The actual implementation of a vector
consists of a word v which contains in its right half the address
of the 0-th word of the vector; i.e., v is really a pointer to
the actual vector.
This implementation can lead to a fine trap for the unwary. If
we say
auto u[10], v[10];<br /> ---<br /> u = v;<br /> v[0] = ...<br /> v[1] = ...<br /> ---<br />
the unsuspecting might believe that u[0] and u[1] contain the old
values of v[0] and v[1]; in fact, since u is just a pointer to
v[0] , u actually refers to the new content. The statement “u=v”
does not cause any copy of information into the elements of u;
they may indeed be lost because u no longer points to them.
The fact that vector elements are referenced by a pointer to the
zeroeth entry makes subscripting trivial – the address of v[i] is
simply v+i. Furthermore, constructs like v[i][j] are quite
legal: v[i] is simply a pointer to a vector, and v[i][j] is its
j-th entry. You have to set up your own storage, though.
To facilitate manipulation of addresses when it seems advisable,
B provides two unary ad~ress operators, ‘*’ and ‘&’. ‘&’ is the
address operator so &x is the address of x, assuming it has
one. ‘*’ is the indirection operator; “*x” means “use the content of x as an address.”
Subscripting operations can now be expressed differently:
x[0] is equivalent to *x<br /> x[1] is equivalent to *(x+1)<br /> &x[0] is equivalent to x<br />
A string in B is in essence a vector of characters. It is written as
"this is a string"<br />
and, in internal representation, is a vector with characters
packed four to a word, left justified, and terminated by a mysterious character known as ‘*e’ (ascii EOT). Thus the string
"hello"<br />
has six characters, the last of which is ‘*e’. Characters are
numbered from zero. Notice the difference between strings and
character constants. Strings are double-quoted, and have zero or
more characters; they are left justified and terminated by an
explicit delimiter, ‘*e’. Character constants are single-quoted,
have from one to four characters, and are right justified and
zero-filled.
Some characters can only be put into strings by “escape sequences” (-> Appendix B ). For instance, to get a double quote
into a string, use ‘*”‘, as in
"He said, *"Let's go.*""<br />
External variables may be initialized to string values simply by
following their names by strings, exactly as for other constants.
These definitions initialize a, b, and three elements of v:
a "hello"; b "world'*;<br /> v[2] "now is the time", "for all good men",<br /> "to come to the aid of the party";<br />
B provides several library functions for manipulating strings and
accessing characters within them in a relatively machine-independent way.
These are all discussed in more detail in section 8.2 of [1]. The two most commonly used are
char
and
lchar.
char(s,n) returns the n-th character of s, right justified and
zero-filled. lchar(s,n,c) replaces the n-th character of s by c,
and returns c. (The code for
char
is given in the next section.)
Because strings are vectors, writing “s1=s2″ does not copy the
characters in s2 into s1, but merely makes s1 point to s2. To
copy s2 into s1, we can use char and lchar in a function like
strcopy:
strcopy(sl ,s2){<br /> auto i;<br /> i = 0;<br /> while (lchar(sl,i,char(s2,i)) != '*e') i++;<br /> }<br />
How do we arrange that a function like char returns a value to
its caller? Here is
char:
char(s, n){<br /> auto y,sh,cpos;<br /> y = s[n/4]; /* word containing n-th char */<br /> cpos = n%4; /* position of char in word */<br /> sh = 27-9*cpos; /* bit positions to shift */<br /> y = (y>>sh)&0777; /* shift and mask all but 9 bits */<br /> return(y); /* return character to caller */<br /> }<br />
A
return
in a function causes an immediate return to the calling
program. If the
return
is followed by an expression in
parentheses, this expression is evaluated, and the value returned
to the caller. The expression can be arbitrarily complex, of
course:
char
is actually defined as
char(s,n) return((s[n/4]>>(27-9*(n%4)))&0777);<br />
Notice that char is written without {}, because it can be expressed as a simple statement.
concat(s,al,a2,…,a10) concatenates the zero or more strings ai
into one big string s, and returns s (which means a pointer to
S[0]). s must be declared big enough to hold the result
(including the terminating ‘*e’).
getstr(s) fetches the entire next line from the input unit into
s, replacing the terminating ‘*n’ by ‘*e’. In B, it is
getstr(s){<br /> auto c,i;<br /> while ((c=getchar()) != '*n') lchar(s,i++,c);<br /> lchar(s,i,'*e');<br /> return(s) ;<br /> }<br />
Similarly putstr(s) puts the string s onto the output unit,
except for the final ‘*e’. Thus
auto s[20] ;<br /> putstr(getstr(s)); putchar('*n');<br />
copies an input line to the output.
loop:<br /> switch (c=getchar()){<br /><br /> pr:<br /> case 'p': /* print */<br /> case 'P':<br /> print();<br /> goto loop;<br /><br /> case 's': /* subs */<br /> case 'S':<br /> subs() ;<br /> goto pr;<br /><br /> case 'd': /* delete */<br /> case 'D':<br /> delete();<br /> goto loop;<br /><br /> case '*n': /* quit on newline */<br /> break;<br /><br /> default:<br /> error(); /* error if fall out */<br /> goto loop;<br /><br /> }<br />
This fragment of a text-editor program illustrates the
switch
statement, which is a multi-way branch.
Here, the branch is controlled by a character read into c. If c is ‘p’ or ‘P’, function
print
is invoked. If c is an ‘s’ or ‘S’,
subs
and
print
are both
invoked. Similar actions take place for other values.
If c does
not mention any of the values mentioned in the case statements,
the default statement (in this case, an error function) is invoked.
The general form of a switch is
switch (expression) statement<br />
The statement is always complex, and contains statements of the
form
case constant:<br />
The constants in our example are characters, but they could also
be numbers. The expression is evaluated, and its value matched
against the possible cases. If a match is found, execution continues at that case. (Execution may of course fall through from
one case to the next, and may transfer around within the switch,
or transfer outside it.) Notice we put multiple cases on several
statements.
If no match is found, execution continues at the statement labeled
default:
if it exists; if there is no match and no
default,
the entire statement part of the switch is skipped.
The
break
statement forces an immediate transfer to the next
statement after the switch statement, i.e., the statement after
the {} which enclose the statement part of the
switch.
break
may also be used in while statements in an analogous manner.
break
is a useful way to avoid useless labels.
In this section, we point to the function
printf,
which is used
for producing formatted IO.
This function is so useful that it
is actually placed in Appendix C for ready reference.
File IO is described in much more detail in [1], section 8. This
discussion does only the easy things.
Basically, all IO in B is character-oriented, and based on
getchar and putchar. By default, these functions refer to the
terminal, and IO goes there unless explicit steps are taken to
divert it. The diversion is easy and systematic, so IO unit
switching is quite feasible.
At any time there is one input unit and one output unit;
getchar
and
putchar
use these for their input and output by implication.
The unit is a number between -1 and 10 (rather like Fortran file
numbers). The current values are stored in the external variables
rd.unit
and
wr.unit
so they can be changed easily, although
most programs need not use them directly. When execution of a B
program begins,
rd.unit
is 0, which means “read from terminal”,
and
wr.unit
is -1, meaning “write on terminal”.
To do input from a file, we set
rd.unit
to a value, and assign a
file name to that unit. Then, until the assignment or the value
is changed,
getchar
reads its characters from that file. Thus,
to open for reading an ascii permanent file called “cat/file”, as
input unit 5,
openr(5, "cat/file")<br />
The first argument is the unit number, and the second is a
cat/file description. (An empty string means the terminal.)
rd.unit
is set to 5 by
openr
so successive calls to
getchar,
getstr,
etc., will fetch characters from this file. If the file
is non-existent or if we read to end of file, all successive
calls produce ‘*e’.
Writing is much the same:
openw(u,s)<br />
opens ascii file s as unit u for writing. Successive calls to
putchar,
putstr,
printf,
etc., will place output on file s.
If the IO unit mentioned in
openr
or
openw
is already open, it is
closed before the next use. That is, any output for output files
is flushed and end of file written; any input from input files is
thrown away. Files are also closed this way upon normal termination.
Programs which have only one input and one output unit open
simultaneously need not reference
rd.unit
and
wr.unit
explicitly,
since the opening routines will do It automatically. Otherwise,
don’t forget to declare them in an
extrn
statement.
The function
flush
closes the current output unit without writing
a terminating newline character. If this file is the terminal,
this is the way to force a prompting question before reading a
response on the same line:
putstr("old or new?");<br /> flush();<br /> getstr(s);<br />
prints
<tt> old or new?<br /></tt>
and reads the response from the same line.
File names may only be “cat/file”, “/file”, or “file”: no permissions, passwords subcatalogs or alternate names are allowed.
File names containing a ‘/’ are assumed to be permanent files; if
you try to open a permanent file which is already accessed, it is
released and reaccessed. If it can’t be found, the access fails.
A file name without ‘/’ may or may not be a permanent file, so if
a file of this name is already accessed, it is used without question. If it is not already accessed, a search of the user’s
catalog is made for it. If it can’t be found there either, and
writing is desired, a temporary file is made.
The function
reread
is used to re-read a line. Its primary function is that if it is called before the first call to
getchar,
it
retrieves the command line with which the program was called.
<tt> reread();<br /> getstr(s);<br /></tt>
fetches the command line, and puts it into string s.
TSS users can easily execute other TSS subsystems from within a
running B program, by using the
library function
system.
For
instance,
<tt> system("./rj (w) ident;file");<br /></tt>
acts exactly as if we had typed
<tt> ./rj (w) ident;file<br /></tt>
in response to “SYSTEM?”. The argument of
system
is a string,
which is executed as if typed at “SYSTEM?” level. (No ‘*n’ is
needed at the end of the string.) Return is to the B program
unless disaster strikes. This feature permits B programs to use
TSS subsystems and other programs to do major functions without
bookkeeping or core overhead.
We can also use
printf
(->Appendix C) to write on the
“system” IO
unit, which is predefined as -1. All output written on unit -1
acts as if typed at “SYSTEM?” level. Thus,
<tt> extrn wr.unit;<br /> ---<br /> wr.unit = -1;<br /> opts = "(w)";<br /> fname = "file";<br /> printf("./rj %s ident;%s*n", opts,fname');<br /></tt>
will set the current output unit to -1, the system, and then
print on it using
printf
to format the string. This example does
the same thing as the last, but the RUNJOB options and the file
names are
variables, which can be changed as desired. Notice that
this time a ‘*n’ is necessary to terminate the line.
Because of serious design failings in TSS, there is generally no
decent way to send more than the command line as input to a program called this way, and no way to retrieve output from it.
<tt> putnumb(n) {<br /> auto a;<br /> if(a=n/10) /* assignment, not equality test */<br /> putnumb(a); /* recursive */<br /> putchar(n%10 + '0');<br /> }<br /></tt>
This simplified version of the library function
putnum
illustrates the use of recursion. (It only works for n>0.) “a” is set
to the quotient of n/10; if this is non-zero, a recursive call on
putnumb is made to print the quotient. Eventually the high-order
digit of n will be printed, and then as each invocation
of putnumb is popped up,
the next digit will be added on.
There is a subtlety in function usage which can trap the unsuspecting Fortran programmer. Argument passing is call by
value”, which means that the called function is given the actual
values of its arguments, and doesn’t know their addresses. This
makes it very hard to change the value of one of the input
arguments!
For instance,
consider a function flip(x,y) which is to interchange its arguments.
We might naively write
<tt> flip(x,y){<br /> auto t;<br /> t = x;<br /> x = y;<br /> y = t;<br /> }<br /></tt>
but this has no effect at all.
(Non-believers: try it!) What we
have to do is pass the arguments as explicit addresses, and use
them as addresses.
Thus we invoke
flip
as
<tt> flip(&a,&b);<br /></tt>
and the definition of flip is
<tt> flip(x,y){<br /> auto t;<br /> t = *y;<br /> *x = *y;<br /> *y = t;<br /> }<br /></tt>
(And don’t leave out the spaces on the right of the equal signs.)
This problem doesn’t arise if the arguments are vectors, since a
vector is represented by its address.
As we mentioned, B doesn’t have floating
point, multi-dimensional arrays,
and similar things that Fortran does better. A B program,
callf,
allows B programs to call Fortran and GMAP
subroutines, like this:
<tt> callf(name, a1,a2, . . .,a10)<br /></tt>
Here
name
is the Fortran function or subroutine to be used, and
the a’s are the zero or more arguments of the subroutine.
There are some restrictions on
callf,
related to the “call by
value” problem mentioned above. First, variables that are not
vectors or strings must be referenced by address: use “&x” instead of “x” as an argument. Second, no constants are allowed
among the arguments, because the construction “&constant” is
illegal in B. We can’t say
<tt> tod = callf(itimez,&0)<br /></tt>
to get the time of day; instead we have to use
<tt> t=0;<br /> tod = callf(itimez,&t) ;<br /></tt>
Third, it is not possible to return floating-point function
values from Fortran programs, since the results are in the wrong
register. They must be explicitly passed back as arguments. Thus
we can’t say
<tt> s = callf(sin,&x)<br /></tt>
but rather
<tt> callf(sin2,&x,&s)<br /></tt>
where sin2 is defined as
<tt> subroutine sin2(x,y)<br /> y = sin(x)<br /> return<br /> end<br /></tt>
Fourth,
callf
isn’t blindingly efficient, since there’s a lot of
overhead converting calling sequences. (Very short GMAP routines
to interface with B programs can often be coded quite efficiently
see [1], section 11.)
1273-bwk-pdp
B. W. KERNIGHAN
Attached
References
Appendix A,B,C,D
Diagnostics consist of two letters, an optional name, and a
source line number. Because of the free form input, the source
line number may be too high.
<tt>$) - { } imbalance<br />() - ( ) imbalance<br />*/ - /**/ imbalance<br />[] - [] imbalance<br />>c - case table overflow (fatal)<br />>e - expression stack overflow (fatal)<br />>i - label table overflow (fatal)<br />>s - symbol table overflow (fatal)<br />ex - expression syntax error<br />lv - address expected<br />rd name name redeclaration - multiple definition<br />sx keyword statement syntax error<br />un name undefined name - line number is last line<br /> of function where definition is missing<br />xx - syntax error in external definition<br /></tt>
Escape sequences are used in character constants and strings to
obtain characters which for one reason or another are hard to
represent directly. They consist of ‘*-’, where ‘-’ is as below:
<tt> *0 null (ascii NUL = 000)<br /> *e end of string (ascii EOT = 004)<br /> *( {<br /> *) }<br /> *t tab<br /> ** *<br /> *' '<br /> *" "<br /> *n newline<br /></tt>
Users of non-ascii devices like model 33/35 Teletypes or IBM
2741′s should use a reasonably clever text-editor like QED to
create special characters for B programs.
printf(fmt,a1,a2,a3,.. . ,a10)
This function writes the arguments ai (from 0 to 10 of which may
be present) onto the current output stream under control of the
format string
fmt.
The format conversion is controlled by
two-letter sequences of the form ‘%x’ inside the string
fmt,
where x
stands for one of the following:
<tt>c -- character data (ascii)<br />d -- decimal number<br />o -- octal number<br />s -- character string<br /></tt>
The characters in
fmt
which do not appear in one of these two
character sequences are copied without change to the output.
Thus the call
<tt> printf("%d + %o is %s or %c*n", 1,-1,"zero",'0');<br /></tt>
leads to the output line
<tt> 1 + 777777777777 is zero or 0<br /></tt>
As another example, a permanent file whose name is in the string
s can be created with size n blocks and general read permission
by using
printf
together with the system output unit (->29) and
the “filsys” subsystem:
<tt> wr.unit = -1 ;<br /> printf("filsys cf %s,b/%d/,r*n",s,n);<br /></tt>
Operators are listed from highest to lowest binding strength;
there is no order within groups. Operators of equal strength
bind left to right or right to left as indicated.
<tt> ++ -- * & - ! ~ (unary) [RL]<br /> * / % (binary) [LR]<br /> + - [LR]<br /> >> << [LR]<br /> > < <= >=<br /> == !=<br /> & [LR]<br /> ^ [LR]<br /> | [LR]<br /> ?: [RL]<br /> = =+ =- etc. (all assignment operators) [RL]<br /></tt>
Description
creators
Ken Iverson et al, at IBM.
papers & manuals
n.a.
software
APL
versions
APL\360, APL SV, VS APL, Sharp APL, Sharp APL/PC, APL2, APL*PLUS, APL*PLUS/PC, APL*PLUS/PC II, MCM APL, Honeyapple, DEC APL.
.
see also
J, S, Matlab
keywords
interpreter language mathemetics statistics
APL stands for “A Programming Language.” It was created in the 1960′s by Ken Iverson and his colleagues at IBM. The language was very much mathematically inspired and used a powerful notation for mathematical algorithms. Therefore APL uses non-ASCII (or non-EBCDIC) symbols, including some Greek letters. So eg the character “X” differs from the arithmetic operation multiply “x” ; the arithmetic operation “devide” is not a “/” but has its own character “a horizontal line and a dot above and below that line” (see below).
APL is a interactive, array and matrices oriented language. Compilers are available. There isn’t even an IF statement, although branching is possible, but that should be avoided. In APL, all expressions are evaluated from right to left. A few simple APL statements will give a feeling for the language:
 |
assignement, assign the values 10 22 25 33 to the variable COSTS; so the variable COSTS is a vector containing 4 values |
 |
reduce-function, reads as “sum over COSTS”, take the plus-reduction-of-variable COSTS, or just calculate the sum of all elements in vector COSTS |
 |
reduce-function, but now use multiply, reads as “mutiply over COSTS” |
 |
assignement using the rho-function, which define a matrix; variable COSTS2 will be a matrix of 2 rows and 4 columns and gets values 11 … 12 |
 |
the rho-function is used monadic, this means that there is only a right argument and not, as in above example, a right and a left argument (used dyadic); this monadic function wil give the number of rows and columns, so the result is a vector |
 |
do a “multiply over the result of a monadic rho over COSTS2″; this means give the total number of elements in COSTS2 |
 |
the “rho over COSTS” gives the number of elements in COSTS, the “sum over COSTS” gives the total sum over all elements; divede these two and it gives the total average |
 |
the “rho over matrix COSTS2″ gives the number of rows and columns; the “multiply over this result” gives the total number of elements in the matrix; the “plus over the matrix COSTS2″ gives the sum per row, so two values; the sum over that result gives the total sum, etc. |
This just gives a feeling for APL. There are a lot of powerfull monadic and dyadic functions, which make it possible to program in a very compact way. For a mathematician it is a perfect language, but the level of abstraction is very often too high for most “normal” programmers. Another example:
 |
This line of code calculates the prime numbers from 2 to the starting value of R, in this example 20. the “iota funtion” of R filles a vector (and that will be R again) with numbers from 1 to the value of the variable (20 in this example), the first element is dropped (that is the 1); so to the right of the “/” there will be 2 3 4 5 … 18 19 20 the “small.circle-dot-multiply” defines an outer product so all elements of R are multiplied by all elements of R giving a matrix; check whether elements of R are in the matrix and make a vector containing “1″-s at the place where that is true and “0″-s where that is not true inverse that vector and use it to grab that elements from R using the “over” function |
If you like this, go and enjoy APL. If not, no problem, and forget this language. Because of the compact style, maintenance of old programs is very often a hard job. Nowadays one finds APL on nearly all computers, whether micro, mini or mainframe [1].
Notwithstanding its age, many ideas in APL are still unique, while others have found their way into other programming languages. Eg “inverted files” are sold as a new technology for data warehousing and data mining, but APLDI used this technology in the 1970-s. A inverted files can not only read rows of a table as records, but can also read columns as records.
Links
The largest archive of APL and J software can be found at Waterloo University. Interpreters, workspaces, information, and more! [2].
There are a lot of APL associations, clubs, etc. The community seemes small, but has a high spirit. Look at site from eg the British APL Association , the Finnish APL Association , etc, A fine overview of associations, vendors, books, etc can be found at all these sites and on a lot of personal sites, eg Jim W’s APL Information . These links proof the theorem, “Once an APL programmer, always an APL addict”.
Specifications
see above
Chronology
Now that Unicode support in browsers is decent, I’ll try to put the code examples in Unicode characters rather than images. Let me know if there are any problems. (I’m keeping the images for now — feel free to delete if the Unicode characters are sufficiently useful.) –MarnenLaibowKoser
Interesting. U+2373 (the APL iota, �) gets converted by Wiki into a diamond with question mark. It’s not just a font issue, either: it shows up as the diamond when the page is edited. Changing it back to an iota in the editor *looks* different in the editor view, but Wiki doesn’t notice the change. This happens on MacOsx 10.6 with both Safari and Firefox. Is this a bug in handling this particular value? –MarnenLaibowKoser — Sounds similar to the OhAcuteBug.
APL stands for A Programming Language. It is an ArrayOrientedLanguage.
Its character set is a superset of ASCII. This is demonstrated in the following APL code sample:
Reserved words are preceded by a special symbol (called quad).
There are no precedence rules in APL: statements are simply read from right to left. For example,
12 – 3 + 4 yields 5, same as 12 – (3 + 4)
Contributors: DanB (Dan Baronet, or Dan Bernstein?)
While APL is executed right to left, it is read from left to right. — JimRussell
The intent was to use ‘function’al notation i.e. f(g(x)).
Could someone give a list of what the characters in the above example mean? I remember some of them, and a number of them are described in http://www.users.cloud9.net/~bradmcc/APL.html. However I have no idea what LJUST, RJUST or VTOM mean – I don’t believe they are APL primitives, but are either functions written in APL, or else functions from some language which replaces APL characters with alphanumeric strings. –PaulMorrison
Yes, you needed a special keyboard, and yes, you need a special terminal, since at that time we are talking about VT100 and variants, mostly IBM terminals actually, but I can’t remember their names.
I found some keyboard designs in Google. The one I used was similar to the most complex.
Although difficult to get used to, APL was Fun. I know of a large bank in Brazil that had a team of economists just doing what we call today DataMining in APL 20 years ago.
As I understand, if you had an extended APL, you needed an extended keyboard also. IBM must have loved this language at that time.
An APL program to find all PrimeNumbers <= an integer:
PRIMES : (~R∈R○.×R)/R←1↓�R
from: http://www.users.cloud9.net/~bradmcc/APL.html
So Apple stole the option key trick from APL? That makes the fact that Windows doesn’t use it even more disappointing than it already was.
APL was originally created to DefineDocumentSpecify? the IBM 360…
…and it was close enough to being an actual computer language that an interpreter was implemented for it (and a special type ball on the ibm selectric was created to represent it).
APL was once used to prototype SQL – SQL could be looked at as an attempt to extract the data-storage aspects of APL into a form which is generally useful.
APL is now a dead language: the user community is so small that you almost never hear about it
…and there are so many divergent variants that little is held in common beyond the basic language.
Still, there are lessons to be learned from APL which could benefit even the most cutting edge technologies.
For example: one of the lessons of UML is that it’s a mistake to introduce aggregations or multiplicities early on. These are details which are added later. And yet, “object-oriented” languages force you to learn design patterns dedicated to dealing with these concepts. In APL, on the other hand, you can use the same code to deal with 1:1, 1:n, n:1, or n:n multiplicities (yes, n:n is really 1:1 multiplicity, but you wouldn’t know that by the way you have to represent it in a classic OO language). n:m (outer join) multiplicities take a slightly different approach, but we’re talking a minor syntactic difference here, not a design pattern which requires the creation of several different classes.
When you look at a body of OO code (like .NET, or J2EE), and compare it to a body of APL code (like what you see at http://www.kx.com/download/documentation.htm, you can’t help but realize that there are lessons about CodeReuse which we’ve yet to integrate into the mainstream.
Q Anyone know where to get a “free” AplLanguage processor that works in WindowsXp, can communicate with a ComComponent (or activex) that has GUI, and also links up to databases via ODBC or OLEDB drivers?
Any dialect will do, though I prefer basic APL with ability to remap keyboard to using APL keys
A Did you try http://www.jsoftware.com, home of the “free” JayLanguage interpreter [RandyMacDonald]
A Workstation APL2 Time Limited Version of APL2
Last time I looked, the limitation is accumulated CPU time, so one can use this over a period of days, weeks, or months.
http://www14.software.ibm.com/webapp/download/preconfig.jsp?id=2002-12-22+21%3A26%3A37.604297R&cat=&fam=&s=p&S_TACT=104AH%20W42&S_CMP=
[IBM.com ... Products & services > Software > Software Development]
gerry lowry gerry.lowry@abilitybusinesscomputerservices.com
(Wednesday 2004-11-03 03:15 Eastern Time)
– sorry, I do not know the exact time limit … regardless, because it’s in CPU allocation, unless you stuck in a loop, you should get a substantial number of days, weeks, or months to play with it … as for clean uninstall, I am not that sure … one would hope that IBM can perform a clean uninstall but unfortunately, I can not speak on their behalf. As for me, I never uninstalled it, so I do not have an answer from my personal experience. — gerry http://abilitybusinesscomputerservices.com
A I’ve found NARS2000 at http://www.nars2000.org/ to be a solid player. It’s a Windows executable but it does easily run using Wine on Linux as suggested on it’s page. See also the “What it’s Not” section to know where it’s aimed. I certainly have used it to play around and attempt to rekindle my 30 year old skills (and I’m only 45 so what kind of geek does that make me?)
by
Alfred V. Aho,
Brian W. Kernighan,
and Peter J. Weinberger,
Addison-Wesley, 1988.
ISBN 0-201-07981-X.
The AWK book has been translated:
Alternative books that contain significant amounts of AWK include
Effective AWK Programming, 3rd edition by Arnold Robbins
(O’Reilly, 2001, ISBN 0-596-00070-7),
and
Sed & Awk, 2nd edition
by Dale Dougherty and Arnold Robbins
(O’Reilly, 1997, ISBN 1-56592-225-5).
History
ALGOL (ALGOrithmic Language) is one of several high level languages designed
specifically for programming scientific computations. It started out in the late 1950′s, first formalized in a
report titled ALGOL 58, and then progressed through reports ALGOL 60, and
ALGOL 68. It was designed by an international committee to be a universal language. Their original conference, which took place in Zurich, was one of the
first formal attempts to address the issue of software portability. ALGOL’s machine
independence permitted the designers to be more creative, but it made
implementation much more difficult. Although ALGOL never reached the level of commercial popularity of
FORTRAN and COBOL, it is considered the most important language of its era
in terms of its influence on later language development. ALGOL’s lexical
and syntactic structures became so popular that virtually all languages
designed since have been referred to as “ALGOL – like”; that is they have
been hierarchical in structure with nesting of both environments and control
structures.
by Eric DeArment, Team Ada
ejd@efn.org
“Why learn Ada?,” you ask.
I can think of at least three good reasons:
Back in 1957, a computer scientist at IBM Corporation named John Backus
created a new language that was intended to make it so that scientists,
engineers and mathematicians could more easily solve mathematical and
scientific problems. The language, FORTRAN, which is short for “FORmula
TRANslation,” was a complete success; forty years later, it’s still being
actively used and developed.
Across the Atlantic, in Europe, some computer scientists who had known
about FORTRAN formed a committee to create their own language, one that
they could use for the same purposes as FORTRAN. Only months later, in
1958, the new programming language, dubbed “ALGOL,” an acronym for
“ALGOrithmic Language,” was all finished, and quickly standardized.
It’s often considered “tradition” to name a computer language standard
after the year that it was standardized, so the creators of ALGOL named it
ALGOL 58. People all over Europe continued to work on ALGOL, and only two
years later, ALGOL 60 was unleashed.
ALGOL 60 is very important in the history of several languages used today,
including Ada. From ALGOL 60 we get three language families:
So, enough on Ada’s ancestry, and now on to the actual creation of the
language.
In the 1960s and 1970s, the United States Department of Defense was using
more than 2,000 languages for its mission-critical programming. Most of
these were languages that were developed for one specific job. Finally,
in 1975, the DoD formed the U.S. Department of Defense High-Order
Language Working Group (HOLWG) to find a solution to what was often called
the “software crisis.”
What the HOLWG group members decided was that they needed to create a
language that they could use for just about anything, whether it be systems
programming, artificial intelligence, and, most important of all, real-time
programming and embedded systems. Real-time programs are the
programs used for controlling such things as traffic lights, guided
missiles, and bar-code scanners. Embedded systems are the
small computers that are built into most modern cars, airplanes, and
stereos.
Rather than create this new language themselves, they decided to hold a
contest. Several teams joined, each represented by a color. Coincidentally,
all of the teams created Pascal-based languages. In the end, the winner was
the green team — CII Honeywell-Bull in France. Eventually, the language was
christened “Ada,” in honor of Lady Ada Lovelace, daughter of famed poet Lord
Byron and assistant to mathematician Charles Babbage, who invented the
Analytical Machine. Lady Ada is often considered to be the world’s first
programmer.
In 1979, the DoD created its first draft documentation on Ada, and the
language was first standardized in 1983. Now named “Ada 83″, this standard was
originally controlled entirely by the DoD, and nobody outside the DoD
could create any Ada compiler without the authorization of the Defense
Department.
All that changed in 1987, however, when the DoD released Ada to the public
and the language was made an international standard by the International
Standards Organization (ISO). By 1990, over 200 validated Ada compilers had
been produced, and in 1995 a new standard, called Ada 95, was announced.
Ada 95 is object-oriented, and offers interfaces to the languages C, FORTRAN
and COBOL.
Normally, you’d probably expect a compiler for a language as powerful as
Ada 95 to cost a fortune, but you’ll be surprised when you find that one of
the most powerful and popular Ada 95 compilers, GNAT, the GNU/NYU Ada 95
Translator, is provided free of charge.
GNAT can be obtained from the Public Ada Library (PAL) FTP site,
ftp://wuarchive.wustl.edu, in the
/languages/ada/compiler/gnat
directory. This directory contains versions of GNAT for several variants of
Unix, including SunOS/Solaris, Linux, NetBSD, SGI IRIX, IBM’s AIX, DEC’s
Digital Unix, and others.
There are also versions of GNAT for WinNT, Win95, MacOS, and a version for DOS
called “EZ2Load,” which can be found in the
/compiler/ez2load directory.
Now I’m going to go on to the actual tutorial part of this article. Of
course, this isn’t a complete tutorial, it’s just a brief introduction that
shows you the basic structure of an Ada program and provides a couple of
Ada programs that are ready to be compiled.
First of all, I’d like the reader to know what Ada’s actually like. Like
its ancestor Pascal and its cousin C, Ada is a structured language. In
other words, a program is organized into different sections, whereas in
unstructured languages like BASIC, you can basically put anything anywhere.
Also, Ada has its own terminology, and I will be using a few words with
whose meanings you may be unfamiliar:
All Ada programs share a basic structure:
<b>with</b> Package_Name; <b>use</b> Package_Name;
<b>procedure</b> Program_Name <b>is</b>
Variable : Some_Type;
<b>begin</b>
Statement_1;
Statement_2;
<b>end</b> Program_Name;
The procedure is basically the program’s name.
The place where it says Variable : Some_Type is a variable
declaration. “So what does ‘Some_Type’ mean?” you ask. Well, that defines the
type of variable it is. In other words, if the variable were an integer
value, it would be changed to Variable : Integer;. If it
were a floating-point (decimal) value, it would be
Variable : Float;.
Semicolons are used to end a variable declaration or statement, allowing
you to put more than one variable declaration or statement on one line.
The statement begin begins the execution of the actual
statements of the program.
The Statement_1; and Statement_2;
lines don’t actually mean anything in Ada; in a real program they would be
replaced with commands that do something.
The statement end Program_Name; basically ends the
program. Now, this little “demo” was just meant to demonstrate the
structure of an Ada program, but now I’ll give you one that actually works.
This is the simple “Hello World” program that’s often taught to people who
are new to programming:
<b>with</b> Ada.Text_IO; <b>use</b> Ada.Text_IO;<br /><br /> <b>procedure</b> Hello_World <b>is</b><br /><br /> -- no variables needed here<br /><br /> <b>begin</b><br /><br /> Put ("Hello world!");<br /><br /> <b>end</b> Hello_World;
The package “Text_IO” contains all of the functions for input/output
operations in Ada; it’s used for programs involving the display and
gathering of text. I should probably comment on why it says “Ada.”
before “Text_IO.” Because Ada can interface with so many different
languages — i.e. you can link C or COBOL code and Ada code –
and there may be libraries with thousands of packages to choose from,
it’s necessary to specify which library you are using.
The procedure name is “Hello_World.” The statements “with” and “use” evoke
the Text_IO package into the program so that its functions can be used. If
you plan on running this program, you may want to give it the name
hello_world.ada when you save it. Note: You should use the name
hello_world.adb if you’re using the GNAT compiler.
Since this program does nothing more than print a couple of words out on
the screen, there aren’t any variable declarations required, so the section
where variables are normally declared is left blank. Note the double
hyphens (–) before the text “No variables needed here .” Those
hyphens indicate something called a comment. A comment is a string
of text in a program that is ignored by the compiler. However, if you
intend to add the “No variables needed here ” string to the program and
run the program with that string in it, you must include the
double hyphens, or else the compiler will construe that as an attempt by you to use
“No variables needed here ” as a variable declaration, and you’ll get
an error message when you try to compile the program.
The statement Put ("Hello world!"); is the command
for actually printing the text on the screen.
Even though the use of parentheses seems to make things harder, it is
required. You can’t just write “Put “Hello world!”;”
Notice also that many of the names begin with capital letters
(“Text_IO” for example). This isn’t required, it’s just for
“touching-up.” While it isn’t required, however, it is suggested,
because just like a wood carver or a music composer, a computer
programmer wants his/her work to look presentable.
The next program is a little more complicated. It asks the user for his/her
first name, and then prints it out on the screen along with some other text:
<b>with</b> Ada.Text_IO; <b>use</b> Ada.Text_IO;<br /><br /> <b>procedure</b> Get_Name <b>is</b><br /><br /> Name : String (1..80);<br /> Length : Integer;<br /><br /> <b>begin</b><br /><br /> Put ("Enter your first name> ");<br /> Get_Line (Name, Length);<br /> New_Line;<br /> Put ("Hello ");<br /> Put (Name (1..Length));<br /> Put (", we hope that you enjoy learning Ada!");<br /><br /> <b>end</b> Get_Name;
Here’s how it works. We already know what Text_IO is,
and the statement procedure Get_Name is should also
make some sense.
The variable Name is the name entered by the user, and
the type indication String (1..80) signifies that
Name is a string of characters, i.e. a person’s name,
with up to 80 characters in it.
The second variable, Length, is an integer used to remember
the number of characters actually typed by the user of the program.
Now on to the statements. When the program is run, it will print “Enter
your first name> ” on the screen, and it will be ready to accept input from
the user. After the user enters his/her name and presses Enter, the program
will skip a line (New_Line;) and print out “Hello
[user's name], we hope that you enjoy learning Ada!”
-- Source code for an article published at the Ada Home <http://www.adahome.com/><br />--<br />-- Introducing Ada<br />-- by Eric DeArment<br />-- January 1998<br />--<br />-- See <http://www.adahome.com/articles/1998-01/ar_intro.html><br /><br /><br />with Ada.Text_IO; use Ada.Text_IO;<br /><br />procedure Get_Name is<br /><br /> Name : String (1..80);<br /> Length : Integer;<br /><br />begin<br /><br /> Put ("Enter your first name> ");<br /> Get_Line (Name, Length);<br /> New_Line;<br /> Put ("Hello ");<br /> Put (Name (1..Length));<br /> Put (", we hope that you enjoy learning Ada!");<br /><br />end Get_Name;<br /><br /><br />
ABC is an imperative language originally designed as a
replacement for BASIC: interactive, very easy to learn, but
structured, high-level, and easy to use. ABC has been designed
iteratively, and the present version is the 4th iteration. The
previous versions were called B (not to be confused with the
predecessor of C).
It is suitable for general everyday programming, the sort of
programming that you would use BASIC, Pascal, or AWK for. It is not
a systems-programming language. It is an excellent teaching
language, and because it is interactive, excellent for prototyping.
It is much faster than Unix ‘bc’ for doing quick calculations.
ABC programs are typically very compact, around a quarter to a
fifth the size of the equivalent Pascal or C program. However, this
is not at the cost of readability, on the contrary in fact (see the
examples below).
ABC is simple to learn due to the small number of types in the
language (five). If you already know Pascal or something similar
you can learn the whole language in an hour or so. It is easy to
use because the data-types are very high-level.
The five types are:
With a programming language like Pascal, the experience is that most
of the time in class is spent on the details of the language, leaving
too little time to teach about what really matters: the principles of
programming. Quite possibly, a one-term course may not even get round
to introducing pointers. With ABC, the full language can be covered
in a few hours, leaving ample time to treat interesting and
instructive examples of programming in detail.
Unlike BASIC, ABC is a language that offers strong support for
structured programming, even better than Pascal. Refinements, for
top-down stepwise program development, are an integral part of the
language. Because of the powerful data-types of ABC, including tables
(associative arrays), algorithms can be written at a problem-oriented
level of abstraction. There is no GOTO statement in ABC, and
expressions do not have side-effects.
With many other languages, including BASIC and Pascal, it is always
hard to pick interesting examples. Especially early in the course,
when only numeric types and arrays have been introduced, it is very
problematic to handle more challenging problems than say computing the
average of a sequence. The lack of procedures at the early stages may
also cause the students to develop bad programming habits. With ABC,
you can treat interesting examples right from the start. Programming
problems involving texts (strings) are as easy to solve in ABC as
problems with numbers. Programs in ABC are often five to twenty times
as short as their counterparts coded in BASIC or Pascal. There is no
distinction whatsoever in ABC between a program and a procedure.
For basically the same reasons, you can set assignments you would not
even think about if the students had to program in BASIC or Pascal.
Here are some examples of instructive problems that students can solve
after only a few weeks, using ABC:
ABC is fully interactive, doing away with the edit-compile-run cycle.
The language has strong type checking without declarations. The
error messages are to the point and self-explanatory, both for syntax
and for run-time errors, always showing the spot in the source program
where the error occurred. The dedicated editor of ABC, which knows the
ABC syntax and which has a multiple UNDO, greatly reduces both the
opportunities for making syntax errors (no more unbalanced
parentheses) and the time needed for entering a program, thus
demanding less time from the instructor for helping with trivial
problems. ABC programs are automatically displayed pretty-printed,
with indentation showing the logical grouping. The ABC environment is
persistent, meaning that variables (including tables) survive a
session and remain accessible until explicitly deleted.
The (second) best way to appreciate the power of ABC is to see some
examples (the first is to use it). In what follows, >>> is the
prompt from ABC.
There are five types in the language: two basic — Numbers and Texts — and three structured — Compounds, Lists, and Tables.
Numbers are unbounded, and stored exact:
>>> WRITE 2**1000 107150860718626732094842504906000181056140481170553360744375038837 035105112493612249319837881569585812759467291755314682518714528569 231404359845775746985748039345677748242309854210746050623711418779 541821530464749835819412673987675591655439460770629145711964776865 42167660429831652624386837205668069376 >>> PUT 1/(2**1000) IN x >>> WRITE 1 + 1/x 107150860718626732094842504906000181056140481170553360744375038837 035105112493612249319837881569585812759467291755314682518714528569 231404359845775746985748039345677748242309854210746050623711418779 541821530464749835819412673987675591655439460770629145711964776865 42167660429831652624386837205668069377
Non-exact numbers use machine-precision:
>>> WRITE root 2<br /> 1.414213562373095<br />
Texts (strings of characters) are also unbounded:
>>> PUT ("ha " ^^ 3) ^ ("ho " ^^ 3) IN laugh<br /> >>> WRITE laugh<br /> ha ha ha ho ho ho <br /><br /> >>> WRITE #laugh<br /> 18<br /><br /> >>> PUT "Hello! "^^1000 IN greeting<br /> >>> WRITE #greeting<br /> 7000<br /><br /> >>> WRITE greeting|4<br /> Hell<br /><br /> >>> WRITE greeting@4|3<br /> lo!<br /><br />
Lists are sorted lists of values of any one other type:
>>> WRITE {1..10}<br /> {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}<br /> >>> PUT {1..10} IN l<br /> >>> REMOVE 5 FROM l<br /> >>> INSERT 4 IN l<br /> >>> INSERT pi IN l<br /> >>> WRITE l<br /> {1; 2; 3; 3.141592653589793; 4; 4; 6; 7; 8; 9; 10}<br />
You can have lists of any type, so here is a list of lists:
>>> PUT {} IN ll<br /> >>> FOR i IN {1..3}:<br /> INSERT {1..i} IN ll<br /> >>> WRITE ll<br /> {{1}; {1; 2}; {1; 2; 3}}<br /> >>> FOR l IN ll:<br /> WRITE l /<br /> {1}<br /> {1; 2}<br /> {1; 2; 3}<br /> >>> WRITE #ll<br /> 3<br /><br />
Compounds are like records or structures, but without field names:
>>> PUT ("Square root of 2", root 2) IN c<br /> >>> WRITE c<br /> ("Square root of 2", 1.414213562373095)<br /> >>> PUT c IN name, value<br /> >>> WRITE name<br /> Square root of 2<br /> >>> WRITE value<br /> 1.414213562373095<br /><br />
Tables resemble arrays:
>>> PUT {} IN tel<br /> >>> PUT 4054 IN tel["Jennifer"]<br /> >>> PUT 4098 IN tel["Timo"]<br /> >>> PUT 4134 IN tel["Guido"]<br /><br /> >>> WRITE tel["Jennifer"]<br /> 4054<br /><br />
You can write all ABC values out. Tables are kept sorted on the keys:
>>> WRITE tel<br /> {["Guido"]: 4134; ["Jennifer"]: 4054; ["Timo"]: 4098}<br />
The keys function returns a list:
>>> WRITE keys tel<br /> {"Guido"; "Jennifer"; "Timo"}<br /><br /> >>> FOR name IN keys tel:<br /> WRITE name, ":", tel[name] /<br /> Guido: 4134<br /> Jennifer: 4054<br /> Timo: 4098<br />
The (second) best way to appreciate the power of ABC is to see some
examples (the first is to use it). In the examples, >>> is the
prompt from ABC.
Some of these articles are followed by a link to a
source file for the program.
These source files were produced by using the ‘abc -p’ option for packing a
workspace. To unpack it in your own workspaces, save the file as F, choose the
name of your new workspace W, and say:
abc -u -w W F
(you may freely choose the names W and F, but avoid using an
existing workspace name for W).
To use Eliza interactively, just run the command ELIZA.
To watch Eliza talking to someone else, run the command
SESSION grammar
where ‘grammar’ is some grammar to generate English sentences.
There is only one such grammar supplied, paranoid, so you say:
SESSION paranoid
If the grammar is empty, then Eliza tries to psychoanalyse herself:
SESSION {}
To quote from her interacting with herself:
> Do you enjoy this sort of interaction?
What a question!
<br /><br />