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

John Backus, 1978, Communications of the ACM (Turing Award lecture)

About this paper中文日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

English
Tiếng Việt

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

Có thể giải phóng lập trình khỏi phong cách von Neumann? Một phong cách hàm và đại số của các chương trình

John Backus

Phòng thí nghiệm Nghiên cứu IBM, San Jose

Các ngôn ngữ lập trình truyền thống ngày càng trở nên khổng lồ hơn, nhưng không mạnh hơn. Những khiếm khuyết cố hữu ở mức cơ bản nhất khiến chúng vừa cồng kềnh vừa yếu: phong cách lập trình nguyên thủy theo từng từ một của chúng được thừa hưởng từ tổ tiên chung là máy tính von Neumann, sự gắn kết chặt chẽ của ngữ nghĩa với các chuyển đổi trạng thái, sự phân chia lập trình thành một thế giới của các biểu thức và một thế giới của các câu lệnh, sự bất lực của chúng trong việc sử dụng hiệu quả các dạng kết hợp mạnh để xây dựng các chương trình mới từ những chương trình hiện có, và sự thiếu vắng các tính chất toán học hữu ích để suy luận về các chương trình.

Một phong cách lập trình hàm thay thế được xây dựng dựa trên việc sử dụng các dạng kết hợp để tạo ra các chương trình. Các chương trình hàm xử lý dữ liệu có cấu trúc, thường không lặp lại và không đệ quy, được xây dựng theo thứ bậc, không đặt tên cho các đối số của chúng, và không yêu cầu cơ chế phức tạp của các khai báo thủ tục để trở nên có khả năng áp dụng tổng quát. Các dạng kết hợp có thể sử dụng các chương trình cấp cao để xây dựng những chương trình còn ở cấp cao hơn theo một phong cách không thể có trong các ngôn ngữ truyền thống.

Gắn với phong cách lập trình hàm là một đại số của các chương trình, trong đó các biến của nó lấy giá trị trên các chương trình và các phép toán của nó là các dạng kết hợp. Đại số này có thể được sử dụng để biến đổi các chương trình và giải các phương trình mà các “ẩn số” là các chương trình theo cách rất giống với việc người ta biến đổi các phương trình trong đại số trung học.

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.

References

  1. Arvind, and Gostelow, K.P. A new interpreter for data flow schemas and its implications for computer architecture. Tech. Rep. No. 72, Dept. Comptr. Sci., U. of California, Irvine, Oct. 1975.
  2. Backus, J. Programming language semantics and closed applicative languages. Conf. Record ACM Symp. on Principles of Programming Languages, Boston, Oct. 1973, 71–86.
  3. Berkling, K.J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft für Mathematik und Datenverarbeitung MBH, Bonn, Sept. 1976.
  4. Burge, W.H. Recursive Programming Techniques. Addison-Wesley, Reading, Mass., 1975.
  5. Church, A. The Calculi of Lambda-Conversion. Princeton U. Press, Princeton, N.J., 1941.
  6. Curry, H.B., and Feys, R. Combinatory Logic, Vol. 1. North-Holland Pub. Co., Amsterdam, 1958.
  7. Dennis, J.B. First version of a data flow procedure language. Tech. Mem. No. 61, Lab. for Comptr. Sci., M.I.T., Cambridge, Mass., May 1973.
  8. Dijkstra, E.W. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976.
  9. Friedman, D.P., and Wise, D.S. CONS should not evaluate its arguments. In Automata, Languages and Programming, S. Michaelson and R. Milner, Eds., Edinburgh U. Press, Edinburgh, 1976, pp. 257–284.
  10. Henderson, P., and Morris, J.H. Jr. A lazy evaluator. Conf. Record Third ACM Symp. on Principles of Programming Languages, Atlanta, Ga., Jan. 1976, pp. 95–103.
  11. Hoare, C.A.R. An axiomatic basis for computer programming. Comm. ACM 12, 10 (Oct. 1969), 576–583. Read it here
  12. Iverson, K. A Programming Language. Wiley, New York, 1962.
  13. Kosinski, P. A data flow programming language. Rep. RC 4264, IBM T.J. Watson Research Ctr., Yorktown Heights, N.Y., March 1973.
  14. Landin, P.J. The mechanical evaluation of expressions. Computer J. 6, 4 (1964), 308–320.
  15. Magó, G.A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptr. and Inform. Sci.
  16. Manna, Z., Ness, S., and Vuillemin, J. Inductive methods for proving properties of programs. Comm. ACM 16, 8 (Aug. 1973) 491–502.
  17. McCarthy, J. Recursive functions of symbolic expressions and their computation by machine, Pt. 1. Comm. ACM 3, 4 (April 1960), 184–195.
  18. McJones, P. A Church-Rosser property of closed applicative languages. Rep. RJ 1589, IBM Res. Lab., San Jose, Calif., May 1975.
  19. Reynolds, J.C. GEDANKEN—a simple typeless language based on the principle of completeness and the reference concept. Comm. ACM 13, 5 (May 1970), 308–318.
  20. Reynolds, J.C. Notes on a lattice-theoretic approach to the theory of computation. Dept. Syst. and Inform. Sci., Syracuse U., Syracuse, N.Y., 1972.
  21. Scott, D. Outline of a mathematical theory of computation. Proc. 4th Princeton Conf. on Inform. Sci. and Syst., 1970.
  22. Scott, D. Lattice-theoretic models for various type-free calculi. Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972.
  23. Scott, D., and Strachey, C. Towards a mathematical semantics for computer languages. Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn, 1971.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.