15 ms·

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

202 points by adgasf 10y ago

segmondy 10y ago
It already has, unfortunately it's not too popular. This is why Prolog gives most folks a case of headache. My moment of enlightenment while studying Prolog happened when I realized that I wasn't logical, but trying to solve the problem in Von Neumann style. I was humbled to see simple logic solutions in place of my overly complicated solutions. This has made me such a better developer, I keep my code as declarative as possible.
- honnix 10y ago
  thumb up!
- catnaroek 10y ago
  Prolog is rather imperative. If it were declarative and pure, it wouldn't mandate a specific execution strategy, but rather leave it as an implementation detail - a user-adjustable one, even. In an imperative language (including all functional ones), optimizing a program is rewriting it. In a declarative language, optimizing a program is adjusting the language implementation (e.g., making a smarter SQL query planner). A better argument for declarative languages is the Haskell technique of decoupling the abstract syntax of a DSL (usually a free monad) from its possible interpreters (monad morphisms).
  - _yosefk 10y ago
    SQL is not Prolog though. SQL, at least the parts mapping to relational algebra, is not Turing-complete, Prolog is. I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. In other words, it's not a lie to promise that you can specify a query over tables in a declarative way, but it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Specifying an execution strategy doesn't make it less of a lie but it lets you write a working program kinda looking as if it weren't a lie.
    - catnaroek 10y ago
      > I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. Yup! But it's not as bad as it seems. In a pure logic language, the changing the execution strategy can only change three things: (0) Whether a query terminates, in which case it returns the entire soution set. (1) If the query doesn't terminate, which subset of the solution set is returned. (2) How fast it runs, of course. Which is a lot better than the subtle things that can go wrong when optimizing imperative programs by hand. Selecting an execution strategy for a declarative program is no different from tuning a garbage collector: if you do it wrong, bad things can still happen, but they won't be as bad as if you manage things by hand and do it wrong. > it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Yup! Which leads (IMO) to the conclusion that general-purpose languages must always include some imperative (explicit control) component. Declarative languages really shine as DSLs, though.
    - garyclarke27 10y ago
      SQL is turing complete, at least on Postgres. Case statements provide control of flow and WITH Recursive CTEs provide looping/iteration/recursion. Pure SQL functions can accomplish nearly anything (except dynamic execution, think macros) that procedural PL/pgSQL can, WITH statements provide variables and temp tables. SQL is the most declarative language I'm aware of.
- agumonkey 10y ago
  I have the feeling many schools try to convey the imperative, functional, logic progression scheme, but very few people will either get the love or the wit to follow. FP and Prolog flipped my mind around computing twice. The notion of tasks, stack, processes, programs, function, properties, sets, space, graph traversal, continuations, etc etc all fit in a small framework it's maddening.
- Animats 10y ago
  Oh, Prolog. I once wrote a hardware configuration in Prolog. (Dependency resolution - rules like "An A requires a B or a C".) The configuration part was fine. Trying to write a menu system in pure Prolog, though... Most of the troubles with functional programming come when you actually have to do something. The imperative/functional boundary remains a problem.
  - agumonkey 10y ago
    That was Backus conclusion after his FP forray.
  - tome 10y ago
    > Most of the troubles with functional programming come when you actually have to do something. The imperative/functional boundary remains a problem. How does it remain a problem? I've been writing commercial Haskell programs that do something for years now.
    - Animats 10y ago
      Monads are kind of a hack.[1] [1] http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf http://research.microsoft.com/en-us/um/people/simonpj/papers...
      - dllthomas 10y ago
        "X is a solution to problem Y" doesn't imply that X is a hack. You'll need to be more verbose if you were making a more specific argument.
    - pron 10y ago
      (User-visible, generic) monads are absolutely terrible for expressing effects. That so many people have a hard time understanding them fully shows that it's a real problem of the most serious kind (aside from their inherent shortcomings). That just a vanishingly small portion of developers enjoys working with them is not an indication of a lack of a problem, but rather of its presence. That people in PL research are actively trying to find alternatives to monads (and you have people like Martin Odersky publicly saying they don't like monads) is yet another (though less powerful) indication. That some pure languages like Haskell decided to treat mutation as a side-effect like IO (requiring monads) only exacerbates matters.
- ktRolster 10y ago
  That's really cool to hear.
PaulHoule 10y ago
Yes
adgasf 10y ago
I find funcional languages great for modelling application logic, but when working with graphics cards, printers, web APIs, etc. procedural code is more intuitive. Maybe it's a limitation of my thinking, but I find an impure functional language (C# and F# are good examples) the best fit for most problems.
- dmreedy 10y ago
  I would argue that this is largely because the systems you mention do not have the requisite (hardware or software) functional abstractions required to make them mesh nicely with functional or declarative control* code. Backus here is writing from a hypothetical word in which that is not a problem. --- * a dangerous word in and of itself in such a conversation, because of its imperative significance.
  - nickpeterson 10y ago
    Wouldn't that just place the burden of providing those abstractions on the hardware implementer. In essence, are we not just pushing the problem down the stack?
    - dmreedy 10y ago
      Absolutely; the problem has to go somewhere. It's just the balance of how much semantic weight belongs to the encoder vs. the decoder
hellofunk 10y ago
Well, is not all the new trendiness in functional programming some evidence of the answer to this?
- meira 10y ago
  New to who?
  - mordocai 10y ago
    The industry as a whole
  - adgasf 10y ago
    I used to work in financial services, and functional programming was a very new and alien concept there, even in 2016.
    - willtim 10y ago
      Not in all banks. Standard Chartered and Barclays have probably the largest Haskell codebases in existence. Many others are investing in Scala (e.g. Morgan Stanley). It's probably more of an alien concept to the likes of Google and Amazon.
      - jghn 10y ago
        Google has a fair amount of clojure, or at least they did at one point of time, although it was inherited from an acquisition.
        willtim 10y ago
        Ah yes Clojure, Citigroup had a team of 70+ fulltime Clojure developers in Credit last I heard. The examples I'm giving are all strategic commitments to FP by senior management. The Google situation sounds more likely to be viewed as a "problem" by them as (last I heard), Clojure was not on their white list.
  - 10y ago
jerf 10y ago
The answer was "not while computing was getting exponentially better every year". This sort of improvement curve is really difficult to compete with. It's in the process of being liberated now. GPUs are already deployed in many machines with a fundamentally different architecture. And there's a bubbling foment of alternatives being developed now. In the end, I don't think it was necessarily a case of us getting stuck on "von Neumann" per se... we would have gotten stuck on anything we settled on in the 1960s. And despite familiarity breeding contempt, I'm not that convinced we could have done that much better in the 1960s. A lot of the alternatives are not universally better, they're better in some limited domain but it's not obvious that they are going to uniformly beat von Neumann for general computing, even accounting for the fact that "general computing" has coevolved for 50 years with von Neumann. See also https://news.ycombinator.com/item?id=12155561 https://news.ycombinator.com/item?id=12155561 (which may well have been the inspiration for this submission)
- nickbauman 10y ago
  Now that Moore's Law has effectively ended on a single chip (ended around 2007), FP is front-and-center again, but mostly because of the emphasis on immutability, which is a prerequisite for parallelization. Moore's Law has been replaced with Amdahl's Law.
  - adwn 10y ago
    > Now that Moore's Law has effectively ended on a single chip (ended around 2007), FP is front-and-center again Ah yes, the decades-old claim that FP will make parallel programming much simpler. I wonder when that notion will go the way of "Java will be faster than C because of the JIT compiler" or "Compilers become better and better, so dynamic scripting languages will be quite fast soon." There are two main problems with this sentiment: 1) Immutability does not automatically result in parallelity. If your algorithm is sequential, there's nothing a functional, immutable language can do to help. Oh, and a lot of algorithms are hard or impossible to parallelize efficiently, and even if you can parallelize it in theory, you still have work with limited latency and throughput to other processing elements. 2) Mutable arrays of compact, pointer-less data elements map incredibly well to transistor arrays (SRAM for caches) and transistor/capacitor arrays (DRAM for main memory). > the emphasis on immutability, which is a prerequisite for parallelization This is blatantly false. Basically all parallel algorithms in high-performance-computing make extensive use of mutable memory.
Maultasche 10y ago
When I saw this, I wondered whether this was the same Von Neumann who gave his name to Von Neumann probes, which are hypothetical self-replicating spacecraft that can fill the galaxy within a relatively short timespan. It turns out that this is the same Van Neumann, who appeared to have been very influential in the early days of computing. In reading about him, I was impressed with all the work he'd done. The people who came up with the concept of Von Neumann probes named them after Von Neumann because of his theoretical work regarding how computing machines can self-replicate. Fermi also used the concept of Von Neumann probes and the lack of alien Von Neumann spacecraft as proof that aliens (or at least interstellar spacefaring aliens) don't exist.
- Ar-Curunir 10y ago
  Von Neumann was one of the greatest mathematicians ever. Theoretical physics, computer science, game theory, statistics, he was a master at everything.
- copperx 10y ago
  > In reading about him, I was impressed with all the work he'd done. I think he's considered the smartest man to have ever lived.
  - bordercases 10y ago
    Man? The way I see it, he's the only extraterrestrial we've ever had direct contact with.
    - sevensor 10y ago
      He was nicknamed "the Martian".
- bbctol 10y ago
  Von Neumann was often considered by colleagues to be the smartest person they'd ever met. There's an old story that goes something like this: Von Neumann was asked a mathematical puzzle: two bicyclists start 20 miles apart and head towards each other at a steady speed of 10 mph each. At the same time, a fly that travels at a steady 15 mph starts from the front wheel of the southbound bicycle and heads to the front wheel of the northbound one, then immediately turns around and heads to the wheel of the southbound one, and continues until the bicycles meet and he is crushed. What total distance did the fly travel? The trick is that it seems you'd need to compute an infinite series, figuring out the distance traveled on the first journey, then the second, then the third and sum them all. In fact, you can just realize that two bicycles starting 20 miles away, each moving at 10 miles an hour, will meet in 1 hour; if the fly's traveling at 15 mph constantly during that time, it travels 15 miles. Von Neumann provided the solution immediately. The man who posed it to him said "Oh, you must have heard the trick already!" "What trick?" said von Neumann. "I just summed the geometric series!"
nemo1618 10y ago
I think abandonment of the Von Neumann paradigm will be crucial for AI. For decades we have labored under the misguided assumption that the brain is isomorphic to the Von Neumann architecture, with "memory banks" and "processing units." This approach has failed. Admittedly, Lisp was once the first choice for AI research, and it did not readily lead us into the promised land either. Perhaps a functional approach is not radical enough :)
- visarga 10y ago
  Some of the most interesting applications of ML include recurrent neural nets, that act as processors, augmented with memory and an attention mechanism (memory addressing). They even call them Neural Turing Machines. The fundamental difference is that NTMs are learning from experience, and are not programmed top-down. So there is still a twist in the Von Neumann architecture.
- runeks 10y ago
  > For decades we have labored under the misguided assumption that the brain > is isomorphic to the Von Neumann architecture, with "memory banks" and > "processing units." Who has been working under this assumption for decades? It seems rather obvious to me that this is very far from reality, so I'm a bit surprised if the AI community thought the brain were a CPU for several decades.
  - riboflava 10y ago
    He seems to be under several misconceptions... This one may just be a mutation of the widely accepted idea that we can in principle emulate a brain using our standard computer models, even if it'll take n more decades of hardware advances, the idea that the brain is discretely computable.
- bogomipz 10y ago
  Can you elaborate on why you believe abandoning Von Neuman will be crucial for AI?
- ktRolster 10y ago
mLuby 10y ago
Is functional programming the only other style?
- jsmith0295 10y ago
  it is on HN
- undersuit 10y ago
  The paper describes function-level programming, it is different than functional programming; see the languages APL, K, and J.
  - scottlocklin 10y ago
    Thank you for saying this. I don't think anybody else noticed. In fact, people in the J community occasionally get confused about this as well. Most people shit their pants when confronted with something like FP (Backus language demonstrating these ideas): I know I did when I first encountered J. Much more confusing than ML or Lisp. Still not sure it's the right thing, but for parallel problems it probably is. Kids don't seem to have a problem with it though, so it's probably just old habits. Wiki page for anyone who reads this: https://en.wikipedia.org/wiki/Function-level_programming https://en.wikipedia.org/wiki/Function-level_programming
- PeterisP 10y ago
  There are a bunch of other paradigms, e.g. declarative programming was considered the thing some decades ago; but in general nowadays most domains are best handled by the tools & approaches we have from either the direct imperative simplicity, the OOP camp, or the functional mindset.
  - wtetzner 10y ago
    I think declarative is still preferred, if you can make it work. I think the real issue is coming up with a declarative language that is general purpose and efficient enough. For specific domains, however, declarative languages have done quite well, e.g. SQL, regexps, XPath, etc.
pklausler 10y ago
It's not about liberating programming, it's about liberating programmers by enabling them with more powerful abstractions. And pure lazy statically-typed FP is one hell of a powerful abstraction.
- david927 10y ago
  You can only say the first sentence if you limit yourself to the second sentence. If we go beyond FP, I think you'll find we're going to end up liberating programming.
Razengan 10y ago
I guess one way to approach questions like this, that challenge our fundamentals of Doing Things, is to ask this: Would an alien race be doing the same things? Using electricity, decimals, binary, registers, memory etc. the same way we do? As opposed to say photonics or biochemicals-based computers, trinary or quarternary number systems, belt architectures and so on.. How much of our world has been shaped by simply the ORDER in which we discovered things? If there is only one Right Way of doing things then all the intelligent civilizations out there will eventually use the exact same architectures and have the exact same technology and, personally, that would make for a very boring universe.
- stuxnet79 10y ago
  It's a bit silly but that's exactly the way I tend to approach such questions and my conclusions after musing on the subject for years is that we are hamstrung by the historical ordering of past breakthroughs. Further, it is very difficult to determine the extent to which our current ways of thinking are limiting us.
- marcosdumay 10y ago
  Would an alien race discover things at the same ORDER we did? For most things, I do think the answer is a huge yes. Electronics before photonics is a serious candidate for universal order. We got biochemical computers first, but we don't get an easy way to improve them, again looks probably that this is universal. About binary, yes, that's a theoretical best. If we stop using it some day, it will be only because our physical computers somehow suck at encoding them, or shine a lot on another specific basis. Registers and memory, I have no idea.
topkekz 10y ago
A review of the 1977 Turing Award Lecture by John Backus by Edsger W.Dijkstra https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD692.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...
- chewyshine 10y ago
  This guy's arrogance takes your breath away! Correspondence between Dijkstra and Backus on the Turing award. https://medium.com/@acidflask/this-guys-arrogance-takes-your-breath-away-5b903624ca5f#.5nc69kp8u https://medium.com/@acidflask/this-guys-arrogance-takes-your...
elwell 10y ago
Here's an interesting talk that covers some of these topics: "Erlang Factroy SF 2016 - Keynote - John Hughes - Why Functional Programming Matters" https://www.youtube.com/watch?v=Z35Tt87pIpg https://www.youtube.com/watch?v=Z35Tt87pIpg
dmreedy 10y ago
Note: in the time it took me to write this ramble and also the code review I had to do in between writing and posting, others like catnaroek have addressed similar themes Speculating wildly here, but part of why I think there is continued (albeit unconscious) resistance to other paradigms is that the procedural/imperative paradigm seems to be the most `hackable' of the bunch. I'm not using `hackable' in a positive sense here. Procedural code is bare-level, almost the machine code of programming models. "First do this thing, then do this thing, then do this thing", etc etc. There's a relatively small implicit underlying `physics'[1] in a procedural system. In some sense, every procedural program involves the creation of some higher-order logic (a model) as a part of its construction, in order to both define the state machine, and dictate the manner in which state flows through it. The trick, of course, is that every model has a bias, encodes some manner of thinking. An aspect of that is that it is easier to represent some things and harder to represent others[2]. In a procedural program, when the model you've (consciously or not) developed fails, it's trivial to 'fall out' of the model and revert to writing base-level imperative code, hacking your way to a solution. Functional and other Declarative paradigms, on the other hand, have a stronger, more complex `physics' to them. In the case of declarative, for example, a user is asked only to declare the state machine; the execution of it is left to the `physics' of the system. This can mean that a well-written program in a functional or declarative language appears to be simpler, more elegant. In reality, this is largely because a large set of assumptions that would need to be explicitly declared in a procedural language have been encoded directly into the language itself in the functional/declarative case[3]. This means that when you're operating withing the paradigm that the functional/declarative language affords, everything is smooth, beautiful, elegant, and verifiable according to the physics of the system. However, it's much harder to 'fall out' of the assumed model, because the granularity required to do so isn't at the native resolution of the language. --- [1] By physics, I mean a set of assumptions one needs to make about the behavior of the system that are not directly encoded by the user's input [2] Think of how easy it is to, say, pick up a piece of steak with a fork, and how hard it is to scoop soup with the same implement. Different models have different affordances, recommend different problems, or different solutions to the same problem. [3] As the Church-Turing thesis shows us, these systems -are- equivalent in power, so those semantics still have to be somewhere. To paraphrase Hofstader, there are two kinds of music-playing systems (with a continuum in between). On one end, a system with a different record for each song, and a single record player capable of playing all records. On the other a system with a single records, and a different record player for each song. The difference is how much semantic weight you put on the encoding, and how much you put on the decoding (but they still need to sum to 1)
dharmatech 10y ago
Furry Paws is an "optimizing whole-program compiler and runtime-system for a dialect of John Backus' FP language": http://www.call-with-current-continuation.org/fp/ http://www.call-with-current-continuation.org/fp/
- abecedarius 10y ago
  Here's a much smaller and less ambitious interpreter in Python as a hackable taste of the language: https://github.com/darius/parson/blob/master/eg_fp.py https://github.com/darius/parson/blob/master/eg_fp.py -- or rather another dialect, since everyone who implements FP makes up their own concrete syntax. Mine reads left to right instead of right to left, and leaves out the noisy compose operator (it's implicit by juxtaposition), making it read kind of like Forth or Joy. I also wrote an optimizing compiler to Scheme from this dialect back around 1990, but it's lost in the sands of time.
ozy 10y ago
No. I always wanted to say that to the title of this paper ;) The complaint of van neumann programming langauges, as the paper describes, is that it can only be extended as a framework. Todays imperative languages are much more powerful, either they are untyped (implicitly generic), or they include generics, or at least have objects with polymorphism. The paper puts forward applicative (functional) programming, as a start, because it can be extended much better. The main point, functions can be put together, because you don't have to name, and thus not give types to, the arguments. To make the system complete (useful), he adds a applicative state transition system, or mutable state. Think IO monad. I have a different take. You want systems where everything can be abstracted over. That is, put inside of a function (abstraction). And whatever the system does is truly hidden, unobservable to the outside. That might sound like fp, but it has problems when you want to hide state, or when the abstraction is about input/output. Example: function downloadAndVerify(url): data = http.get(url) hash = http.get(url + ".md5") return data, md5(data) == hash In my opinion, the above expresses what I want. If I need async, my callers need async. If I need IO monad, my callers need IO monad. Neither can hide that. If it blocks, it can be solved the same way as CPU intensive operations, do it in the background. So processes need to be easy. You want a language where any async api can be converted into a blocking api, and any blocking api into an async api. (Using processes, most likely.)
carapace 10y ago
One very important aspect of this paper that I seldom see given proper emphasis is the ability to treat programs algebraically. Also, check out Manfred von Thun's Joy.
sroussey 10y ago
Reminds me that we put so much work into making things "digital", that we forget how many layers of abstraction there are. All the work to add numbers when superposition is instantaneous. It's not just the tyranny of memory, but tyranny of the clock! It will be interesting when we get rid of both...
gavinpc 10y ago
Backus and von Neumann have a history, from their time at IBM. When Backus first proposed the idea of Fortran to his boss, he first "had to overcome the persuasive arguments of von Neumann, who was then a consultant to IBM." In Backus' words: > He didn't see programming as a big problem. I think one of his major objections is that you wouldn't know what you were getting with floating point calculations. You at least knew where trouble was with fixed point if there was trouble. But he wasn't sensitive to the issue of the cost of programming. He really felt that Fortran was a wasted effort.[0] Backus and von Neumann had made innovations in the use of floating-point and fixed-point numbers by computers, respectively. From what I can gather, von Neumann was an incredible genius who just continuously pushed new ideas. He introduced "scaling factors" (fixed point) to solve a scientific problem (in nuclear physics) and didn't worry about improving its "usability." Backus, on the other hand, cared about the difficulty of programming. Both Fortran and his work on floating-point, as well as his later efforts in functional programming, manifested that. After leaving computing altogether, Backus took to meditation and, as he calls it, "living." [0] Quotes are from chapter 1 of Out of Their Minds: the Lives and Discoveries of 15 Great Computer Scientists, by Shasha and Lazere.
ankurdhama 10y ago
You can always come up with some really elegant and expressive formal systems to model programming/computing and thats the mathematics side of things BUT people often ignore the physical/engineering side of things. We need to engineer actual physical systems that can implement those so called elegant formal systems of mathematics. This is where the problem is, engineering a physical systems is a very complex problem with lots of constraints and is not as simple as coming up with a bunch of symbols and rules of a formal system. Physics is about reality and mathematics is about representations, you can create representations from thin air but you cant do that with reality :)
kristianp 10y ago
By the way, Bret Victor's worrydream website references this paper from this page on the talk "The Future of Programming": [1] http://worrydream.com/dbx/ http://worrydream.com/dbx/
mtrn 10y ago
Kanerva has discussed alternative computing styles as well. Especially, he asks, why it is hard to encode intelligence in such a rigid setup. > The disparity in architecture between brains and computers is matched by disparity in performance. Notably, computers excel in routine tasks that we - our brains - accomplish with effort, such as calculation, whereas they are yet to be programmed for universal human traits such as flexible learning, language use, and understanding. He focuses on the representation problem and develops a more flexible representation of concepts with what he called hyperdimensional computing[1]. [1] http://redwood.berkeley.edu/pkanerva/papers/kanerva09-hyperdimensional.pdf http://redwood.berkeley.edu/pkanerva/papers/kanerva09-hyperd...
Tawnyctar 10y ago
Now that Moore's Law has effectively ended on a single chip (ended around 2007), FP is front-and-center again, but mostly because of the emphasis on immutability, which is a prerequisite for parallelization. Moore's Law has been replaced with Amdahl's Law.
Tawnyctar 10y ago
Well, is not all the new trendiness in functional programming some evidence of the answer to this?
jefffoster 10y ago
"Out of the Tarpit" (http://shaffner.us/cs/papers/tarpit.pdf http://shaffner.us/cs/papers/tarpit.pdf) is a paper with a similar bent arguing that we can eliminate complexity with a functional/relational approach to designing software.
qznc 10y ago
Wikipedia argues [0] that we actually use a "Modified Harvard Architecture" instead of a "Von Neumann Architecture" today, since we have a separated data and instruction cache. Also, various embedded chips really separate instructions and data. [0] https://en.wikipedia.org/wiki/Modified_Harvard_architecture https://en.wikipedia.org/wiki/Modified_Harvard_architecture
DonHopkins 10y ago
Not all of von Neumann's architectures were von Neumann architectures [1]. That is to say, not all of the architectures he invented [2] ended up being given the name "von Neumann Architecture". His 29 state cellular automata rule [3] for implementing a universal constructor [2] was "non von Neumann" in the sense of [1]. It's just so amazing what he accomplished with his mind, a pencil, and a piece of paper, without the use of computers, which he also helped invent. [1] https://en.wikipedia.org/wiki/Von_Neumann_architecture https://en.wikipedia.org/wiki/Von_Neumann_architecture [2] https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... [3] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton

202 points by adgasf 10y ago

It already has, unfortunately it's not too popular. This is why Prolog gives most folks a case of headache. My moment of enlightenment while studying Prolog happened when I realized that I wasn't logical, but trying to solve the problem in Von Neumann style. I was humbled to see simple logic solutions in place of my overly complicated solutions. This has made me such a better developer, I keep my code as declarative as possible.

honnix 10y ago
thumb up!
catnaroek 10y ago
Prolog is rather imperative. If it were declarative and pure, it wouldn't mandate a specific execution strategy, but rather leave it as an implementation detail - a user-adjustable one, even. In an imperative language (including all functional ones), optimizing a program is rewriting it. In a declarative language, optimizing a program is adjusting the language implementation (e.g., making a smarter SQL query planner). A better argument for declarative languages is the Haskell technique of decoupling the abstract syntax of a DSL (usually a free monad) from its possible interpreters (monad morphisms).
- _yosefk 10y ago
  SQL is not Prolog though. SQL, at least the parts mapping to relational algebra, is not Turing-complete, Prolog is. I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. In other words, it's not a lie to promise that you can specify a query over tables in a declarative way, but it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Specifying an execution strategy doesn't make it less of a lie but it lets you write a working program kinda looking as if it weren't a lie.
  - catnaroek 10y ago
    > I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. Yup! But it's not as bad as it seems. In a pure logic language, the changing the execution strategy can only change three things: (0) Whether a query terminates, in which case it returns the entire soution set. (1) If the query doesn't terminate, which subset of the solution set is returned. (2) How fast it runs, of course. Which is a lot better than the subtle things that can go wrong when optimizing imperative programs by hand. Selecting an execution strategy for a declarative program is no different from tuning a garbage collector: if you do it wrong, bad things can still happen, but they won't be as bad as if you manage things by hand and do it wrong. > it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Yup! Which leads (IMO) to the conclusion that general-purpose languages must always include some imperative (explicit control) component. Declarative languages really shine as DSLs, though.
  - garyclarke27 10y ago
    SQL is turing complete, at least on Postgres. Case statements provide control of flow and WITH Recursive CTEs provide looping/iteration/recursion. Pure SQL functions can accomplish nearly anything (except dynamic execution, think macros) that procedural PL/pgSQL can, WITH statements provide variables and temp tables. SQL is the most declarative language I'm aware of.
agumonkey 10y ago
I have the feeling many schools try to convey the imperative, functional, logic progression scheme, but very few people will either get the love or the wit to follow. FP and Prolog flipped my mind around computing twice. The notion of tasks, stack, processes, programs, function, properties, sets, space, graph traversal, continuations, etc etc all fit in a small framework it's maddening.
Animats 10y ago
Oh, Prolog. I once wrote a hardware configuration in Prolog. (Dependency resolution - rules like "An A requires a B or a C".) The configuration part was fine. Trying to write a menu system in pure Prolog, though... Most of the troubles with functional programming come when you actually have to do something. The imperative/functional boundary remains a problem.
- agumonkey 10y ago
  That was Backus conclusion after his FP forray.
- tome 10y ago
  > Most of the troubles with functional programming come when you actually have to do something. The imperative/functional boundary remains a problem. How does it remain a problem? I've been writing commercial Haskell programs that do something for years now.
  - Animats 10y ago
    Monads are kind of a hack.[1] [1] http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf http://research.microsoft.com/en-us/um/people/simonpj/papers...
    - dllthomas 10y ago
      "X is a solution to problem Y" doesn't imply that X is a hack. You'll need to be more verbose if you were making a more specific argument.
  - pron 10y ago
    (User-visible, generic) monads are absolutely terrible for expressing effects. That so many people have a hard time understanding them fully shows that it's a real problem of the most serious kind (aside from their inherent shortcomings). That just a vanishingly small portion of developers enjoys working with them is not an indication of a lack of a problem, but rather of its presence. That people in PL research are actively trying to find alternatives to monads (and you have people like Martin Odersky publicly saying they don't like monads) is yet another (though less powerful) indication. That some pure languages like Haskell decided to treat mutation as a side-effect like IO (requiring monads) only exacerbates matters.
ktRolster 10y ago
That's really cool to hear.

PaulHoule 10y ago

Yes

adgasf 10y ago

I find funcional languages great for modelling application logic, but when working with graphics cards, printers, web APIs, etc. procedural code is more intuitive. Maybe it's a limitation of my thinking, but I find an impure functional language (C# and F# are good examples) the best fit for most problems.

dmreedy 10y ago
I would argue that this is largely because the systems you mention do not have the requisite (hardware or software) functional abstractions required to make them mesh nicely with functional or declarative control* code. Backus here is writing from a hypothetical word in which that is not a problem. --- * a dangerous word in and of itself in such a conversation, because of its imperative significance.
- nickpeterson 10y ago
  Wouldn't that just place the burden of providing those abstractions on the hardware implementer. In essence, are we not just pushing the problem down the stack?
  - dmreedy 10y ago
    Absolutely; the problem has to go somewhere. It's just the balance of how much semantic weight belongs to the encoder vs. the decoder

hellofunk 10y ago

Well, is not all the new trendiness in functional programming some evidence of the answer to this?

meira 10y ago
New to who?
- mordocai 10y ago
  The industry as a whole
- adgasf 10y ago
  I used to work in financial services, and functional programming was a very new and alien concept there, even in 2016.
  - willtim 10y ago
    Not in all banks. Standard Chartered and Barclays have probably the largest Haskell codebases in existence. Many others are investing in Scala (e.g. Morgan Stanley). It's probably more of an alien concept to the likes of Google and Amazon.
    - jghn 10y ago
      Google has a fair amount of clojure, or at least they did at one point of time, although it was inherited from an acquisition.
      - willtim 10y ago
        Ah yes Clojure, Citigroup had a team of 70+ fulltime Clojure developers in Credit last I heard. The examples I'm giving are all strategic commitments to FP by senior management. The Google situation sounds more likely to be viewed as a "problem" by them as (last I heard), Clojure was not on their white list.
- 10y ago

jerf 10y ago

The answer was "not while computing was getting exponentially better every year". This sort of improvement curve is really difficult to compete with. It's in the process of being liberated now. GPUs are already deployed in many machines with a fundamentally different architecture. And there's a bubbling foment of alternatives being developed now. In the end, I don't think it was necessarily a case of us getting stuck on "von Neumann" per se... we would have gotten stuck on anything we settled on in the 1960s. And despite familiarity breeding contempt, I'm not that convinced we could have done that much better in the 1960s. A lot of the alternatives are not universally better, they're better in some limited domain but it's not obvious that they are going to uniformly beat von Neumann for general computing, even accounting for the fact that "general computing" has coevolved for 50 years with von Neumann. See also https://news.ycombinator.com/item?id=12155561 https://news.ycombinator.com/item?id=12155561 (which may well have been the inspiration for this submission)

nickbauman 10y ago
Now that Moore's Law has effectively ended on a single chip (ended around 2007), FP is front-and-center again, but mostly because of the emphasis on immutability, which is a prerequisite for parallelization. Moore's Law has been replaced with Amdahl's Law.
- adwn 10y ago
  > Now that Moore's Law has effectively ended on a single chip (ended around 2007), FP is front-and-center again Ah yes, the decades-old claim that FP will make parallel programming much simpler. I wonder when that notion will go the way of "Java will be faster than C because of the JIT compiler" or "Compilers become better and better, so dynamic scripting languages will be quite fast soon." There are two main problems with this sentiment: 1) Immutability does not automatically result in parallelity. If your algorithm is sequential, there's nothing a functional, immutable language can do to help. Oh, and a lot of algorithms are hard or impossible to parallelize efficiently, and even if you can parallelize it in theory, you still have work with limited latency and throughput to other processing elements. 2) Mutable arrays of compact, pointer-less data elements map incredibly well to transistor arrays (SRAM for caches) and transistor/capacitor arrays (DRAM for main memory). > the emphasis on immutability, which is a prerequisite for parallelization This is blatantly false. Basically all parallel algorithms in high-performance-computing make extensive use of mutable memory.

Maultasche 10y ago

When I saw this, I wondered whether this was the same Von Neumann who gave his name to Von Neumann probes, which are hypothetical self-replicating spacecraft that can fill the galaxy within a relatively short timespan. It turns out that this is the same Van Neumann, who appeared to have been very influential in the early days of computing. In reading about him, I was impressed with all the work he'd done. The people who came up with the concept of Von Neumann probes named them after Von Neumann because of his theoretical work regarding how computing machines can self-replicate. Fermi also used the concept of Von Neumann probes and the lack of alien Von Neumann spacecraft as proof that aliens (or at least interstellar spacefaring aliens) don't exist.

Ar-Curunir 10y ago
Von Neumann was one of the greatest mathematicians ever. Theoretical physics, computer science, game theory, statistics, he was a master at everything.
copperx 10y ago
> In reading about him, I was impressed with all the work he'd done. I think he's considered the smartest man to have ever lived.
- bordercases 10y ago
  Man? The way I see it, he's the only extraterrestrial we've ever had direct contact with.
  - sevensor 10y ago
    He was nicknamed "the Martian".
bbctol 10y ago
Von Neumann was often considered by colleagues to be the smartest person they'd ever met. There's an old story that goes something like this: Von Neumann was asked a mathematical puzzle: two bicyclists start 20 miles apart and head towards each other at a steady speed of 10 mph each. At the same time, a fly that travels at a steady 15 mph starts from the front wheel of the southbound bicycle and heads to the front wheel of the northbound one, then immediately turns around and heads to the wheel of the southbound one, and continues until the bicycles meet and he is crushed. What total distance did the fly travel? The trick is that it seems you'd need to compute an infinite series, figuring out the distance traveled on the first journey, then the second, then the third and sum them all. In fact, you can just realize that two bicycles starting 20 miles away, each moving at 10 miles an hour, will meet in 1 hour; if the fly's traveling at 15 mph constantly during that time, it travels 15 miles. Von Neumann provided the solution immediately. The man who posed it to him said "Oh, you must have heard the trick already!" "What trick?" said von Neumann. "I just summed the geometric series!"

nemo1618 10y ago

I think abandonment of the Von Neumann paradigm will be crucial for AI. For decades we have labored under the misguided assumption that the brain is isomorphic to the Von Neumann architecture, with "memory banks" and "processing units." This approach has failed. Admittedly, Lisp was once the first choice for AI research, and it did not readily lead us into the promised land either. Perhaps a functional approach is not radical enough :)

visarga 10y ago
Some of the most interesting applications of ML include recurrent neural nets, that act as processors, augmented with memory and an attention mechanism (memory addressing). They even call them Neural Turing Machines. The fundamental difference is that NTMs are learning from experience, and are not programmed top-down. So there is still a twist in the Von Neumann architecture.
runeks 10y ago
> For decades we have labored under the misguided assumption that the brain > is isomorphic to the Von Neumann architecture, with "memory banks" and > "processing units." Who has been working under this assumption for decades? It seems rather obvious to me that this is very far from reality, so I'm a bit surprised if the AI community thought the brain were a CPU for several decades.
- riboflava 10y ago
  He seems to be under several misconceptions... This one may just be a mutation of the widely accepted idea that we can in principle emulate a brain using our standard computer models, even if it'll take n more decades of hardware advances, the idea that the brain is discretely computable.
bogomipz 10y ago
Can you elaborate on why you believe abandoning Von Neuman will be crucial for AI?
ktRolster 10y ago

mLuby 10y ago

Is functional programming the only other style?

jsmith0295 10y ago
it is on HN
undersuit 10y ago
The paper describes function-level programming, it is different than functional programming; see the languages APL, K, and J.
- scottlocklin 10y ago
  Thank you for saying this. I don't think anybody else noticed. In fact, people in the J community occasionally get confused about this as well. Most people shit their pants when confronted with something like FP (Backus language demonstrating these ideas): I know I did when I first encountered J. Much more confusing than ML or Lisp. Still not sure it's the right thing, but for parallel problems it probably is. Kids don't seem to have a problem with it though, so it's probably just old habits. Wiki page for anyone who reads this: https://en.wikipedia.org/wiki/Function-level_programming https://en.wikipedia.org/wiki/Function-level_programming
PeterisP 10y ago
There are a bunch of other paradigms, e.g. declarative programming was considered the thing some decades ago; but in general nowadays most domains are best handled by the tools & approaches we have from either the direct imperative simplicity, the OOP camp, or the functional mindset.
- wtetzner 10y ago
  I think declarative is still preferred, if you can make it work. I think the real issue is coming up with a declarative language that is general purpose and efficient enough. For specific domains, however, declarative languages have done quite well, e.g. SQL, regexps, XPath, etc.

pklausler 10y ago

It's not about liberating programming, it's about liberating programmers by enabling them with more powerful abstractions. And pure lazy statically-typed FP is one hell of a powerful abstraction.

david927 10y ago
You can only say the first sentence if you limit yourself to the second sentence. If we go beyond FP, I think you'll find we're going to end up liberating programming.

Razengan 10y ago

I guess one way to approach questions like this, that challenge our fundamentals of Doing Things, is to ask this: Would an alien race be doing the same things? Using electricity, decimals, binary, registers, memory etc. the same way we do? As opposed to say photonics or biochemicals-based computers, trinary or quarternary number systems, belt architectures and so on.. How much of our world has been shaped by simply the ORDER in which we discovered things? If there is only one Right Way of doing things then all the intelligent civilizations out there will eventually use the exact same architectures and have the exact same technology and, personally, that would make for a very boring universe.

stuxnet79 10y ago
It's a bit silly but that's exactly the way I tend to approach such questions and my conclusions after musing on the subject for years is that we are hamstrung by the historical ordering of past breakthroughs. Further, it is very difficult to determine the extent to which our current ways of thinking are limiting us.
marcosdumay 10y ago
Would an alien race discover things at the same ORDER we did? For most things, I do think the answer is a huge yes. Electronics before photonics is a serious candidate for universal order. We got biochemical computers first, but we don't get an easy way to improve them, again looks probably that this is universal. About binary, yes, that's a theoretical best. If we stop using it some day, it will be only because our physical computers somehow suck at encoding them, or shine a lot on another specific basis. Registers and memory, I have no idea.

topkekz 10y ago

A review of the 1977 Turing Award Lecture by John Backus by Edsger W.Dijkstra https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD692.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/E...

chewyshine 10y ago
This guy's arrogance takes your breath away! Correspondence between Dijkstra and Backus on the Turing award. https://medium.com/@acidflask/this-guys-arrogance-takes-your-breath-away-5b903624ca5f#.5nc69kp8u https://medium.com/@acidflask/this-guys-arrogance-takes-your...

elwell 10y ago

Here's an interesting talk that covers some of these topics: "Erlang Factroy SF 2016 - Keynote - John Hughes - Why Functional Programming Matters" https://www.youtube.com/watch?v=Z35Tt87pIpg https://www.youtube.com/watch?v=Z35Tt87pIpg

dmreedy 10y ago

Note: in the time it took me to write this ramble and also the code review I had to do in between writing and posting, others like catnaroek have addressed similar themes Speculating wildly here, but part of why I think there is continued (albeit unconscious) resistance to other paradigms is that the procedural/imperative paradigm seems to be the most `hackable' of the bunch. I'm not using `hackable' in a positive sense here. Procedural code is bare-level, almost the machine code of programming models. "First do this thing, then do this thing, then do this thing", etc etc. There's a relatively small implicit underlying `physics'[1] in a procedural system. In some sense, every procedural program involves the creation of some higher-order logic (a model) as a part of its construction, in order to both define the state machine, and dictate the manner in which state flows through it. The trick, of course, is that every model has a bias, encodes some manner of thinking. An aspect of that is that it is easier to represent some things and harder to represent others[2]. In a procedural program, when the model you've (consciously or not) developed fails, it's trivial to 'fall out' of the model and revert to writing base-level imperative code, hacking your way to a solution. Functional and other Declarative paradigms, on the other hand, have a stronger, more complex `physics' to them. In the case of declarative, for example, a user is asked only to declare the state machine; the execution of it is left to the `physics' of the system. This can mean that a well-written program in a functional or declarative language appears to be simpler, more elegant. In reality, this is largely because a large set of assumptions that would need to be explicitly declared in a procedural language have been encoded directly into the language itself in the functional/declarative case[3]. This means that when you're operating withing the paradigm that the functional/declarative language affords, everything is smooth, beautiful, elegant, and verifiable according to the physics of the system. However, it's much harder to 'fall out' of the assumed model, because the granularity required to do so isn't at the native resolution of the language. --- [1] By physics, I mean a set of assumptions one needs to make about the behavior of the system that are not directly encoded by the user's input [2] Think of how easy it is to, say, pick up a piece of steak with a fork, and how hard it is to scoop soup with the same implement. Different models have different affordances, recommend different problems, or different solutions to the same problem. [3] As the Church-Turing thesis shows us, these systems -are- equivalent in power, so those semantics still have to be somewhere. To paraphrase Hofstader, there are two kinds of music-playing systems (with a continuum in between). On one end, a system with a different record for each song, and a single record player capable of playing all records. On the other a system with a single records, and a different record player for each song. The difference is how much semantic weight you put on the encoding, and how much you put on the decoding (but they still need to sum to 1)

dharmatech 10y ago

Furry Paws is an "optimizing whole-program compiler and runtime-system for a dialect of John Backus' FP language": http://www.call-with-current-continuation.org/fp/ http://www.call-with-current-continuation.org/fp/

abecedarius 10y ago
Here's a much smaller and less ambitious interpreter in Python as a hackable taste of the language: https://github.com/darius/parson/blob/master/eg_fp.py https://github.com/darius/parson/blob/master/eg_fp.py -- or rather another dialect, since everyone who implements FP makes up their own concrete syntax. Mine reads left to right instead of right to left, and leaves out the noisy compose operator (it's implicit by juxtaposition), making it read kind of like Forth or Joy. I also wrote an optimizing compiler to Scheme from this dialect back around 1990, but it's lost in the sands of time.

ozy 10y ago

No. I always wanted to say that to the title of this paper ;) The complaint of van neumann programming langauges, as the paper describes, is that it can only be extended as a framework. Todays imperative languages are much more powerful, either they are untyped (implicitly generic), or they include generics, or at least have objects with polymorphism. The paper puts forward applicative (functional) programming, as a start, because it can be extended much better. The main point, functions can be put together, because you don't have to name, and thus not give types to, the arguments. To make the system complete (useful), he adds a applicative state transition system, or mutable state. Think IO monad. I have a different take. You want systems where everything can be abstracted over. That is, put inside of a function (abstraction). And whatever the system does is truly hidden, unobservable to the outside. That might sound like fp, but it has problems when you want to hide state, or when the abstraction is about input/output. Example: function downloadAndVerify(url): data = http.get(url) hash = http.get(url + ".md5") return data, md5(data) == hash In my opinion, the above expresses what I want. If I need async, my callers need async. If I need IO monad, my callers need IO monad. Neither can hide that. If it blocks, it can be solved the same way as CPU intensive operations, do it in the background. So processes need to be easy. You want a language where any async api can be converted into a blocking api, and any blocking api into an async api. (Using processes, most likely.)

carapace 10y ago

One very important aspect of this paper that I seldom see given proper emphasis is the ability to treat programs algebraically. Also, check out Manfred von Thun's Joy.

sroussey 10y ago

Reminds me that we put so much work into making things "digital", that we forget how many layers of abstraction there are. All the work to add numbers when superposition is instantaneous. It's not just the tyranny of memory, but tyranny of the clock! It will be interesting when we get rid of both...

gavinpc 10y ago

Backus and von Neumann have a history, from their time at IBM. When Backus first proposed the idea of Fortran to his boss, he first "had to overcome the persuasive arguments of von Neumann, who was then a consultant to IBM." In Backus' words: > He didn't see programming as a big problem. I think one of his major objections is that you wouldn't know what you were getting with floating point calculations. You at least knew where trouble was with fixed point if there was trouble. But he wasn't sensitive to the issue of the cost of programming. He really felt that Fortran was a wasted effort.[0] Backus and von Neumann had made innovations in the use of floating-point and fixed-point numbers by computers, respectively. From what I can gather, von Neumann was an incredible genius who just continuously pushed new ideas. He introduced "scaling factors" (fixed point) to solve a scientific problem (in nuclear physics) and didn't worry about improving its "usability." Backus, on the other hand, cared about the difficulty of programming. Both Fortran and his work on floating-point, as well as his later efforts in functional programming, manifested that. After leaving computing altogether, Backus took to meditation and, as he calls it, "living." [0] Quotes are from chapter 1 of Out of Their Minds: the Lives and Discoveries of 15 Great Computer Scientists, by Shasha and Lazere.

ankurdhama 10y ago

You can always come up with some really elegant and expressive formal systems to model programming/computing and thats the mathematics side of things BUT people often ignore the physical/engineering side of things. We need to engineer actual physical systems that can implement those so called elegant formal systems of mathematics. This is where the problem is, engineering a physical systems is a very complex problem with lots of constraints and is not as simple as coming up with a bunch of symbols and rules of a formal system. Physics is about reality and mathematics is about representations, you can create representations from thin air but you cant do that with reality :)

kristianp 10y ago

By the way, Bret Victor's worrydream website references this paper from this page on the talk "The Future of Programming": [1] http://worrydream.com/dbx/ http://worrydream.com/dbx/

mtrn 10y ago

Kanerva has discussed alternative computing styles as well. Especially, he asks, why it is hard to encode intelligence in such a rigid setup. > The disparity in architecture between brains and computers is matched by disparity in performance. Notably, computers excel in routine tasks that we - our brains - accomplish with effort, such as calculation, whereas they are yet to be programmed for universal human traits such as flexible learning, language use, and understanding. He focuses on the representation problem and develops a more flexible representation of concepts with what he called hyperdimensional computing[1]. [1] http://redwood.berkeley.edu/pkanerva/papers/kanerva09-hyperdimensional.pdf http://redwood.berkeley.edu/pkanerva/papers/kanerva09-hyperd...

Tawnyctar 10y ago

Now that Moore's Law has effectively ended on a single chip (ended around 2007), FP is front-and-center again, but mostly because of the emphasis on immutability, which is a prerequisite for parallelization. Moore's Law has been replaced with Amdahl's Law.

Tawnyctar 10y ago

Well, is not all the new trendiness in functional programming some evidence of the answer to this?

jefffoster 10y ago

"Out of the Tarpit" (http://shaffner.us/cs/papers/tarpit.pdf http://shaffner.us/cs/papers/tarpit.pdf) is a paper with a similar bent arguing that we can eliminate complexity with a functional/relational approach to designing software.

qznc 10y ago

Wikipedia argues [0] that we actually use a "Modified Harvard Architecture" instead of a "Von Neumann Architecture" today, since we have a separated data and instruction cache. Also, various embedded chips really separate instructions and data. [0] https://en.wikipedia.org/wiki/Modified_Harvard_architecture https://en.wikipedia.org/wiki/Modified_Harvard_architecture

DonHopkins 10y ago

Not all of von Neumann's architectures were von Neumann architectures [1]. That is to say, not all of the architectures he invented [2] ended up being given the name "von Neumann Architecture". His 29 state cellular automata rule [3] for implementing a universal constructor [2] was "non von Neumann" in the sense of [1]. It's just so amazing what he accomplished with his mind, a pencil, and a piece of paper, without the use of computers, which he also helped invent. [1] https://en.wikipedia.org/wiki/Von_Neumann_architecture https://en.wikipedia.org/wiki/Von_Neumann_architecture [2] https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... [3] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton