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

Backus, J. (1978). Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of the ACM, 21(8), 613-641.

Type

Journal article

Intellectual base

Primary research

Year

1978

DOI

10.1145/359576.359579

Link

https://doi.org/10.1145/359576.359579

Cited from

computer_science, linguistics_semiotics

Cited by

6 citations across 6 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Iteration
  • The imperative-versus-functional iteration duality
• Meta-Symbolic Reflection
  • Listed in the references but not attached to a specific claim.
• Modularity
  • Backus's 1978 Turing lecture on the algebra of programs argued for compositionality in this formal sense: program semantics constructed from a small set of combinators applied to primitive functions.

    This sourceACM Turing Award lecture; introduces an algebra of programs built from combinators applied to primitive functions — the canonical statement of semantic compositionality in programming.

• Recursion
  • A common failure is preferring the recursive form for clarity while paying large computational costs in execution

Domain-specific

• Applicative programming language
  • … core, applying an abstraction to an argument reduces by capture-avoiding substitution, subject to the selected evaluation strategy. to Standard ML organizes much programming around curried functions and application while also providing references, exceptions, and input/output effects. demonstrates that continuity.
• Function-Level Programming
  • Backus contrasted this with value-level or object-level construction, in which existing functions are applied to values and intermediate values are named, combined, and abstracted over to obtain a result.

    This sourceIntroduces FP, its primitive functions and combining forms, the program algebra, and the contrast with von Neumann and lambda-style value-level programming.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:55215fdcca16 · see in the full table