The nineteen seventies were dense enough to require two articles. This first article covers the pragmatic side of the decade, namely the consolidation of structured programming as a discipline, the maturation of the denotational semantics program that Scott and Strachey had begun in the previous decade, the development of production programming languages that established the reference points against which every subsequent language design would be measured, and John Backus’s public argument that the industrial mainstream was on the wrong path. The companion article, A210, covers the theoretical side of the same decade, namely Hindley-Milner type inference, Robin Milner’s Logic for Computable Functions and the first ML, Per Martin-Löf’s type theory, Dorothy Denning’s information-flow lattice, and the founding of the ACM Symposium on Principles of Programming Languages in nineteen seventy-three.

The division between the pragmatic and the theoretical is editorial. The two sides interacted continuously. Robin Milner’s LCF was a pragmatic tool built on Dana Scott’s theoretical work. Niklaus Wirth’s Pascal drew on the same ALGOL sixty tradition that generated denotational semantics. The reader should treat the two articles as a single treatment in two parts.

Structured Programming as a Settled Position

Ole-Johan Dahl, Edsger Dijkstra, and C. A. R. Hoare published the book Structured Programming through Academic Press in nineteen seventy-two. The book consolidated the arguments that had accumulated across the previous decade into a single treatment. Dijkstra’s contribution, Notes on Structured Programming, laid out a programming discipline whose central practice was the stepwise refinement of a problem statement into an implementation. Hoare’s contribution, Notes on Data Structuring, extended the same discipline to the design of data representations. Dahl’s contribution, Hierarchical Program Structures, tied the discipline to the class-based structure that Simula sixty-seven had introduced.

Niklaus Wirth had already published, in April nineteen seventy-one in Communications of the ACM, the paper Program Development by Stepwise Refinement, which presented a worked example of the discipline applied to an eight-queens problem. Wirth’s paper made the practice concrete by walking through the successive refinements of an informal specification into a program that could be executed. The paper became the standard classroom introduction to structured programming for the following two decades.

The combined effect of the nineteen seventy-two book and Wirth’s nineteen seventy-one paper was to move structured programming from a position that required argument to a position that required justification only in its absence. By the middle of the decade the goto statement had become a construct whose use called for explicit defense rather than occasional caution. The transition was substantially complete by the end of the decade in new language design, though existing production languages that included the goto statement continued to carry it for backward compatibility.

Denotational Semantics Matures

Dana Scott and Christopher Strachey’s nineteen seventy-one Oxford technical monograph, Toward a Mathematical Semantics for Computer Languages, launched what became known as denotational semantics in the following years. The monograph proposed that the meaning of a program should be a mathematical object in a specific domain, namely a partial order of computational elements whose limits correspond to the results of nonterminating or partially defined computations. Scott’s domain theory supplied the mathematical infrastructure.

The nineteen seventies saw the denotational program expand in three directions.

The first direction was the treatment of specific language features. Denotational descriptions of assignment, of higher-order functions, of control operators such as continuations, and of nondeterminism were developed by Scott, Strachey, Peter Mosses, and others at Oxford’s Programming Research Group. Continuations in the sense that later work would use the term were introduced by Christopher Strachey and Christopher Wadsworth in a nineteen seventy-four Oxford PRG memo titled Continuations, a Mathematical Semantics for Handling Full Jumps. The memo gave a mathematical account of nonlocal control transfer that would later underwrite first-class continuations in Scheme and delimited continuations in modern functional languages.

The second direction was the elaboration of domain theory itself. Scott’s nineteen seventy-six paper Data Types as Lattices in the SIAM Journal on Computing consolidated the mathematical treatment of the domain construction into a form that other researchers could apply directly. The paper introduced what became known as D-infinity, the reflexive domain that satisfies the equation D ≅ D → D, namely that a domain is isomorphic to its own function space, which underwrites the treatment of the untyped lambda calculus as a denotational object.

The third direction was the exposition of the denotational program in a form that could be taught to graduate students. Joseph Stoy’s nineteen seventy-seven book Denotational Semantics, subtitled The Scott-Strachey Approach to Programming Language Theory, published by the MIT Press, gave the discipline its first textbook. Stoy had been a research fellow at the Oxford PRG. His book made the Scott-Strachey approach accessible to readers who did not have direct access to the Oxford technical monograph series.

Dijkstra’s Discipline of Programming

Edsger Dijkstra had continued the research program that his nineteen sixty-eight Go To letter had opened. His nineteen seventy-five paper Guarded Commands, Nondeterminacy and Formal Derivation of Programs, published in Communications of the ACM volume eighteen, issue eight, introduced two related contributions.

The first was a small programming language called the guarded command language, whose central control construct was a nondeterministic choice among guarded alternatives. An alternative consisted of a boolean guard and a statement. The construct executed by choosing any alternative whose guard evaluated to true and executing its statement. A construct in which no guard was true either aborted or did nothing, depending on which of the two guarded constructs, if or do, was in use. The guarded command language was not intended as a production programming language. It was a notation for reasoning about programs whose control flow had been abstracted to its essential structure.

The second contribution was the weakest precondition semantics. For each statement S in the guarded command language and each postcondition Q, the weakest precondition, written wp(S, Q), was the weakest predicate such that if it held before S executed then Q would hold after S terminated. The weakest precondition was defined compositionally by rules that recursed on the structure of the statement. The rule for assignment reads wp(x := E, Q) = Q[E/x], which mirrors the Hoare assignment axiom of the previous decade. The rules together provided a mechanical procedure for computing what a program required of its input to guarantee that its output would satisfy a given specification.

Dijkstra’s nineteen seventy-six book, A Discipline of Programming, published by Prentice-Hall, developed the weakest precondition approach into a systematic method for constructing programs that were correct by construction. The method took a specification, represented as a precondition and postcondition pair, and derived the program that satisfied it by mechanical application of the weakest precondition rules in reverse. The book worked through a substantial catalog of programming problems using this method.

The Dijkstra approach and the Hoare axiomatic method of the previous decade are closely related. The Hoare method takes a program and a specification and proves that the program satisfies the specification. The Dijkstra method takes a specification and derives a program from it. The two directions correspond to verification and program derivation respectively. Both directions depend on the same weakest precondition apparatus. Modern program verifiers carry both directions as selectable modes.

Pascal

Niklaus Wirth began work on Pascal at the Eidgenössische Technische Hochschule Zürich in nineteen sixty-eight. The language grew out of ALGOL-W, an ALGOL sixty successor that Wirth had proposed in the ALGOL sixty-eight design process and that had been developed as a working language at Stanford while Wirth was there. When Wirth returned to Zurich in nineteen sixty-eight, he began a new language design that would carry the ALGOL-W direction without the ALGOL sixty-eight complexity.

The first Pascal compiler became operational in early nineteen seventy. The initial attempt was written in FORTRAN and failed because the Pascal type system’s data-structure requirements could not be expressed cleanly in FORTRAN. The second attempt, by Urs Ammann, Edgar Marmier, and Rudolf Schild, was written in Pascal itself using a bootstrap compiler and succeeded. The compiler was a single-pass recursive-descent compiler whose performance was comparable to contemporary FORTRAN compilers on the same hardware. The technical report The Programming Language Pascal appeared in November nineteen seventy as Technical Report Number One of the Zurich computer science department. By nineteen seventy-two Pascal was in use in introductory programming courses.

Kathleen Jensen and Niklaus Wirth published the Pascal User Manual and Report through Springer in nineteen seventy-four. The book consolidated the language definition and gave the language its reference document for the following two decades. The Pascal-P portable compiler, developed at Zurich, generated p-code, a bytecode for a stack-based virtual machine, that could be interpreted on any target platform that ran the interpreter. The p-code approach made Pascal implementations straightforward to port and became the technique by which Pascal spread across academic and industrial installations.

Pascal was designed to be a small language that could be taught in a semester and understood in its entirety. It included records, enumerations, subranges, sets, and pointers, which together gave the programmer enough data-structuring apparatus to write non-trivial programs without appealing to external libraries. It excluded features whose semantics were considered problematic, including separate compilation and unrestricted pointer arithmetic.

The exclusions were the origin of Pascal’s principal criticism as an industrial language. Brian Kernighan published a nineteen eighty-one paper titled Why Pascal Is Not My Favorite Programming Language, which catalogued the practical difficulties that the exclusions imposed on substantial software development. The criticism was substantive. Pascal had been designed for teaching rather than for industrial use, and its use as an industrial language required extensions whose incompatibility across implementations undid much of the portability that the p-code approach had provided. The Modula and Modula-2 languages, covered below, were Wirth’s response to the industrial-use case.

C

Dennis Ritchie developed what became C at Bell Laboratories between nineteen seventy-two and nineteen seventy-three. C grew out of Ken Thompson’s B language of nineteen sixty-nine, which in turn had grown out of Martin Richards’s BCPL of nineteen sixty-seven. The transition from B to C happened as Bell Labs migrated its UNIX operating system from the PDP-7 to the PDP-11 minicomputer. The shortcomings of B became apparent on the newer hardware, and Ritchie extended the language over the following year to give it data types and the structural apparatus that B had lacked.

Ken Thompson rewrote the UNIX kernel in C in nineteen seventy-two. The rewrite was substantial evidence for the position that a systems programming language could be substantially higher-level than assembly without paying an unacceptable cost. The rewrite also established that an operating system that one wanted to port to a new hardware architecture could be ported by writing a C compiler for the new architecture rather than by rewriting the operating system. Every subsequent UNIX-family operating system that has been ported to a new architecture has relied on this technique.

Brian Kernighan and Dennis Ritchie published The C Programming Language through Prentice Hall in February nineteen seventy-eight. The book became known as K&R after the initials of the authors. It served as the reference document for the language until the American National Standards Institute published the C 89 standard in nineteen eighty-nine. The pre-standard version of the language that K&R described is sometimes called K&R C to distinguish it from the subsequent standardized versions.

C’s design made different trade-offs than Pascal’s. It included separate compilation through header files, pointer arithmetic, and a preprocessor that supported conditional compilation and macro definition. It excluded the array-bounds checking and subrange types that Pascal included. The trade-offs made C directly usable for systems programming and for the writing of compilers, operating systems, and device drivers. The trade-offs also made C substantially more error-prone than Pascal in application programming, which became the substance of the systems-versus-application-language debate that subsequent decades would carry forward.

Prolog

Alain Colmerauer and his team at the Université d’Aix-Marseille implemented the first version of Prolog in the summer of nineteen seventy-two. The name Prolog was coined by Philippe Roussel as an abbreviation of Programmation en Logique. The language was the first practical logic programming language.

The discovery that a specific fragment of first-order logic, namely Horn clauses of the form H :- B1, B2, ..., Bn, where H is a head atom and each Bi is a body atom that must hold for H to hold, could be executed by a resolution theorem prover in a way that constitutes a computational procedure was the result of a collaboration between Colmerauer at Marseille and Robert Kowalski at Edinburgh. Kowalski’s nineteen seventy-four paper Predicate Logic as Programming Language, delivered at the International Federation for Information Processing Congress in Stockholm, formalized the theoretical basis. Colmerauer’s Marseille group had built the practical implementation in the interim.

Prolog executes a Horn clause program by attempting to prove a goal using SLD resolution, a specific strategy that processes clauses in source order and resolves subgoals depth-first from left to right. The strategy is not complete in the theorem-proving sense, because depth-first search can enter an infinite computation where a breadth-first search would succeed. The trade-off is efficiency. A Prolog implementation runs comparably to an imperative language implementation of the same problem when the problem matches the depth-first search pattern. Extending Prolog to handle programs that require a different search strategy became the substance of later work on constraint logic programming and other logic programming paradigms.

Prolog introduced the discipline of declarative programming as a working style, distinct from the imperative style of C and Pascal and from the functional style that Backus’s Turing Award lecture would argue for. The three styles have coexisted in the discipline since, with individual production languages selecting among them according to their intended use.

Concurrent Pascal and Modula

Per Brinch Hansen developed Concurrent Pascal at the California Institute of Technology in nineteen seventy-four and nineteen seventy-five. The language extended Pascal with the monitor construct, which Brinch Hansen had introduced in a nineteen seventy-two paper and which C. A. R. Hoare had independently formalized in a nineteen seventy-four paper titled Monitors, An Operating System Structuring Concept. A monitor is a module that encapsulates shared data together with the operations that access it, and that enforces mutual exclusion by allowing at most one operation to execute at any given time.

Concurrent Pascal was implemented on the PDP-11/45 by January nineteen seventy-five. The implementation demonstrated that a language whose concurrency primitives were tied to the monitor construct could be implemented efficiently on a single-processor system and that the resulting programs were substantially easier to reason about than programs that used lower-level synchronization primitives. The Solo operating system, written in Concurrent Pascal at Caltech, was the first published operating system written in a high-level concurrent programming language.

Niklaus Wirth developed Modula at Zurich across nineteen seventy-five through nineteen seventy-seven, publishing Modula, A Language for Modular Multiprogramming in Software: Practice and Experience in nineteen seventy-seven, as a response to the industrial-use criticism of Pascal. Modula added separate compilation through modules, which grouped related declarations and provided an interface that other modules could import. The module facility resolved Pascal’s principal industrial deficiency. The subsequent Modula-2, published by Wirth in nineteen eighty, consolidated the module design into what became the primary Wirth language of the nineteen eighties.

Backus and the Critique of the von Neumann Style

John Backus received the nineteen seventy-seven ACM Turing Award at the ACM Annual Conference in Seattle on October seventeenth nineteen seventy-seven. His Turing Award lecture, titled Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, was published in Communications of the ACM in August nineteen seventy-eight. The lecture was the most influential critique of the industrial mainstream delivered in the decade.

Backus’s argument had two parts. The first part diagnosed what Backus called the von Neumann style of programming as the source of the difficulty of reasoning about industrial programs. The style was characterized by the assignment statement, which Backus called the von Neumann bottleneck, because every state change in a program had to pass through a single-slot pipeline of sequential assignments. The style also required the programmer to think in word-at-a-time terms rather than in whole-computation terms. The style, Backus argued, did not scale to the size of programs that industrial software was increasingly asked to be.

The second part of the argument proposed an alternative, namely a functional programming style in which programs were composed by combining smaller programs using a small set of combining forms. Backus’s specific proposal was a language called FP, whose programs were compositions of primitive functions by functional forms such as composition, condition, insert, and apply-to-all. FP was not intended as a production language but as a demonstration that a functional style could be made formal in a way that supported algebraic reasoning about whole programs. The lecture’s title called this the algebra of programs.

The lecture was influential substantially beyond its specific technical proposal. Its central diagnosis, that the assignment statement was the source of the industrial mainstream’s difficulty, became the founding argument for the functional programming research program of the following two decades. Standard ML, Miranda, Haskell, and every subsequent statically typed functional language descend from the position that Backus’s lecture articulated. The Turing Award recipient who had defined the FORTRAN era argued that the FORTRAN era was the wrong era. The subsequent decades would develop the alternative.

What This Era Enables

The pragmatic side of the nineteen seventies supplied five things that the following decades consumed.

First, structured programming as a settled discipline that new language designs took as a starting point rather than as a position requiring defense.

Second, denotational semantics as a mature mathematical framework for specifying the meaning of programming languages in a form that other researchers could apply.

Third, Pascal and C as reference points for subsequent language design. Every subsequent statically typed procedural language either extends one of these or is defined in opposition to one of these.

Fourth, Prolog as the first practical demonstration that declarative programming was a viable working style alongside the imperative and functional styles.

Fifth, the Backus critique as the founding argument for the functional programming research program.

The next article, A210, covers the theoretical developments of the same decade that the pragmatic side depended on.

Conclusion

The pragmatic side of the nineteen seventies took the questions that the nineteen sixties had made sharp and turned them into working tools. Structured programming became a discipline. Denotational semantics became a research program. Pascal and C became the reference points against which every subsequent procedural language would be measured. Prolog demonstrated that declarative programming was practical. Backus’s lecture articulated what the following decades would develop.

The next article, A210, covers the theoretical side of the same decade.

References