Fundamental Concepts in Programming Languages
📜 Abstract
This paper forms the substance of a course of lectures given at the International Summer School in Computer Programming at Copenhagen in August, 1967. The lectures were originally given from notes and the paper was written after the course was finished. In spite of this, and only partly because of the shortage of time, the paper still retains many of the shortcomings of a lecture course. The chief of these are an uncertainty of aim—it is never quite clear what sort of audience there will be for such lectures—and an associated switching from formal to informal modes of presentation which may well be less acceptable in print than it is natural in the lecture room. For these (and other) faults, I apologise to the reader. There are numerous references throughout the course to CPL [1–3]. This is a programming language which has been under development since 1962 at Cambridge and London and Oxford. It has served as a vehicle for research into both programming languages and the design of compilers. Partial implementations exist at Cambridge and London. The language is still evolving so that there is no definitive manual available yet. We hope to reach another resting point in its evolution quite soon and to produce a compiler and reference manuals for this version. The compiler will probably be written in such a way that it is relatively easy to transfer it to another machine, and in the first instance we hope to establish it on three or four machines more or less at the same time. The lack of a precise formulation for CPL should not cause much difficulty in this course, as we are primarily concerned with the ideas and concepts involved rather than with their precise representation in a programming language.
✨ Summary
Overview
Strachey presents programming-language design as a search for fundamental semantic concepts rather than primarily a problem of notation or grammar. He argues that insight should precede complete axiomatisation and develops a conceptual model linking program expressions, an idealized store, and abstract values.
The paper’s central distinction is between L-values, which denote mutable locations, and R-values, which denote the contents or values associated with those locations. Assignment is modeled as an operation that transforms an abstract store. This provides a way to reason about variables, sharing, compound structures, side effects, and non-addressable locations while preserving a form of referential transparency at the level of locations.
For expressions, Strachey develops an applicative view based on operators, operands, lambda expressions, environments, bound variables, and free variables. He explains evaluation order as a partial ordering rather than necessarily a fixed sequence, and shows how conditional expressions require delayed evaluation. Commands are treated as functions over stores, allowing sequencing, conditionals, and loops to be described through function composition and recursion.
The paper also analyzes functional abstraction, parameter-passing modes, the treatment of free variables, private or persistent variables, and the distinction between functions and routines. It advocates treating functions as first-class data and defines a function value with an associated environment as a closure. Recursive functions are represented through cyclic closure structures. The discussion of types distinguishes manifest from latent properties and introduces the now-standard distinction between ad hoc polymorphism and parametric polymorphism, illustrated by a general mapping function over lists.
Further topics include programmer-defined compound data structures, dynamically typed elements, pointers, arrays, sharing, fixed versus free objects, and load-update pairs as a uniform representation for general locations. The paper closes by comparing macro expansion with functional abstraction and proposing a store-based approach to formal semantics.
Influence
The paper was originally written in 1967, circulated privately for decades, and formally published in 2000. Peter Mosses describes it as widely circulated and highly influential, noting that its ideas were subsequently used by numerous authors in textbooks and research papers. (cs.tufts.edu) Its terminology and explanations helped establish concepts such as L-values and R-values, referential transparency, closures, and the distinction between ad hoc and parametric polymorphism as standard subjects in programming-language theory. (fpl.cs.depaul.edu)
The paper’s store-and-environment perspective also contributed to the conceptual lineage of denotational semantics. Later expositions explicitly present programming-language semantics using environments, stores, functions, and mathematical meanings in the Scott–Strachey tradition; modern research continues to cite Strachey’s paper when discussing closures, semantic auxiliary operations, and polymorphism. (mendeley.com)