History of John Backus's functional programming project (draft)

Paul McJones paul@mcjones.org https://mcjones.org/dustydecks

John Backus explored a sequence of applicative, functional and function-level languages starting before 1969 and continuing until he retired in 1991. The goal of this project is to preserve the surviving materials from this research and to put them into context. Comments, suggestions, and donations of additional materials are greatly appreciated.

In the late 1960s the "software crisis" became a frequent topic of discussion. Computers had become much more capable in speed and memory sizes and prices had come down, but as ambitions grew, a number of programming projects suffered from cost and shedule overruns and poor reliability. A pair of NATO-sponsored conferences on Software Engineering in 1968 and 1969 brought attention to the problems and served as an initial forum for discussing solutions, which included formal methods, design methodologies, and management techniques.

Although John Backus attended neither of these conferences, they resonated with his long-held desire to simplify the task of programming. He'd had early success with his Speedcoding and FORTRAN projects. FORTRAN in particular revolutionized the task of writing numerically-oriented programs, in many cases allowing scientists and engineers to write programs rivalling or exceeding the performance of programs written by professional programmers—members of the "priesthood," as Backus sometimes referred to them. After FORTRAN, he participated in the Algol project, and in 1963 was named an IBM Fellow in 1963, giving him the flexibility to choose any problem to work on. He then spent a number of years working on four color conjecture (now theorem). But somewhere around 1967–1969, Backus decided to take another try at the programming problem:

For several years, Backus worked mostly alone on this new idea. Ted Codd consulted with him briefly, but that didn't last [Booch2007]. In late 1969, Dines Bjørner began working with him, first explaining the details of lambda-calculus and Curry's Combinatory Logic, then writing an interpreter (in PL/I) based on “finite state tree-transformer” semantic for Backus's language (which was then called RedSys) [ Bjørner2025 , 1972 ]. Bjørner worked with Backus until 1972, when they parted ways; Bjørner went on to work with Ted Codd [ Bjørner2025 ], [ BjørnerEtAl1973 ].

Backus's first publication was a 1972 research report titled "Reduction languages and variable-free programming"; the report acknowledges Bjørner "for writing a program to reduce Red items which was used to test some of the operators in this paper."[ Backus1972a ] This report introduced a family of expression-oriented languages with semantics given by simple rewrite rules. The featured language, called Red for reduction, was similiar in size to Pure Lisp [McCarthy1960], but rather than defining a function by describing its effect on the formal parameters, the programmer built up a function from a set of base functions using a function composition operator as well as a set of combining forms (here known as 'modifiers'). Each function took one (implicit) argument, which could be a sequence. This led to a programming style somewhat reminiscent of APL's "one-liners", and Backus later cited APL as an inspiration. During 1972, Phil Summers (then probably a graduate student intern from Yale, later an IBM researcher) did an experimental implementation of Red in Lisp [ Summers1972 ].

This first report was fairly mild in its claims about Red, which he positioned more as a formal system than a practical programming language. In 1973 he followed up with a paper,presented at the first ACM Principles of Programming Languages conference [Backus1973a, c]. It refined the hierarchy of languages, presented a tidied-up version of Red as the centerpiece and concluded: "Hopefully, this work will lead to a semantic theory for a new class of programming languages, one which possesses an axiomatic foundation of the simplicity required for rigorous mathematical treatment."

During 1973, Backus went on the lecture circuit, giving 14 lectures at universities and research labs across the country [ Backus1973d ]. His annual report as an IBM Fellow described that year's work on language frameworks and the Red language, and then made two claims [ Backus1974a ]:

He concluded, "If there is any truth to the two assertions above, then Research should ask itself whether it has fallen into a comfortable but mistaken orthodoxy with respect to programming languages. I believe it should re-evaluate its emphasis and goals in computer science and programming; at least IBM computer scientists should be aware that reducing the cost of programming would do more to help IBM's growth than perhaps any other technical, accomplishment." In support of these claims, he introduced the phrase "von Neumann bottleneck"—the word-at-a-time nature of conventional computers—and argued that this carried over to the design of conventional programming languages, leading to their inefficiency and complexity.

It fell to Patricia Goldberg, Manager of the Automatic Programming group at IBM's Watson Research Center, to respond to Backus [ Goldberg1974 ]. She agreed with the criticality of reducing the cost of programming, the need to go beyond languages of the "PL/I genre," the significance of APL, and the importance of discovering aggregate operations in various fields. But she noted, "I am not, however, convinced that we ought altogether to dispense with the notion of an explicit store and an assignment operator." She pointed out ongoing work at IBM on non-von Neumann frameworks as well as attempts to integrate these into useful programming systems. Backus responded with a vigorous reiteration of the need for IBM Research to study language frameworks with the goal of defining a very simple framework supporting rich definitions [ Backus1974b ].

Despite the lukewarm response from research management, Backus persevered. In the "Plans for 1974" section of his 1973 annual report, Backus had mentioned, "If time and assistance permit, I hope to begin work on an optimizing interpreter for Red languages." He let it be known he was interested in hiring someone to work with him , and Jim Gray, then at IBM San Jose Research and knowing I was looking for permanent employment, introduced me to Backus. I'd attended one of his lectures at UC Berkeley in 1972 and signed up for his mailing list, so I'd received and at least partially digested his two research reports. I'd also worked on interpreters for Snobol4 and APL . For the next 15 months or so, I worked with Backus to refine the language and to explore implementation ideas, including writing some experimental interpreters in Lisp and Mcg, an ISWIM-like language designed by W. H. Burge [ Burge1968 ]. I gave a short talk to the department shortly after joining [ McJones1974b ] and wrote a technical report on "A Church-Rosser Property of Closed Application Languages" [ McJones1975 ]. During this time Backus and I explored a series of minor variations on the Red language—see [ Backus1974b ] through [ Backus1975b ]. Work on the algebra of programs (first mentioned in [Backus1974a]) and modeling state transformations also begin. Sensing that the language was still in flux and the emphasis was more on formal methods than actual implementation, I eventually moved over to the System R relational database project.

***** Include some of my Red evaluators?

During this period several researchers at universities began projects based on Backus's ideas. Klaus Berkling initiated design work at GMD in Germany for a reduction-based machine influenced by [ Backus1973c ]; it is said the be the first reduction machine actually implemented [ Berkling1975 ], [ Kluge1983 ]. Also Gyula A. Magó at the University of North Carolina initiated the FFPM project [ Magó1976 ]. [ Partain1989 ] describes these and other graph reduction machines.

John Backus received the 1977 ACM Turing Award "For profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on FORTRAN, and for seminal publication of formal procedures for the specification of programming languages." His award lecture "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" was published in the Communications of the ACM, received by all ACM members [ Backus1978b ]. He argued:

"Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming, inherited from their common ancestor—the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs."

The alternative he proposed was an "informal" functional programming language FP (with a related "formal" version FFP), an algebra of functional programs, and a framework for applicative state transitions (AST) for modeling history-sensitive systems. FP included a set of primitive functions for working with numbers, atoms, and sequences, as well as a set of combining forms for constructing more complex functions from simpler ones. Here's an example function for matrix multiplication:

&#9675 represents function composition, while α applies a function to each element of a sequence. MM expects a pair of compatible matrices, each represented as a sequences of rows. Reading from right to left, the function in brackets transposes the second matrix while leaving the first matrix intact. distr pairs a copy of the transposed second matrix with each row of the first matrix. αdistl applies distl to each such pair, resulting in a sequence of sequences of pairs of rows. ααIP applies IP (inner product) to each such pair, thus producing the desired matrix product.

Note ony functions are mentioned, never the data items (variables or constants) to which they are applied. (There was a combining form for creating a constant-valued function from a data value.) This later became known as point-free style. Backus felt it contributed greatly to the power and simplicity of FP.

One of the problems with conventional languages cited by Backus was their complexity and the resultant difficulty in specifying them and proving properties about them. In contrast, Backus exhibited an algebra of programs for FP that could be used for showing program equivalance, for example when transforming a program to a more efficient form. The algebra was based on identities stemming from the properties of the combining forms, for example:

[f1, ..., fN] &#9675 g ≡ [f1 &#9675 g, ... fN &#9675 g]

αf &#9675 [g1, ..., gN] ≡ [f &#9675 g1, ..., f &#9675 gN]

/f ○ [g1, g2, ... gN-1, gN] ≡ f ○ [g1, f ○ [g2, ... f ○ [gN-1, gN]...] ]

/ takes a function on pairs and produces a function on sequences, like APL's reduction operator.

There were also theorems based on these laws for more complex transformations, such as for converting a self-referencing definition into an (infinite) conditional. The paper spent many pages explaining and proving several of these theorems. Examples showed the equivalence between recursive and non-recursive versions of matrix multiplication and factorial.

Finally, Backus presented Applicative State Transition systems, in which the system has a state consisting of a set of named cells each containing a user-defined function or a data item. The user submits a series of inputs, each of which is examined by a system function that dispatches to the appropriate handler, which runs a computation and then