Skip to content
Back to the collection

Can programming be liberated from the von Neumann style?

John Backus

1978 · Communications of the ACM

Read the paper
HN score
0
Mentions
14
Readers
11
Months
11
What’s in a score?

From the 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.

Metadata: Crossref. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

14 selected excerpts · 14 total mentions

nyrikki
Neutral mention · rule
Here is John Backus' original paper[0], which is an easy read, but note what he calls functional programming_ has nothing to do with lambda calculus, Haskel etc... it is the APL family. He is absolutely one of IBM's historical rockstars. IMHO they are invoking him to sell their NorthPole chips which have on-die memory distributed between the processing components and probably has value. > In its simplest form a von Neumann computer has three parts: a central processing unit (or CPU), a store, and a connecting tube that can transmit a single word between the CPU and the store (and send an address to the store). I propose to call this tube the yon Neumann bottleneck. The…
Read the full comment
task of a program is to change the contents of the store in some major way; when one considers that this task must be accomplished entirely by pumping single words back and forth through the von Neumann bottleneck, the reason for its name becomes clear. IMHO IBM is invoking John Backus' work to sell what may be an absolutely great product but are really just ASICs and don't relate to his machine or programming language limits. [0] https://dl.acm.org/doi/pdf/10.1145/359576.359579
123nameuser
Neutral mention · rule
Why everything is inflated and bloated? It is foundational to our computer systems.* There is alternative way, functional programming, that is much harder to learn than Object-Oriented, but makes cleaner code without side effects. So Six/NixOS is very promising and going to install it when I have learned Haskell first to understand it's foundations more deeply. * "Can programming be liberated from the von Neumann style?" https://dl.acm.org/doi/pdf/10.1145/359576.359579
johnnyjeans
Neutral mention · rule
Prolog (and logic programming in general) is much older than you think. In fact, if we take modern functional programming to have been born with John Backus' Turing Award presentation[1], then it even predates it. Many advancements to functional programming were implemented on top of Prolog! Erlang's early versions were built on top of a Prolog-derived language who's name escapes me. It's the source of Erlang's unfamiliar syntax for more unlearned programmers. It's very much like writing Prolog if you had return values and no cuts or complex terms. As for penetrating general use, probably not without a major shift in the industry. But it's a very popular language just on the periphery, even to this day. [1] - https://dl.acm.org/doi/10.1145/359576.359579
malcolmgreaves
Neutral mention · rule
I agree that TypeScript is quite amazing. And that it's indeed improved the programs created that run in the browser or on `node`. However, I wanted to point out something that I think often gets overlooked when folks talk about TypeScript. I'd argue that TS has realized it for the web programming masses, who usually don't have any computer science education and thus are unaware of computing fundamentals such as types. TS hasn't realized the promise of strong typing only because it has been quite late to the game, so to speak. I do think I understand where you're coming from. Web programmers are the largest group of programming-related professionals. Bringing CS wins to…
Read the full comment
this large group absolutely does bring the largest gains and impact to industry. There have been many programming languages created decades before TypeScript that have realized the promise of strong typing. Unfortunately, I think this road took too long. Collectively, people have known about these ideas since John Backus's 1977 Turing Award Lecture [1] -- "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" Anyways, I digress. Hopefully this was insightful! Have a great day :) [1] https://dl.acm.org/doi/pdf/10.1145/359576.359579
sa46
Neutral mention · rule
> I think people get hemmed up talking about what FP is You've defined purely functional programming, which seems to be the increasingly common meaning of FP. The original definitions only explicitly refer to constructing programs by combining functions: A History of Lisp http://jmc.stanford.edu/articles/lisp/lisp.pdf > LISP is characterized by [...] composition of functions as a tool for forming more complex functions. Can programming be liberated from the von Neumann style? https://dl.acm.org/doi/pdf/10.1145/359576.359579 > informal description of a class of simple applicative programming systems called functional programming (FP) systems, in which "programs" are simply functions without variables. However, Backus defines his functional programming system mathematically, which could reasonably be construed as referentially transparent.
mlajtos
Neutral mention · rule
I see FP [0] (and FL [1,2]) as continuations of the original APL vision – an algebra for programs. It is really nice to see this implementation of FP and I hope it will spark interest in the community. :) [0]: https://dl.acm.org/doi/pdf/10.1145/359576.359579 [1]: https://theory.stanford.edu/~aiken/publications/trs/FLProjec... [2]: https://www.youtube.com/watch?v=FxcT4vK01-w
mpweiher
Neutral mention · rule
> If "constraining architecture" means any separation of concerns or interface. It doesn't. It means you work with constraints, for example dataflow constraints. For example: https://dl.acm.org/doi/abs/10.1145/506315.506318 > I also thought the implementation was a little muddled Yes! That was the point of that section of the paper, that doing the straightforward thing leads to a muddle: "At this point, it becomes clear that our original strategy of updating the UI from the individual setter methods is probably not tenable in the long run." A little later: "As we have seen, even a conceptually very simple application such as a temperature converter quickly attracts…
Read the full comment
significant complexity with non-obvious trade-offs once the requirements of an interactive version of that application are taken into account." The fact that you need to create these centralised updater methods is non-obvious, and leads to a bunch of related non-local changes. Also a muddle. "This complexity is not the result of a complicated domain model, but rather of the architectural embellishments required to move data from location to location in order to keep the different parts of the application (model, user interface, persistence) synchronized. In the next section, we will look at a mechanism for simplifying this kind of overhead." > ReactJS (uses HOM like Objective-Smalltalk) ReactJS uses Higher Order Messaging? Where? > Chatty: "We highlight a strong coupling between languages and architecture,..." Which was my point, yes, thank you! We are limited in what languages let us express cleanly. React/SwiftUI etc. are workarounds for this issue: they try to re-cast the GUI "problem" as a simple function/procedure. "The UI is a pure function of the model". If it were true, that would make things very simple. Alas, it isn't true: https://blog.metaobject.com/2018/12/uis-are-not-pure-functio... But even without being true, it makes things very convenient, particularly for simple cases. > Backus (https://dl.acm.org/doi/pdf/10.1145/359576.359579) proposed that FP was possibly preferable. Yep, but he later said that FP was a mistake (Interview with Grady Booch). https://www.youtube.com/watch?t=3896&v=dDsWTyLEgbk&feature=y... > The main problem with presenting FP as a different architecture, is that it's just a bunch of abstractions on top of VNA That is also one of my contentions: FP, procedural and OO are just variants of the call/return architectural style. https://dl.acm.org/doi/10.1145/3397537.3397546 Which is why they are insufficient for today's systems. What's VNA? > you might enjoy watching https://www.youtube.com/watch?v=otAcmD6XEEE Yes, already seen it. Was good. > feature rich FP languages around, aren't popular for GUI development. If there was a tangible benefit, I believe it would have been demonstrated. Yes. There isn't. If you look at the papers, you will see that the benefit isn't so much claimed as assumed: "now we can get the wonders of FP for nasty GUI development". > "And not group little bits of GUI+model together, that way madness lies." - almost every game engine and GUI framework uses it. Yep, and that's why they all share the same problems (roughly "Massive View Controller"). It's not a trivial issue, because reusable widgets definitely make sense, but they lead you down a nasty path. https://blog.metaobject.com/2015/04/model-widget-controller-... You need to treat those widgets as easy-to-use Views, and interact with them largely as if they were just views.
Supermancho
Neutral mention · rule
I will start with a couple clarifications, in good faith. I will admit that I have made lazy errors in this discussion. Specifically in regard to terminology. Afaik, there is no term for "temporally unsynchronized" other than parallelism or concurrency, and I have misused the term concurrency at times. I have also used the term transition to mean "asynchronous state transition". This may clarify my past statements, but I will attempt to do better, going forward. So I'll visit on the material you are most familiar with so that my comments might have the most specific impact or irrelevance. For your verification, I read your paper…
Read the full comment
here: https://www.hpi.uni-potsdam.de/hirschfeld/publications/media... To begin, I agree on the concept. If "constraining architecture" means any separation of concerns or interface. To demonstrate that I did read through the code snippets you provided and completely irrelevant to the points being discussed, I believe there was an error in the code you posted in Listing 8@p.136 - - k: degreesK { self basicC :( degreesF - 273.15. \*wat?\* ivar : ui / celsiusTextField / intValue := self c . ivar : ui / fahrenheitTextField / intValue := self f. } I also thought the implementation was a little muddled and would implement a solution similar to this^. Object subclass: #Temperatures { var c. -changedC : sender { self c: sender intValue. self updateValues: { #val : c, #type: 'Celcius' }. } -changedF : sender { self f: sender intValue. self updateValues: { #val : f, #type: 'Farenheit' }. } -changedK : sender { self k : sender intValue. self updateValues: { #val : k, #type: 'Kelvin' }. } -<void>updateValues: dict { stringValue := dict#type. intValue := dict#val. stringValue = 'Celsius' ifTrue: [self c:= intValue] ifFalse: [ stringValue = 'Farenheit' ifTrue: [self c:= ((intValue-32)*5/9)] ifFalse: [self c:= (intValue-273.15)] ]. self:updateUi. } -<void>updateUi { ivar : ui / celciusTextField / intValue := c. ivar : ui / fahrenheitTextField / intValue := c*5/9+32. ivar : ui / kelvinTextField / intValue := c+273.15. } } ^I don't have all the necessary syntax for Objective-Smalltalk, I have munged in some Smalltalk and made up some dictionary derefence syntax. I other languages, I would construct this differently, with the same overall strategy. After digesting the material, I do not think about the concept of architecture in the way you or Chatty or Backus have been presenting it. In support of this thinking, the idea of seeking the proper GUI abstractions has been sought by most programming language communities. ReactJS (uses HOM like Objective-Smalltalk) or a vanilla actor model^^^, is considered the current state-of-the-art. The MVC layers are most popular in areas where inputs are relatively static within a thread (eg web backend software). In opposition to this thinking, I believe Software Architecture emerges from a combination of mental modeling, language syntax, supported data exchange formats, and resource dependencies/components^^. To some extent, Chatty recognizes this; "We highlight a strong coupling between languages and architecture,..." Backus (https://dl.acm.org/doi/pdf/10.1145/359576.359579) proposed that FP was possibly preferable. The main problem with presenting FP as a different architecture, is that it's just a bunch of abstractions on top of VNA (you might enjoy watching https://www.youtube.com/watch?v=otAcmD6XEEE). Chatty references Turing in 3.1.1@p.6. Ofc Lisp and Occam rely on implicit grouping, in the form of blocks (or any other lexical scope). Fundamentally, FP vs any other style is all the same implementation running on the same kind of machine. A second problem, having to do with specific purpose, is that the side effects in procedural are largely a benefit for the median developer. At each interaction with state, a developer can use a program (that is nothing more than some psuedo-algebraic transforms), into an actor via the consequences of the imperative structure. Lastly, the imperative structure is explicit; although this has started to break down across modern languages. To demonstrate, when using the FP "apply(...)" in Javascript, you can generate outputs that have no explicit inputs (eg https://www.w3schools.com/js/js_function_apply.asp) breaking the input/output paradigm. This is perfectly normal in FP, which (like the Java Spring Framework) makes VNA code harder to reason about by introducing composition of unrelated structures resolving at runtime. This is a step backward for maintainability, reasoning, testing and formalizing. I cannot be convinced that FP is "the future" or is a different software architecture in any meaningful sense. As an aside, Erlang and Haskell, which are the most feature rich FP languages around, aren't popular for GUI development. If there was a tangible benefit, I believe it would have been demonstrated. ^^https://resources.sei.cmu.edu/asset_files/TechnicalReport/19... - M. Shaw's diagrams supposes that design is focused on components. This is partly incorrect. SDA Diagrams, uniformly track information flow, which necessarily involves a multiple components for information to flow between. ^^^"And not group little bits of GUI+model together, that way madness lies." - almost every game engine and GUI framework uses it. Heck, even the Objective-Smalltalk program is taking inputs from non-trivial widgets, which are precisely small GUI+model underneath.
js8
Neutral mention · rule
> which was a bit of an unguided mess at the time Oh, come on. There was https://en.wikipedia.org/wiki/Structured_program_theorem and https://en.wikipedia.org/wiki/Modular_programming. There was a discussion about functional programming, for example famous John Backus article - https://dl.acm.org/doi/pdf/10.1145/359576.359579.
mlajtos
Neutral mention · rule
Well, Python was at the right place at the right time. I am actually happy that array-oriented programming (via Numpy) got mainstream. A lot of great ideas came from sheer number of people doing tinkering and great engineering in this domain. If only people caught on to Iverson's 'Notation as a Tool of Thought' [0] and Backus' 'Can programming be liberated from the von Neumann style? A functional style and its algebra of programs'. [0] https://dl.acm.org/doi/pdf/10.1145/358896.358899 [1] https://dl.acm.org/doi/pdf/10.1145/359576.359579
carapace
Neutral mention · rule
Backus emphasized the algebra of programs in his Turing Award lecture: "Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs" https://amturing.acm.org/award_winners/backus_0703524.cfm https://dl.acm.org/doi/10.1145/359576.359579

Keep following the thread.

More in Programming languages

More from the same topics.

1994arXiv

On proof and progress in mathematics

William P. Thurston

In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.

29 mentions21 months
9HN score
2012arXiv

Geometric Algebra

Eric Chisolm

This is an introduction to geometric algebra, an alternative to traditional vector algebra that expands on it in two ways: 1.

11 mentions10 months
3HN score