8 ms·

Can Programming Be Liberated from the von Neumann Style? (1978) [pdf]

91 points by beefman 11y ago

jacobolus 11y ago
Why is this discussion using the lecture’s subtitle? The title (“Can Programming Be Liberated from the von Neumann Style?”) is much more recognizable. Anyway, this is a perennial favorite: https://news.ycombinator.com/item?id=768057 https://news.ycombinator.com/item?id=768057 https://news.ycombinator.com/item?id=1033401 https://news.ycombinator.com/item?id=1033401 https://news.ycombinator.com/item?id=1254157 https://news.ycombinator.com/item?id=1254157 https://news.ycombinator.com/item?id=1360017 https://news.ycombinator.com/item?id=1360017 https://news.ycombinator.com/item?id=3126168 https://news.ycombinator.com/item?id=3126168 https://news.ycombinator.com/item?id=5214601 https://news.ycombinator.com/item?id=5214601 https://news.ycombinator.com/item?id=7671379 https://news.ycombinator.com/item?id=7671379 https://news.ycombinator.com/item?id=8821808 https://news.ycombinator.com/item?id=8821808 https://news.ycombinator.com/item?id=9448833 https://news.ycombinator.com/item?id=9448833 Also see https://news.ycombinator.com/item?id=1020230 https://news.ycombinator.com/item?id=1020230
- sctb 11y ago
  We reverted the title from “A Functional Style of Programming and Its Algebra of Programs”.
bitL 11y ago
Why would you call it "liberated"? Stuff like SmallTalk wouldn't be possible if programming was turned into math (and SmallTalk is way too cool by allowing changing any part of its image on the fly and redefine all rules), and frankly I don't understand why mathematicians want to take over a completely different domain, computing. The relation between computing and math is more like the relation between physics and math. It's great to have multiple paradigms, why restrict oneself to a functional one when there is so much more?
- jacobolus 11y ago
  Note that this was the Turing Award lecture by John Backus, who created FORTRAN in the 1950s, and pretty much invented higher-level imperative programming. Before Backus, there was only machine code. Of course he was a mathematician: in those days “computing” didn’t exist as its own separate field. He can hardly be accused of “taking the domain over”.
  - deleted 11y ago
    [deleted]
- smosher_ 11y ago
  > Stuff like SmallTalk wouldn't be possible if programming was turned into math > and frankly I don't understand why mathematicians want to take over a completely different domain I would like to challenge the assumption here: that programming (in whatever mode) can't be adequately described by mathematics. I don't have time to make a thorough argument, but consider this: instead of thinking of what programming would be like as some kind of math, think of what math would need to be like to adequately describe your favourite mode of programming. (Forget arithmetic, consider algebra, geometry.) As for FP: these days it wants all the tools, and it is picking up whatever it can formalize. Some FP tools are uncommon or don't work well outside the paradigm. To me that makes all the difference: I'd feel more restricted working without FP than by being strictly within it.
  - eli_gottlieb 11y ago
    >I would like to challenge the assumption here: that programming (in whatever mode) can't be adequately described by mathematics. Well, the entire lesson of the Halting Problem and Rice's Theorem is that it can't. Indeed, Haskell loves to just cut through the bullshit about math and be inconsistent: bottom inhabits every type, and Type inhabits Type (in Dependent Haskell). No fixed mathematical system is capable of formally verifying all programs, or even all interesting programs. You always need more bits of axioms than of program if you want to prove theorems about your programs (Chaitin's principle, proved formally by Calude). What we can say for FP is that Fast and Loose Reasoning is Morally Correct, and that if we use nicely categorical constructions, then when our programs happen to terminate at all, those nice constructions describe their behavior.
kragen 11y ago
Most of this talk is, in retrospect, embarrassingly wrongheaded, but I think it does point the way toward better approaches. Unfortunately, I still haven't finished writing the counterpoint to it that I began writing in 2007, so I haven't published it yet.
- cousin_it 11y ago
  I'm a big fan of your writings and would be very interested to hear the main points of your argument, even in an unfinished form.
  - kragen 11y ago
    I'm flattered! The unfinished draft is in http://canonical.org/~kragen/tmp/backus-rebuttal http://canonical.org/~kragen/tmp/backus-rebuttal.
    - cousin_it 11y ago
      Thank you! I agree that the original paper is kind of all over the place, that many of its ideas turned out to be not very good, and that garbage collection is a huge productivity aid that covers most of the remaining benefits. Another (possibly controversial) point is that "word-at-a-time" programming is sometimes the clearest solution to a problem, especially when you need to think about time and space complexity. The usual example is Knuth-Morris-Pratt. I wonder how Backus would express it?
      - kragen 11y ago
        Coincidentally, I was investigating a slightly more general version of that question last week, and I found this paper getting a 3× speedup, and more on parallel machines: http://research.microsoft.com/pubs/208237/asplos302-mytkowicz.pdf http://research.microsoft.com/pubs/208237/asplos302-mytkowic... The summary is that once you've computed the KMP state transition function, you compute its prefix sum under composition and then ask at which textual indices it assumes a final state. This abstract description of the KMP algorithm is sufficiently general to cover realizations with different time and space complexity, including not just the purely serial uniprocessor O(N)-time constant-space realization, but also potentially the 3× efficient SIMD realization described in the paper, efficient O(log N)-time parallel realizations and GPGPU realizations; and it is sufficiently specific to automatically derive an efficient realization. An even more interesting question, to me, is what kind of formalism would make it easy to rigorously (and perhaps even automatically) derive KMP and/or BM from the abstract definition of the string search problem and an objective of reducing computation time.
jostmey 11y ago
Liberated implies that today's computers are limited in what they can do, which I disagree with. But I can imagine special purpose machines being constructed to carry out tasks faster than otherwise possible. If we depart from the von Neumann style of computers, we probably won't program these new machines in the traditional sense. I can see, for example, a computer designed to run an artifical neural network at the hardware level being trained on various datasets. In this case, training might be the new way of programming.
- easter6 11y ago
  Today's computers are limited in what they can do, by way of their architecture's constraints. The von Neumann architecture has served us well up to this point, but going forward it's going to be a real handicap. But it isn't just the architecture that needs rethinking. As you say, 'we probably won't program these new machines in the traditional sense'. And you're probably right. Programming languages are also part of the problem. We've wasted so much time reinventing the wheel, over and over again. I don't know what form the next computing architecture will take, but I do know there will come a time when the notion of using a 'programming language' to get things done will seem quaint. Hell, I thought it was an archaic way of doing things 20 years ago, and it's why I didn't pursue a career as a programmer. The tedium was incompatible with my temperament!
  - andars 11y ago
    Do you feel similarly about written language?
    - easter6 11y ago
      A computing architecture doesn't need to use a language. The language is there for our benefit, not the machine's. I'm merely suggesting that all these (by now, countless) languages are getting in the way of efficiency. If we have something in mind that we want the computer to do, why not just do it in hardware directly, as that would provide the most optimal efficiency? I don't 'feel similarly about written language', because written language is kind of important for human communication. Last I checked, human brains have very little in common with computers and our capabilities are not the same as a computer's. We are not computers, we're social organisms. So we need written language. One could even say that we need written language to do 'our work'. Society would fall apart without it. But I guess if there were a better way to communicate or record/relay our thoughts to others, I'd be all for it.
twcooper 11y ago
wut
- twcooper 11y ago
  This stuff goes completely over my head.
segmondy 11y ago
yeah, see declarative languages, they are very liberated from the von neumann style.
nickpsecurity 11y ago
MIT's McCarthy says yes in 1956. Implemented in hardware one year after this paper. :) http://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2 http://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.p...
- nightcracker 11y ago
  No? Lisp is von Neumann.
  - nickpsecurity 11y ago
    Maybe I should've just said Lambda Calculus, which is waht I was thinking. Von Neumann architecture is prevailing implementation of it because Von Neumann machines prevail. However, functions operating on state w/ I/O don't require a CPU or main memory: LISP/Scheme have been directly synthesized to hardware. That means you can describe non-Von Neumann architecture with LISP in a way that produces actual hardware. So, Lambda Calculus being a separate concept and fact that it can use non-Von Neumann implementations mean a Lambda Calculus implementation is non-Von Nuemann but can be if chosen. That's what I was thinking. Unless those with more experience in Lambda Calculus, etc tell me [with evidence] that Lambda Calculus is von-Neumann, so is any LISP/Scheme, and never can be implemented alternatively.
musesum 11y ago
Seems like Backus likes postfix syntax. Same goes with BNF which reserves cardinality at the end. Does anyone consider the first example easier to read? As a mere Human, I find the syntax hard to follow. 1978 was the era when AI provers were solving theorems in hundreds of steps, which was impossible for a Human to follow. So, what are the non-von architectures to play with? GPUs? FPGAs? For GPUs, Cellular Automata is a lot of fun. For FPGAs, perhaps Petri Nets. A classic connectionist book is the Minds of Robots, by Culbertson. What next? Light prisms? How the hell would you program one of those? Or perhaps the problem becomes how to create highly distributed pipelines?
Bonogongo 11y ago
The wording "liberated" is a nice frame. See "George Lakoff: Don't Think of an Elephant"

91 points by beefman 11y ago

Why is this discussion using the lecture’s subtitle? The title (“Can Programming Be Liberated from the von Neumann Style?”) is much more recognizable. Anyway, this is a perennial favorite: https://news.ycombinator.com/item?id=768057 https://news.ycombinator.com/item?id=768057 https://news.ycombinator.com/item?id=1033401 https://news.ycombinator.com/item?id=1033401 https://news.ycombinator.com/item?id=1254157 https://news.ycombinator.com/item?id=1254157 https://news.ycombinator.com/item?id=1360017 https://news.ycombinator.com/item?id=1360017 https://news.ycombinator.com/item?id=3126168 https://news.ycombinator.com/item?id=3126168 https://news.ycombinator.com/item?id=5214601 https://news.ycombinator.com/item?id=5214601 https://news.ycombinator.com/item?id=7671379 https://news.ycombinator.com/item?id=7671379 https://news.ycombinator.com/item?id=8821808 https://news.ycombinator.com/item?id=8821808 https://news.ycombinator.com/item?id=9448833 https://news.ycombinator.com/item?id=9448833 Also see https://news.ycombinator.com/item?id=1020230 https://news.ycombinator.com/item?id=1020230

sctb 11y ago
We reverted the title from “A Functional Style of Programming and Its Algebra of Programs”.

bitL 11y ago

Why would you call it "liberated"? Stuff like SmallTalk wouldn't be possible if programming was turned into math (and SmallTalk is way too cool by allowing changing any part of its image on the fly and redefine all rules), and frankly I don't understand why mathematicians want to take over a completely different domain, computing. The relation between computing and math is more like the relation between physics and math. It's great to have multiple paradigms, why restrict oneself to a functional one when there is so much more?

jacobolus 11y ago
Note that this was the Turing Award lecture by John Backus, who created FORTRAN in the 1950s, and pretty much invented higher-level imperative programming. Before Backus, there was only machine code. Of course he was a mathematician: in those days “computing” didn’t exist as its own separate field. He can hardly be accused of “taking the domain over”.
- deleted 11y ago
  [deleted]
smosher_ 11y ago
> Stuff like SmallTalk wouldn't be possible if programming was turned into math > and frankly I don't understand why mathematicians want to take over a completely different domain I would like to challenge the assumption here: that programming (in whatever mode) can't be adequately described by mathematics. I don't have time to make a thorough argument, but consider this: instead of thinking of what programming would be like as some kind of math, think of what math would need to be like to adequately describe your favourite mode of programming. (Forget arithmetic, consider algebra, geometry.) As for FP: these days it wants all the tools, and it is picking up whatever it can formalize. Some FP tools are uncommon or don't work well outside the paradigm. To me that makes all the difference: I'd feel more restricted working without FP than by being strictly within it.
- eli_gottlieb 11y ago
  >I would like to challenge the assumption here: that programming (in whatever mode) can't be adequately described by mathematics. Well, the entire lesson of the Halting Problem and Rice's Theorem is that it can't. Indeed, Haskell loves to just cut through the bullshit about math and be inconsistent: bottom inhabits every type, and Type inhabits Type (in Dependent Haskell). No fixed mathematical system is capable of formally verifying all programs, or even all interesting programs. You always need more bits of axioms than of program if you want to prove theorems about your programs (Chaitin's principle, proved formally by Calude). What we can say for FP is that Fast and Loose Reasoning is Morally Correct, and that if we use nicely categorical constructions, then when our programs happen to terminate at all, those nice constructions describe their behavior.

kragen 11y ago

Most of this talk is, in retrospect, embarrassingly wrongheaded, but I think it does point the way toward better approaches. Unfortunately, I still haven't finished writing the counterpoint to it that I began writing in 2007, so I haven't published it yet.

cousin_it 11y ago
I'm a big fan of your writings and would be very interested to hear the main points of your argument, even in an unfinished form.
- kragen 11y ago
  I'm flattered! The unfinished draft is in http://canonical.org/~kragen/tmp/backus-rebuttal http://canonical.org/~kragen/tmp/backus-rebuttal.
  - cousin_it 11y ago
    Thank you! I agree that the original paper is kind of all over the place, that many of its ideas turned out to be not very good, and that garbage collection is a huge productivity aid that covers most of the remaining benefits. Another (possibly controversial) point is that "word-at-a-time" programming is sometimes the clearest solution to a problem, especially when you need to think about time and space complexity. The usual example is Knuth-Morris-Pratt. I wonder how Backus would express it?
    - kragen 11y ago
      Coincidentally, I was investigating a slightly more general version of that question last week, and I found this paper getting a 3× speedup, and more on parallel machines: http://research.microsoft.com/pubs/208237/asplos302-mytkowicz.pdf http://research.microsoft.com/pubs/208237/asplos302-mytkowic... The summary is that once you've computed the KMP state transition function, you compute its prefix sum under composition and then ask at which textual indices it assumes a final state. This abstract description of the KMP algorithm is sufficiently general to cover realizations with different time and space complexity, including not just the purely serial uniprocessor O(N)-time constant-space realization, but also potentially the 3× efficient SIMD realization described in the paper, efficient O(log N)-time parallel realizations and GPGPU realizations; and it is sufficiently specific to automatically derive an efficient realization. An even more interesting question, to me, is what kind of formalism would make it easy to rigorously (and perhaps even automatically) derive KMP and/or BM from the abstract definition of the string search problem and an objective of reducing computation time.

jostmey 11y ago

Liberated implies that today's computers are limited in what they can do, which I disagree with. But I can imagine special purpose machines being constructed to carry out tasks faster than otherwise possible. If we depart from the von Neumann style of computers, we probably won't program these new machines in the traditional sense. I can see, for example, a computer designed to run an artifical neural network at the hardware level being trained on various datasets. In this case, training might be the new way of programming.

easter6 11y ago
Today's computers are limited in what they can do, by way of their architecture's constraints. The von Neumann architecture has served us well up to this point, but going forward it's going to be a real handicap. But it isn't just the architecture that needs rethinking. As you say, 'we probably won't program these new machines in the traditional sense'. And you're probably right. Programming languages are also part of the problem. We've wasted so much time reinventing the wheel, over and over again. I don't know what form the next computing architecture will take, but I do know there will come a time when the notion of using a 'programming language' to get things done will seem quaint. Hell, I thought it was an archaic way of doing things 20 years ago, and it's why I didn't pursue a career as a programmer. The tedium was incompatible with my temperament!
- andars 11y ago
  Do you feel similarly about written language?
  - easter6 11y ago
    A computing architecture doesn't need to use a language. The language is there for our benefit, not the machine's. I'm merely suggesting that all these (by now, countless) languages are getting in the way of efficiency. If we have something in mind that we want the computer to do, why not just do it in hardware directly, as that would provide the most optimal efficiency? I don't 'feel similarly about written language', because written language is kind of important for human communication. Last I checked, human brains have very little in common with computers and our capabilities are not the same as a computer's. We are not computers, we're social organisms. So we need written language. One could even say that we need written language to do 'our work'. Society would fall apart without it. But I guess if there were a better way to communicate or record/relay our thoughts to others, I'd be all for it.

twcooper 11y ago

wut

twcooper 11y ago
This stuff goes completely over my head.

segmondy 11y ago

yeah, see declarative languages, they are very liberated from the von neumann style.

nickpsecurity 11y ago

MIT's McCarthy says yes in 1956. Implemented in hardware one year after this paper. :) http://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2 http://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.p...

nightcracker 11y ago
No? Lisp is von Neumann.
- nickpsecurity 11y ago
  Maybe I should've just said Lambda Calculus, which is waht I was thinking. Von Neumann architecture is prevailing implementation of it because Von Neumann machines prevail. However, functions operating on state w/ I/O don't require a CPU or main memory: LISP/Scheme have been directly synthesized to hardware. That means you can describe non-Von Neumann architecture with LISP in a way that produces actual hardware. So, Lambda Calculus being a separate concept and fact that it can use non-Von Neumann implementations mean a Lambda Calculus implementation is non-Von Nuemann but can be if chosen. That's what I was thinking. Unless those with more experience in Lambda Calculus, etc tell me [with evidence] that Lambda Calculus is von-Neumann, so is any LISP/Scheme, and never can be implemented alternatively.

musesum 11y ago

Seems like Backus likes postfix syntax. Same goes with BNF which reserves cardinality at the end. Does anyone consider the first example easier to read? As a mere Human, I find the syntax hard to follow. 1978 was the era when AI provers were solving theorems in hundreds of steps, which was impossible for a Human to follow. So, what are the non-von architectures to play with? GPUs? FPGAs? For GPUs, Cellular Automata is a lot of fun. For FPGAs, perhaps Petri Nets. A classic connectionist book is the Minds of Robots, by Culbertson. What next? Light prisms? How the hell would you program one of those? Or perhaps the problem becomes how to create highly distributed pipelines?

Bonogongo 11y ago

The wording "liberated" is a nice frame. See "George Lakoff: Don't Think of an Elephant"