Software Preservation Group of the Computer History Museum

History of John Backus's functional programming project

***** Work in progress *****

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

Last modified 6 September 2026

Abstract

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

How to cite this page: Paul McJones. History of John Backus's functional programming project. Web site, Software Preservation Group, Computer History Museum. Last visited dd mmm yyyy. https://softwarepreservation.computerhistor.org/FP

Contents

Acknowledgments

In search of a challenge

By the late 1960s, computers had become much cheaper, faster, and larger, but as ambitions grew, a number of programming projects suffered from cost and schedule overruns and poor reliability. A pair of NATO software engineering conferences 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, giving him the flexibility to choose what he wanted work on. He then spent a number of years working on the four color conjecture (now theorem). But somewhere around 1969, Backus decided to take another try at the programming problem:

"I was just trying to think of some sort of really higher level 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

At first Backus worked 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 semantics for Backus's language (which was then called RedSys) [Bjørner2025, 1972]. Bjørner worked with Backus until they parted ways in 1972; Bjørner went on to work with Ted Codd in San Jose for a year, and then joined the IBM Vienna Lab. [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 similar 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 Backus 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]:

  1. "Simple, whole-entity programming languages, as contrasted to conventional complex, word-at-a-time programming languages, have the potential for drastically reducing the cost of programming.
  2. Present efforts to clean up and extend conventional concepts of programming languages have no such potential; ... indeed they will continue to add complexity to languages without dealing with the word-at-a-time problem, as they have for the past 15 years, and thereby actually increase the cost of programming and the expertise required for its practice. (Thus PL/I is perhaps 10 times as complex as Fortran, less economical in execution, and only 20-30% more powerful in expressiveness.)"

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 perhaps the first written use of the now-famous 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].

My role

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 began. 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. Later I moved to Xerox's office system and wrote toy implementations of Red in Mesa and Poplar, a lazy functional language.

Scan the Red evaluators I wrote in Lisp, Mcg, and (later) Mesa and Poplar.

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 to be the first reduction machine actually implemented [Berkling1975], [Kluge1983]. Gyula A. Magó at the University of North Carolina initiated the FFPM project [Magó1976]. [Partain1989] describes these and other graph reduction machines.

The Turing Award

Lecture

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 [Backus1978]. 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:

Def MM ≡ (ααIP) ○ (αdistl) ○ distr ○ [1st, trans ○ 2nd]

○ represents function composition, α applies a function to each element of a sequence, and [,...,] applies a list of functions to a value, producing a sequence of results. 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 only 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 equivalence, 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] ○ g ≡ [f1 ○ g, ... fN ○ g]

αf ○ [g1, ..., gN] ≡ [f ○ g1, ..., f ○ 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 produces a pair (output, new state). The system function does a validity check on the new state, then installs it and sends the output to the user. The paper describes this in some detail, including bootstrapping from an empty state, and suggests various ways the system could be elaborated.

Response

Given the prestige of the Turing Award and the provocative title, the paper was widely read and discussed. Personal letters from Dana Scott [Scott1978] and Robin Milner [Milner1978] congratulated Backus in his effort to bring proofs of programs to working programmers, but pointed out a number of technical problems with FP and FFP and encouraged him to base his work on an extended typed λ-calculus such as presented in [Scott1976]. (Scott also chided, "Thank you very much indeed for the several kind references to me. Of course, just as you use the name 'von Neumann' in a generic sense, so you use 'Scott'. I would have suggested including references to my Turing lecture [Scott1977] and to the SIAM paper [Scott1976] where some of the other contributors are mentioned.")

A more energetic interchange was launched when Edsger Dijkstra reviewed Backus's lecture as number 692 in his personal EWD series, which was directly distributed to about a dozen of Dijkstra's friends but made its way indirectly to a larger audience, including Backus. His conclusion was relatively bland [Dijkstra1978b]:

"In short, the article is a progress report on a valid research effort but suffers badly from aggressive overselling of its significance, long before convincing results have been reached. This is the more regrettable as it has been published by way of Turing Award Lecture."

but his full review was quite negative, and triggered an exchange of letters between Backus and Dijkstra [Chen2016] in which Dijkstra declared his review had been a "political pamphlet" aimed to counter what he apparently felt was Backus's attack on the axiomatic semantics being developed by Dijkstra, Hoare, and others.

By August 2026, the ACM's Digital Library recorded over 2000 citations of [Backus1978], with more trickling in. Although the vast majority seemed to cite the paper as a reference for "von Neumann architecture", many dozen papers, especially in the first decade, were genuine attempts to apply or extend Backus's ideas in a variety of ways:

Algebra and advocacy

Algebra

Backus had worked alone since I moved to the System R project in 1975. In July 1978 he was joined by John Hayden Williams. Williams received his PhD at the University of Wisconsin-Madison with a dissertation entitled Bounded Context Parsable Grammars. He joined the faculty at Cornell University, where he conducted research on programming languages. They both attended a 1977 workshop on dataflow and reduction languages [Gostelow1977] and Backus mentioned him in the acknowledgments to [Backus1973a] and [Backus1978]. Perhaps the idea of joining IBM was discussed in December 1977, when Backus gave a talk at Cornell. The summer Williams arrived he was one of the lecturers at the annual NATO Summer School at Marktoberdorf, Germany. Dijkstra reported [Dijkstra1978a]:

"The last lecture of the last day --on Reduction Languages-- was given by one of the participants, John H. Williams (in the process of moving from Cornell University to IBM? San Jose). It was a brilliant lecture, forcefully delivered. In view of the fact that the participants were the best part of the Summer School, we couldn't have wished for a more appropriate closing lecture."
John Backus and John Williams in Peñíscola, Spain, 1981 John Backus and John Williams at the whiteboard
John Backus and John Williams. Courtesy of John Williams.

Backus and Williams set to work further developing the algebra of programs. Through early papers [Backus1979], [Backus1981a] and [Williams1982], foundations for the algebra emerged with functions, forms, limits, linearity, and a linear expansion theorem that allowed an interesting class of recursive function definitions to be restated in iterative form. If H is a linear form with "predicate transformer" Ht, then the least solution of:

f = p → q; Hf

is:

f = p → q; ...; Htnp → Hnq; ...

thus allowing an explicit definition.

[Backus1981a] noted a 1975 paper [Raymond1975] in which François Henri Raymond had independently and earlier developed a quite similar algebra of functions, unbeknownst to Backus.

Many people found this variable-free, function-level style to be difficult to master. [Backus1979] pointed out two problems: "naming" (variables are useful when lots of quantities need to be kept track of) and "forgetting" (a computation intended both to compute a value and provide an updated version of a database need to thread the database through the computation). [Backus1981a] introduced "extended definitions" with named formal function variables. For example:

xdef f ○ [x, [y, z]] = [[x, y], [x, z]]

replaces:

def f = [[1, 1 ○ 2], [1, 2 ○ 2]]

The paper noted joint work with S. W. Smoliar (never published) that would extend similar function variables into predicates used in conditional expressions. The later FL language included similar ideas in its pattern feature.

[Backus1985a] introduces "Fortran constructs" and demonstrates the algebraic transformation of MM to a form for which code could be easily generated for the usual three nested loops:

MM' = [ [ \+ ○ [ * ○ [k ○ i ○ l, j ○ k ○ 2]
       k=˜1, len ○ 2]
        j=˜1, len ○ 1 ○ 2]
 i=˜1, len ○ 1]

(An extra right bracket in the original has been deleted.)

Advocacy

[Dijkstra1978b] described the Turing lecture as "aggressive overselling of its significance, long before convincing results have been reached". Dijkstra found this "regrettable" especially given the prestige of a Turing Award lecture. But Backus continued his strong advocacy for function-level programming and criticism of "von Neumann languages" through the mid 1980s, apparently only softening his arguments as he and his group became absorbed in designing and implementing an actual programming language.

His Turing lecture had made a number of assertions about conventional languages:

  1. They were growing larger and more complex to gain functionality, implying the growth was linear or worse (ignoring newcomers like Pascal and C).
  2. Most were word-at-a-time (downplaying APL and ignoring newcomers like SETL and SQL).
  3. Their semantics were based on state transitions.
  4. They were divided into worlds of expressions and statements.
  5. They lacked "combining forms" (downplaying APL and ignoring Unix pipelines and emerging applicative techniques).
  6. They lacked useful mathematical properties for reasoning about programs (dismissing work on axiomatic and denotational semantics)

[Backus1979] expanded on point 3 above. His approach focussed on formal semantics. In an imperative language with assignments and side-effects, the meaning of a statement (or expression with side-effects) is modeled as a function mapping stores (memory states) to stores, whereas a functional program maps values to values. He concluded that a functional program, using four main combining forms (constant, composition, condition, and construction) was much more powerful because of the existence of the algebra of programs interrelating these combining forms. He demonstrated an embedding of a von Neumann language, referred to as L, within a functional language, L*, by modeling the semantic function for L as an L* program, but pointed out the resultant functions were far too unwieldy to apply the algebra of programs.

[Backus1981a] took up the lambda style (e.g., LISP [McCarthy1960] and Landin's ISWIM [Landin1964]): "In general, we suggest that the FP style offers a framework in which one can perceive and reason about program structures, truths, and transformations at a higher level of generality than that presently available for reasoning about lambda style programs." He acknowledged that using lambda abstraction one can define all of the FP program forming operations and "an infinity of others," but argued that this power would lead to undisciplined use and concluded: "Therefore perhaps it is time to begin designing a new generation of functional languages, languages that emphasize function level structure and function level reasoning." Later, his FL would allow the use of lambda expressions to define higher-order functions.

In several talks he spoke of the inflexibility of the "storage plans" of von Neumann programs: composing two programs would require they have compatible storage plans so the output of the first program would be at the same address as the input of the second program, which seemed to ignore the existence of subroutine mechanisms that were present as early as FORTRAN II.

This advocacy took place in industry magazines [Backus1982b], talks inside [Backus1985b] and outside [Backus1983] IBM, as well as the more specialized conferences mentioned previously.

Implementation

Williams and Backus began thinking about implementation issues fairly early on. [GuttagEtAl1981] mentions "In current implementations of FP, a large amount of redundant checking is performed, since each of the primitives needs to check that its argument x is of the right form." That implementation was written in PL/I "to provide a vehicle for trying out different storage schemes for FP objects and consequently is highly modular (and highly inefficient)." Williams also did an implementation of FP "on" Lisp: definitions of the FP primitive functions and combining forms as Lisp functions. [BruceWilliams1982]

By 1983, the algebra's foundation was fairly solid and had been applied to some program transformation work. To further stress the algebra, a body of larger programs was needed. This suggested designing a suitably expressive version of the language, carefully specifying its semantics, and implementing it. Perhaps for this reason Backus's team expanded further. In September 1983, Edward L. Wimmers joined. He had received a Ph.D. in mathematical logic from the University of Wisconsin-Madison the previous year.

FP84

Starting in 1984, Williams and Wimmers collaborated with fellow IBM researcher Joseph Halpern on an investigation into the soundness and completeness of rewrite rules for languages such as FP. They began by generalizing FP, as described in [WilliamsWimmers1988]:

"Informally, FP84 is the result of altering the language FP of [Backus1978] to include infinite sequences, programmer-defined combining forms, and lazy evaluation. Moreover, unlike the formal language FFP of [Backus1978], FP84 makes a clear distinction between objects and functions; i.e., sequences of objects are no longer used to represent functions. These extensions are accomplished in FP84 by removing the FP restriction that sequence construction be applied only to non-⊥ objects; in FP84 the entire set of expressions (including those whose meaning is ⊥) is closed under sequence construction."
Tim Winkler, John Williams, and John Backus
Ed Wimmers, John Williams, and John Backus, 1984. Courtesy of John Williams.

The theoretical work culminated in [HalpernEtAl1990] and [HalpernWimmers1995].

FL86

With its lazy evaluation and infinite sequences, FP84 could model input/output and large-scale (e.g., file system) state change:

Composition of IFR programs connected to a file system (from [HughesEtAl1987])
From [HughesEtAl1987]

Writing functions to do useful work (e.g., editing, compiling) and threading the stream connections would be fussy and would require new combining forms for composing IFR (Interactive, File Referencing) programs. It was decided to use a different approach, which used a strict language (as with the earlier FP) and an implicit history component.

Diagram showing the FL strict-history approach to IFR programming (from [HughesEtAl1987])
From [HughesEtAl1987]

Although this also required careful specification of the language's order of evaluation to make side-effects manageable, analysis showed a quite usable algebra remained. This language was the first to be called FL, but we refer to it here as FL86 to distinguish it from the later version [BackusEtAl1986, 1990].

The core of FL86 was similar to the FP of [Backus1978], with the addition of an error value, ?, and tagged values used to implement programmer-defined data types (which were influenced by [GuttagEtAl1981]). This core language was higher-order: combining forms were functionals, and in addition to the familiar primitive combining forms of FP, new higher-order functions could be defined. The core language was defined via both denotational and operational semantics (rewrite rules), which were proved to be sound and complete. The language had additional convenience features implemented as "syntactic sugar," including statically scoped local definitions of functions (where clauses), encapsulated type definitions (influenced by [GuttagEtAl1981]), pattern matching, and various notations making it easier to define new higher-level functions, including currying, lifting, and infix notation. A talk given at Antibes in 1987 shows the scheme for types [BackusEtAl1987].

John Hughes visited from the University of Glasgow the summer of 1987 and helped think through the issues with strict and higher-order evaluation of function-level rewrite rules. Findings were presented in a talk at the Year Of Programming Conference at U.T. Austin [HughesEtAl1987].

[Mary Sheeran visited at the same time. Also, see [Sheeran2025].]

FL

Two new research staff members joined the group in 1988. In February, Peter Lucas joined; he'd worked at IBM since 1961 at the IBM Vienna Laboratory and IBM Research in Yorktown and San Jose/Almaden. In August, Alexander S. Aiken joined. He received his PhD from Cornell University. Brian Murphy was an MIT Co-op student who came in 1987 and 1988. Thom Linden, an Advisory Programmer, joined the project in November 1988, and Paul Tucker joined from IBM Menlo Park Laboratory by early 1990.

Backus, Williams, Wimmers, Aiken, and Lucas redesigned the FL language, producing a detailed new language manual [BackusEtAl1989b]. FL was both simpler and more powerful than FL86, with several important new features [BackusEtAl1990]:

Review and planning documents from 1988 indicate there was a bootstrap compiler running on IBM LISP on VM/370 that compiled FL to LISP, which could then be compiled and run on the VM/370 system to try out the language and could also be used in bootrapping, since it was expected that the prototype and optimized compilers would be written in FL These documents estimated completion of an operational system, with some optimization, by June 1991. [Backus1988a, b]. Backus's Annual Fellow Report of December 1990 announced [Backus1990]:

"As more and more programs are written in FL, we are finding the language to be powerful and convenient for a wide variety of tasks. The entire language is implemented in the current compiler. Provided that the optimization technology we are developing can be made to work as well across the board as it now does on our examples, our FL programming experience to date indicates that the FL language can serve as a very high level "fast prototyping" language (whose accuracy and robustness is enhanced by powerful type checking) and yet at the same time yield fast, production-level object code directly from the compiler. FL should thus eliminate the need to recode "fast prototype programs" in C while providing a more powerful and extensible language than those currently used for prototyping."

The report went on to describe progress on many components of the compiler:

Backus retired in 1991 [Backus1991], and the project ended about three years later.

Ed Wimmers, Alex Aiken, John Backus, and John Williams
Ed Wimmers, Alex Aiken, John Backus, and John Williams. Courtesy of John Williams.
John Backus with a necktie
John Backus (with necktie!), his wife Barbara Stannard, and John Williams, November 1999.
Courtesy of John Williams.
John Williams and John Backus, 2003
John Williams and John Backus, 2003. Courtesy of John Williams.
Alex Stepanov, John Backus, and Paul McJones, Zazzie's, 2004.
Alex Stepanov, John Backus, and Paul McJones, Zazzie's, 2004.

By others

Assessment

Backus's Turing Lecture [Backus1978] was a polemic against the computer architecture and programming languages of the day, and in favor of an applicative, function-level language that supported an algebra of programs. He felt that the "von Neumann bottleneck" of the interconnection between a computer's processor and memory was limiting performance and tending to constrain the design of programming languages. His objections to conventional programming languages included that:

  1. their size and compexity grew as they were adapted to new kinds of problems;
  2. they were "word-at-a-time" rather than "whole-entity";
  3. their semantics were based on state transitions rather than on reduction (rewrites);
  4. they were divided into worlds of expressions and statements;
  5. they lacked ways to directly combine smaller programs into larger programs;
  6. they lacked useful mathematical properties for reasoning about programs.

Backus spoke in terms of absolutes, and perhaps that blinded him to trends already underway.

Instead of the hardware stagnation he predicted, Moore's Law would lead to an increase of six orders of magnitude in density of transistors in integrated circuits, and computer architects would invent a long list of performance-enhancing techniques including caches, pipelining, multiple issue, SIMD, and specialized processors such as GPUs and TPUs.

Language designers were already experimenting with "whole-entity" programming, such as the array operations of APL, the set operations of SETL, and the relation operations of SQL.

Unix pipes already allowed the connection of separately-written programs to build new ones, and lambda-style functional languages were allowing experimentation with a variety of styles, including combinators. Lambda calculus pioneeer J. Barkley Rosser would later say, "Backus (1978) does not seem to be in the mainstream of this activity, but he has some quite novel combinatory functions, and something interesting may evolve out of his work." [Rosser1984]

Others were experimenting with abstraction techniques such as modules, interfaces, abstract data types, and objects that would allow programmers to extend language cores with separate extensions for each application area.

Work on operational, denotational, and axiomatic semantics made slow but steady progress. Programmers became familiar with pre- and post-conditions, loop invariants, and proofs of termination. Proof and model checkers were developed. In this coming age of LLM-based artificial intelligence, such formal methods may well become the key to avoiding "hallucinations".

Function-level programming turned out to be difficult for many programmers to master. The FL techniques of extended definitions, predicates, and pattern matching helped, but lambda bindings were eventually added to FL to ease the definition of higher-order functions. So-called point-free programming is a style supported by languages such as Haskell, but it's optional rather than required.

Backus and his colleagues made limited progress with the algebra. The clean operational semantics of FL supported rewrite-based transformations that were useful for optimization but did not eliminate the complexity of such optimizations. It's interesting to note that Richard Bird and Lambert Meertens, in parallel work, did extensive work deriving programs from specifications using equational reasoning [BirdEtAl2021]. As [KapurEtAl1981] pointed out, "... an operator should be associated with a structure having the algebraic properties on which the operator's behavior depends." (This line of thinking eventually led to the C++ Standard Template Library [Stepanov2007].)

Backus's advocacy helped popularize research into functional programming in general, and by now the functional style has permeated most modern programming languages. Dealing with effects (mutable storage and asynchronous i/o) remains a challenge for all applicative frameworks, whether function-level or value-level.

Archive and references

Part 1: By Backus and his colleagues

[Aiken1988]
Alex Aiken. Optimization Strategies for FL. 5 October 1988. From [Backus2004]. PDF
[AikenEtAl1989]
Alexander Aiken, Edward L. Wimmers, and John H. Williams. 1989. Program transformation in the presence of errors. In Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '90). Association for Computing Machinery, New York, pages 210–217. https://doi.org/10.1145/96709.96730 / https://theory.stanford.edu/~aiken/publications/papers/popl90.pdf
[AikenEtAl1990]
Alexander Aiken, John H. Williams, and Edward L. Wimmers. The Program Feature in FL. IBM Almaden Research Center, 16 October 1990. From [Backus2004]. PDF
[Aiken1991]
AA [Alex Aiken]. Another Stab at Monads. 29 April 1991. From [Backus2004]. PDF
[AikenEtAl1991a]
Alex Aiken, Brennan Gaunce, Brian Murphy. Implementing FL in C. 22 June 1991. From [Backus2004]. PDF
[AikenEtAl1991b]
Alexander Aiken, John H Williams, Edward L Wimmers. Programming a language. 1991. From [Backus2003 #189]. PDF
[AikenMurphy1991a]
Alexander Aiken and Brian R. Murphy. Implementing Regular Tree Expressions. In Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture. Springer-Verlag, Berlin, Heidelberg, 427–447. https://theory.stanford.edu/~aiken/publications/papers/fpca91.pdf
[AikenMurphy1991b]
Alexander Aiken and Brian R. Murphy. Static type inference in a dynamically typed language. In Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '91). Association for Computing Machinery, New York, NY, USA, 279–290. https://doi.org/10.1145/99583.99621
[AikenWimmers1993]
Alexander Aiken and Edward L. Wimmers. Type inclusion constraints and type inference. In Proceedings of the Conference on Functional programming languages and Computer architecture (FPCA '93). Association for Computing Machinery, New York, NY, USA, 1993, pages 31–41. https://doi.org/10.1145/165180.165188
[AikenEtAl1993]
Alexander Aiken, John H. Williams, and Edward L. Wimmers. The FL Project: The design of a Functional Language. IBM Almaden Research Center, September 1993. https://theory.stanford.edu/~aiken/publications/trs/FLProject.pdf / PDF
[AikenEtAl1994]
Alexander Aiken, Edward L. Wimmers, and T. K. Lakshman. Soft typing with conditional types. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '94). Association for Computing Machinery, New York, NY, USA, 1994 pages 163–173. https://doi.org/10.1145/174675.177847
[AikenEtAl1995]
Alexander Aiken, John H. Williams, and Edward L. Wimmers. Safe: a semantic technique for transforming programs in the presence of errors. ACM Trans. Program. Lang. Syst. 17, 1 (Jan. 1995), 63–84. https://doi.org/10.1145/200994.201002
[Aiken2007]
Alex Aiken. John Backus 1924–2007: A memorial given at the 2007 Conference on Programming Language Design and Implementation. http://theory.stanford.edu/~aiken/other/backus.pdf
[Backus1972a]
John Backus. Reduction languages and variable-free programming. RJ 1010, IBM Research Laboratory, San Jose, California, 7 April 1972. PDF
[Backus1972b]
John Backus. Re: "Reduction languages and variable-free programming." Cover letter for RJ 1010. IBM Research Laboratory, San Jose, California, 19 April 1972. PDF
[Backus1973a]
John Backus. Programming language semantics and closed applicative languages. RJ 1245, IBM Research Laboratory, San Jose, California, 5 July 1973. See [Backus1973c]. PDF
[Backus1973b]
John Backus. To Recipients of "Reduction languages and variable-free programming." Cover letter for RJ 1245. IBM Research Laboratory, San Jose, California, 17 July 1973. Paul McJones's copy, with errata applied. PDF
[Backus1973c]
John Backus. Programming language semantics and closed applicative languages. In Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of Programming Languages (POPL '73). Association for Computing Machinery, New York, NY, USA, 71–86. https://doi.org/10.1145/512927.512934
[Backus1973d]
John Backus. Class notes -- Red languages. Probably for two one-hour lectures at the University of California, Santa Cruz? See [Backus1974a]. 14 November 1973, 6 pages: PDF / 21 November 1973, 7 pages: PDF
[Backus1974a]
John Backus. Memorandum for R. E. Gomory. Annual report and Research goals in programming. 21 January 1974, 7+1 pages. PDF
[Backus1974b]
John Backus. Memorandum for P S. Dauber and P. C. Goldberg. Pat Goldberg's memo of 2/15/74. IBM San Jose Research Laboratory, 19 March 1974, 3 pages. PDF
[Backus1974b]
John Backus. Definition of Red with "items" and "rows". As transcribed by Paul McJones, 10 May 1974. PDF
[Backus1974c]
John Backus. Proposal for a quote-like feature: pseudo-applications. As transcribed by Paul McJones, 20 May 1974. PDF
[Backus1974d]
John Backus. Semantic definitions, top down and bottom up. As transcribed by Paul McJones, 23 May 1974. PDF
[Backus1974e]
John Backus. John's definitions: Red with "instruction", "world pair" {i.e, environment}. As transcribed by Paul McJones, 30 October 1974. PDF
[Backus1974f]
John Backus. Red with Rows and Contexts. Includes quoted expressions per [McJones1974a]. As transcribed by Paul McJones, circa 10 December 1974. PDF
[Backus1974g]
John Backus. Red with Contexts (but no general rows). As transcribed by Paul McJones, 20 December 1974. PDF
[Backus1974h]
John Backus. "Proper expressions." As transcribed by Paul McJones, 30 December 1974. PDF
[Backus1975a]
John Backus. Syntax and semantics. 29 January 1975. PDF
[Backus1975b]
John Backus. Class notes -- A variable-free functional programming system, FP. 19 February 1975, 9 pages: PDF / 5 March 1975, 3 pages: PDF / 30 April 1975, 7 pages: PDF / 7 May 1975, 5 pages: PDF
[Backus1978]
John Backus. Can Programming be liberated from the von Neumann Style? A functional style and its algebra of programs. 1977 ACM Turing Award Lecture.
[Backus1979]
J. W. Backus. On extending the concept of program and solving linear functional equations. Draft paper distributed at Summer Workshop on Programming Methodology, Univ. of Calif. at Santa Cruz, Santa Cruz, Calif., August 1979. Backus's correction copy. A revised version was published as [Backus1981a]. From [Backus2004]. PDF
[Backus1980]
J. W. Backus. Programming in the 1950's - some personal impressions.
[Backus1981a]
John Backus. The algebra of functional programs: Function level reasoning, linear equations, and extended definitions. In: J. Diaz, I. Ramos (eds.), Formalization of Programming Concepts. International Colloquium, Peñíscola, Spain, April 19-25, 1981. Lecture Notes in Computer Science 107, Berlin-Heidelberg-New York: Springer 1981, 1-43. Derived from [Backus1979]; reprinted as [Backus1982a]. https://doi.org/10.1007/3-540-10699-5_91 / PDF
[Backus1981b]
John Backus. Function level programs as mathematical objects. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1–10, 18 October 1981. https://doi.org/10.1145/800223.806757
[Backus1981c]
John Backus. Is Computer Science Based on the Wrong Fundamental Concept of 'Program'? An Extended Concept. In Algorithmic Languages, de Backker and van Vliet (eds). International Symposium on Algorithmic Languages Amsterdam, The Netherlands, 26-29 October 1981. IFIP, North-Holland Publishing Company, 1981, pages 133-165. https://ir.cwi.nl/pub/34328/34328D.pdf#page=158 / Preprint from [Backus2004]: PDF
[Backus1982a]
John Backus. The algebra of functional programs: Function level reasoning, linear equations, and extended definitions. RJ 3555, IBM Research Laboratory, San Jose, California, 23 July 1982. Reprint of [Backus1981a]. PDF / Backus's correction copy from [Backus2004]: PDF
[Backus1982b]
John Backus. Function-level computing. IEEE Spectrum 19:8, August 1982, 22-27. https://doi.org/10.1109/MSPEC.1982.6366967 / From [Backus2004]: PDF
[Backus1983]
John Backus. The Coming Revolution. RJ 3994, IBM Research Laboratory, San Jose, California, 23 August 1983. This paper is the text of a lecture given at MIT on May 5, 1983. From [Backus2004]. PDF
[Backus1985a]
John Backus. From Function Level Semantics to Program Transformation and Optimization.
[Backus1985b]
John Backus. The Programming Problem. Text and slides for "Future Computing" series of talks, IBM Yorktown, 26 July 1985. From [Backus2004]. PDF
[BackusEtAl1986]
John Backus, John H. Williams, and Edward L. Wimmers. The FL language manual (Preliminary Version). RJ 5339, IBM Research Laboratory, San Jose, California, November 1986. Replaced by [BackusEtAl1989b]. [Backus2003 #75] observes: "On re-reading this, it looks like we lost our way & got pretty complicated trying to provide 'conveniences'".
[BackusEtAl1987]
John Backus, John H. Williams, and Edward L. Wimmers. Data Types in FL: An alternative to strong typing? Slides for talk given at IFIP WG 2.2, Antibes, 4 June 1987. From [Backus2003 #27] PDF
[Backus1987]
John Backus. Function Level Programming and the FL Language. Video, 27 October 1987, University Video Communications. https://archive.org/details/JohnBack1987
[Backus1988a]
Programming Languages. Review slides for Juri Matisoo (lab director), 26 April 1988? ([Backus2003 #147] claims 1989). From [Backus2004]. PDF
[Backus1988b]
John Backus. Plan for implementing an FL system. 29 September 1988. From [Backus2004]. PDF
[BackusEtAl1988]
John Backus, Peter Lucas, John H. Williams, and Edward L. Wimmers. FL Reference Manual. 23 November 1988. Abstract: This is the (unreadable) reference manual for FL. From [Backus2003 #194]. PDF
[BackusEtAl1989a]
John Backus Group Meeting. Video recording at IBM Almaden Laboratory, 5 July 1989. Mary Van Deusen, videographer: "Raw footage from B-roll I shot at Almaden, the Calfornia IBM Reseach lab for a video on their computer science department. John allowed me to crawl around the floor through the meeting, then I shot his group's video segments. The videos were part of my multimedia research project for Abe Peled, back in NY's IBM Research." https://www.youtube.com/watch?v=KzBkb-bvNK4
[BackusEtAl1989b]
John Backus, John H. Williams, Edward L. Wimmers, Peter Lucas, and Alexander Aiken. FL language manual, Parts 1 and 2. RJ 7100, IBM Almaden Research Center, San Jose, California, 26 October 1989. Part 3, to be a formal description of the denotational semantics and the primitive functions of FL, was never published. From [Backus2004]. PDF
[Backus1990]
John Backus. Annual Fellow report for 1990: The Functional Programming Project. IBM Corporation. 17 December 1990. From [Backus2004]. PDF
[BackusEtAl1990]
John Backus, John H. Williams, and Edward L. Wimmers. An Introduction to the FL Language. In Research Topics in Functional Programming, D.A. Turner (Ed.), Addison-Wesley, Reading, MA, 1990. Revised excerpt from [BackusEtAl1986]. PDF
[Backus1991]
John Backus. FL Project Status. 4 April 1991. "Last review, for McGroddy. I was very saddened and disgusted by IBM’s failure to support this really exciting project that was doing great, had wonderful people, great prospects." From [Backus2003 #188]. PDF
[Backus2003]
John W. Backus papers, 1951-2001 (bulk 1953-1991). Library of Congress, Manuscript Division. https://lccn.loc.gov/mm2003084968
[Backus2004]
John W. Backus. Collection of papers given to Paul McJones, 7 November 2004. These will be offered to the Computer History Museum, along with documents acquired during 1974-1975 while working with Backus.
[Bjørner1972]
Dines Bjørner. Finite State Tree Computations (Part I). RJ-1053, IBM Research, San José, Calf., June 1972.
[BjørnerEtAl1973]
D. Bjørner, E. F. Codd, K. L. Deckert, and I. L. Traiger. The Gamma-0 n-ary Relational Data Base Interface Specifications of Objects and Operations. RJ-1200, IBM San Jose Research Laboratory, 11 April 1973. PDF
[Bjørner2025]
Dines Bjørner. Reflections. 30 December 2025. https://www.imm.dtu.dk/~dibj/2025/reflections/reflektioner.pdf
[Booch2007]
Grady Booch, interviewer. Oral History of John Backus, recorded 5 September 2006. X3715.2007, Computer History Museum, 2007.
[BruceWilliams1982]
Kim B. Bruce and John H. Williams. Letters concerning FP implementations. April 1982. From [Williams2026]. PDF
[Chen2016]
Jiahao Chen. “This guy’s arrogance takes your breath away”: Letters between John W. Backus and Edsger W. Dijkstra, 1979. Medium, 29 May 2016. https://medium.com/@acidflask/this-guys-arrogance-takes-your-breath-away-5b903624ca5f
[Dijkstra1978a]
Edsger W. Dijkstra. Trip report, Marktoberdorf 24 July–6 August 1978. https://www.cs.utexas.edu/~EWD/ewd06xx/EWD676.PDF / https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD676.html
[Dijkstra1978b]
Edsger W. Dijkstra. A review of the 1977 Turing Award Lecture by John Backus. EWD692, undated (late 1978). http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD692.PDF / https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD692.html
[Goldberg1974]
P. C. Goldberg. John Backus's Remarks on Red Languages and Reducing the Cost of Programming. Memo to P. S. Dauber, IBM Research Yorktown Heights, 15 February 1974. PDF
[Gostelow1977]
Kim P. Gostelow. Letter to John Williams re 1977 Dataflow and Reduction Languages Workshop, 4 April 1977. From [Williams2026]. PDF
[GuttagEtAl1981]
John Guttag, James Horning, and John Williams. FP with data abstraction and strong typing. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 11–24. https://doi.org/10.1145/800223.806758
[HalpernEtAl1985]
Joseph Y. Halpern, John H. Williams, Edward L. Wimmers, and Timothy C. Winkler. Denotational Semantics and Rewrite Rules for FP. In Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '85). Association for Computing Machinery, New York, NY, USA, 108–120. https://doi.org/10.1145/318593.318623
[HalpernEtAl1986]
Joseph Y. Halpern, John H. Williams, Edward L. Wimmers: Good Rewrite Strategies for FP. Proceedings of the 1st IEEE Symposium on Logic in Computer Science (Boston, Mass.), IEEE, New York, 1986, pages 149–162.
[HalpernEtAl1990]
Joseph Y. Halpern, John H. Williams, and Edward L. Wimmers. Completeness of rewrite rules and rewrite strategies for FP. J. ACM 37, 1 (Jan. 1990), 86–143. Subsumes [HalpernEtAl1985, HalpernEtAl1986]. https://doi.org/10.1145/78935.78939
[HalpernWimmers1995]
J. Y. Halpern and E. L. Wimmers. Full Abstraction and Expressive Completeness for FP. Information and Computation Volume 118, Number 22, 1995, pages 246-271. Preprint https://www.cs.cornell.edu/home/halpern/papers/FP_abstraction.pdf Earlier version in Proceedings of the Symposium on Logic in Computer Science (1987), pages 257-271.
[HughesEtAl1987]
John Hughes, John Williams, Ed Wimmers, John Backus. Higher Order Functions and I/O in Strict Functional Languages. Slides for talk at Year Of Programming Conf., Univ of Texas, 28 August 1987. PDF
[McJones1974a]
Paul McJones. Proposal for Quoted Expressions in Red. 15 May 1974. PDF
[McJones1974b]
Paul McJones. [Slides for Red talk for Department K55], 20 June 1974. PDF
[McJones1975]
Paul McJones. A Church-Rosser Property of Closed Applicative Languages. RJ 1589, IBM Research Laboratory, San Jose, California 95193, 23 May 1975. PDF
[McJones2007]
Paul McJones. Remembering John Backus. Dusty Decks blog, 1 April 2007. https://mcjones.org/dustydecks/remembering-john-backus
[Milner1978]
Robin Milner. Letters to John Backus. 29 September 14 and 11 October, 1978. From [Backus2004].
[Murphy1990]
Brian R. Murphy. A type inference system for FL. Master's thesis, MIT, September 1990. PDF (from http://suif.stanford.edu/~brm/papers/msthesis.ps.gz)
[Rosen1974a]
Barry K. Rosen. Notes on application of complete posets to RED languages. Computer Science Department, IBM Watson Research Center, 1 August 1974. PDF
[Rosen1974b]
Barry K. Rosen. More notes on application of complete posets to RED languages. Computer Science Department, IBM Watson Research Center, 28 October 1974. PDF
[Scott1978]
Dana Scott. Letters to John Backus. From [Backus2004]. 14 and 23 September 14, 1978.
[Stegman1979]
Claire Stegmann. Pathfinder. THINK, IBM Corporation, July/August 1979, pages 18-27. PDF
[Summers1972]
P. D. Summers. Documentation and source code of RED systems based on [Backus1972a], T. J. Watson Research Center, August 1972.
[TuckerWimmers199x]
P. Tucker and E. Wimmers. The FL Rewrite Engine. Research Report (in preparation). Cited in [WilliamsWimmers1990b].
[Williams1981a]
John H. Williams. Formal Representations for Recursively Defined Functional Programs. J. Diaz, I. Ramos (eds.). Formalization of Programming Concepts. International Colloquium, Peñíscola, Spain, April 19-25, 1981. Lecture Notes in Computer Science 107, Berlin-Heidelberg-New York: Springer 1981, pages 460-470. https://doi.org/10.1007/3-540-10699-5_119 / PDF
[Williams1981b]
John H. Williams. Notes on the FP Style of Functional Programming. In: Functional Programming and its Applications: An Advanced Course, J. Darlington, P. Henderson, and D. A. Turner (eds.), Cambridge University Press, March 1982. Proceedings of an advanced course held at Newcastle University, 20-31 July 1981. PDF
[Williams1982]
John H. Williams. On the Development of the Algebra of Functional Programs.
[Williams2026]
John Williams. Collection of papers given to Paul McJones, August 2026.
[WilliamsWimmers1988]
J. H. Williams and E. L. Wimmers. Sacrificing simplicity for convenience: Where do you draw the line? In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '88). Association for Computing Machinery, New York, NY, USA, 169–179. https://doi.org/10.1145/73560.73575
[WilliamsWimmers1990a]
John H. Williams and Edward L. Wimmers. The New Simplification Algorithm. 8 February 1990. "I include this item to show the difficulties in accurately transforming FL programs, even though it would require a lot of study of the FL manual and many other papers to understand this." From [Backus2003 #201]. PDF
[WilliamsWimmers1990b]
John H. Williams and Edward L. Wimmers. An optimizing compiler based on program transformation. IBM Almaden Research Center, 3 December 1990. From [Backus2004]. PDF
[Wimmers1988]
Ed Wimmers. Some Basic FL Laws. 23 September 1988. "Shows the richness of the algebra of the higher order functions of FL." From [Backus2003 #198]. PDF

Part 2: Related work

[BackusHerrick1954]
J. W. Backus and H. Herrick. IBM 701 Speedcoding and other automatic programming systems. In Proc. Symp. on Automatic Programming for Digital Computer, Washington DC, The Office of Naval Research, May 1954, pages 106-113. PDF
[BeebeMcJones2026]
Nelson H. F. Beebe and Paul McJones. A bibliography of publications of John Warner Backus. Report, University of Utah, Department of Mathematics, Salt Lake City, UT 84112-0090, USA, 16 June 2026. 35 pages https://ftp.math.utah.edu/pub/bibnet/authors/b/backus-john-w.html
[BirdEtAl2021]
Richard Bird, Jeremy Gibbons, Ralf Hinze, Peter Höfner, Johan Jeuring, et al. Algorithmics. Advancing Research in Information and Communication Technology, AICT-600, pages 59-98, 2021. https://inria.hal.science/hal-03325977/document
[Burge1968]
W. H. Burge. Mcg—A Functional Programming System. RC-2189, IBM Research, Yorktown Heights, New York, 29 August 1968. PDF
[Landin1964]
P. J. Landin. The mechanical evaluation of expressions. Computer J. 6, 4, 1964, pages 308-320. https://doi.org/10.1093/comjnl/6.4.308
[McCarthy1960]
John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. Commun. ACM 3, 4 (April 1960), 184–195. https://doi.org/10.1145/367177.367199
[Raymond1975]
François-Henri Raymond. Note sur l’algèbre des fonctions. Revue française d’automatique informatique recherche opérationnelle. Informatique théorique, tome 9, no R3 (1975), pages 25–49. (French) http://www.numdam.org/item?id=ITA_1975__9_3_25_0 / English translation by Claude.ai PDF
[Raymond1977]
François-Henri Raymond. Note sur la suppression des étiquettes en programmation. RAIRO – Informatique théorique, tome 11, no 1 (1977), pages 3–16. https://www.numdam.org/item/?id=ITA_1977__11_1_3_0 / English translation by Claude.ai PDF
[Rosser1984]
J. Barkley Rosser. Highlights of the History of the Lambda-Calculus, IEEE Annals of the History of Computing, Volume 6, Number 4, Oct.–Dec. 1984, pages 337–349. https://doi.org/10.1109/MAHC.1984.10040 / https://lawrencecpaulson.github.io/papers/Rosser-Lambda-Calculus.pdf
[Scott1976]
Dana Scott. Data Types as Lattices. SIAM Journal on Computing, Volume 5, Number 3, September 1976, pages 522–587. https://doi.org/10.1137/0205037 / https://www.cs.ox.ac.uk/files/3287/PRG05.pdf
[Scott1977]
Dana Scott. Logic and Programming Languages. 1976 ACM Turing Award lecture. Comm. ACM, Vol. 20, 1975, pages 634–641. https://doi.org/10.1145/359810.359826

Part 3: Influenced by Backus

[ChristopherAmeiss1990]
T. Christopher and D. Ameiss. Functional programming in a parallel environment: the implementation of FP in MDC. SIGPLAN Not. 25, 11 (Nov. 1990), 85–94. https://doi.org/10.1145/101356.101362
[BadenPatel1983]
S. B. Baden and D. R. Patel. Berkeley FP — Experiences with a Functional Programming Language. Conference Record of COMPCON ’83, San Francisco, California, pages 274–277, March 1983.
[Baden1983a]
Scott Baden. Berkeley FP User's Manual, Version 41. UNIX Programmer’s Manual Supplementary Documents
[Baden1983b]
Scott Baden. DFT → FFT transformation in FP. University of California, Berkeley, 3 May 1983. PDF
[Baden1983c]
Scott Baden. Berkeley FP source code. 1983–1985. .zip
[Banerjee1992]
Debasish Banerjee. A technique for solving a class of quadratic FP equations. Science of Computer Programming, Volume 19, Issue 1, 1992, pages 61–85, ISSN 0167–6423. https://doi.org/10.1016/0167-6423(92)90004-U
[Bellegarde1986]
Françoise Bellegarde. Rewriting systems on FP expressions to reduce the number of sequences yielded. Science of Computer Programming, Volume 6, 1986, Pages 11–34, ISSN 0167–6423. https://doi.org/10.1016/0167-6423(86)90017-1
[Bellot1984]
Patrick Bellot. Semantiques comparees des systemes de programmation fonctionnelle FP et FFP de J.W. Backus ["Comparative Semantics of J.W. Backus's Functional Programming Systems FP and FFP"]. In: Paul, M., Robinet, B. (eds) International Symposium on Programming. Programming 1984. Lecture Notes in Computer Science, vol 167. Springer, Berlin, Heidelberg, 1984. https://doi.org/10.1007/3-540-12925-1_25
[Bellot1985]
Patrick Bellot. 1985. High order programming in extended FP. High order programming in extended FP. In: Jouannaud, JP. (eds) Functional Programming Languages and Computer Architecture. FPCA 1985. Lecture Notes in Computer Science, vol 201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15975-4_30
[Ben-AsherEtAl1993]
Y. Ben-Asher, G. Rünger, A. Schuster, and R. Wilhelm. 2DT-FP: An FP based programming language for efficient parallel programming of multiprocessor networks. In: Bode, A., Reeve, M., Wolf, G. (eds) PARLE '93 Parallel Architectures and Languages Europe. PARLE 1993. Lecture Notes in Computer Science, vol 694. Springer, Berlin, Heidelberg, 1993. https://doi.org/10.1007/3-540-56891-3_4
[Berkling1975]
Klaus J. Berkling. Reduction Languages for Reduction Machines. 2nd Annual Symposium on Computer Architecture, Houston, Texas, 20–22 January 1975. PDF
[Biagioni1988]
Edoardo S. Biagioni. FPC: A Translator for FP. Report R88-027, University of North Carolina, May 1988. PDF / https://www.cs.unc.edu/techreports/88–027.pdf
[Böhm1982]
Corrado Böhm. Combinatory foundation of functional programming. In Proceedings of the 1982 ACM Symposium on LISP and Functional Programming (LFP '82). Association for Computing Machinery, New York, 1982, pages 29–36. https://doi.org/10.1145/800068.802132
[BossiGhezzi1984]
Annalisa Bossi, Carlo Ghezzi. Using FP as a query language for relational data-bases. Computer Languages, Volume 9, Issue 1, 1984, Pages 25–37, ISSN 0096-0551. https://doi.org/10.1016/0096-0551(84)90010-9
[Buccianti2020]
Benjamín Buccianti. Interactive FP interpreter written in Clojure. 2020. .zip / https://github.com/bbuccianti/fp
[BunemanFrankel1979]
Peter Buneman and Robert E. Frankel. FQL: a functional query language. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data (SIGMOD '79). Association for Computing Machinery, New York, NY, USA, 1979, pages 52–58. https://doi.org/10.1145/582095.582104
[Chiarini1980]
A. Chiarini. 1980. On FP languages combining forms. SIGPLAN Not. 15, 9 (September 1980), 25–27. https://doi.org/10.1145/947706.947709
[ChoppyEtAl1983]
C. Choppy, G. Guiho, and S. Kaplan. Algebraic semantics for FP languages, a lisp compiler and its proof, Rapport LRI N° 133, Orsay, 1983.
[ChoppyEtAl1985]
C. Choppy, G. Guiho, and S. Kaplan. A LISP compiler for FP language and its proof via algebraic semantics. In: Ehrig, H., Floyd, C., Nivat, M., Thatcher, J. (eds) Mathematical Foundations of Software Development, CAAP 1985. Lecture Notes in Computer Science, vol 185. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15198-2_26 (open access)
[CremersHibbard1983]
A. B. Cremers and T. N. Hibbard. Applicative State Transition Systems in LISP-Like Notation. In: Kupka, I. (eds) GI - 13. Jahrestagung. Informatik-Fachberichte, vol 73. Springer, Berlin, Heidelberg, 1983. https://doi.org/10.1007/978-3-642-69298-7_6
[Deleuze2003]
Christophe Deleuze. oc-FP: An OCAML implementation of John Backus' FP system. Version 0.21, 2003.
[DiGiorgio2019]
Alessandro Di Giorgio. fpar: a data parallel implementation of Backus's FP programming language as an embedded DSL in C++17. 2019. .zip / https://github.com/alessandrodgr/fpar
[DoschMöller1984]
Walter Dosch and Bernhard Möller. Busy and lazy FP with infinite objects. In Proceedings of the 1984 ACM Symposium on LISP and functional programming (LFP '84). Association for Computing Machinery, New York, NY, USA, 1984, pp282–292. https://doi.org/10.1145/800055.802045
[Ei-Affendi1994]
M.A. Ei-Affendi. Imposing an FP Layer on a Risc Machine. Journal of King Saud University—Engineering Sciences, Volume 6, Issue 2, 1994, Pages 167–183, ISSN 1018-3639. https://doi.org/10.1016/S1018-3639(18)30606-8
[Facorro2011]
Juan Facorro. fp interpreter written in Lisp. Common Lisp source code, 2011. .zip / https://github.com/jfacorro/fp-interpreter-in-lisp
[FickertSudkamp1992]
Chris Fickert and Thomas Sudkamp. Unification based FP interpreters. SIGPLAN Not. 27, 11 (Nov. 1992), 49–58. https://doi.org/10.1145/141018.141042
[Frank1981]
Geoffrey A. Frank. Specification of data structures for FP programs. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 221–228. https://doi.org/10.1145/800223.806782
[Gabriëls2007]
René Gabriëls, Dirk Gerrits, and Peter Kooijmans. John W. Backus : 3 December 1924–17 March 2007. Report for class 2R930 Geschiedenis van Informatica (History of Computing), Faculteit Wiskunde & Informatica, Technische Universiteit Eindhoven, 29 May 2007. https://dirkgerrits.com/publications/john-backus.pdf
[George1988]
K. M. George. Objects and data structures in the FP paradigm. Seventh Annual International Phoenix Conference on Computers an Communications. 1988 Conference Proceedings, Scottsdale, AZ, USA, 1988, pages 256–260. https://doi.org/10.1109/PCCC.1988.10081
[HalpernEtAl1988]
Brent Hailpern, T. Huynh, and G. Revesz. Comparing two functional programming systems. IEEE Transactions on Software Engineering, 15(5):532–542. http://doi.ieeecomputersociety.org/10.1109/32.24702 Also RJ–12598, IBM Research Division, 17 March 1988. https://brent.hailpern.com/wp-content/uploads/2019/12/rc12598.pdf
[HendersonEtAl1983]
Peter Henderson‚ Geraint A. Jones and Simon B. Jones. The LispKit Manual. Oxford University Computer Laboratory Programming Research Group, 1983. Technical Monographs PRG-32(1) and PRG-32(2). Includes an implementation of muFP written in LispKit. mirror
[HongLingzi1989]
Z. Hong and J. Lingzi. A knowledge-based system to synthesize FP programs from examples. In: Martins, J.P., Morgado, E.M. (eds) EPIA 89. EPIA 1989. Lecture Notes in Computer Science, vol 390. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51665-4_89
[HuynhEtAl1985]
Tien Huynh, Brent Hailpern Lee W. Hoevel. An execution architecture for FP. IBM J. Res. Development, Vol. 30, No. 6, November 1986, pages 609–616. https://brent.hailpern.com/wp-content/uploads/2017/03/IJRD_30_6_1986.pdf / https://doi.org/10.1147/rd.306.0609
[HuynhHailpern1986]
Tien Huynh and Brent Hailpern. An Improved DEL-Style Execution Architecture for FP. RC-12202, IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598, 2 October 1986. https://brent.hailpern.com/wp-content/uploads/2017/03/rc12202.pdf Also published in Proc. Twentieth Hawaii Int. Conf. System Sciences, vol. 1, Kona, HI, Jan. 1987, pages 369–376.
[Ida1982]
T. Ida. A manual of IPCR-FP. Information Science Laboratory, Institute of Physical and Chemical Research. 1982.
[Ida1983]
Tetsuo Ida. Some FP algebra with Currying operation. Information Processing Letters, Volume 17, Issue 5, 1983, Pages 259–261, ISSN 0020–0190. https://doi.org/10.1016/0020-0190(83)90110-2
[IdaTanaka1983]
Tetsuo Ida and Jiro Tanaka. Functional Programming with Streams. Information Processing '83: Proceedings of the IFIP Ninth World Computer Congress, Sept 19–23, 1983, pp 265–270.
[IdaTanaka1984]
T. Ida and J. Tanaka. Functional programming with streams —Part II—. New Generation Computing 2, pages 261–275 (1984). https://doi.org/10.1007/BF03037060
[IslamEtAl1981]
N. Islam, T. J. Myers, and P. Broome. A simple optimizer for FP-like languages. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1981, pp33–40. https://doi.org/10.1145/800223.806760
[JonesMuchnick1982]
Neil D. Jones and Steven S. Muchnick. A fixed-program machine for combinator expression evaluation. In Proceedings of the 1982 ACM symposium on LISP and functional programming (LFP '82). Association for Computing Machinery, New York, NY, USA, 1982, 11–20. https://doi.org/10.1145/800068.802130
[KapurEtAl1981]
D. Kapur, D. R. Musser, and A. A. Stepanov. Operators and algebraic structures. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, pages 59–64. https://doi.org/10.1145/800223.806763
[KiebertzShultis1981]
Richard B. Kieburtz and Jonathan Shultis. Transformations of FP program schemes. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1981, pages 41–48. https://doi.org/10.1145/800223.806761
[Kluge1983]
Werner E. Kluge. Cooperating reduction machines. IEEE Transactions on Computers, C-32(11):1002-1012, November, 1983. https://doi.org/10.1109/TC.1983.1676151
[Koster1980]
A. Koster. An algorithm for translating LISP programs into reduction language programs. In: Robinet, B. (eds) International Symposium on Programming. Programming 1980. Lecture Notes in Computer Science, vol 83. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-09981-6_14
[Koster1985]
Alexis Koster. Compiling APL for parallel execution on an FFP machine. In Proceedings of the international conference on APL: APL and the future (APL '85). Association for Computing Machinery, New York, NY, USA, 1985, pp29–37. https://doi.org/10.1145/17701.255327
[Leszczyłowski1980]
J. Leszczyłowski. On Proving Laws of the Algebra of FP-Systems in Edinburgh LCF. In Proceedings of AAAI-80, 1980, pages 84–86. https://cdn.aaai.org/AAAI/1980/AAAI80-024.pdf
[Leszczyłowski1981]
J. Leszczyłowski. FP systems in Edinburgh LCF. In: Díaz, J., Ramos, I. (eds) Formalization of Programming Concepts. ICFPC 1981. Lecture Notes in Computer Science, vol 107. Springer, Berlin, Heidelberg, 1981. https://doi.org/10.1007/3-540-10699-5_112
[LinLin1988]
Yen-Chun Lin and Ferng-Ching Lin. The use of aFP to design regular array algorithms. Proceedings. 1988 International Conference on Computer Languages, Miami Beach, FL, USA, 1988, pages 388-395. https://doi.org/10.1109/ICCL.1988.13088
[LuoKatayama1990]
Junhui Luo, Takuya Katayama. A Type Inference System for FP Programs. Advances in Software Science and Technology, Elsevier, Volume 1, 1990, Pages 105–131. https://doi.org/10.1016/B978-0-12-037101-3.50012-0
[LichtensteinKaplan1990]
Lichtenstein, N., Kaplan, S. FPL : Functional plus logic programming: an integration of the FP and Prolog languages. In: Kaplan, S., Okada, M. (eds) Conditional and Typed Rewriting Systems. CTRS 1990. Lecture Notes in Computer Science, vol 516. Springer, Berlin, Heidelberg, 1991. https://doi.org/10.1007/3-540-54317-1_98
[Magó1976]
Gyula A. Magó. A network of microprocessors to execute reduction languages. Department fo Computer Science, University of North Carolina, June 1976. PDF
[Magó1981]
Gyula Magó. Copying operands versus copying results: A solution to the problem of large operands in FFP'S. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 93–98. https://doi.org/10.1145/800223.806767
[NguyenEtAl1986]
Van Nguyen, Alan Demers, and Brent Hailpern. FPL: A Functional Parallel Language. RC-11858, IBM Thomas J. Watson Research Center Yorktown Heights, NY 10598, 5 May 1986. https://brent.hailpern.com/wp-content/uploads/2017/03/rc11858.pdf
[Norman1986]
Eric Norman. Tracking the Elusive Eureka. Technical Report TR636, Computer Sciences Department, University of Wisconsin, March 1986. zhttps://minds.wisconsin.edu/handle/1793/58710
[OngEtAl1990]
E. Teng Ong, K. M. George and K. A. Teague. BT-Server FP Interpreter. Proceedings of the Fifth Distributed Memory Computing Conference, 1990, Charleston, SC, USA, 1990, pages 1147-1152. https://doi.org/10.1109/DMCC.1990.556329
[O'Rourke2002]
Sean O'Rourke. Language-FP-0.03, 1 June 2002. https://metacpan.org/release/SEANO/Language-FP-0.03
[Pagan1986]
Frank G. Pagan. On the feasibility of teaching Backus-type functional programming (FP) as a first language. SIGCSE Bull. 18, 3 (Sep 1 1986), 31–35. https://doi.org/10.1145/378905.378929
[Pagan1987]
Frank G. Pagan. A graphical FP language. SIGPLAN Notices. 22, 3 (March 1987), 21–39. https://doi.org/10.1145/24697.24699
[Partain1989]
William Partain. Graph Reduction Without Pointers. Ph.D. Thesis, TR89-045, Department of Computer Science, University of North Carolina at Chapel Hill, December 1989. https://www.cs.unc.edu/techreports/89-045.pdf
[PresnellPargas1981]
H. A. Presnell and R. P. Pargas. Communication along shortest paths in a tree machine. In Proceedings of the 1981 Conference on Functional Programming Languages and Computer Architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 107–114. https://doi.org/10.1145/800223.806769
[Radensky1987]
A Radensky. Lazy evaluation and nondeterminism make Backus' FP-systems more practical. SIGPLAN Not. 22, 4 (April 1987), pages 33–40. https://doi.org/10.1145/24714.24718
[Robison1987a]
Arch D. Robison. A Functional Programming Interpreter. M.S. Thesis, University of Illinois, Urbana-Champaign, January 1987.
[Robison1987b]
Arch D. Robison. Illinois Functional Programming: A Tutorial. BYTE, Volume 12, Number 2, February 1987, page 115–125. PDF
[Robison1987c]
Arch D. Robison. IFP User's Manual. Professional Workstation Research Group Technical Report #7, University of Illinois, Urbana-Champaign, 9 February 1987. ASCII
[Robison1987d]
Arch D. Robison. The Illinois functional programming interpreter. In Papers of the Symposium on Interpreters and interpretive techniques (SIGPLAN '87). Association for Computing Machinery, New York, NY, USA, pages 64–73. https://doi.org/10.1145/29650.29657
[Robison1987e]
Arch D. Robison. IFP source code. 7 July 1987. .zip / https://sources.vsta.org/comp.sources.unix/volume10/ifp/
[RyderPendergrast1988]
B. G. Ryder and J. S. Pendergrast. Experiments in optimizing FP. IEEE Transactions on Software Engineering, vol. 14, no. 4, pages 444–454, April 1988. https://doi.org/10.1109/32.4668
[Seo2016]
Kwang Yul Seo. A Haskell implementation of John Backus's FP (Functional Programming) system. .zip / https://github.com/kseo/fp
[Sheeran1983]
Mary Sheeran. μFP: An Algebraic VLSI Design Language. Ph.D. thesis, PRG39, Oxford University Computing Laboratory, November 1983. https://www.cs.ox.ac.uk/publications/publication3787-abstract.html
[Sheeran1984]
Mary Sheeran. muFP, a language for VLSI design. In Proceedings of the 1984 ACM Symposium on LISP and functional programming (LFP '84). Association for Computing Machinery, New York, NY, USA, 1984, pages 104–112. https://doi.org/10.1145/800055.802026
[Sheeran2025]
Mary Sheeran interview. Programming pioneer with a passion for an inclusive academia. Chalmers University, 5 September 2025. https://www.chalmers.se/en/research/meet-our-scientists/researcher-profiles/programming-pioneer-with-a-passion-for-an-inclusive-academia/
[SrinivasSangal1986]
Y. V. Srinivas and R. Sangal. A generalization of Backus' FP. In: Nori, K.V. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1986. Lecture Notes in Computer Science, vol 241. Springer, Berlin, Heidelberg, 1986. https://doi.org/10.1007/3-540-17179-7_8
[StanatWilliams1981]
Donald F. Stanat and E. Hollins Williams. 1981. Optimal associative searching on a cellular computer. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, pages 99–106. https://doi.org/10.1145/800223.806768
[Stepanov2007]
Alexander Stepanov. Short History of STL. http://www.stepanovpapers.com/history%20of%20STL.pdf Included in: Bjarne Stroustrup. Evolving a language in and for the real world: C++ 1991-2006. In Proceedings of the third ACM SIGPLAN conference on History of programming languages (HOPL III). Association for Computing Machinery, New York, NY, USA, 2007. https://doi.org/10.1145/1238844.1238848
[Sun1988]
Y. Sun. Verification of systolic array: An FP functional approach. J. of Comput. Sci. & Technol. 3, pages 81–101 (1988). https://doi.org/10.1007/BF02943335
[Thomas1988]
Teresa Anne Thomas. The Semantics of an FP Language with Infinite Objects. PhD. thesis, The University of North Carolina at Chapel Hill Department of Computer Science, TR88-022, April 1988. https://www.cs.unc.edu/techreports/88-022.pdf
[ThomasStanat1985]
T. A. Thomas and D. F. Stanat. An FP domain with infinite objects. In: Melton, A. (eds) Mathematical Foundations of Programming Semantics. MFPS 1985. Lecture Notes in Computer Science, vol 239. Springer, Berlin, Heidelberg, 1986. https://doi.org/10.1007/3-540-16816-8_40
[Tolle1981]
Donald MacDavid Tolle. Implanting FFP trees in binary trees: An architectural proposal. In Proceedings of the 1981 conference on Functional programming languages and computer architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA, 1981, pages 115–122. https://doi.org/10.1145/800223.806770
[TsanakasEtAl1992]
Panayotis Tsanakas, George Papakonstantinou, Nikolaos Bilalis. Systematic synthesis of parallel VLSI architectures from FP specifications and its application to scene matching. Microprocessing and Microprogramming, Volume 35, Issues 1–5, 1992, pages 579–586. https://doi.org/10.1016/0165-6074(92)90371-D
[Valencia1986]
Andy Valencia. Stanford FP source code.
[WeiGaudiot1988]
Y.-H. Wei and J.-L. Gaudiot. Demand-driven interpretation of FP programs on a data-flow multiprocessor. In IEEE Transactions on Computers, vol. 37, no. 8, pages 946–966, Aug. 1988. https://doi.org/10.1109/12.2246
[Winkelmann2007]
Felix L. Winkelmann. FP-to-Scheme translator. egg for CHICKEN Scheme 6.
[Winkelmann2009]
Felix L. Winkelmann. Furry Paws FP-to-C translator.
[Winkelmann201x]
Felix L. Winkelmann. muFP-to-Scheme translator. CHICKEN Scheme source code. See [Sheeran1983, 1984]. After 2009. https://codeberg.org/Bunny351/muFP
[ZhangEtAl1988]
Z. Zhang, K. M. George, and G. E. Hedrick. A data flow approach to the evaluation of FP programs. In Proceedings of the 1988 ACM sixteenth annual conference on Computer science (CSC '88). Association for Computing Machinery, New York, 1988, pages 586–592. https://doi.org/10.1145/322609.323131

Related resources

Appendix: People

Changelog