9 ms·

Bartosz Milewski - The Downfall of Imperative Programming

119 points by dons 15y ago

doktrin 15y ago
While I do agree with the author that FP has in-arguable benefits when it comes to optimizing for multithreading, I'm not sure I buy the logic pronouncing the full-fledged demise of imperative languages. The notion that dev shops will switch to fully-functional languages because a junior dev is bound to muck up the code base seems a little far fetched. That's a huge price to pay for what amounts to a warm fuzzy feeling of immutable certainty (pun intended).
- siavosh 15y ago
  I don't think it's just a matter of a junior programmer messing things up. To really maintain concurrent code, you have to fully grasp a lot of pieces in your head, like what's the correct locking order etc. This is huge mental debt that needs to be transferred between teammates. And if there's no testing for it, errors creep in. The largest source of heart burn in my career has been just this. That said, I agree with you that imperative languages will be around for a long time to come.
  - bunderbunder 15y ago
    In my experience, code for which the phrase "locking order" is applicable is frequently overdue for a refactoring.
16s 15y ago
I'd like to be able to use C++ in a purely functional manner rather than use Haskell, etc. Has anyone done that, if so, what was it like?
- ajax77 15y ago
  With the niceties of C++11, it's certainly become a lot less painful; lambdas, auto (both variable and return type), variadic templates and r-value references give the language just enough flexibility to allow functional style with far more natural syntax. To be sure, it's not a perfect setup; type traits (e.g., enable_if) in function signatures are ugly and hardly a replacement for concepts. I've been dabbling in the creation of a functional library that provides a modest subset of Prelude-inspired features from Haskell. https://github.com/jdduke/fpcpp https://github.com/jdduke/fpcpp Many of the algorithms are simply wrappers around stl algorithms, hiding some of the syntactic awkwardness attendant with the heavy use of iterators. Some day I'll get around to playing with monadic devices, and integrating the list comprehension work that I've done recently.
- eli_gottlieb 15y ago
  One of my undergraduate mentors wrote a library called FC++.
- hristov 15y ago
  You can if you want to. Just make sure you write all your functions in a purely functional way, and avoid all side effects. You do not really need changes to the language, just iron discipline.
  - ttt_ 15y ago
    >> just iron discipline That's where it gets tricky. It's hard enough dealing with your own discipline ironing, imagine a dev team composed of varied expertise and awareness levels.
    - swalsh 15y ago
      imagine the dev team who takes over the project after you leave. Iron discipline doesn't exist over long periods of time, that's why it needs to be built into the language.
keveman 15y ago
Should we all take a serious look at functional programming? Absolutely. Should we start learning a functional programming language? Maybe not. C++ is a multi-paradigm language in which one can write functional programs, and it lends itself nicely to switching back to stateful imperative programming when needed.
- gtani 15y ago
  Maybe not general knowledge, but OP author wasa designer fo D language, is on a C++ subcommittee and has a lot invested in that language: http://bartoszmilewski.com/2012/04/06/lang-next-trip-report/ http://bartoszmilewski.com/2012/04/06/lang-next-trip-report/
- deleted 15y ago
  [deleted]
- jerf 15y ago
  You can not "switch" to an imperative style in C++. You are always in imperative land by default in C++. You can "switch" to a functional island in the middle of C++, but it will forever be a foreign body in the greater C++ program, and a mere moment's inattention will quickly re-introduce imperative side-effects into your purely functional code. Or you'll use some library that re-introduces it, or somebody else on your team will use your putatively functional higher-order function to do something imperative. C++ is a particularly awful language for trying to manage side-effects in or maintain a purely functional constraint on your code, because it offers so very, very many ways of performing side effects without meaning to, and only the thinnest possible compiler support for maintaining those constraints in the face of temptation (const). To be sure "a = b.c(d, e)" is a purely functional statement requires understanding arbitrary amounts of code to be sure that none of reams of code that can invoke accidentally violates your constraints.
  - fferen 15y ago
    I've only been using C++ for a few months, but it's my opinion that all function parameters should have been "const &" by default (except for maybe primitive types). Const correctness has helped me spot some nasty bugs, and it's too easy to accidentally forget the "&" and pass horrendously large structures by value, which must go through a copy constructor and destructor with every call. Plus, it gets really tedious typing "const Mat &src" a million times (guess which library I'm using, lol).
NathanRice 15y ago
While I agree with some things the author says, his conclusions are bullshit. Very few processes want to be parallel. People who primarily do parallel programming think everything needs to be parallel, so they assume everyone must be going through the pain they are going through. This is false. Most people write sequential software. Another issue is that purely functional programming is fundamentally flawed, because it attempts to eschew state. Many functional programmers will call this a virtue, but the world is stateful, and being able to reason about necessary state is how you do anything useful. Purely functional programming is great when you want a convenient test-bed for ideas, but Haskell as a practical programming language is a horrible idea. Ultimately, what we want is to eliminate unnecessary state, while reasoning about necessary state. Modern programming language researchers are doing this under the guise of "effects systems", however most of the research I've seen far has left me underwhelmed. Eventually functional programming researchers are going to end up somewhere that is quite far from where they started, but just a few small steps from logic programming.
- fleitz 15y ago
  We actually don't know that the world is stateful. Quantum physics would tend to suggest that the world is a waveform function that collapses on a discrete value when evaluated. If you think about it the current 'state' of the world should entirely depend on how the previous functions collapsed to produce the current 'state'. Perhaps like in physics there is a sort of Church-Turing duality to it all that is hard to tease apart.
  - NathanRice 15y ago
    The reality is stateful on a macro-scale. I find the idea that the universe is actually stateful, and we do not completely understand behavior at quantum level far more parsimonious than the converse.
    - fleitz 15y ago
      The double slit experiment confirms the wavelike nature of the universe at macro scale. A completely stateful universe where a photon discretely moves through spacetime could not exhibit self interference, only if the photon takes all paths (suggesting 'functions' that describe its movement) could it then collapse into a discrete position after being observed (aka. evaluated) What I'm getting at is that in between emission and observation the photon is not in any one state, at best it's state could be described as a superposition. To take the analogy one step too far, perhaps worst of all this suggests a lazily evaluated haskellian universe with a giant state monad whose NUMA architecture updates at the speed of light.
webjprgm 15y ago
The article starts by mentioning data ownership, but then diverges after saying that didn't take hold in D and discusses just FP. Yes, FP works well for concurrency. But if you're complaining about data races, letting a thread own a piece of data and only be able to share it via channels solves the concurrency problem too. Thus imperative languages can live on if they adopt memory models in which data is owned by a single thread and cannot be shared. I notice Rust has a mechanism for sharing this kind of data by transferring ownership. That looks pretty cool to me. Also, there are still plenty of applications where high level scripting languages like Python and Ruby work great for application logic, and where single threaded event-based systems work for handling user events. It's the data processing part that needs to be put in a safe concurrency sandbox.
- bascule 15y ago
  Can we form a club or something? I keep saying this, but it's still a relatively unpopular idea. Kilim (lightweight actor-like concurrency for the JVM) implements what it describes as "linear ownership transfer", to where objects are owned by a single thread at a time, eliminating any potential data races. I'd certainly like to see more of that
deleted 15y ago
[deleted]
DarkShikari 15y ago
If only it was that easy: change programming languages, change programming models, and poof! Magical parallelism. But parallelism is harder than that. It's an algorithm problem, a design problem, not a language or code problem. While OpenCL might be harder to write than plain C, for anything except the most embarrassingly parallel problems, that difficulty pales in comparison to making the solution parallel to begin with. For every problem where you can simply split into masses of shared-nothing tasks, there's a dozen others where you can't. Rate-constrained video compression. Minimax AI search. Emulation. All of these can be parallelized, but it requires parallelizing the algorithm and making sacrifices that are light-years beyond what a dumb compiler that isn't even allowed to change program output (let alone rewrite half the program) could do. Modifying an algorithm -- possibly even changing its structure entirely, changing its output, or even accepting nondeterminism -- is inherent complexity, to use the terminology of Mythical Man Month. No programming language or tool can eliminate this complexity. Good tools can make it easier to implement an algorithm efficiently, but they really can't take a complicated application and figure out how to change its design, structure, and behavior. Until we have AI-complete compilers that take program specs as "code" to be compiled, that's a human job.
- jmtulloss 15y ago
  What you say is true (http://en.wikipedia.org/wiki/Amdahls_law http://en.wikipedia.org/wiki/Amdahls_law), but it's not really the point. Most programming is not that hard, it's just moving data from one place to another, operating on that data, and then moving it somewhere else. Using functional languages trivially allows you parallelize these types of operations, and forces you to think about problems in a way that will allow you to parallelize other things more easily. So you're right, good design is a human's job, but when you're just doing things the grunt work that most of software development is, having tools that enforce The Right Thing is very helpful.
  - DarkShikari 15y ago
    This isn't about Amdahl's law; this is about the fact that many problems are simply hard. Let's look at some examples. One common example is the need to split a larger task into smaller subcomponents, but where all of the components combined need to obey some global constraints. A specific example: we're compressing a video frame, the result must fit within a certain size, and we can't parallelize over multiple frames for latency reasons. This means we need to split the frame into chunks, but somehow all the chunks have to communicate with each other in real-time, as they work, in order to ensure they obey the global constraint. Do you have a "master" thread that manages them all and makes decisions? Do you use some sort of algorithm where they act as separate agents, asking each other questions? Suddenly this is a lot more complicated than what you started with. Another example is a search algorithm. Whether you're performing a minimax search of a game tree or simplex optimization, you're implementing algorithms that are normally not parallel. Parallelizing minimax is actually incredibly difficult and requires making a lot of hard decisions about where you branch threads, where a thread gives up, how to avoid duplication, and so forth. Fancy programming tools can give you features like thread-safe hash tables that help you, but they don't solve the actual problem. See any multithreaded chess engine for an example of this problem. Note particularly that the engines don't get perfect speedup from multithreading -- but it's NOT because of Amdahl's Law! It's because the searches between threads unavoidably duplicate at least some work. "Moving data, operating on it" would be grossly oversimplifying real-world, complex programs like these, and there's nothing a functional language would do to "trivially parallelize" them. Dependencies in calculations are often so tangling that you cannot naively parallelize them without making dramatic, possibly sacrificial, changes. Tools like FP can be useful, but they don't solve problems of inherent complexity. There is no silver bullet.
bunderbunder 15y ago
Mutable state won't eat your children if you know how to handle it in a disciplined manner. Pure functions and immutable datatypes are definitely preferable in a variety of cases. However, just because you discover one day that there are better tools for driving screws than a hammer doesn't mean you have to start banging your nails in with a screwdriver and wearing a saffron robe and preaching to your friends that you have achieved liberation and that they won't be free until they also throw away their hammers. The softwareverse (and he universe, for that matter) is still full of patterns and constructs that are inherently stateful, and need to be constructed such that they behave as if they were stateful. Heck, some constructs simply can't be made to work efficiently in a purely functional manner. Hash tables come to mind. Fortunately we already have a tool that's proven to be excellent for efficiently and effectively modeling state. No, it's not monads. It's state. And it does the job so well that even Haskell was forced to resort to it for its hash table implementation. (Though admittedly not until after much sound and fury to the effect of, "Nobody needs hash tables; trees are Pure and just as good!" I'll say this for silver bullets - people sure can cling to them.)
- gnuvince 15y ago
  I don't think anyone says that mutable state should be completely eliminated; the argument is that it should (1) not be the default, and (2) be made explicit through the type system.
  - jinfiesto 15y ago
    While you're right, I think that's kind of obscured by the language that a lot of functional evangelists use. I myself prefer FP (Lisp first, now Haskell,) but most people who are coming from an imperative programming languages tend to see Functional languages as uselessly pure. As a matter of fact, in LYAH, the author states that Haskell is totally 100% pure. Which of course, is true in a sense, but false in another, at least in that we still model and use mutable state. (It's just marked by the type system, as you mentioned, and it's done in a functional way and usually heavily sugared.) In Haskell, I'm disregarding the IO monad.
- jfoutz 15y ago
praptak 15y ago
I am a big believer in FP (reasoning about functional code is much sounder even in the sequential case) but not in parallel programming. Most algorithms just do not parallelize that well, regardless of the programming paradigm used. Quote Donald Knuth: '[...] So why should I be so happy about the future that hardware vendors promise? They think a magic bullet will come along to make multicores speed up my kind of work; I think it’s a pipe dream. (No—that’s the wrong metaphor! "Pipelines" actually work for me, but threads don’t. Maybe the word I want is "bubble.")' 'I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrific—until it turned out that the wished-for compilers were basically impossible to write.'
- bunderbunder 15y ago
  If you look at classes of problems, sure, only a few of them are easily parallelizable. But if you look at what many programmers are actually doing on a day-to-day basis, it turns out that a huge chunk of it is really basic, straightforward SIMD. Hence the popularity of for-each loops in modern programming languages. That kind of stuff is often quite trivially parallelizable. Microsoft demonstrated that nicely with the introduction of, e.g., Parallel.ForEach() in .NET 4. There's also something to be said for tasks which are naturally. . . let's say concurrent. ETL comes to mind - if you do ETL using purely sequential code, you're going to end up with software that's immensely slow compared to code that has enough basic time management skills to realize it could probably be doing something more productive than twiddling its thumbs while waiting on the disk controller.
  - _delirium 15y ago
    That's true, but for those tasks, it's not clear you need to abandon imperative languages at all. In cases where you're just doing the same operation on all elements in an array, with no data dependency, you can do that in C without fiddling with pthreads by using OpenMP's "parallel for" construct. FP promises to make it less error-prone and practical to do more complex parallelization than these trivial kinds of parallelization, but the skeptical take (which I partially share) wonders whether that is a big win. In other words, are the trivial parallelizations just the 10% tip of the iceberg, and there are 90% wins left from more complex parallel programming (in which case perhaps FP is what lets us unlock that future), or is trivially parallelizable stuff more like 90% of the parallelization win?
keypusher 15y ago
No mention of Erlang?
- tedunangst 15y ago
  The article I read mentioned Erlang.
josephg 15y ago
This is a cute idea, but your computer is almost never CPU pegged. It spends most of its time waiting for input from you. For 95% of software, faster execution (through parallelism or whatever) would have no effect. But don't take my word for it. Look at all the applications you have open right now and check if a magical 1e100Hz processor would make any meaningful difference. For me: iTunes: no. Vim: no. Chrome with hackernews: no. VLC: no. Terminal: no. "We need to rethink software design to make our programs run faster" – Hardly. We're actually seeing the opposite trend. People are caring less about CPU performance now than they used to. One of the effects is that real software is being written in slow languages like Ruby and Coffeescript, performance be damned. There are obviously exceptions (games and scientific simulations). But for the other 95% of code out there, we simply don't need the parallelism of functional languages to write good software.
- j_baker 15y ago
  I think it's stretching it to say that 95% of programs won't peg your CPU. Ok, maybe 95% of all programs written for an actual desktop/laptop that aren't games are. But we live in a more complex world where mobile devices are slow, but have multiple cores. And what about games? Game developers are always trying to squeeze that last little bit of performance out. And we haven't even gotten into server-side software, nor have we discussed concurrency due to I/O-boundedness.
  - josephg 15y ago
    On mobile devices, you can already be a bit sloppy with your code and your UI will still be responsive. The fact that Corona and Phonegap are usable is proof of that. The 'comfort margin' of mobile CPUs will only increase over the next few years. You certainly don't need functional languages to write efficient server-side code for I/O-bound applications. People have solved the C10k problem for every imperative language I know. Ryah (the nodejs guy) makes a pretty strong case that functional programming's parallelism doesn't help you on the server side anyway, because you'll need to scale across multiple machines. Multiple machines mean multiple processes. If you're doing that anyway, you may as well avoid threads entirely and parallelize by spawning a few processes on each server. Games are the big exception, though I find it curious that I've never heard of any published game (big or small) that was written in a purely functional language. If functional programming really does make concurrent code easier to write, I'd expect at least a couple indie computer game developers to be using them, somewhere! Anyway, despite how visible game development is, it makes up a small percentage of the computer industry. That we will experience 'The Downfall of Imperative Programming' because some day, I hope game developers use functional languages to make their games run faster is a bit of a stretch. The ability of functional programming languages to do parallelization is really cool, but you're not solving a problem that many programmers actually have. Its like selling a car by saying it has lots of leg room for tall people. Its a great pitch to the right customer, but don't expect a revolution.
ww520 15y ago
Another silver bullet to chase after. When will people learn? There ain't no silver bullet. Parallel programming has complexity. Deal with it.
protomyth 15y ago
I guess I am kind of confused about the title because I was under the impression Occam counts as imperative. Also, if we are talking general parallelization strategies then Grand Central Station is something to look at on the Mac.
- alexbell 15y ago
  Grand Central Dispatch, I think you mean. :) It's on iOS 4+ as well.
  - protomyth 15y ago
    Thanks, I keep doing that with GCD and calling the "First Responder" First Listener. I am glad they ported it to iOS. It really helps to be able to use the same programming structure on both platforms. I still think one of the agent oriented programming variants might not be a bad way to build parallel programs.
6ren 15y ago
> In fact the most popular language for parallel and distributed programming is Erlang — a functional language. Erlang achieves its parallelism not through immutability (though it has that) but through a shared-nothing architecture, like smalltalk. You can implement shared-nothing concurrency imperatively. It circumvents the problem of two threads accessing the same memory location by restricting access to only one thread. Of course, then there's the problem when you do need to share data between threads - Erlang does this with STM (software transactional memory - like a DB).
6ren 15y ago
Hunch: as hardware (multi-core) improves, we will not achieve a sudden breakthrough that enables us to run conventional software approaches on it (functional, imperative or otherwise). Clever people have been anticipating and investigating multi-core for decades, without result, apart from the "embarrassingly parallelizable". In later decades, actual multi-core hardware was adopted in leading-edge then mainstream applications: in supercomputers; in server farms (esp google); in GPUs. Mainstream desktop CPUs have been multi-core for a decade now; and, today, as the article indicates, even phones are multi-core. Phones. In the big picture, multi-core instead will slowly become good enough to solve problems suited to it, that couldn't be solved easily or cheaply before, such as massive simulation in non-government/military applications, and including problems that we did not even see as "problems" before, they seemed so insoluble. It will be a new golden age of computation, with utterly different concepts, approaches and values from today. Our current issues of programming languages will disappear, pushed down to a lower level, and compared to it, imperative and functional programming will be as twins.
ak39 15y ago
Great article, but does it answer the question it raised: Why has software evolution lagged behind? Also, is the focus on parallel computing the only litmus to judge this as the downfall of every imperative programming language? To answer the first question, we have to abandon our technical computing hats in favour of the philosopher's hat. What went wrong with the promise of reusable objects? Whatever happened to 4GL? Why are frameworks confined to isolated corners of language evolution, far-removed from the domain problems faced by end-users? Why, oh is every nerd developing an Order-Entry system from scratch? Why are nerds doing the same code again and again for decades in every conceivable new language (now FP). You see, if we start accepting structural restrictions like those imposed by FP, then philosophically we should follow that maxim to its logical conclusion. Restrict to the point where we do not harm ourselves (by repeating). Rant over. ;-)
CookWithMe 15y ago
I think this article is a really bad introduction, both to parallel and functional programming. There is just so much stuff that is badly informed, or simply wrong, e.g: > For a functional programmer there is no barrier to concurrency, parallelism, or GPU programming. Amdahls law? And GPUs, while having branch support recently, still only perform great for problems that are highly data parallel and are not in high need for branching. > I may surprise you that the state of the art in parallel programming is OpenMP and OpenCL. This did in fact surprise me a lot! Erlang? Well, if you think about it, a webserver renders webpages in parallel. If that is not state of the art and parallel, then what is? While I am very interested both in parallel and functional programming, I am actually disappointed this article has made it onto the frontpage of HN...

119 points by dons 15y ago

While I do agree with the author that FP has in-arguable benefits when it comes to optimizing for multithreading, I'm not sure I buy the logic pronouncing the full-fledged demise of imperative languages. The notion that dev shops will switch to fully-functional languages because a junior dev is bound to muck up the code base seems a little far fetched. That's a huge price to pay for what amounts to a warm fuzzy feeling of immutable certainty (pun intended).

siavosh 15y ago
I don't think it's just a matter of a junior programmer messing things up. To really maintain concurrent code, you have to fully grasp a lot of pieces in your head, like what's the correct locking order etc. This is huge mental debt that needs to be transferred between teammates. And if there's no testing for it, errors creep in. The largest source of heart burn in my career has been just this. That said, I agree with you that imperative languages will be around for a long time to come.
- bunderbunder 15y ago
  In my experience, code for which the phrase "locking order" is applicable is frequently overdue for a refactoring.

16s 15y ago

I'd like to be able to use C++ in a purely functional manner rather than use Haskell, etc. Has anyone done that, if so, what was it like?

ajax77 15y ago
With the niceties of C++11, it's certainly become a lot less painful; lambdas, auto (both variable and return type), variadic templates and r-value references give the language just enough flexibility to allow functional style with far more natural syntax. To be sure, it's not a perfect setup; type traits (e.g., enable_if) in function signatures are ugly and hardly a replacement for concepts. I've been dabbling in the creation of a functional library that provides a modest subset of Prelude-inspired features from Haskell. https://github.com/jdduke/fpcpp https://github.com/jdduke/fpcpp Many of the algorithms are simply wrappers around stl algorithms, hiding some of the syntactic awkwardness attendant with the heavy use of iterators. Some day I'll get around to playing with monadic devices, and integrating the list comprehension work that I've done recently.
eli_gottlieb 15y ago
One of my undergraduate mentors wrote a library called FC++.
hristov 15y ago
You can if you want to. Just make sure you write all your functions in a purely functional way, and avoid all side effects. You do not really need changes to the language, just iron discipline.
- ttt_ 15y ago
  >> just iron discipline That's where it gets tricky. It's hard enough dealing with your own discipline ironing, imagine a dev team composed of varied expertise and awareness levels.
  - swalsh 15y ago
    imagine the dev team who takes over the project after you leave. Iron discipline doesn't exist over long periods of time, that's why it needs to be built into the language.

keveman 15y ago

Should we all take a serious look at functional programming? Absolutely. Should we start learning a functional programming language? Maybe not. C++ is a multi-paradigm language in which one can write functional programs, and it lends itself nicely to switching back to stateful imperative programming when needed.

gtani 15y ago
Maybe not general knowledge, but OP author wasa designer fo D language, is on a C++ subcommittee and has a lot invested in that language: http://bartoszmilewski.com/2012/04/06/lang-next-trip-report/ http://bartoszmilewski.com/2012/04/06/lang-next-trip-report/
deleted 15y ago
[deleted]
jerf 15y ago
You can not "switch" to an imperative style in C++. You are always in imperative land by default in C++. You can "switch" to a functional island in the middle of C++, but it will forever be a foreign body in the greater C++ program, and a mere moment's inattention will quickly re-introduce imperative side-effects into your purely functional code. Or you'll use some library that re-introduces it, or somebody else on your team will use your putatively functional higher-order function to do something imperative. C++ is a particularly awful language for trying to manage side-effects in or maintain a purely functional constraint on your code, because it offers so very, very many ways of performing side effects without meaning to, and only the thinnest possible compiler support for maintaining those constraints in the face of temptation (const). To be sure "a = b.c(d, e)" is a purely functional statement requires understanding arbitrary amounts of code to be sure that none of reams of code that can invoke accidentally violates your constraints.
- fferen 15y ago
  I've only been using C++ for a few months, but it's my opinion that all function parameters should have been "const &" by default (except for maybe primitive types). Const correctness has helped me spot some nasty bugs, and it's too easy to accidentally forget the "&" and pass horrendously large structures by value, which must go through a copy constructor and destructor with every call. Plus, it gets really tedious typing "const Mat &src" a million times (guess which library I'm using, lol).

NathanRice 15y ago

While I agree with some things the author says, his conclusions are bullshit. Very few processes want to be parallel. People who primarily do parallel programming think everything needs to be parallel, so they assume everyone must be going through the pain they are going through. This is false. Most people write sequential software. Another issue is that purely functional programming is fundamentally flawed, because it attempts to eschew state. Many functional programmers will call this a virtue, but the world is stateful, and being able to reason about necessary state is how you do anything useful. Purely functional programming is great when you want a convenient test-bed for ideas, but Haskell as a practical programming language is a horrible idea. Ultimately, what we want is to eliminate unnecessary state, while reasoning about necessary state. Modern programming language researchers are doing this under the guise of "effects systems", however most of the research I've seen far has left me underwhelmed. Eventually functional programming researchers are going to end up somewhere that is quite far from where they started, but just a few small steps from logic programming.

fleitz 15y ago
We actually don't know that the world is stateful. Quantum physics would tend to suggest that the world is a waveform function that collapses on a discrete value when evaluated. If you think about it the current 'state' of the world should entirely depend on how the previous functions collapsed to produce the current 'state'. Perhaps like in physics there is a sort of Church-Turing duality to it all that is hard to tease apart.
- NathanRice 15y ago
  The reality is stateful on a macro-scale. I find the idea that the universe is actually stateful, and we do not completely understand behavior at quantum level far more parsimonious than the converse.
  - fleitz 15y ago
    The double slit experiment confirms the wavelike nature of the universe at macro scale. A completely stateful universe where a photon discretely moves through spacetime could not exhibit self interference, only if the photon takes all paths (suggesting 'functions' that describe its movement) could it then collapse into a discrete position after being observed (aka. evaluated) What I'm getting at is that in between emission and observation the photon is not in any one state, at best it's state could be described as a superposition. To take the analogy one step too far, perhaps worst of all this suggests a lazily evaluated haskellian universe with a giant state monad whose NUMA architecture updates at the speed of light.

webjprgm 15y ago

The article starts by mentioning data ownership, but then diverges after saying that didn't take hold in D and discusses just FP. Yes, FP works well for concurrency. But if you're complaining about data races, letting a thread own a piece of data and only be able to share it via channels solves the concurrency problem too. Thus imperative languages can live on if they adopt memory models in which data is owned by a single thread and cannot be shared. I notice Rust has a mechanism for sharing this kind of data by transferring ownership. That looks pretty cool to me. Also, there are still plenty of applications where high level scripting languages like Python and Ruby work great for application logic, and where single threaded event-based systems work for handling user events. It's the data processing part that needs to be put in a safe concurrency sandbox.

bascule 15y ago
Can we form a club or something? I keep saying this, but it's still a relatively unpopular idea. Kilim (lightweight actor-like concurrency for the JVM) implements what it describes as "linear ownership transfer", to where objects are owned by a single thread at a time, eliminating any potential data races. I'd certainly like to see more of that

deleted 15y ago

[deleted]

DarkShikari 15y ago

If only it was that easy: change programming languages, change programming models, and poof! Magical parallelism. But parallelism is harder than that. It's an algorithm problem, a design problem, not a language or code problem. While OpenCL might be harder to write than plain C, for anything except the most embarrassingly parallel problems, that difficulty pales in comparison to making the solution parallel to begin with. For every problem where you can simply split into masses of shared-nothing tasks, there's a dozen others where you can't. Rate-constrained video compression. Minimax AI search. Emulation. All of these can be parallelized, but it requires parallelizing the algorithm and making sacrifices that are light-years beyond what a dumb compiler that isn't even allowed to change program output (let alone rewrite half the program) could do. Modifying an algorithm -- possibly even changing its structure entirely, changing its output, or even accepting nondeterminism -- is inherent complexity, to use the terminology of Mythical Man Month. No programming language or tool can eliminate this complexity. Good tools can make it easier to implement an algorithm efficiently, but they really can't take a complicated application and figure out how to change its design, structure, and behavior. Until we have AI-complete compilers that take program specs as "code" to be compiled, that's a human job.

jmtulloss 15y ago
What you say is true (http://en.wikipedia.org/wiki/Amdahls_law http://en.wikipedia.org/wiki/Amdahls_law), but it's not really the point. Most programming is not that hard, it's just moving data from one place to another, operating on that data, and then moving it somewhere else. Using functional languages trivially allows you parallelize these types of operations, and forces you to think about problems in a way that will allow you to parallelize other things more easily. So you're right, good design is a human's job, but when you're just doing things the grunt work that most of software development is, having tools that enforce The Right Thing is very helpful.
- DarkShikari 15y ago
  This isn't about Amdahl's law; this is about the fact that many problems are simply hard. Let's look at some examples. One common example is the need to split a larger task into smaller subcomponents, but where all of the components combined need to obey some global constraints. A specific example: we're compressing a video frame, the result must fit within a certain size, and we can't parallelize over multiple frames for latency reasons. This means we need to split the frame into chunks, but somehow all the chunks have to communicate with each other in real-time, as they work, in order to ensure they obey the global constraint. Do you have a "master" thread that manages them all and makes decisions? Do you use some sort of algorithm where they act as separate agents, asking each other questions? Suddenly this is a lot more complicated than what you started with. Another example is a search algorithm. Whether you're performing a minimax search of a game tree or simplex optimization, you're implementing algorithms that are normally not parallel. Parallelizing minimax is actually incredibly difficult and requires making a lot of hard decisions about where you branch threads, where a thread gives up, how to avoid duplication, and so forth. Fancy programming tools can give you features like thread-safe hash tables that help you, but they don't solve the actual problem. See any multithreaded chess engine for an example of this problem. Note particularly that the engines don't get perfect speedup from multithreading -- but it's NOT because of Amdahl's Law! It's because the searches between threads unavoidably duplicate at least some work. "Moving data, operating on it" would be grossly oversimplifying real-world, complex programs like these, and there's nothing a functional language would do to "trivially parallelize" them. Dependencies in calculations are often so tangling that you cannot naively parallelize them without making dramatic, possibly sacrificial, changes. Tools like FP can be useful, but they don't solve problems of inherent complexity. There is no silver bullet.

bunderbunder 15y ago

Mutable state won't eat your children if you know how to handle it in a disciplined manner. Pure functions and immutable datatypes are definitely preferable in a variety of cases. However, just because you discover one day that there are better tools for driving screws than a hammer doesn't mean you have to start banging your nails in with a screwdriver and wearing a saffron robe and preaching to your friends that you have achieved liberation and that they won't be free until they also throw away their hammers. The softwareverse (and he universe, for that matter) is still full of patterns and constructs that are inherently stateful, and need to be constructed such that they behave as if they were stateful. Heck, some constructs simply can't be made to work efficiently in a purely functional manner. Hash tables come to mind. Fortunately we already have a tool that's proven to be excellent for efficiently and effectively modeling state. No, it's not monads. It's state. And it does the job so well that even Haskell was forced to resort to it for its hash table implementation. (Though admittedly not until after much sound and fury to the effect of, "Nobody needs hash tables; trees are Pure and just as good!" I'll say this for silver bullets - people sure can cling to them.)

gnuvince 15y ago
I don't think anyone says that mutable state should be completely eliminated; the argument is that it should (1) not be the default, and (2) be made explicit through the type system.
- jinfiesto 15y ago
  While you're right, I think that's kind of obscured by the language that a lot of functional evangelists use. I myself prefer FP (Lisp first, now Haskell,) but most people who are coming from an imperative programming languages tend to see Functional languages as uselessly pure. As a matter of fact, in LYAH, the author states that Haskell is totally 100% pure. Which of course, is true in a sense, but false in another, at least in that we still model and use mutable state. (It's just marked by the type system, as you mentioned, and it's done in a functional way and usually heavily sugared.) In Haskell, I'm disregarding the IO monad.
jfoutz 15y ago

praptak 15y ago

I am a big believer in FP (reasoning about functional code is much sounder even in the sequential case) but not in parallel programming. Most algorithms just do not parallelize that well, regardless of the programming paradigm used. Quote Donald Knuth: '[...] So why should I be so happy about the future that hardware vendors promise? They think a magic bullet will come along to make multicores speed up my kind of work; I think it’s a pipe dream. (No—that’s the wrong metaphor! "Pipelines" actually work for me, but threads don’t. Maybe the word I want is "bubble.")' 'I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrific—until it turned out that the wished-for compilers were basically impossible to write.'

bunderbunder 15y ago
If you look at classes of problems, sure, only a few of them are easily parallelizable. But if you look at what many programmers are actually doing on a day-to-day basis, it turns out that a huge chunk of it is really basic, straightforward SIMD. Hence the popularity of for-each loops in modern programming languages. That kind of stuff is often quite trivially parallelizable. Microsoft demonstrated that nicely with the introduction of, e.g., Parallel.ForEach() in .NET 4. There's also something to be said for tasks which are naturally. . . let's say concurrent. ETL comes to mind - if you do ETL using purely sequential code, you're going to end up with software that's immensely slow compared to code that has enough basic time management skills to realize it could probably be doing something more productive than twiddling its thumbs while waiting on the disk controller.
- _delirium 15y ago
  That's true, but for those tasks, it's not clear you need to abandon imperative languages at all. In cases where you're just doing the same operation on all elements in an array, with no data dependency, you can do that in C without fiddling with pthreads by using OpenMP's "parallel for" construct. FP promises to make it less error-prone and practical to do more complex parallelization than these trivial kinds of parallelization, but the skeptical take (which I partially share) wonders whether that is a big win. In other words, are the trivial parallelizations just the 10% tip of the iceberg, and there are 90% wins left from more complex parallel programming (in which case perhaps FP is what lets us unlock that future), or is trivially parallelizable stuff more like 90% of the parallelization win?

keypusher 15y ago

No mention of Erlang?

tedunangst 15y ago
The article I read mentioned Erlang.

josephg 15y ago

This is a cute idea, but your computer is almost never CPU pegged. It spends most of its time waiting for input from you. For 95% of software, faster execution (through parallelism or whatever) would have no effect. But don't take my word for it. Look at all the applications you have open right now and check if a magical 1e100Hz processor would make any meaningful difference. For me: iTunes: no. Vim: no. Chrome with hackernews: no. VLC: no. Terminal: no. "We need to rethink software design to make our programs run faster" – Hardly. We're actually seeing the opposite trend. People are caring less about CPU performance now than they used to. One of the effects is that real software is being written in slow languages like Ruby and Coffeescript, performance be damned. There are obviously exceptions (games and scientific simulations). But for the other 95% of code out there, we simply don't need the parallelism of functional languages to write good software.

j_baker 15y ago
I think it's stretching it to say that 95% of programs won't peg your CPU. Ok, maybe 95% of all programs written for an actual desktop/laptop that aren't games are. But we live in a more complex world where mobile devices are slow, but have multiple cores. And what about games? Game developers are always trying to squeeze that last little bit of performance out. And we haven't even gotten into server-side software, nor have we discussed concurrency due to I/O-boundedness.
- josephg 15y ago
  On mobile devices, you can already be a bit sloppy with your code and your UI will still be responsive. The fact that Corona and Phonegap are usable is proof of that. The 'comfort margin' of mobile CPUs will only increase over the next few years. You certainly don't need functional languages to write efficient server-side code for I/O-bound applications. People have solved the C10k problem for every imperative language I know. Ryah (the nodejs guy) makes a pretty strong case that functional programming's parallelism doesn't help you on the server side anyway, because you'll need to scale across multiple machines. Multiple machines mean multiple processes. If you're doing that anyway, you may as well avoid threads entirely and parallelize by spawning a few processes on each server. Games are the big exception, though I find it curious that I've never heard of any published game (big or small) that was written in a purely functional language. If functional programming really does make concurrent code easier to write, I'd expect at least a couple indie computer game developers to be using them, somewhere! Anyway, despite how visible game development is, it makes up a small percentage of the computer industry. That we will experience 'The Downfall of Imperative Programming' because some day, I hope game developers use functional languages to make their games run faster is a bit of a stretch. The ability of functional programming languages to do parallelization is really cool, but you're not solving a problem that many programmers actually have. Its like selling a car by saying it has lots of leg room for tall people. Its a great pitch to the right customer, but don't expect a revolution.

ww520 15y ago

Another silver bullet to chase after. When will people learn? There ain't no silver bullet. Parallel programming has complexity. Deal with it.

protomyth 15y ago

I guess I am kind of confused about the title because I was under the impression Occam counts as imperative. Also, if we are talking general parallelization strategies then Grand Central Station is something to look at on the Mac.

alexbell 15y ago
Grand Central Dispatch, I think you mean. :) It's on iOS 4+ as well.
- protomyth 15y ago
  Thanks, I keep doing that with GCD and calling the "First Responder" First Listener. I am glad they ported it to iOS. It really helps to be able to use the same programming structure on both platforms. I still think one of the agent oriented programming variants might not be a bad way to build parallel programs.

6ren 15y ago

> In fact the most popular language for parallel and distributed programming is Erlang — a functional language. Erlang achieves its parallelism not through immutability (though it has that) but through a shared-nothing architecture, like smalltalk. You can implement shared-nothing concurrency imperatively. It circumvents the problem of two threads accessing the same memory location by restricting access to only one thread. Of course, then there's the problem when you do need to share data between threads - Erlang does this with STM (software transactional memory - like a DB).

6ren 15y ago

Hunch: as hardware (multi-core) improves, we will not achieve a sudden breakthrough that enables us to run conventional software approaches on it (functional, imperative or otherwise). Clever people have been anticipating and investigating multi-core for decades, without result, apart from the "embarrassingly parallelizable". In later decades, actual multi-core hardware was adopted in leading-edge then mainstream applications: in supercomputers; in server farms (esp google); in GPUs. Mainstream desktop CPUs have been multi-core for a decade now; and, today, as the article indicates, even phones are multi-core. Phones. In the big picture, multi-core instead will slowly become good enough to solve problems suited to it, that couldn't be solved easily or cheaply before, such as massive simulation in non-government/military applications, and including problems that we did not even see as "problems" before, they seemed so insoluble. It will be a new golden age of computation, with utterly different concepts, approaches and values from today. Our current issues of programming languages will disappear, pushed down to a lower level, and compared to it, imperative and functional programming will be as twins.

ak39 15y ago

Great article, but does it answer the question it raised: Why has software evolution lagged behind? Also, is the focus on parallel computing the only litmus to judge this as the downfall of every imperative programming language? To answer the first question, we have to abandon our technical computing hats in favour of the philosopher's hat. What went wrong with the promise of reusable objects? Whatever happened to 4GL? Why are frameworks confined to isolated corners of language evolution, far-removed from the domain problems faced by end-users? Why, oh is every nerd developing an Order-Entry system from scratch? Why are nerds doing the same code again and again for decades in every conceivable new language (now FP). You see, if we start accepting structural restrictions like those imposed by FP, then philosophically we should follow that maxim to its logical conclusion. Restrict to the point where we do not harm ourselves (by repeating). Rant over. ;-)

CookWithMe 15y ago

I think this article is a really bad introduction, both to parallel and functional programming. There is just so much stuff that is badly informed, or simply wrong, e.g: > For a functional programmer there is no barrier to concurrency, parallelism, or GPU programming. Amdahls law? And GPUs, while having branch support recently, still only perform great for problems that are highly data parallel and are not in high need for branching. > I may surprise you that the state of the art in parallel programming is OpenMP and OpenCL. This did in fact surprise me a lot! Erlang? Well, if you think about it, a webserver renders webpages in parallel. If that is not state of the art and parallel, then what is? While I am very interested both in parallel and functional programming, I am actually disappointed this article has made it onto the frontpage of HN...