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 paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

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.

从冯·诺依曼风格中解放编程？一种函数式风格及其程序代数

John Backus

IBM Research Laboratory, San Jose

传统编程语言变得越来越庞大，但并没有变得更强大。在最基本层面固有的缺陷使它们既臃肿又弱小：它们从共同祖先——冯·诺依曼计算机继承而来的原始逐字编程风格，它们将语义与状态转换紧密耦合，它们将编程划分为表达式世界和语句世界，它们无法有效地使用强大的组合形式从已有程序构建新程序，以及它们缺乏用于推理程序的有用数学性质。

一种替代性的函数式编程风格建立在使用组合形式创建程序之上。函数式程序处理结构化数据，通常是非重复和非递归的，以层次方式构造，不命名其参数，并且不需要复杂的过程声明机制即可具有普遍适用性。组合形式可以使用高级程序构建更高级的程序，这种风格是传统语言所无法实现的。

与函数式编程风格相关的是一种程序代数，其中变量的取值范围是程序，其运算是组合形式。该代数可以用于转换程序，并求解其“未知量”为程序的方程，其方式与高中代数中转换方程的方式大致相同。

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. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.