13 ms·

Can Programming Be Liberated From The Von Neumann Style? (1977) [pdf]

64 points by jw2013 12y ago

cheepin 12y ago
I feel like "industry" doesn't really want functional style programming to take over. Languages like OCaml provide really great speed while having also utilizing a relatively high abstraction level, while Lisp may not have as much speed but it takes your brain on a journey to another dimension. However, in practice, people seem to just want "C with Lambdas" languages like Go.
- aortega 12y ago
  You know when toddlers try to put a round peg in a square hole? that's how it feels using functional programming in a turing-machine-like CPU. It just don't fit.
  - nnq 12y ago
    If you are far away from the peg and the hole, you use a robotic arm with high strength and poor sensors, and you have blurry vision (this would be the equivalent of the mindset of a high level programmer that lives far away from actual hardware, and I "ashamefully" include myself here), all pegs are pegs, all holes are holes, and the trusty robotic arm dutifully forces any peg into any hole, regardless of their shape :) When you eyes and mind swim in weird Javascript architectures all day, with 70% of stuff happening in the browser and the other half in a high level server-side language VM, monads in Haskell don't feel any less natural than anything else. That's why you see a lot of things like 'lisp to javascript' or 'haskell to javascript' compilers, because at this level, so far away from the actual hardware, the shapes of the pegs and holes don't matter that much (because trusty VMs fit anything into anything) and they are too blurred to distinguish anyway...
    - pekk 12y ago
      They do matter because they affect your control of resource use. We can't just hand-wave away memory issues in Haskell
  - deleted 12y ago
    [deleted]
  - antimagic 12y ago
    "Monads: fitting square pegs in round holes since 1991"
- nnq 12y ago
  Yeah, this is why I'd bet a lot on Go's success. The nice thing is that once you get "C with lambdas" most of the FP abstractions can be brought in. ...what "industry" doesn't like is "deep thinking" in general and anything else that can make programmers less replaceable and interchangeable. The fun thing will be when they'll realize that this is exactly what FP can bring :) ...less side-effects means less time for a programmer to "load a codebase-part into his working memory" and start working productively on a new project he's never seen before. And as a programmer too I tend to like languages that make me replaceable: it's always fun to be able to jump from one project to another and be able to quickly "load it in your mind". Paradoxically, both "retarded OOP" languages like Java, "retarded dynamic" languages like Javascript and "fundamentalist" languages like Haskell give you this. Anything in between, like Ruby or Lisp, forces you to first to load someone else's pseudo-DSL into your mind before being able to start doing productive work on a new project. Dunno about "hybrids" like Scala though... maybe they are a solution, maybe not. EDIT: 'more' -> 'less' in first sentence, sorry... dunno who upvoted before the edit as the message gets kind of reversed :)
- emsy 12y ago
  This is probably going to be unpopular: My main problem with most functional languages is that they encourage cryptic code. From the tutorials I've read Lisp seemed somewhat readable, but the tutorials encouraged me to use list comprehension all over the place because it's so convenient. I need to decrypt all the map zip range calls in order to grasp what's happening. Disclaimer: I don't know if Lisp is used like this in a productive environment. Haskell is often described as "elegant" (Here for instance: http://www.haskell.org/haskellwiki/Why_Haskell_matters#Elegance http://www.haskell.org/haskellwiki/Why_Haskell_matters#Elega...). To me, the examples are far from elegant. They just prove how much functionality one can cramp into an operator. But if I have to decrypt code in order to understand it then the language does it wrong. Math works like that and I never understood why they called variables "x" instead of "potatoes" or "time". It's simply non-descriptive. I don't know if you can write code that is as descriptive as code from an imperative language, but the FP community doesn't encourage it either.
  - throwaway8972d9 12y ago
    User-defined, powerful operators are the most important feature that make programming in Haskell feel so foreign. Yet, since they often require the programmer to sort of grasp a model of the thing the program is trying to accomplish, once you understand the operators (e.g. parser combinators) you have a rather deep understanding of the foundation for this particular program and the rest of the code is expressed very concisely and (sometimes) reasoned about easily. Regarding the short variable names in math: They are supposed to be written and, more importantly, manipulated by hand and so short notation is very important.
    - emsy 12y ago
      This reply goes to axman6 as well: I for one, write code under the assumption that the reader will have to decrypt it in order to understand it. Therefore I postpone implementation details until the very end. This leads to code that outlines the logic in a fairly readable manner. Of course the implementation details are still code, but at that point there is so little code that you will understand it in no time. The Haskell examples of elegance I've seen so far seem to cramp so much responsibilities in so little code, yet nobody seems to bother about the Single Responsibility Principle. I like operator overloading, but I use them for implementation details, not to keep the number of lines small. The downside is that I have a deeply nested programming structure, which can be unfamiliar for people who churn out 500 lines of bare implementation details in one function. My criticism towards math goes further than variable naming. The language of math is non-descriptive and anyone accepts it with the reasons that: a) That's how it's always been. b) It's short and once you get used to it it's easy. But this just keeps people who struggle with the language of math to embrace and love mathematics. I don't say I have a better solution, but I say that we can get in programming right what's wrong in math: a descriptive language with a low entrance barrier.
- pjmlp 12y ago
  > However, in practice, people seem to just want "C with Lambdas" languages like Go. Most likely because that is what is desired by companies that see developers as replaceable cogs, that they can change at will and off-shore to far away galaxies. Languages with better expressive power require people with skillets they aren't willing to pay for and harder to replace.
- CmonDev 12y ago
  The "industry" took OCaml and built F# to make it possible to leverage more of existing libraries and frameworks and make it more approachable - the thing still did not take off. Unfortunately the tools are still missing (e.g. automated refactoring). The academics who are fond of functional languages unfortunately don't like real-world messy things, such as proper IDE support. I personally would have chosen F# over C# had ReSharper for it been available. But not even Roslyn is...
  - pjmlp 12y ago
    > the thing still did not take off. Just look around in the finance and insurance sector for data modeling. Although developers aren't writing full stack applications in OCaml and F#, they surely are writing kernel modules of the applications.
    - CmonDev 12y ago
      "Just look around in the finance and insurance sector for data modeling." That is a very narrow niche.
      - pjmlp 12y ago
        So what?! It is a very profitable one where the languages are currently being used in the industry. I bet they get more used and generate more revenue, than typical Go startup projects that get upvoted here all the time.
deleted 12y ago
[deleted]
signa11 12y ago
i would rather have a mix-n-match of different paradigms based on the task at hand. here is something that works best with an imperative style so let's just use it, for something over-there functional style is best suited, rule-based stuff will be exactly right in this instance, let's use that etc. etc. if you have not seen sussman's 2011 strange-loop talk "We Really Don’t Know How to Compute!", please do, it is quite enlightening (whatever that means)
- ZoF 12y ago
  Here's the talk[0] for anyone wondering; I'm watching it now. Thanks for referencing it, glad I watched it. Edit: So far this is a talk comparing computer systems to the human genome in a somewhat abstract manner. Sussman is the creator of Scheme and wrote SICP. [0]-http://www.infoq.com/presentations/We-Really-Dont-Know-How-To-Compute http://www.infoq.com/presentations/We-Really-Dont-Know-How-T...
- chas 12y ago
  I think the key bit of the title is "Algebra of Programs". This is a piece about being able to calculate programs. In section 12, Backus goes into some detail on how this construction makes algebraic reasoning easier and gives some specific examples. While it is not required to have a pure FP system to have a language that can be reasoned about algebraically, introducing arbitrary ad-hoc iteration will certainly destroy those algebraic properties. I think this ties in well with Erik Meijer's essay from a few days ago[1]. If you are trying to produce a framework for mathematical reasoning, it does not make sense to allow arbitrary exceptions. As a species, humans are pretty new to this whole computing thing, so I would agree we don't have it figured out yet. However, over the last 5000 years or so we have developed a shockingly effective toolkit for reasoning about arbitrarily-defined abstract objects and I don't think it is unreasonable to try to bring those tools to bear on a newer class of abstract object, that is to say programs. The cost of this is that we have to figure out how to formalize our ad-hoc methods. This will be painful, but every engineering discipline does it. In essence, formalized design methods applied to practical problems are the core of engineering practice in general. For example, I think software engineering right now is in the same place as electronic filter design was in the 1920's. We have methods that work, given enough design effort, but our results are brittle and it is very difficult to make changes to working systems without introducing problems. [1] https://news.ycombinator.com/item?id=7654601 https://news.ycombinator.com/item?id=7654601 [2] http://en.wikipedia.org/wiki/Butterworth_filter#Original_paper http://en.wikipedia.org/wiki/Butterworth_filter#Original_pap... Note: I am blown away by Sussman's talk every time I watch it, but I think throwing out math as a tool for understanding computing is very premature given its success as a tool for building and understanding abstraction, especially given that computing as a field started as an attempt to understand some deep questions about the foundations of mathematics.
slacka 12y ago
While we have achieved greatness with the Von Neumann evolutionary line, now that the Mhz free lunch is ending, it’s time for us to recognize that its sequential nature is holding us back. There are still many branches of Computer Science that researchers and industry have barely explored. We need to reevaluate these other branches like Functional and Dataflow programming. Ivan Sutherland explains it best when he says that concurrency is not fundamentally hard. The problem is that we constraining ourselves to the fundamentally sequential Von Neumann architecture. https://www.youtube.com/watch?v=jR9pAaQlVRc#t=267 https://www.youtube.com/watch?v=jR9pAaQlVRc#t=267
- axman6 12y ago
  I feel the Mill architecture is sufficiently familliar while still being quite different that it could help us transition to more interesting/efficient/parallel/concurrent etc. architectures.
- robinh 12y ago
  I agree that concurrency isn't fundamentally hard, but the reason everyone kind of prefers faster serial execution is because a lot of algorithms (extremely simple example: f^100000(x)) are fundamentally unparallelizable. Faster serial execution is just so much more straightforward. So a common problem with concurrency tends to be not "How do I make these functions run in parallel", but "Is there an algorithm that does the same thing I want without relying on constant function composition?"
- userbinator 12y ago
  On the contrary, I think that we haven't exploiting sequential machines to their full potential, and what's "holding us back" is all this theoreticism and overabstraction. There likely is a point where concurrency is really necessary, but one only has to look at the demoscene, full of people who have never formally studied CS, to see something closer to what hardware can really do -- and then wonder how so many others working in software, with formal backgrounds and extensive education in CS, couldn't.
  - weland 12y ago
MarkPNeyer 12y ago
the von neumann architecture is the internal combustion engine of computing. we've made it do some pretty amazing stuff, but it'd be awesome to try something new.
- fractallyte 12y ago
  I think that's a very appropriate (if oblique) 'car analogy'. To extend it further, one might consider an alternative to the ubiquitous IC, the steam engine: external combustion, clean(er), more efficient, multi-fuel... Aside: steam cars were actively developed throughout the 20th century, even advancing to a sports car in the 1960s. The best article I read on this subject was 'Steamer Time?' by Wallace West, in the September 1968 issue of Analog Science Fiction. Fittingly, the same article mentions the concept of 'steam engine time', a term coined by Charles Fort, who "contended that the steamboat was invented only when economic, political, scientific and engineering developments combined to usher in steamboat time."
  - mjcohen 12y ago
    And in the early 60's there was the Dean drive (in Analog).
chubot 12y ago
You know when toddlers try to put a round peg in a square hole? that's how it feels using functional programming in a turing-machine-like CPU. It just don't fit. Yup, I agree. Functional languages failed in part because they modelled the machine poorly (Richard Gabriel has some reflections on Lisp in this area). But the funny thing is that hardware has changed! Imperative programming languages are now the square peg in the round hole :) Multicore machines are going to elaborate lengths to maintain the illusion of a uniform address space. But if we programmed with message passing and heterogeneous processes, then our programs would have more mechanical sympathy for the machine. Shared memory and locks are basically the result of not wanting to disturb too much source code when converting from a single-threaded to a concurrent/parallel program. But it results in poor performance and scalability, not to mention untestable and unmaintainable programs. You can look at the evolution of multicore scalability in the Linux and FreeBSD kernels, or Python and Ruby GILs (coarse grained locks in a Turing machine model), for examples of this. The other thing that has changed is that our hardware is distributed (not just clusters, but also client-server). Networks are fundamentally unreliable, and that means that idempotency of subprograms is a very important property. Idempotency is of course a word from the same area of mathematics that functional programming comes from (abstract algebra). The other algebraic property that is important in distributed systems is commutativity. This basically has to do with physics[1]. Commuter[2] is a nice project which addresses commutativity in interface design. It's not an accident that MapReduce and all the newer big data frameworks are based on the model of functional programming. They are using the imperative model at the scale of a single machine, where its appropriate, but the functional model at the scale of the cluster, so subprograms can be retried and executed in any order. The alternative to explicitly thinking about these properties in your program design is to (only) use slow state machine protocols like Paxos. You could naively apply this transformation to your sequential programs, but you will be making very poor use of the hardware. There is a reason that they are only used for very small bits of state in distributed systems. tl;dr Distributed systems (multicore included) are not Turing machines. I see a lot of bugs that are a result of people in the imperative mindset not understanding this. [1] http://scholar.google.com/scholar?cluster=4892527405117123487&hl=en&as_sdt=0,5&sciodt=0,5 http://scholar.google.com/scholar?cluster=489252740511712348... [2] http://pdos.csail.mit.edu/commuter/ http://pdos.csail.mit.edu/commuter/
picktheorem 12y ago
a note on Haskell's failure to liberate us from imperative IO, with a view towards frp: http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm http://conal.net/blog/posts/can-functional-programming-be-li...
stiff 12y ago
It is funny how this paper like the writings of Dijkstra is widely cherished, while its attitude and conclusions simultaneously are completely ignored. Seems to me that people simply really like to complain about the current state of the matter, how dirty programming is and how everything is inelegant just to get back to churning code a minute later using exactly the style criticized. People like Backus and Dijkstra really wanted to prove theorems about programs and do formal derivations like they were used to do in mathematics, that's practically all they cared for, as far as their writings go. The "liberation" is in fact an act of bondage, an attempt to limit programming techniques to a narrow range to try to get all the noble benefits of mathematics, which is a priori assumed to be the best way to go about reasoning. It's really ironic in the case of Dijkstra, who writes about how people cannot appreciate "radical" novelties and instead keep old mental habits, and then proceeds to argue how programming is just a branch of mathematics. I wonder how many people who mention those papers as cornerstones of CS actually prove their programs correct on a daily basis or derive them from "axioms". I actually think many people in the formal methods camp had a very narrow and limited vision of what programming is and what it will be become, and as a result turned out to be very much wrong about the importance of proofs in programming. Some of them actually admitted it: http://www.gwern.net/docs/1996-hoare.pdf http://www.gwern.net/docs/1996-hoare.pdf In the end, reducing all programming to formal manipulations of this kind turned out to be as successful as the ideas of axiomatization of biology. Formal methods are useful in mission-critical software, functional programming penetrated mainstream languages and is interesting in its own right, but even its proponents hardly go about writing programs the way Backus imagined; mathematical theories of programming turned out to be very limited and yield poor crops compared to the mathematical theories that turned out to be successful, hardly any new insights over what was found earlier by dabbling were found, and that is that. I love math, but it seems that programming, like biology, is actually richer than math in some sense. Consider the example Peter Norvig gives in "Coders at work": how do you prove Google is correct? You immediately run into issues with the very notion of correctness, not everything can be convincingly formalized to the last detail, and we build more and more of those "fuzzy" systems, just consider the rise of machine learning and data mining in the last years. I see no reason to go around pretending programming didn't live up to the noble vision of the ancient masters. The masters were frequently wrong (no shame for they were pioneers of the field and nothing was known), and we simply moved on.
stevesun21 12y ago
If you cannot write code with immutability, then don't try to blame the programming language you are writing has no functional programming feature.

64 points by jw2013 12y ago

I feel like "industry" doesn't really want functional style programming to take over. Languages like OCaml provide really great speed while having also utilizing a relatively high abstraction level, while Lisp may not have as much speed but it takes your brain on a journey to another dimension. However, in practice, people seem to just want "C with Lambdas" languages like Go.

aortega 12y ago
You know when toddlers try to put a round peg in a square hole? that's how it feels using functional programming in a turing-machine-like CPU. It just don't fit.
- nnq 12y ago
  If you are far away from the peg and the hole, you use a robotic arm with high strength and poor sensors, and you have blurry vision (this would be the equivalent of the mindset of a high level programmer that lives far away from actual hardware, and I "ashamefully" include myself here), all pegs are pegs, all holes are holes, and the trusty robotic arm dutifully forces any peg into any hole, regardless of their shape :) When you eyes and mind swim in weird Javascript architectures all day, with 70% of stuff happening in the browser and the other half in a high level server-side language VM, monads in Haskell don't feel any less natural than anything else. That's why you see a lot of things like 'lisp to javascript' or 'haskell to javascript' compilers, because at this level, so far away from the actual hardware, the shapes of the pegs and holes don't matter that much (because trusty VMs fit anything into anything) and they are too blurred to distinguish anyway...
  - pekk 12y ago
    They do matter because they affect your control of resource use. We can't just hand-wave away memory issues in Haskell
- deleted 12y ago
  [deleted]
- antimagic 12y ago
  "Monads: fitting square pegs in round holes since 1991"
nnq 12y ago
Yeah, this is why I'd bet a lot on Go's success. The nice thing is that once you get "C with lambdas" most of the FP abstractions can be brought in. ...what "industry" doesn't like is "deep thinking" in general and anything else that can make programmers less replaceable and interchangeable. The fun thing will be when they'll realize that this is exactly what FP can bring :) ...less side-effects means less time for a programmer to "load a codebase-part into his working memory" and start working productively on a new project he's never seen before. And as a programmer too I tend to like languages that make me replaceable: it's always fun to be able to jump from one project to another and be able to quickly "load it in your mind". Paradoxically, both "retarded OOP" languages like Java, "retarded dynamic" languages like Javascript and "fundamentalist" languages like Haskell give you this. Anything in between, like Ruby or Lisp, forces you to first to load someone else's pseudo-DSL into your mind before being able to start doing productive work on a new project. Dunno about "hybrids" like Scala though... maybe they are a solution, maybe not. EDIT: 'more' -> 'less' in first sentence, sorry... dunno who upvoted before the edit as the message gets kind of reversed :)
emsy 12y ago
This is probably going to be unpopular: My main problem with most functional languages is that they encourage cryptic code. From the tutorials I've read Lisp seemed somewhat readable, but the tutorials encouraged me to use list comprehension all over the place because it's so convenient. I need to decrypt all the map zip range calls in order to grasp what's happening. Disclaimer: I don't know if Lisp is used like this in a productive environment. Haskell is often described as "elegant" (Here for instance: http://www.haskell.org/haskellwiki/Why_Haskell_matters#Elegance http://www.haskell.org/haskellwiki/Why_Haskell_matters#Elega...). To me, the examples are far from elegant. They just prove how much functionality one can cramp into an operator. But if I have to decrypt code in order to understand it then the language does it wrong. Math works like that and I never understood why they called variables "x" instead of "potatoes" or "time". It's simply non-descriptive. I don't know if you can write code that is as descriptive as code from an imperative language, but the FP community doesn't encourage it either.
- throwaway8972d9 12y ago
  User-defined, powerful operators are the most important feature that make programming in Haskell feel so foreign. Yet, since they often require the programmer to sort of grasp a model of the thing the program is trying to accomplish, once you understand the operators (e.g. parser combinators) you have a rather deep understanding of the foundation for this particular program and the rest of the code is expressed very concisely and (sometimes) reasoned about easily. Regarding the short variable names in math: They are supposed to be written and, more importantly, manipulated by hand and so short notation is very important.
  - emsy 12y ago
    This reply goes to axman6 as well: I for one, write code under the assumption that the reader will have to decrypt it in order to understand it. Therefore I postpone implementation details until the very end. This leads to code that outlines the logic in a fairly readable manner. Of course the implementation details are still code, but at that point there is so little code that you will understand it in no time. The Haskell examples of elegance I've seen so far seem to cramp so much responsibilities in so little code, yet nobody seems to bother about the Single Responsibility Principle. I like operator overloading, but I use them for implementation details, not to keep the number of lines small. The downside is that I have a deeply nested programming structure, which can be unfamiliar for people who churn out 500 lines of bare implementation details in one function. My criticism towards math goes further than variable naming. The language of math is non-descriptive and anyone accepts it with the reasons that: a) That's how it's always been. b) It's short and once you get used to it it's easy. But this just keeps people who struggle with the language of math to embrace and love mathematics. I don't say I have a better solution, but I say that we can get in programming right what's wrong in math: a descriptive language with a low entrance barrier.
pjmlp 12y ago
> However, in practice, people seem to just want "C with Lambdas" languages like Go. Most likely because that is what is desired by companies that see developers as replaceable cogs, that they can change at will and off-shore to far away galaxies. Languages with better expressive power require people with skillets they aren't willing to pay for and harder to replace.
CmonDev 12y ago
The "industry" took OCaml and built F# to make it possible to leverage more of existing libraries and frameworks and make it more approachable - the thing still did not take off. Unfortunately the tools are still missing (e.g. automated refactoring). The academics who are fond of functional languages unfortunately don't like real-world messy things, such as proper IDE support. I personally would have chosen F# over C# had ReSharper for it been available. But not even Roslyn is...
- pjmlp 12y ago
  > the thing still did not take off. Just look around in the finance and insurance sector for data modeling. Although developers aren't writing full stack applications in OCaml and F#, they surely are writing kernel modules of the applications.
  - CmonDev 12y ago
    "Just look around in the finance and insurance sector for data modeling." That is a very narrow niche.
    - pjmlp 12y ago
      So what?! It is a very profitable one where the languages are currently being used in the industry. I bet they get more used and generate more revenue, than typical Go startup projects that get upvoted here all the time.

deleted 12y ago

[deleted]

signa11 12y ago

i would rather have a mix-n-match of different paradigms based on the task at hand. here is something that works best with an imperative style so let's just use it, for something over-there functional style is best suited, rule-based stuff will be exactly right in this instance, let's use that etc. etc. if you have not seen sussman's 2011 strange-loop talk "We Really Don’t Know How to Compute!", please do, it is quite enlightening (whatever that means)

ZoF 12y ago
Here's the talk[0] for anyone wondering; I'm watching it now. Thanks for referencing it, glad I watched it. Edit: So far this is a talk comparing computer systems to the human genome in a somewhat abstract manner. Sussman is the creator of Scheme and wrote SICP. [0]-http://www.infoq.com/presentations/We-Really-Dont-Know-How-To-Compute http://www.infoq.com/presentations/We-Really-Dont-Know-How-T...
chas 12y ago
I think the key bit of the title is "Algebra of Programs". This is a piece about being able to calculate programs. In section 12, Backus goes into some detail on how this construction makes algebraic reasoning easier and gives some specific examples. While it is not required to have a pure FP system to have a language that can be reasoned about algebraically, introducing arbitrary ad-hoc iteration will certainly destroy those algebraic properties. I think this ties in well with Erik Meijer's essay from a few days ago[1]. If you are trying to produce a framework for mathematical reasoning, it does not make sense to allow arbitrary exceptions. As a species, humans are pretty new to this whole computing thing, so I would agree we don't have it figured out yet. However, over the last 5000 years or so we have developed a shockingly effective toolkit for reasoning about arbitrarily-defined abstract objects and I don't think it is unreasonable to try to bring those tools to bear on a newer class of abstract object, that is to say programs. The cost of this is that we have to figure out how to formalize our ad-hoc methods. This will be painful, but every engineering discipline does it. In essence, formalized design methods applied to practical problems are the core of engineering practice in general. For example, I think software engineering right now is in the same place as electronic filter design was in the 1920's. We have methods that work, given enough design effort, but our results are brittle and it is very difficult to make changes to working systems without introducing problems. [1] https://news.ycombinator.com/item?id=7654601 https://news.ycombinator.com/item?id=7654601 [2] http://en.wikipedia.org/wiki/Butterworth_filter#Original_paper http://en.wikipedia.org/wiki/Butterworth_filter#Original_pap... Note: I am blown away by Sussman's talk every time I watch it, but I think throwing out math as a tool for understanding computing is very premature given its success as a tool for building and understanding abstraction, especially given that computing as a field started as an attempt to understand some deep questions about the foundations of mathematics.

slacka 12y ago

While we have achieved greatness with the Von Neumann evolutionary line, now that the Mhz free lunch is ending, it’s time for us to recognize that its sequential nature is holding us back. There are still many branches of Computer Science that researchers and industry have barely explored. We need to reevaluate these other branches like Functional and Dataflow programming. Ivan Sutherland explains it best when he says that concurrency is not fundamentally hard. The problem is that we constraining ourselves to the fundamentally sequential Von Neumann architecture. https://www.youtube.com/watch?v=jR9pAaQlVRc#t=267 https://www.youtube.com/watch?v=jR9pAaQlVRc#t=267

axman6 12y ago
I feel the Mill architecture is sufficiently familliar while still being quite different that it could help us transition to more interesting/efficient/parallel/concurrent etc. architectures.
robinh 12y ago
I agree that concurrency isn't fundamentally hard, but the reason everyone kind of prefers faster serial execution is because a lot of algorithms (extremely simple example: f^100000(x)) are fundamentally unparallelizable. Faster serial execution is just so much more straightforward. So a common problem with concurrency tends to be not "How do I make these functions run in parallel", but "Is there an algorithm that does the same thing I want without relying on constant function composition?"
userbinator 12y ago
On the contrary, I think that we haven't exploiting sequential machines to their full potential, and what's "holding us back" is all this theoreticism and overabstraction. There likely is a point where concurrency is really necessary, but one only has to look at the demoscene, full of people who have never formally studied CS, to see something closer to what hardware can really do -- and then wonder how so many others working in software, with formal backgrounds and extensive education in CS, couldn't.
- weland 12y ago

MarkPNeyer 12y ago

the von neumann architecture is the internal combustion engine of computing. we've made it do some pretty amazing stuff, but it'd be awesome to try something new.

fractallyte 12y ago
I think that's a very appropriate (if oblique) 'car analogy'. To extend it further, one might consider an alternative to the ubiquitous IC, the steam engine: external combustion, clean(er), more efficient, multi-fuel... Aside: steam cars were actively developed throughout the 20th century, even advancing to a sports car in the 1960s. The best article I read on this subject was 'Steamer Time?' by Wallace West, in the September 1968 issue of Analog Science Fiction. Fittingly, the same article mentions the concept of 'steam engine time', a term coined by Charles Fort, who "contended that the steamboat was invented only when economic, political, scientific and engineering developments combined to usher in steamboat time."
- mjcohen 12y ago
  And in the early 60's there was the Dean drive (in Analog).

chubot 12y ago

You know when toddlers try to put a round peg in a square hole? that's how it feels using functional programming in a turing-machine-like CPU. It just don't fit. Yup, I agree. Functional languages failed in part because they modelled the machine poorly (Richard Gabriel has some reflections on Lisp in this area). But the funny thing is that hardware has changed! Imperative programming languages are now the square peg in the round hole :) Multicore machines are going to elaborate lengths to maintain the illusion of a uniform address space. But if we programmed with message passing and heterogeneous processes, then our programs would have more mechanical sympathy for the machine. Shared memory and locks are basically the result of not wanting to disturb too much source code when converting from a single-threaded to a concurrent/parallel program. But it results in poor performance and scalability, not to mention untestable and unmaintainable programs. You can look at the evolution of multicore scalability in the Linux and FreeBSD kernels, or Python and Ruby GILs (coarse grained locks in a Turing machine model), for examples of this. The other thing that has changed is that our hardware is distributed (not just clusters, but also client-server). Networks are fundamentally unreliable, and that means that idempotency of subprograms is a very important property. Idempotency is of course a word from the same area of mathematics that functional programming comes from (abstract algebra). The other algebraic property that is important in distributed systems is commutativity. This basically has to do with physics[1]. Commuter[2] is a nice project which addresses commutativity in interface design. It's not an accident that MapReduce and all the newer big data frameworks are based on the model of functional programming. They are using the imperative model at the scale of a single machine, where its appropriate, but the functional model at the scale of the cluster, so subprograms can be retried and executed in any order. The alternative to explicitly thinking about these properties in your program design is to (only) use slow state machine protocols like Paxos. You could naively apply this transformation to your sequential programs, but you will be making very poor use of the hardware. There is a reason that they are only used for very small bits of state in distributed systems. tl;dr Distributed systems (multicore included) are not Turing machines. I see a lot of bugs that are a result of people in the imperative mindset not understanding this. [1] http://scholar.google.com/scholar?cluster=4892527405117123487&hl=en&as_sdt=0,5&sciodt=0,5 http://scholar.google.com/scholar?cluster=489252740511712348... [2] http://pdos.csail.mit.edu/commuter/ http://pdos.csail.mit.edu/commuter/

picktheorem 12y ago

a note on Haskell's failure to liberate us from imperative IO, with a view towards frp: http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm http://conal.net/blog/posts/can-functional-programming-be-li...

stiff 12y ago

It is funny how this paper like the writings of Dijkstra is widely cherished, while its attitude and conclusions simultaneously are completely ignored. Seems to me that people simply really like to complain about the current state of the matter, how dirty programming is and how everything is inelegant just to get back to churning code a minute later using exactly the style criticized. People like Backus and Dijkstra really wanted to prove theorems about programs and do formal derivations like they were used to do in mathematics, that's practically all they cared for, as far as their writings go. The "liberation" is in fact an act of bondage, an attempt to limit programming techniques to a narrow range to try to get all the noble benefits of mathematics, which is a priori assumed to be the best way to go about reasoning. It's really ironic in the case of Dijkstra, who writes about how people cannot appreciate "radical" novelties and instead keep old mental habits, and then proceeds to argue how programming is just a branch of mathematics. I wonder how many people who mention those papers as cornerstones of CS actually prove their programs correct on a daily basis or derive them from "axioms". I actually think many people in the formal methods camp had a very narrow and limited vision of what programming is and what it will be become, and as a result turned out to be very much wrong about the importance of proofs in programming. Some of them actually admitted it: http://www.gwern.net/docs/1996-hoare.pdf http://www.gwern.net/docs/1996-hoare.pdf In the end, reducing all programming to formal manipulations of this kind turned out to be as successful as the ideas of axiomatization of biology. Formal methods are useful in mission-critical software, functional programming penetrated mainstream languages and is interesting in its own right, but even its proponents hardly go about writing programs the way Backus imagined; mathematical theories of programming turned out to be very limited and yield poor crops compared to the mathematical theories that turned out to be successful, hardly any new insights over what was found earlier by dabbling were found, and that is that. I love math, but it seems that programming, like biology, is actually richer than math in some sense. Consider the example Peter Norvig gives in "Coders at work": how do you prove Google is correct? You immediately run into issues with the very notion of correctness, not everything can be convincingly formalized to the last detail, and we build more and more of those "fuzzy" systems, just consider the rise of machine learning and data mining in the last years. I see no reason to go around pretending programming didn't live up to the noble vision of the ancient masters. The masters were frequently wrong (no shame for they were pioneers of the field and nothing was known), and we simply moved on.

stevesun21 12y ago

If you cannot write code with immutability, then don't try to blame the programming language you are writing has no functional programming feature.