Slashdot Mirror
Time to Get Good At Functional Programming?
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.'"
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?
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.
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.
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."
Ironically, the word ironically is often used incorrectly.
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.
-- The act of censorship is always worse than whatever is being censored. Always.
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.
-- The act of censorship is always worse than whatever is being censored. Always.
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.
>>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.