https://dl.acm.org/doi/10.1145/359576.359579 ACM Digital Library home ACM home * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search Communications of the ACM * Magazine Home * Latest Issue * * Archive * Authors * About + CACM Affiliations + ACM Award Winners * More HomeMagazinesCommunications of the ACMVol. 21, No. 8Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs article Free Access Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs Share on * Author: * [8110023366]John Backus IBM Research Center, San Jose, CA IBM Research Center, San Jose, CA View Profile * Authors Info & Affiliations Communications of the ACMVolume 21Issue 8Aug. 1978 pp 613-641https:// doi.org/10.1145/359576.359579 Published:01 August 1978 * 1,751citation * 21,326Downloads Metrics Total Citations1,751 Total Downloads21,326 Last 12 Months4,063 Last 6 weeks585 * Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account * Save to Binder Save to Binder [loader] Create a New Binder Name [ ] + Cancel + Create * Export Citation * Publisher Site * eReader * PDF Communications of the ACM Volume 21, Issue 8 PreviousArticleNextArticle ACM Digital Library Abstract 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. References 1. 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.Google ScholarGoogle Scholar 2. 2 Backus, J. Programming language semantics and closed applicative languages. Conf. Record ACM Symp. on Principles of Programming Languages, Boston, Oct. 1973, 71-86. Google Scholar Google ScholarDigital LibraryDigital Library 3. 3 Berkling, K.J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft f'dr Mathematik und Datenverarbeitung MBH, Bonn, Sept. 1976.Google ScholarGoogle Scholar 4. 4 Burge, W.H. Recursive Programming Techniques. Addison- Wesley, Reading, Mass., 1975.Google ScholarGoogle Scholar 5. 5 Church, A. The Calculi of Lambda-Conversion. Princeton U. Press, Princeton, N.J., 1941. Google ScholarGoogle ScholarDigital LibraryDigital Library 6. 6 Curry, H.B., and Feys, R. Combinatory Logic, Vol. 1. North- Holland Pub. Co., Amsterdam, 1958.Google ScholarGoogle Scholar 7. 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.Google ScholarGoogle Scholar 8. 8 Dijkstra, E.W. ,4 Discipline of Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976. Google ScholarGoogle ScholarDigital LibraryDigital Library 9. 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.Google ScholarGoogle Scholar 10. 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. Google ScholarGoogle Scholar Digital LibraryDigital Library 11. 11 Hoare, C.A.R. An axiomatic basis for computer programming. Comm. ,4CM 12, 10 (Oct. 1969), 576-583. Google ScholarGoogle ScholarDigital LibraryDigital Library 12. 12 Iverson, K. A Programming Language. Wiley, New York, 1962. Google ScholarGoogle ScholarDigital LibraryDigital Library 13. 13 Kosinski, P. A data flow programming language. Rep. RC 4264, IBM T.J. Watson Research Ctr., Yorktown Heights, N.Y., March 1973.Google ScholarGoogle Scholar 14. 14 Landin, P.J. The mechanical evaluation of expressions. Computer J. 6, 4 (1964), 308-320.Google ScholarGoogle Scholar Cross RefCross Ref 15. 15 Mag~, G.A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptr. and Inform. Sci.Google ScholarGoogle Scholar 16. 16 Manna, Z., Ness, S., and Vuillemin, J. Inductive methods for proving properties of programs. Comm.4 CM 16,8 (Aug. 1973) 491-502. Google ScholarGoogle ScholarDigital LibraryDigital Library 17. 17 McCarthy, J. Recursive functions of symbolic expressions and their computation by machine, Pt. 1. Comm. ,4CM 3, 4 (April 1960), 184-195. Google ScholarGoogle ScholarDigital Library Digital Library 18. 18 Me Jones, P. A Church-Rosser property of closed applicative languages. Rep. RJ 1589, IBM Res. Lab., San Jose, Calif., May 1975.Google ScholarGoogle Scholar 19. 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. Google ScholarGoogle Scholar Digital LibraryDigital Library 20. 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.Google ScholarGoogle Scholar 21. 21 Scott, D. Outline of a mathematical theory of computation. Proc. 4th Princeton Conf. on Inform. Sci. and Syst., 1970.Google ScholarGoogle Scholar 22. 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.Google ScholarGoogle Scholar 23. 23 Scott, D., and Strachey, C. Towards a mathematical semantics for computer languages. Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn, 1971.Google ScholarGoogle Scholar Index Terms 1. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs 1. Software and its engineering 1. Software notations and tools 1. General programming languages 1. Language types 1. Functional languages Comments Please enable JavaScript to view thecomments powered by Disqus. Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Article * Information * Contributors * Published in Communications of the ACM cover image Communications of the ACM Volume 21, Issue 8 Aug. 1978 84 pages ISSN:0001-0782 EISSN:1557-7317 DOI:10.1145/359576 + Editor: + [default-pr]Robert L. Ashenhurst The Univ. of Chicago, Chicago, IL Issue's Table of Contents Copyright (c) 1978 ACM Sponsors In-Cooperation Publisher Association for Computing Machinery New York, NY, United States Publication History + Published: 1 August 1978 Permissions Request permissions about this article. Request Permissions Author Tags + programming languages + applicative computing systems + program transformation + combining forms + von Neumann languages + algebra of programs + applicative state transition systems + models of computing systems + functional programming + metacomposition + program termination + von Neumann computers + program correctness + functional forms Qualifiers + article Conference Funding Sources * Contributor Metrics Expand All + [811002] John Warner Backus IBM Research - Almaden o Publication Years1954 - 2007 o Publication counts23 o Available for Download12 o Citation count2,775 o Downloads (cumulative)35,335 o Downloads (6 weeks)690 o Downloads (12 months)5,575 o Average Citation per Article121 o Average Downloads per Article2,945 View Full Profile + Author: + [8110023366]John Backus IBM Research Center, San Jose, CA IBM Research Center, San Jose, CA View Profile + Authors Info & Affiliations Other Metrics View Article Metrics * Bibliometrics * Citations1,751 * Article Metrics + 1,751 Total Citations View Citations + 21,326 Total Downloads + Downloads (Last 12 months)4,063 + Downloads (Last 6 weeks)585 Other Metrics View Author Metrics * Cited By PDF Format View or Download as a PDF file. PDF eReader View online with eReader. eReader Digital Edition View this article in digital edition. View Digital Edition * Figures * Other * * Share this Publication link https://dl.acm.org/doi/10.1145/359576.359579 Copy Link Share on Social Media Share on * * * * 0References * * * Close Figure Viewer Browse AllReturnChange zoom level[ ] Caption View Issue's Table of Contents Export Citations Select Citation format[BibTeX ] + Download citation + Copy citation * Preview is not available. By clicking download,a new tab will open to start the export process. The process may takea few minutes but once it finishes a file will be downloaded on your browser soplease do not close the new tab. Download Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact * Facebook * Twitter * Linkedin The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2021 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM home About Cookies On This Site We use cookies to ensure that we give you the best experience on our website. Learn more Got it!