Abstracto 84(ID:5547/abs005)Target evolution language for Abstracto, a language for describing languages Places People: Related languages
References: Extract: basics of Abstracto THE ABSTRACTO PROJECT Since December 1977 IFIP Working Group 2.1 has been working on the investigation of "the properties, feasibility and usefulness of a language helping the specification and construction of good algorithms". If this description seems vague (it is so on purpose), it nevertheless describes "something" that is almost tangible by its conspicuous absence from the programmer's tool kit. A programmer who is writing a program is in fact encoding an algorithm in a language for some machine. This need not be a piece of hardware; it can be "the" abstract machine for FORTRAN or some other high-level language. The development of an algorithm down to the machine level takes many steps, some of which require ingenuity, but the larger part of which consists of clerical manipulations and book-keeping. This is partly due to the (not always unjustified) wish of writing an efficient program, and partly to the fact that even the highest-level languages require the specification of details that are relevant to the machinery, but not to the algorithm proper. It would be good practice if the programmer would first write down the algorithm before starting to code it as a program. But now, in what way? Some "algorithmic" language is needed. The available languages, however, are programming languages. (Hill shows convincingly how unsuited natural language is for this purpose.) So we are back were we started: to write an algorithm in a programming language is to write a program. In a nutshell, the aim of the Abstracto project is to fill the gap by designing a language specifically for the purpose of describing algorithms. The language should be a suitable vehicle for applying established programming techniques, and thereby also for teaching such techniques, without danger of having to explain ideosyncracies. The Abstracto project is still in its early phase. There is not even an approximation of consensus about the basics of Abstracto. In this paper some ideas are presented; it should be stressed that these represent solely my position and may not be taken for opinions of WG 2.1. Although some logical formalism is used in this paper, the reader should be warned that this is only done for the purpose of conveying a meaning; nothing is alleged to be "proved" here. Extract: Abstracto as a pidgin 2. Abstracto as a pidgin When people who do not speak a common language establish a regular contact and want to communicate, an interesting phenomenon happens: they develop a "pidgin" language, clumsy but effective. A similar phenomenon has happened in Computer Science literature: a kind of pidgin ALGOL has developed there, from the need of authors to address a broad audience without having to explain over and over the meaning of all notations employed. This pidgin ALGOL is a language, although it is not frozen, let alone formalized. In fact, it has some of the characteristics from natural languages. A major similarity is the property that this language is gradually evolving, to meet the needs in communicating algorithms. One may (and I do) take the position, thus mitigating the grimness of the situation sketched in the previous section, that pidgin ALGOL covers to some extent the need for an algorithmic language. Moreover, the "natural" course of evolution will be to tune the language to the requirements of developing programming methodology. However, we are still far away from what could be achieved even today. As long as we are faced with the situation that the language has to be mastered by picking it up from casual contacts, it will of necessity drag along trails that have been beaten years before. Viewed in this perspective, the Abstracto effort is aimed at speeding up evolution by proposing and using suitable notations for important algorithmic concepts. Of course, it will be possible (and maybe desirable) to take a snapshot of Abstracto at regular intervals, to clean up the picture and to present it as, say, Abstracto 84. But this will not stop Abstracto from evolving on. The obvious advantage of freezing an Abstracto X is the possibility of referring to a "standard" when publishing an algorithm. Moreover, when a language is formalized, it also becomes possible to formalize proof rules and to prove their consistency and completeness. These are not, however, the main reasons why I feel the effort of freezing a version of Abstracto at some future time may prove worth the trouble. It seems much more important to me that this forces one to clarify issues that still appear murky, thereby deepening the understanding of what is going on. Also, it may show us how to design better programming languages. Extract: Abstracto and Transformational Programming Abstracto and Transformational Programming Unlike many fads in Computer Science, the relatively recent technique of "transformational programming" appears to be quite promising. One should of course not make the mistake to expect that it opens up a royal road to program construction; no technique ever will. But the basic idea is quite simple and sound, its value has been demonstrated on diverse, sometimes even not trivial, examples, and it provides a framework for expressing an expanding body of knowledge about programming and for developing new programming techniques (or applying "old" programming techniques known under the collective title of Structured Programming). In essence, the method of transformational programming consists of (a) writing an algorithm, as pure and simple as possible, to meet a given specification as to correctness, and (b) next successively transforming the algorithm, by relatively simple correctness-preserving transformations, to meet other requirements, such as those stemming from efficiency considerations. Transformations may be global, replacing the whole program under development by a new text, but the typical transformation is local, effecting only a small part. Ideally, the algorithm at the top should be identical with the correctness specification, but we do not know in general how to go down from that level by something in the spirit of a transformation. Well-known transformations are stepwise refinement and recursion removal. It may well happen, however, that at some stage of development recursion introduction (Bird[2]) is in order to prepare for a more advantageous step. The nature of transformational programming is quite aptly described by Bird: "The manipulations [...] mirror very closely the style of derivation of mathematical formulas". He also remarks: "As the length of the derivations testify, we still lack a convenient shorthand with which to describe programs". It is here that Abstracto should step in, It is important to realize that the objects one manipulates upon are not the algorithms themselves, but are expressions: algorithmic expressions. In fact, for most steps it is impossible to maintain that there occurs a change in the algorithm (unless one refuses to admit the existence of "the" Euclidean algorithm, or "the" sieve of Eratosthenes). For these algorithmic expressions, we need notations. None of the existing programming languages has been designed with a design objective as ease of manipulation. On the contrary; if one would not know better, one would in many cases be tempted to believe they were designed on purpose to be transformation resistent: the semantic peculiarities often make it devilishly hard to verify that a particular step is applicable. Moreover, the verbosity of existing notations makes it aggravating to write down the derivations and makes it hard to keep track of what is happening. It is to be expected that the introduction of better notations will prove as important for the development of "algorithmics" as it has been for mathematics. in [ACM] Proceedings of the 1979 ACM annual conference view details |