DOI: 10.1145/359576.359579. Can programming be liberated from the von Neumann style?

Can programming be liberated from the von Neumann style?

10.1145/359576.359579

Crossref journal-article

Association for Computing Machinery (ACM)

Communications of the ACM (320)

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.

Bibliography

Backus, J. (1978). Can programming be liberated from the von Neumann style? Communications of the ACM, 21(8), 613â641.

Authors 1

John Backus (first)

References 22 Referenced 1,771

10.1145/512927.512934
Berkling , K.J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft f'dr Mathematik und Datenverarbeitung MBH , Bonn , Sept. 1976 . Berkling, K.J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft f'dr Mathematik und Datenverarbeitung MBH, Bonn, Sept. 1976. / Bonn by Berkling K.J. (1976)
Burge , W.H. Recursive Programming Techniques . Addison- Wesley, Reading , Mass ., 1975 . Burge, W.H. Recursive Programming Techniques. Addison- Wesley, Reading, Mass., 1975. / Recursive Programming Techniques by Burge W.H. (1975)
Church , A. The Calculi of Lambda-Conversion . Princeton U. Press , Princeton, N.J. , 1941 . Church, A. The Calculi of Lambda-Conversion. Princeton U. Press, Princeton, N.J., 1941. / The Calculi of Lambda-Conversion by Church A. (1941)
Curry , H.B. , and Feys , R . Combinatory Logic, Vol. 1 . North- Holland Pub. Co. , Amsterdam , 1958 . Curry, H.B., and Feys, R. Combinatory Logic, Vol. 1. North- Holland Pub. Co., Amsterdam, 1958. / North- Holland Pub. Co. by Curry H.B. (1958)
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 . 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. / Lab. for Comptr. Sci., M.I.T. by Dennis J.B. (1973)
Dijkstra E.W. 4 Discipline of Programming. Prentice-Hall Englewood Cliffs N.J. 1976. Dijkstra E.W. 4 Discipline of Programming. Prentice-Hall Englewood Cliffs N.J. 1976.
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 . 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. / CONS should not evaluate its arguments by Friedman D.P. (1976)
10.1145/800168.811543
10.1145/363235.363259
10.5555/1098666
Kosinski , P. A data flow programming language. Rep. RC 4264 , IBM T.J. Watson Research Ctr. , Yorktown Heights , N.Y. , March 1973 . Kosinski, P. A data flow programming language. Rep. RC 4264, IBM T.J. Watson Research Ctr., Yorktown Heights, N.Y., March 1973. / IBM T.J. Watson Research Ctr. by Kosinski P. (1973)
10.1093/comjnl/6.4.308
Mag~ G.A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptr. and Inform. Sci. Mag~ G.A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptr. and Inform. Sci.
10.1145/355609.362336
10.1145/367177.367199
Me Jones , P. A Church-Rosser property of closed applicative languages. Rep. RJ 1589, IBM Res. Lab., San Jose , Calif. , May 1975 . Me Jones, P. A Church-Rosser property of closed applicative languages. Rep. RJ 1589, IBM Res. Lab., San Jose, Calif., May 1975. / Calif. by Me Jones P. (1975)
10.1145/362349.362364
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 . 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. / Syracuse U. by Reynolds J.C. (1972)
Scott , D. Outline of a mathematical theory of computation . Proc. 4th Princeton Conf. on Inform. Sci. and Syst. , 1970 . Scott, D. Outline of a mathematical theory of computation. Proc. 4th Princeton Conf. on Inform. Sci. and Syst., 1970. / Proc. 4th Princeton Conf. on Inform. Sci. and Syst. by Scott D. (1970)
Scott , D. Lattice-theoretic models for various type-free calculi . Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science , Bucharest , 1972 . Scott, D. Lattice-theoretic models for various type-free calculi. Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972. / Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science by Scott D. (1972)
Scott , D. , and Strachey , C . Towards a mathematical semantics for computer languages . Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn , 1971 . Scott, D., and Strachey, C. Towards a mathematical semantics for computer languages. Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn, 1971. / Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn by Scott D. (1971)

Dates

Type	When
Created	23 years, 1 month ago (July 27, 2002, 7:34 a.m.)
Deposited	2 months, 1 week ago (June 18, 2025, 6:48 p.m.)
Indexed	2 days, 16 hours ago (Aug. 27, 2025, 11:39 a.m.)
Issued	47 years ago (Aug. 1, 1978)
Published	47 years ago (Aug. 1, 1978)
Published Online	47 years ago (Aug. 1, 1978)
Published Print	47 years ago (Aug. 1, 1978)

Funders 0

None

BibTeX

@article{Backus_1978, title={Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs}, volume={21}, ISSN={1557-7317}, url={http://dx.doi.org/10.1145/359576.359579}, DOI={10.1145/359576.359579}, number={8}, journal={Communications of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Backus, John}, year={1978}, month=aug, pages={613–641} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        27
      ]
    ],
    "date-time": "2025-08-27T15:39:22Z",
    "timestamp": 1756309162861,
    "version": "3.41.0"
  },
  "reference-count": 22,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "8",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1978,
            8,
            1
          ]
        ],
        "date-time": "1978-08-01T00:00:00Z",
        "timestamp": 270777600000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        1978,
        8
      ]
    ]
  },
  "abstract": "<jats:p>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\u2014the 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.</jats:p>\n          <jats:p>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.</jats:p>\n          <jats:p>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 \u201cunknowns\u201d 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.</jats:p>\n          <jats:p>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\u2014only one state transition occurs per major computation.</jats:p>",
  "DOI": "10.1145/359576.359579",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:34:59Z",
    "timestamp": 1027769699000
  },
  "page": "613-641",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 1771,
  "title": "Can programming be liberated from the von Neumann style?",
  "prefix": "10.1145",
  "volume": "21",
  "author": [
    {
      "given": "John",
      "family": "Backus",
      "sequence": "first",
      "affiliation": [
        {
          "name": "IBM Research Center, San Jose, CA"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1978,
        8
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/512927.512934"
    },
    {
      "key": "e_1_2_1_3_2",
      "volume-title": "Bonn",
      "author": "Berkling K.J.",
      "year": "1976",
      "unstructured": "Berkling , K.J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft f'dr Mathematik und Datenverarbeitung MBH , Bonn , Sept. 1976 . Berkling, K.J. Reduction languages for reduction machines. Interner Bericht ISF-76-8, Gesellschaft f'dr Mathematik und Datenverarbeitung MBH, Bonn, Sept. 1976."
    },
    {
      "key": "e_1_2_1_4_2",
      "volume-title": "Recursive Programming Techniques",
      "author": "Burge W.H.",
      "year": "1975",
      "unstructured": "Burge , W.H. Recursive Programming Techniques . Addison- Wesley, Reading , Mass ., 1975 . Burge, W.H. Recursive Programming Techniques. Addison- Wesley, Reading, Mass., 1975."
    },
    {
      "key": "e_1_2_1_5_2",
      "volume-title": "The Calculi of Lambda-Conversion",
      "author": "Church A.",
      "year": "1941",
      "unstructured": "Church , A. The Calculi of Lambda-Conversion . Princeton U. Press , Princeton, N.J. , 1941 . Church, A. The Calculi of Lambda-Conversion. Princeton U. Press, Princeton, N.J., 1941."
    },
    {
      "key": "e_1_2_1_6_2",
      "volume-title": "North- Holland Pub. Co.",
      "author": "Curry H.B.",
      "year": "1958",
      "unstructured": "Curry , H.B. , and Feys , R . Combinatory Logic, Vol. 1 . North- Holland Pub. Co. , Amsterdam , 1958 . Curry, H.B., and Feys, R. Combinatory Logic, Vol. 1. North- Holland Pub. Co., Amsterdam, 1958."
    },
    {
      "key": "e_1_2_1_7_2",
      "volume-title": "Lab. for Comptr. Sci., M.I.T.",
      "author": "Dennis J.B.",
      "year": "1973",
      "unstructured": "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 . 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."
    },
    {
      "key": "e_1_2_1_8_2",
      "unstructured": "Dijkstra E.W. 4 Discipline of Programming. Prentice-Hall Englewood Cliffs N.J. 1976.   Dijkstra E.W. 4 Discipline of Programming. Prentice-Hall Englewood Cliffs N.J. 1976."
    },
    {
      "key": "e_1_2_1_9_2",
      "first-page": "257",
      "volume-title": "CONS should not evaluate its arguments",
      "author": "Friedman D.P.",
      "year": "1976",
      "unstructured": "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 . 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."
    },
    {
      "key": "e_1_2_1_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/800168.811543"
    },
    {
      "key": "e_1_2_1_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/363235.363259"
    },
    {
      "key": "e_1_2_1_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1098666"
    },
    {
      "key": "e_1_2_1_13_2",
      "volume-title": "IBM T.J. Watson Research Ctr.",
      "author": "Kosinski P.",
      "year": "1973",
      "unstructured": "Kosinski , P. A data flow programming language. Rep. RC 4264 , IBM T.J. Watson Research Ctr. , Yorktown Heights , N.Y. , March 1973 . Kosinski, P. A data flow programming language. Rep. RC 4264, IBM T.J. Watson Research Ctr., Yorktown Heights, N.Y., March 1973."
    },
    {
      "key": "e_1_2_1_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/comjnl/6.4.308"
    },
    {
      "key": "e_1_2_1_15_2",
      "unstructured": "Mag~ G.A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptr. and Inform. Sci.  Mag~ G.A. A network of microprocessors to execute reduction languages. To appear in Int. J. Comptr. and Inform. Sci."
    },
    {
      "key": "e_1_2_1_16_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/355609.362336"
    },
    {
      "key": "e_1_2_1_17_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/367177.367199"
    },
    {
      "key": "e_1_2_1_18_2",
      "volume-title": "Calif.",
      "author": "Me Jones P.",
      "year": "1975",
      "unstructured": "Me Jones , P. A Church-Rosser property of closed applicative languages. Rep. RJ 1589, IBM Res. Lab., San Jose , Calif. , May 1975 . Me Jones, P. A Church-Rosser property of closed applicative languages. Rep. RJ 1589, IBM Res. Lab., San Jose, Calif., May 1975."
    },
    {
      "key": "e_1_2_1_19_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/362349.362364"
    },
    {
      "key": "e_1_2_1_20_2",
      "volume-title": "Syracuse U.",
      "author": "Reynolds J.C.",
      "year": "1972",
      "unstructured": "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 . 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."
    },
    {
      "key": "e_1_2_1_21_2",
      "volume-title": "Proc. 4th Princeton Conf. on Inform. Sci. and Syst.",
      "author": "Scott D.",
      "year": "1970",
      "unstructured": "Scott , D. Outline of a mathematical theory of computation . Proc. 4th Princeton Conf. on Inform. Sci. and Syst. , 1970 . Scott, D. Outline of a mathematical theory of computation. Proc. 4th Princeton Conf. on Inform. Sci. and Syst., 1970."
    },
    {
      "key": "e_1_2_1_22_2",
      "volume-title": "Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science",
      "author": "Scott D.",
      "year": "1972",
      "unstructured": "Scott , D. Lattice-theoretic models for various type-free calculi . Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science , Bucharest , 1972 . Scott, D. Lattice-theoretic models for various type-free calculi. Proc. Fourth Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972."
    },
    {
      "key": "e_1_2_1_23_2",
      "volume-title": "Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn",
      "author": "Scott D.",
      "year": "1971",
      "unstructured": "Scott , D. , and Strachey , C . Towards a mathematical semantics for computer languages . Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn , 1971 . Scott, D., and Strachey, C. Towards a mathematical semantics for computer languages. Proc. Symp. on Comptrs. and Automata, Polytechnic Inst. of Brooklyn, 1971."
    }
  ],
  "container-title": "Communications of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/359576.359579",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/359576.359579",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T22:48:39Z",
    "timestamp": 1750286919000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/359576.359579"
    }
  },
  "subtitle": [
    "a functional style and its algebra of programs"
  ],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1978,
        8
      ]
    ]
  },
  "references-count": 22,
  "journal-issue": {
    "issue": "8",
    "published-print": {
      "date-parts": [
        [
          1978,
          8
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/359576.359579"
  ],
  "URL": "http://dx.doi.org/10.1145/359576.359579",
  "relation": {},
  "ISSN": [
    "0001-0782",
    "1557-7317"
  ],
  "subject": [],
  "container-title-short": "Commun. ACM",
  "published": {
    "date-parts": [
      [
        1978,
        8
      ]
    ]
  },
  "assertion": [
    {
      "value": "1978-08-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}