Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs
📜 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.
✨ Summary
Main contribution
John Backus criticizes conventional imperative languages as abstractions closely tied to the von Neumann architecture. He argues that variables, assignment, sequential control flow, and the separation between expressions and statements make programs difficult to compose, transform, verify, and reason about mathematically. The paper proposes an alternative functional, or function-level, style in which programs are constructed from functions and combining forms rather than from assignments and explicitly named variables. (hinkali.com)
The proposed language, FP, operates on structured data and emphasizes composition, construction, selection, application to all elements, insertion, and related higher-order combining mechanisms. Backus presents an algebra of programs in which programs themselves are objects of algebraic manipulation. Equational laws are intended to support program transformation, correctness reasoning, and analysis of termination and behavior. The paper also describes an applicative model of computation and illustrates how larger programs can be built hierarchically from smaller components. (hinkali.com)
Influence
The paper helped establish function-level programming and stimulated subsequent work on FP implementations and related program-transformation techniques. Documented follow-on projects include Berkeley FP, parallel implementations of FP, and Backus’s later work on function-level semantics and optimization. (softwarepreservation.computerhistory.org) The paper is also cited in the Haskell 98 language report, indicating its continuing place in the intellectual history of functional-language research, although Haskell follows the lambda-calculus tradition rather than adopting FP’s exact function-level model. (haskell.org)