Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs

1977 ACM Turing Award Lecture

The 1977 ACM Turing Award was presented to John Backus at the ACM Annual Conference in Seattle, October 17. In introducing the recipient, Jean E. Sammet, Chairman of the Awards Committee, made the following comments and read a portion of the final citation. The full announcement is in the September 1977 issue of Communications, page 681.

"Probably there is nobody in the room who has not heard of Fortran and most of you have probably used it at least once, or at least looked over the shoulder of someone who was writing a Fortran program. There are probably almost as many people who have heard the letters BNF but don't necessarily know what they stand for. Well, the B is for Backus, and the other letters are explained in the formal citation. These two contributions, in my opinion, are among the half dozen most important technical contributions to the computer field and both were made by John Backus (which in the Fortran case also involved some colleagues). It is for these contributions that he is receiving this year's Turing award.

The short form of his citation is 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 specifications of programming languages.'

The most significant part of the full citation is as follows:

'... Backus headed a small IBM group in New York City during the early 1950s. The earliest product of this group's efforts was a high-level language for scientific and technical computations called Fortran. This same group designed the first system to translate Fortran programs into machine language. They employed novel optimizing techniques to generate fast machine-language programs. Many other compilers for the language were developed, first on IBM machines, and later on virtually every make of computer. Fortran was adopted as a U.S. national standard in 1966.

During the latter part of the 1950s, Backus served on the international committees which developed Algol 58 and a later version, Algol 60. The language Algol, and its derivative compilers, received broad acceptance in Europe as a means for developing programs and as a formal means of publishing the algorithms on which the programs are based.

In 1959, Backus presented a paper at the UNESCO conference in Paris on the syntax and semantics of a proposed international algebraic language. In this paper, he was the first to employ a formal technique for specifying the syntax of programming languages. The formal notation became known as BNF—standing for "Backus Normal Form," or "Backus Naur Form" to recognize the further contributions by Peter Naur of Denmark.

Thus, Backus has contributed strongly both to the pragmatic world of problem-solving on computers and to the theoretical world existing at the interface between artificial languages and computational linguistics. Fortran remains one of the most widely used programming languages in the world. Almost all programming languages are now described with some type of formal syntactic definition.'"

Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs

John Backus IBM Research Laboratory, San Jose

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.

An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining forms can use high level programs to build still higher level ones in a style not possible in conventional languages.

Associated with the functional style of programming is an algebra of programs whose variables range over programs and whose operations are combining forms. This algebra can be used to transform programs and to solve equations whose “unknowns” are programs in much the same way one transforms equations in high school algebra. These transformations are given by algebraic laws and are carried out in the same language in which programs are written. Combining forms are chosen not only for their programming power but also for the power of their associated algebraic laws. General theorems of the algebra give the detailed behavior and termination conditions for large classes of programs.

A new class of computing systems uses the functional programming style both in its programming language and in its state transition rules. Unlike von Neumann languages, these systems have semantics loosely coupled to states—only one state transition occurs per major computation.

Key Words and Phrases: functional programming, algebra of programs, combining forms, functional forms, programming languages, von Neumann computers, von Neumann languages, models of computing systems, applicative computing systems, applicative state transition systems, program transformation, program correctness, program termination, metacomposition

CR Categories: 4.20, 4.29, 5.20, 5.24, 5.26

フォン・ノイマン・スタイルからプログラミングを解放できるか？ 関数型スタイルとそのプログラム代数

John Backus

IBM Research Laboratory, San Jose

従来のプログラミング言語はますます巨大になっているが、より強力にはなっていない。最も基本的なレベルに内在する欠陥によって、それらは肥大化すると同時に弱体化している。その欠陥とは、共通の祖先であるフォン・ノイマン・コンピューターから受け継いだ、単語を一つずつ処理する原始的なプログラミング・スタイル、意味論と状態遷移との密接な結合、プログラミングを式の世界と文の世界に分割すること、既存のプログラムから新しいプログラムを構築するための強力な結合形式を効果的に利用できないこと、そしてプログラムについて推論するために有用な数学的性質を欠いていることである。

これに代わる関数型のプログラミング・スタイルは、プログラムを作成するための結合形式の利用を基盤とする。関数型プログラムは構造化データを扱い、多くの場合、反復的でも再帰的でもなく、階層的に構成され、引数に名前を付けず、手続き宣言の複雑な機構を必要とせずに一般的に適用可能となる。結合形式は高水準のプログラムを用いて、従来の言語では不可能なスタイルで、さらに高水準のプログラムを構築できる。

関数型のプログラミング・スタイルには、変数がプログラムの範囲を取り、演算が結合形式であるプログラムの代数が伴う。この代数は、プログラムを変形したり、「未知数」がプログラムである方程式を、高校の代数で方程式を変形するのとほぼ同じ方法で解いたりするために使用できる。

Introduction

This section is missing here.

1 Conventional Programming Languages: Fat and Flabby

This section is missing here.

2 Models of Computing Systems

This section is missing here.

3 Von Neumann Computers

This section is missing here.

4 Von Neumann Languages

This section is missing here.

5 Comparison of von Neumann and Functional Programs

This section is missing here.

6 Language Frameworks versus Changeable Parts

This section is missing here.

7 Changeable Parts and Combining Forms

This section is missing here.

8 APL versus Word-at-a-Time Programming

This section is missing here.

9 Von Neumann Languages Lack Useful Mathematical Properties

This section is missing here.

10 What Are the Alternatives to von Neumann Languages?

This section is missing here.

11 Functional Programming Systems (FP Systems)

This section is missing here.

12 The Algebra of Programs for FP Systems

This section is missing here.

13 Formal Systems for Functional Programming (FFP Systems)

This section is missing here.

14 Applicative State Transition Systems (AST Systems)

This section is missing here.

15 Remarks About Computer Design

This section is missing here.

16 Summary

This section is missing here.