History of Computation - High-Level Languages

Mechanical Aids to Computation and the Development of Algorithms

6. Making computing easier: Programming Languages

6.1. Introduction

In the early 1950s even if one had access to a computer facility, actually using this to carry out a specific calculation would often be an extremely frustrating activity. There were two reasons for this: technology; and the problems in describing the task to be performed in a manner that the computer system could act upon. The technological problem arose because the machines were built using several thousand valves. Valves require significant amounts of electrical power, when they are operating they generate heat, when they become too hot they burn-out and have to be replaced (much as an electric bulb does when supplied with too strong a current). Given the size and expense of contemporary systems and the fact that only one calculation series at a time could be run, in order to perform some calculation it was necessary to reserve a time slot in which one had sole access to the facility. It was often the case, however, that having set up the `program' the computer system immediately ceased to function because some of its valves burnt out. This technological drawback was overcome within a few years of the discovery of the transistor. The TRADIC, built in 1954, was the first computer to employ transistors as replacements for valves. Although over-heating still posed (and indeed continue to pose) a problem, transistors were much more reliable. They also led to far faster machines being possible. Almost all of the subsequent development of more reliable `hardware' and faster computer systems came about as a consequence of improved transistor technology and device physics: from the early transistor machines of the mid 1950s, through to machines using LSI components (one which a logical AND gate could be placed) in the 1960s, up to the VLSI devices of the present-day. The last are of such complexity that a computer processor, of far greater power than any of the 1950s machines, can be built on a silicon chip no larger than a fingernail (as opposed to the space of several gymnasia taken by machines like the Whirlwind 1 at M.I.T.).

Improvements in fabricating switching components made large computer systems less prone to hardware failure, but they did not render the task of implementing a series of calculations any less difficult. Recall that a key development in the realisation of automatic calculating machines was the introduction of binary representations as the fundamental items operated upon. John von Neumann, in formulating the structural organisation of stored program computers, had shown how a string of binary digits could be used to encode both instructions and data. Following this approach a machine that operated on, say 16 bit words, the memory locations that held the program would have the instructions interpreted as follows: the first few bits (4 for example) would indicate a particular operation (ADD, STORE, LOAD etc) and the remaining bits (12 in this case) would indicate where the data for the operation was stored in memory. For a such a program to be executable by the computer, however, the binary pattern corresponding to each individual instruction would have to be entered into the memory. A typical application program for a complex scientific calculation might break down into 200 or more such instructions and so to carry out the calculation 3200 0s and 1s would have to be produced and loaded into memory. A single error would render the program useless. Even though entry can be facilitated by paper tape or punched cards, the task of actually generating the correct code offers massive potential for error when it is done manually.

Wilkes' invention of assembly language coding, as described at the end of the last chapter, removed some of the possibility last chapter, removed some of the possibility for transcription error, even this was at such a low level then coding complex applications was a demanding and time-consuming task. It was in this context that the first high-level programming language were developed. The difference between the assembly level and high-level languages were that in the former a single line of the program would typically translate to a single machine instruction, whereas a single statement in a high-level language might require several machine instructions. Of course such programs would have to be transformed (compiled) into a representation that could be executed by a computer. Thus a major problem faced by the developers of the first such languages was the construction of compilers to carry out this task automatically. In the final part of the course we shall, briefly, review the main contributions made within the field of high-level language development.

6.2. Scientific Computing Applications em FORTRAN

A, perhaps surprising, property of the several of the early programming languages has been their durability. The language FORTRAN (an acronym for FORmula TRANslation) is one of the best examples of this phenomenon. Developed in the mid-1950s, FORTRAN was intended for use in scientific and numerical computing applications. As such the analysis of experimental data on computer systems could, in principle, be done by programs designed by the scientists and engineers who had gathered the data. The designers of FORTRAN were among the first to seriously address the principle objection to high-level languages that had been raised: although producing programs that were less error-prone became easier, this fact was counterbalanced by the inefficiency of early compilers. Thus a skilled assembly level programmer could produce code for an application that was more compact and faster than that generated by a compiler. A number of technical decisions were taken in the provision of FORTRAN capabilities that would make it possible to construct FORTRAN compilers which produced machine executable code comparable to that of the best human programmers. The most important of these was that the amount of memory to be used during the running of a program could be exactly determined in advance, using the description of the program alone^1.

1) This feature of the FORTRAN language continued for almost 25 years, through successive revisions of the language.

As a result of this, various optimisations could be made to the code produced to enhance the running of the program.

FORTRAN was promoted by I.B.M. and continues to be extensively used today. The original version of the language has undergone several revisions (on average a new version appears about once every seven years). A key criterion that has to be satisfied by revised versions of the language explains, in part, why FORTRAN has continued to survive as a language today: no revisions to the language are accepted if as a result older FORTRAN programs would cease to compile. AS a consequence of this policy, in principle, FORTRAN programs from 1955 can still be compiled using the latest version of the language. The concept of upward compatibility, as this policy is called, is (commercially) important in ensuring that users of a system can still continue to run old programs when new versions of the language are released.

6.3. Commercial Data Processing em COBOL

We saw, in the opening lecture, that one of the areas in which computer systems have become predominant is that of record maintenance. The field of processing records stored on computer systems, e.g. computing payroll statistics and figures for corporations employing large numbers of people, is known as (commercial) data processing. The Lyons Electronic Office (LEO), mentioned at the end of the last chapter, and the various census collation devices discussed, are both examples of data processing applications. FORTRAN went some way to addressing the requirements of scientific and engineering applications. Although it could have been used as a method of writing typical data processing applications programs it was not really suitable for such tasks. Various primitives desirable for data processing tasks were missing (since they were not needed in numerical applications), and the style of FORTRAN programs (which read as a series of mathematical formulae) was alien to those working in the fields of record maintenance and processing.

COBOL (Common Or Business Oriented Language) was designed at the end of the 1950s by Admiral Grace Hopper in response to a commission from the U.S. Admiralty. Like FORTRAN, it has proved extremely durable and most large-scale data processing systems today are still realised in COBOL. One of the design aims underlying COBOL is that programs written in it should be readable, even to non-computer professionals. So whereas FORTRAN, in describing program instructions, employs standard mathematical symbols and operators, in contrast, COBOL programs attempt to mimic natural language descriptions. In the earliest versions of the language no mathematical symbols were used and arithmetic operators were specified using the equivalent English word. This, amongst other features of the language, made COBOL programs appear to be extremely verbose^2.

2) There is an apocryphal story to the effect that COBOL was designed in this way so that directors and company chairmen could understand and modify the payroll programs run by their corporations and that English was necessary since such people would be incapable of understanding complex mathematical symbols such as +.

Thus the simple statement A = C + D in FORTRAN becomes ADD C TO D GIVING A in COBOL. The belief that by substituting English for mathematical symbols programs would become more understandable and thereby easier to write turned out, however, to be fallacious. The reason for this, which is obvious with hindsight but was not apparent at the time, is that what makes designing a computer program for a specific task difficult to do is the process of specifying, structuring, and ordering the activities to be carried out at a fine enough level of description, i.e. the difficulty in programming is constructing the appropriate algorithmic process. Once this has been done it is usually a relatively easy task to translate the algorithm steps into any programming formalism. Once this fact had been recognised, an important consequence was that more research effort was concentrated on methodologies for designing programs and algorithms rather than on superficial attempts to make such programs `readable' or `comprehensible'. The study of programming methodologies ultimately led to the theoretical disciplines of Programming Language Semantics, Formal Specification, and Formal Verification that were mentioned, briefly in the opening lecture.

As with FORTRAN, COBOL has undergone several revisions since its initial design. In the case of non-academic activity, COBOL has been since the early 1960s probably the most widely used language in commercial applications. This is likely to continue to be the case for the foreseeable future despite the growing use of other languages.

6.4. Artificial Intelligence Applications em LISP

LISP (List Processing) was developed by John McCarthy and a team of research students at M.I.T. in 1960. It subsequently became extremely popular and widely used (in academic environments) as a language for programming Artificial Intelligence systems. While it is still used today for such problems it has been replaced in some specific areas of this field by subsequent developments in programming language theory: most notably by the logic programming language PROLOG. If readability of programs played a significant r&ole in the design of COBOL, and was at least superficially addressed by the designers of FORTRAN, anyone with experience of LISP programming will be aware that no such considerations bothered McCarthy and his team in designing LISP. Underlying LISP is an algebraic formalism for describing effective algorithms developed by the great U.S. logician Alonzo Church (1903-) and called the lambda-calculus. Thus LISP in its most basic form^3 has a precisely defined mathematical semantics and as a consequence. it is, in principle, possible to prove precise properties of such programs. LISP is also of historical interest as

3) All widely used implementations of this language greatly extend the functionality of the language defined by McCarthy, which is now known as `pure' LISP

being one of the first languages to use extensively an algorithm control structure that was (deliberately) not provided in FORTRAN or COBOL: that of recursion. In simple terms this is the action of describing an algorithm in terms of itself, e.g. the mathematical function `n factorial' (denoted n!) defined as the result of multiplying the first n natural numbers can be defined recursively as n! =1 (if n=1) n = n times (n-1)! (if n > 1). This facility is useful in describing approaches to various problems in Artificial Intelligence applications such as automated theorem-proving and game-playing systems. A number of early, apparently successful A.I. systems, were built in the 1960s and 1970s using LISP including Samuel's `checker playing program'; the `conversational' system ELIZA, and an early natural language system SHRDLU built by Winograd in 1972. LISP was also used in robotics and computer vision systems.

6.5. Algorithmic Languages em ALGOL60 and ALGOL68

The three languages we have examined above were all developed in the U.S. and are all still very much in use today. The reasons for this vary: FORTRAN and COBOL were the first languages of their kind available and thus were taken up quickly so that, even when technically superior methods arrived, there was a reluctance to move away from what had become a familiar idiom. A second very important reason for the continuing survival of these two is the fact that they were heavily promoted by U.S. computer companies. In particular, I.B.M. has played a significant part not only in developing new versions of FORTRAN but also in promoting it to run on their systems^4.

4) It should be noted that I.B.M. FORTRAN compilers were until the demise of large-scale `mainframe computers' far ahead of alternative versions in terms of their speed of operation and the efficiency of the machine code generated. The FORTRAN `H' compiler developed by I.B.M. for their 370 series computers is still regarded as one of the best optimising compilers ever designed.

In the same way COBOL has survived largely because of the considerable investment put into building commercial data processing systems that use COBOL. There is little point in promoting or building a `better' language since, in order for it to be adopted, organisations would be faced with the task of reprogramming their complete system.^5 5) This, of course, would be a problem when an old computer system was replaced. One of the primary reasons for I.B.M's dominant position in the computing industry, until very recently, was the fact that when a concern had acquired I.B.M. equipment it was easiest to replace it with a new I.B.M. machine. Moving to a rival company would have entailed extensive rewriting of systems programs. The widespread industrial usage of COBOL and FORTRAN also meant that at least one (often both) of these languages would be covered in undergraduate Computer Science degree programmes. LISP, although largely restricted to academic and research environments, continued to be used partly because of its theoretical interest but largely because of the applications in A.I. that were developed from it. In the latter field there was no serious rival to it as a general-purpose A.I. applications language until the development of PROLOG.

ALGOL60 and its successor ALGOL68 are now (effectively) extinct languages. Nevertheless ALGOL60 was a landmark in the development of programming language theory. Its disappearance can be entirely attributed to the failure of industrial concerns to adopt it, despite the fact that it was extensively taught at European and U.S. universities in the 1960s. Its chief importance now is in the innovations that continue to influence the design of programming languages. The effects of these are apparent in languages such as Niklaus Wirth's PASCAL (which now occupies the position formerly held by ALGOL60 as the language used in degree programmes); the subsequent revisions of FORTRAN; and the U.S. Department of Defense language ADA.

ALGOL60 was designed by an international committee working between 1958 and 1963. It was intended to be a general-purpose language but with a particular emphasis on scientific and numerical applications. In this respect it improved upon FORTRAN in two ways: firstly, ALGOL60 provided facilities to represent and manipulate complex structures inside a program; and, secondly, like LISP, it provided recursion as a control mechanism. Until the advent of PASCAL, the notational style of ALGOL60 was accepted as a standard way of describing complex algorithms and a number of textbooks on the subject of algorithm design employed an ALGOL derived notation for illustrating programs. An important theoretical innovation was the manner in which valid statements in an ALGOL program were described: a system called Backus-Naur Form (or BNF) after two of the committee who worked on the design. In simple terms this described how syntactically correct statements could be recognised by prescribing `grammatical rules'. This formalism was subsequently adopted in describing new programming languages as well as revisions to existing ones.

ALGOL68, the successor to ALGOL60, was also designed by an international committee and was intended to remove some of the weaknesses that had been identified with the original ALGOL60 language and to extend its functionality. The final language posed considerable problems: although it was no more difficult to construct programs in it, the design and implementation of compilers to translate such programs into a machine understandable form was a major task. The first two implementations of such compilers were both carried out in the U.K: one at the R.S.R.E (Royal Signals and Radar Establishment); and the second at the University of Liverpool. ALGOL68 continued to be taught at Liverpool up until 1987. The investment of effort required to construct compilers was one of the factors in ALGOL68's failure to become established, despite its considerable merits as a language.

6.6. Conclusion

From 1954 onwards the significant difficulty facing users of computer systems was not the unreliability of the electrical devices but the task of actually describing what operations were to be performed in a manner that could be executed by the machine. While assembly and low-level languages went some way to addressing this, such methods were mainly in the provenance of computer specialists rather than the individuals who wished to use computers to solve applications problems. As a result a number of `high-level' programming languages began to appear from 1956 onwards. Some, like FORTRAN, were specifically tailored to applications in science and engineering; others, such as COBOL, were intended for the needs of data processing and record maintenance systems. The effect of such languages was to make computers accessible to individuals who did not have a detailed technical knowledge of the actual computer operation.

Previous Section

PED Home Page