Time to Get Good At Functional Programming? 620
prone2tech writes "From an article at Dr. Dobb's: Chipmakers have essentially said that the job of enforcing Moore's Law is now a software problem. They will concentrate on putting more and more cores on a die, and it's up to the software industry to recraft software to take advantage of the parallel-processing capabilities of the new chips. As is argued in this article, this means becoming proficient in parallel functional programming. The bad news? Getting good at functional programming is hard, harder than moving from iterative Pascal or Basic or C coding to object-oriented development. It's an exaggeration but a useful one: When you move to FP, all your algorithms break.'"
Broken Algorithm BS (Score:5, Insightful)
When you move to FP, all your algorithms break
If moving to a functional programming language breaks your algorithms, then you are somehow doing it wrong. That line doesn't even make sense to me. Algorithms are mathematical constructs that have nothing to do with programming paradigm. Assuming the language is Turing complete, how is that even possible?
Amdahl's Law (Score:5, Insightful)
Question is, how realistic is that?
Amdahl's Law also tells us tells us that the amount that parallelization can speed something up is ultimately limited by the parts that can't be done in parallel.
Re:Broken Algorithm BS (Score:5, Insightful)
Formal Methods Initiative (Score:5, Insightful)
This reminds me about the /. article "Twenty Years of Dijkstra's Cruelty" [slashdot.org], just a few days ago.
Problem boils down to fact that programming is in fact a very advanced calculus. And writing a program is 'deriving' it. As in reaching a correct formula with a proof that it's correct. That's how software should be written anyways. And functional programming will only make it *simpler*, not harder.
Moore's Law? (Score:3, Insightful)
How is maintaining the rate of increase in the number of transistors that can be economically placed on an integrated circuit a software problem?
Function is easy (Score:4, Insightful)
The biggest problem with functional languages tends to be their type systems (I'm looking at you, Haskell). A functional language with a nice type system, like Erlang, is easy to pick up. And the example I picked totally at random, Erlang, also happens to have CSP primitives in the language, which makes parallel programming trivial. I've written code in it and then deployed it on a 64-processor machine and watched it nicely distribute my code over all 64 processors. If you program in a CSP style (which is easy) then your code will exhibit 1000-way parallelism or more and so will trivially take advantage of up to this many processes.
And, actually, object orientation is a good option too. Alan Kay, who defined coined term, defined it as 'simple computers [objects] communicating via message passing' - sounds a lot like CSP, no? The main difference is that OO is usually implemented with synchronous message passing, but you can implement it with asynchronous messaging (actor model) then you have something almost identical to CSP. You can also add this implicitly with futures. I've done this in Objective-C for Etoile. Just send an object an -inNewThread message and any subsequent message you send to it is passed via a lockless ring buffer to the other thread and executed. We use it in our music jukebox app, for example, to run the decode in a separate thread from the UI. Implementing it in the language, rather than the library, means you can do it more efficiently, so this by no means replaces Actalk or Erlang in the general case, but modern processors are fast serial processors so it makes sense to program much larger chunks of serial code on these systems than Erlang or Actalk encourage.
Re:Broken Algorithm BS (Score:5, Insightful)
While algorithms won't break, you'll certainly have to rewrite a lot of them to take advantage of multiple processors.
This problem is not new.
The solutions are out there, and are also not new.
Article is pure shit.
Re:Convince your boss. (Score:5, Insightful)
Well, the problem is that no matter how much you bash an algorithm with a functional language you can't magically make a sequential task into a parallel one.
Which is more likely? (Score:5, Insightful)
A. Many programmers start writing or re-writing their code in functional programming languages.
or
B. Programmers continue writing to their platform of choice, e.g. .NET, Java, etc., and the guys writing the virtual machines do the heavy-lifting, making the VM execute more efficiently with multi-cores?
I'll go with B.
Apple is already proving this. Mac OS X Snow Leopard will have a lot of this built-in. Read about "Grand Central."
Re:Convince your boss. (Score:5, Insightful)
Thing is, you probably have a parallel task that was already bashed into a sequential one.
Most real-world problems are parallel problems. Even the ones that aren't (say... compiling a file in C) you can usually run a lot of instances of in parallel.
parallel algorithms, mutable data, and STM (Score:5, Insightful)
While pure functional code isn't allowed to manipulate mutable, shared state, functional languages often provide some mechanism to mix "pure" and "impure" (stateful, imperative code).
In the haskell world, there is the IO monad, which is sort of a sandbox where anything is allowed. Functions within the IO monad (often called "IO actions") are allowed to invoke other IO actions or call pure code, but the reverse is not true; pure code cannot invoke an IO action. Also, due to laziness, pure functions that were passed an unevaluated "thunk" as an argument might trigger deferred IO, but this is (usually) transparent to the programmer.
So far, this doesn't sound any better than a pure imperative language, but there is also an STM monad (for software transactional memory) which is like pure code except that you're allowed to access shared mutable data through a restricted API. STM is based on the idea that if two processes race and manipulate the same shared data structures at the same time, the conflict can be detected by the run time system, which can stop and replay the transaction one after the other.
The reason STM transactions can be safely replayed by the run-time system is that the language guarantees that the STM transaction doesn't have any hidden state somewhere, that might cause problems if the transaction were replayed. This is not a guarantee you can make in C, C++, Java, or any other popular language that I am aware of.
Note 1: It is possible for STM transactions to livelock if they continually conflict and are replayed, so you can still shoot yourself in the foot. However, it does make avoiding certain other problems much easier.
Note 2: I'm not really a haskell guru, so everything above should be taken with a grain of salt. Real World Haskell has a chapter [realworldhaskell.org] on STM, which is the basis of my current understanding (I haven't yet had cause to use STM in any program I've written.)
Re:Broken Algorithm BS (Score:4, Insightful)
>> How can Moore's Law ever be a software issue?
In a sense, it can be: if we start rewriting Java/C#/VB apps in assembler, I'm pretty sure the performance will at least double each year, and we can forget about those cores for good.
Re:Multi Threaded programming (Score:5, Insightful)
Parallel algorithms are fundamentally different from sequential ones. Take sorting. No multi-threading is going to help you if you keep implementing quicksort. While many problems are inherently parallel and it is easy to undo their serialization, several others will turn into bottlenecks. I am almost done with my Ph.D. and still I haven't received a proper education in parallel algorithms. It'll take a whole new generation of CS teachers to make the grand paradigm shift.
Re:Broken Algorithm BS (Score:3, Insightful)
The idea is that it's still easy to add more transistors, but no longer easy to make them run faster. That is why they are moving to multiple cores - they can add three (or even 15) cores far more easily (and using much less energy and putting off much less heat) than they can make a single core run at twice the clock rate.
Moore's law still exists in hardware, but it's manifested in a different way than it had been until a few years ago, due to physical limitations that don't appear to be going away any time soon. But software needs to adjust for those changes to benefit us in the real world.
Of course not all individual tasks can be sped up with parallelization, but many tasks, and the overall computing experience, probably can be.
Re:Broken Algorithm BS (Score:2, Insightful)
You may be right. It just might double in speed (though not every year, just once), but the number of bugs will increase 1000-fold.
Re:Convince your boss. (Score:4, Insightful)
Another question you might ask yourself is, are you going to let the CPU designers push you into a programming paradigm you are not effective in?
This to me sounds like laziness. "But parallel programming is HARD!"
But I'd much rather see them speed the cores up than endlessly multiply the number of them. There is a *lot* of room left to do this.
Please elaborate on this further, because what you wrote that follows is all rather vague to me. Making cores faster means higher clock speeds and/or improved architectures. As far as clock speeds go, apparently, chip designers feel like they are running up against physical limitations that are making this difficult. And when it comes to improved architectures, what quite possibly the #1 thing that has been done over the years to improve performance? Increase parallelism. Pipelining, superscalar architectures, multi-threaded single cores, VLIW, etc.
No, look at the scope (Score:5, Insightful)
It is the cache coherency and memory bandwidth problems with existing architectures that are the problem. We need better low latency data transfer and significant improvement in auto-parallelism technology in compilers.
It should be clear that there has been very little serious investment in basic compiler technology and that is now needed. Academics have realised this but it takes time. The bandwidth issues are solvable else-when with more transistors.
Finally, we have a variety of programming paradigms OO, Functional & procedural and more each of which has a problem niche.
One thing we will certainly have to get away fom is the idea that 'legacy' code can carelessly be re-written in the flavor of month interpreted language eg Java, C#, Perl, Python or Ruby. You can write 95% of your code in a programmet friendly language. But the critical sections need to be in C, FORTRAN or Assembler and need to be very carefully optimized. That can give you x100 on the same architecture.
Re:Convince your boss. (Score:5, Insightful)
I'd much rather have 64 fast cores than 16 slightly faster (but horribly power-inefficient) cores, and that's really the tradeoff that you're talking about. All of the reasonable ways of throwing transistors at getting faster straight-line code execution have already happened. Hell, even the unreasonable ones have been implemented, like fast 64-bit division units.
Intel and AMD have the choice of releasing dual-core processors that are 5-10% faster than last years, or they can release 4/6 core processors for about the same transistor budget. The multi-core processors are better for almost everyone - there's no way to get a 5x speedup out of a 10% faster processor.
Re:Convince your boss. (Score:5, Insightful)
The way I look at it is that we are resigned to do only certain things with a computer since, up until now, the computers we have created are only good at a certain class of problems. They suck donkey balls on most of other interesting things that are immensely useful. Take optimization problems - there is an insane amount of applications that we currently don't think of since, like i said before, we've resigned our hopes in being able to tackle those.
For example, I would love to get parallel computations figure out my 'optimal' tax returns. Have my GPS calculate optimal routes - the routes I get now are pretty crappy etc.
My point to all this is that most of the problems that look like they are one-input-one-output aren't really that. It's just that over the last 50 or so years, we've learned to model them as such out of sheer necessity.
An brief introduction to functional programming (Score:5, Insightful)
>>When you move to FP, all your algorithms break
>If moving to a functional programming language
>breaks your algorithms, then you are somehow
>doing it wrong. That line doesn't even make sense
>to me. Algorithms are mathematical constructs
>that have nothing to do with programming
>paradigm. Assuming the language is Turing
>complete, how is that even possible?
You are confused about the definition of an algorithm, and the significance of Turing completeness.
First of all, an algorithm is a *way* of doing things with an associated complexity specification (a mathematical description of how long it will take to run often denoted like O(n)).
Two turing equivalent machines don't necessarily support the same algorithms, although they will always have *equivalent* algorithms that get the same job done. HOWEVER, those algorithms don't necessarily have the same complexity. For instance, on turing machine A a sort might be done in O(n^2) while on turing machine B a sort can only be done in O(n^3).
To be functional means to be stateless. If you don't have state, then all sorts of algorithms become much more expensive. Notably, it's impossible to do a quicksort in a functional language, although other less efficient sorts may be done. Some people respond to that by saying that you can just buy a faster computer if you want to run functional algorithms; however, anyone with a decent computer science education knows that this can't solve differences in assymtotic complexity.
NOTE: quicksort (which cannot be done functionally) does not have better worst case (big O notation) complexity than mergesort (with can be done functionally), but it does have best average case and takes advantage of the underlying machine implementation much better. In some ways it is a bad example, but most people are familiar with sorting, whereas few people are familiar with dynamic algorithms.
The reason that functional programming languages exists goes back to Church and Turing. Church invented lambda calculus, and Turing invented Turing machines. Both are computationally equivalent in their power.
Turing machines have state, and are essentially a description of a hypothetical machine. Lambda calculus, is well, a calculus. It is functional in nature and has no state.
Not surprisingly, real world computers look more like turing machines than they do Lambda calculus evaluating machines. Also, virtually all programming languages are built around state manipulation, since that's what the underlying hardware has to do.
The idea of a functional programming language is to emulate the lambda calculus on a rough approximation of a Turing machine. Technically it's possible for any Turing equivalent machine to emulate any other. However, since the two machines are so different, this makes things dog slow. Again, faster computers don't solve this problem because there is an assymtotic difference in complexity, not a constant factor difference.
Compiling C in parallel (Score:2, Insightful)
Actually, I can see a whole lot of potential parallelism in compiling C. (Think map-reduce).
--MarkusQ
Re:take it from a computational physicist (Score:3, Insightful)
He's probably talking about Markov chain Monte Carlo, not the simple Monte Carlo where you just draw random numbers. You can run a bunch of Markov chains in a parallel manner with no communication, so MCMC is perfectly parallelizable in that sense. However, that often doesn't help you, since the main problem is usually a slowly mixing chain. Running N poorly-mixed chains isn't much better than running one. What you'd really like is to speed up a single chain. There are parallel MCMC algorithms out there that try to swap members from parallel chains to speed up each individual chain, but they're not always worth the effort.
Re:Convince your boss. (Score:3, Insightful)
My thoughts exactly. I can think of a multitude of possible applications that we have yet to tackle simply single core processors were not up to the task of computing the large data sets efficiently.
So many applications have been relegated to high-performance computing. Such as weather prediction, 3d rendering, chaos math, simulation, etc. Software has been been outpaced to what hardware is capable of (games notwithstanding) for some time now. Even this single core athlong64 3000 i'm using is about 100x faster than the 486 I used to think was blazing, and yet, the best we have is new versions of the same programs with layer upon layer of feature creep added in to the point where Word on the 486 ran about as well as Word on the mini super computer.It amazes me how many applications aren't multithreaded. Even on a single core, you could at least still work on something while the program also executed some task or job in the background. So man applications force you to just sit and wait on some infuriating task bar.
We need more multithreading period.
Re:Broken Algorithm BS (Score:3, Insightful)
I think Moore's law somewhat implies that those transistors will be used. It suggests an increase in computational power to parallel the number of transistors, and if the transistors go unused, they effectively do not exist.
By the same token, I'll believe that FP is the way of the future when I see it. Don't get me wrong - in a lot of ways I like functional programming. Recursion is so much more straightforward than iteration. However, tasks that can be completed with an iterative polynomial-time algorithm often end up exponential when recursive. Of course, a bit of tail recursion and you can deal with that, but some things aren't easily tail recursed (I believe that is what TFA means by all your algorithms break.) And really, when it comes right down to it, tail recursion is just contorting an iterative approach to look recursive.
Re:Why would the Algorithm break? (Score:3, Insightful)
If you're writing an algorithm in a programming language you're doing it wrong.
Re:Broken Algorithm BS (Score:4, Insightful)
It isn't recursion vs. iteration but rather pure vs. environmental (i.e. mutable variables) that make parallelism safe.
Re:Convince your boss. (Score:3, Insightful)
This to me sounds like laziness. "But parallel programming is HARD!"
That's probably a better argument than fighting the CPU designers. If parallel programming is hard, it's more expensive to create parallel programs. They'll take longer to write. It'll take longer to implement new features for them. It'll take more money to maintain them. All that seems like a good reason to avoid parallel programming.
On the other hand, if someone comes up with a new parallel programming paradigm that's slightly more difficult than procedural/object-oriented programming, but offers these benefits -- or if this exists already -- it'll make sense to switch to that paradigm as your performance needs increase.
Re:Convince your boss. (Score:3, Insightful)
That doesn't make sense. The power used by the chip will exactly equal the heat generated by the chip due to the law of conservation of energy.
Ok, that sounds reasonable.
Re:No, look at the scope (Score:3, Insightful)
Your completely right that Perl, Python, and Ruby are pigs. Java looks a little like it was dropped on its head as a child. I don't know much about C#; it tastes too much like MSWindows for me to touch it.
While different programmers have different tastes in friends, modern functional languages actually have compilers that produce code competitive with C, and a garbage collector can be a performance advantage for some use cases (faster thread-local allocation and greater sharing of data structures). But for some things, ie most numerical code, you're right that you just can't beat a static language like C or Fortran.
"everything that has been invented will be..." (Score:4, Insightful)
All of the reasonable ways of throwing transistors at getting faster straight-line code execution have already happened. Hell, even the unreasonable ones have been implemented, like fast 64-bit division units.
You, and the chipmakers, have apparently become stale.
There have been claims like this made throughout history. The patent office was closed because of this, bill gates once declared a maximum filesize we'd ever need, and the list goes on and on.
If today's major chipmakers are too lazy and uncreative to come up with new ideas, then academics and entrepreneurs will come and eat their lunch.
Quick, forward your thoughts to intel! (Score:3, Insightful)
Apologies (honest) for the sarcasm, but do really think that if the CPU vendors had any useful room left to increase sequential processing performance that they wouldn't use it? Are 3D layouts out of the research labs yet? Are production fabs for 3D chips feasible?
I.e. what basis is there to think CPU designers have any choice (for the mid-term) but to spend the transistor income from Moore's Law on parallel processing?
Re:Compiling C in parallel (Score:5, Insightful)
Bull. An industry like software doesn't depend on talent alone. If all the engineering disciplines relied on talent, we'd be in the stone ages.
The real issue is that there are shitloads of people in the software business who either have grown up knowing nothing at all but the imperative paradigm or that know about FP but think it isn't really useful or think is just the stuff os masturbatory braniacs.
As to any claims somebody would make of being a supercoder, I would be highly skeptical. The software industry is plagued be delays and bugs. Security bugs in Linux and Windows have become the norm. People have grown up thinking it's as natural for a computer to get a "virus" as it is for you to catch a cold.
Many a good people have worked hard on theories and products to produce safer code, but they are largely ignored, except in industries where it is critical (military, aviation, etc.). The average developer is an ignoramus.