History of John Backus's FP languages

?\C- ?\C-f ?\C- ?\C-s ?\] ?\C-b ?\C-w ?\C-y ?\C-r ?\[ ?\C- ? ?\C-s ?\] ?\C- ?])-->

History of John Backus's functional programming project

***** DRAFT *****

Paul McJones

paul@mcjones.org

https://mcjones.org/dustydecks

Last modified 18 July 2026

Abstract

John Backus explored a sequence of applicative, functional and function-level languages starting before 1969 and continuing until<br>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.

Contents

Acknowledgements

The software crisis

Launching a project

Another assistant

The Turing Lecture

Refining the algebra

The FL team

Implementations by others

Assessment

References

Related resources

Acknowledgements

John Backus for hiring me in 1974 and giving me a number of historic materials in 2004.

Scott Baden for a copy of his "DFT &rarr; FFT transformation in FP."

Edoardo S. Biagioni for the source code to his FPC and information about Gyula A. Mag&oacute;'s FFP Machine project.

Dines Bj&oslash;rner for information on his work with John Backus.

Will Partain for information about Gyula A. Mag&oacute;.

Barry Rosen for permission to post [Rosen1974a, b].

The software crisis

In the late 1960s the "software crisis" became a frequent topic of discussion. Computers had become much<br>more capable<br>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:

"I was just trying to think of some sort of really higher level<br>programming that wasn’t as difficult as Fortran. The problem was that the idea of functional programming, the 'combining forms' and stuff like that, came pretty easily. But trying to make it into a real full system where you could deal with all the other issues that you couldn’t express in that language got very confusing and messy." [Booch2007]

Launching a project

For several years, Backus worked mostly alone on this new idea. Ted Codd consulted with him briefly, but that didn't last<br>[Booch2007]. In late 1969, Dines Bj&oslash;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&oslash;rner<br>worked with Backus until 1972, when they parted ways; Bj&oslash;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<br>programming"; the report acknowledges Bj&oslash;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<br>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...