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

Volume

21

Issue

8

Pages

613-641

DOI

10.1145/359576.359579

DOI registrant

Association for Computing Machinery

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

    Supported in partVerified against the work's full text

    Backus contrasts von Neumann for/while loop repetition with loop-free functional combining forms and gives an algebraic iteration theorem, but never frames the two as a duality.

    “these languages provide some primitive combining forms in the statement world--the for, while, and if-then-else statements”

    Read by an automated reader; not a human review. How support was checked

• 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

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 6 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

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