Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs 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 off 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 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. CACM August, 1978 Backus, J. 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 4.20 4.29 5.20 5.24 5.26 CA780801 DH February 7, 1979 3:13 PM 1024 4 3077 1051 4 3077 1102 4 3077 1132 4 3077 1390 4 3077 1486 4 3077 1549 4 3077 1706 4 3077 1826 4 3077 1878 4 3077 378 4 3077 2021 4 3077 2060 4 3077 2155 4 3077 2155 4 3077 2168 4 3077 2222 4 3077 2227 4 3077 2294 4 3077 2315 4 3077 2326 4 3077 2470 4 3077 2558 4 3077 2719 4 3077 2723 4 3077 2732 4 3077 2838 4 3077 2842 4 3077 2842 4 3077 2855 4 3077 2865 4 3077 2879 4 3077 2896 4 3077 2943 4 3077 2981 4 3077 3014 4 3077 3030 4 3077 3068 4 3077 3077 4 3077 3077 4 3077 3077 4 3077 3077 4 3077 3080 4 3077 3104 4 3077 3106 4 3077 3143 4 3077 3150 4 3077 627 4 3077 106 4 3077 210 5 3077 1834 5 3077 2060 5 3077 2457 5 3077 3077 5 3077 3077 5 3077 3077 5 3077