Slashdot Mirror

← Back to Stories (view on slashdot.org)

Time to Get Good At Functional Programming?

Posted by Soulskill on from the dysfunctional-programming-on-the-way-out dept.

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.'"

22 of 620 comments (clear)

  1. Convince your boss. by narcberry · · Score: 5, Funny

    You mean oo isn't the only option?

    --
    Modding me -1 troll doesn't make me wrong.
    1. Re:Convince your boss. by fyngyrz · · Score: 5, Interesting

      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? Personally, I can see a machine being quite useful with say, 16 or 32 cores just because these machines do more than one thing at a time. 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. Three D architectures offer more connectivity than is currently being used, and both the number and type of one-cycle instructions within a CPU can be increased until the summary is "all of 'em", which I doubt they're going to ever get to, orthogonality can be increased until again, the answer is that all instructions are available to the same degree for all registers and addressing modes no matter what. Compilers like broad orthogonality (and so do assembly programmers, not that there are a lot of us left.)

      If CPU designers run off towards the horizon making many-core designs, what if no significant number of people follow them there? Which... frankly... pretty much seems to be the case. I've an 8-core machine, and just about the only things that actually use those cores together are the easy ones: graphics and waveform encoding/decoding. Aperture sure enough uses all my cores in a well-balanced fashion and can build a JPEG in a snap; but that's a far cry from my web browser doing the same thing while trying to render a page.

      I'm just saying that the direction the CPU folks have chosen lately doesn't have to be the direction we actually end up going, and there are points in favor of this as the best choice.

      Just some thoughts.

      --
      I've fallen off your lawn, and I can't get up.
    2. Re:Convince your boss. by Zironic · · 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.

    3. Re:Convince your boss. by Chandon+Seldon · · 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.

      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.
    4. Re:Convince your boss. by Chandon+Seldon · · Score: 5, Insightful

      The real question is if Intel and AMD will save some cash from their MMC(massive multi-core) projects and deliver a more sensible number of faster cores. You just can't depend on a given user's programs being set up to run efficiently in parallel.

      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.
    5. Re:Convince your boss. by Hooya · · 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.

    6. Re:Convince your boss. by Chandon+Seldon · · Score: 5, Interesting

      Granted, they tend to do this on an instruction level basis, but the concepts are no different at the thread level and beyond.

      That's not really true. Supporting instruction level parallelism is reasonably straightforward - you just analyses the per-instruction data dependencies and output things ordered in such a way that the hardware instruction scheduler can do it's thing. There's only one problem - optimally ordering a set of instructions is NP-hard. So if you want to do a good job ordering 5 instructions you're fine, 15 instructions is obnoxious, and 150 instructions is basically impossible.

      Further, instruction level re-ordering doesn't change the basic algorithm. If you're compiling a heapsort routine, the re-ordered instructions are still going to implement heapsort. And heapsort doesn't parallelize well. Maybe you could build logic into your compiler to detect heapsort and automatically replace it with parallel quicksort, but that doesn't help you when you run into a non-sorting routine.

      Realistically, programmers have to write parallel code for many-processor platforms. It's not amazingly difficult (given reasonable training and a reasonable set of tools), but it is different. But it's not something that's going to go away when the gcc guys / java team / VS.NET team implement some clever optimization.

      --
      -- The act of censorship is always worse than whatever is being censored. Always.
  2. Broken Algorithm BS by marnues · · 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?

    1. Re:Broken Algorithm BS by marnues · · Score: 5, Insightful

      Christ on a crutch...I didn't even pick up on it the first time around. How can Moore's Law ever be a software issue? I can accept that most people don't care about transistor count, but saying it can somehow become a software issue is just too many steps removed from the original meaning. I love functional programming languages, but this article is hurting my brain.

    2. Re:Broken Algorithm BS by sexconker · · 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.

    3. Re:Broken Algorithm BS by reginaldo · · Score: 5, Informative

      Moore's Law becomes a software issue when we need to change our coding paradigm to use all of the cores on the chip. The hardware holds up it's end of the deal, but we need to develop software that utilizes the hardware correctly.

      That's where FP comes into play, as it allows developer's to develop heavily parallelized code that is also safe and fault-tolerant.

    4. Re:Broken Algorithm BS by Anonymous Coward · · Score: 5, Informative

      It's true that Moore actually said the transistor count doubles every 18 months. However, for a long time, an immediate corollary of Moore's Law was that software doubled in speed every 18 months, which is essentially why Moore's Law as important. I think what they author is trying to say is that in order for this corollary to remain true, people must learn to write parallel software. It is much easier for a compiler to get an FP running in parallel than a sequential program (SP) running in parallel. Hence, those who can write in FP languages will be better suited to write the software of tomorrow than whose who can only write in SP languages.

  3. Amdahl's Law by Mongoose+Disciple · · 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.

    1. Re:Amdahl's Law by Tenek · · Score: 5, Informative

      And Gustafson's Law tells us that as the problem size increases the non-parallelizable portion of the program will shrink.

    2. Re:Amdahl's Law by funkatron · · Score: 5, Funny

      And funkatron's law tell us that as problems size increases you'll move into management and give the problem to someone else.

      --
      "Welcome to our world. We are the wasted youth. And we are the future too." Yes, I know these are stupid lyrics.
    3. Re:Amdahl's Law by Samah · · Score: 5, Funny

      And Godwin's Law says that functional programming was developed by Hitler for the Nazis.

      --
      Homonyms are fun!
      You're driving your car, but they're riding their bikes there.
  4. it's always a good time to try functional by cats-paw · · Score: 5, Interesting

    It's been said in the comments on slashdot many times. Learning functional programming techniques will improve your programming skills. There are many good functional languages out there, and many have imperative features for ease of transition. No functional will not solve all of your problems, but it will give you that most valuable of all lessons, how to think about a problem _differently_.

    You don't need an excuse, start today.

    --
    Absolute statements are never true
    1. Re:it's always a good time to try functional by LaskoVortex · · Score: 5, Interesting

      You don't need an excuse, start today.

      The excuse is: it's fun. But if you do start, choose the right language for the job. Python for example seems good for fp, but was not designed for the task. Don't choose a language that simply supports functional programming. Choose a language that was designed specifically for functional programming. You'll be happier in the long run when you don't run into limitations of the language you choose.

      My 2c.

      --
      Just callin' it like I see it.
    2. Re:it's always a good time to try functional by TheRaven64 · · Score: 5, Informative

      Python for example seems good for fp

      Last time I heard this, I checked, and the python developers were refusing to commit tail-recursion optimisation patches because it 'made debugging too hard'. Since most functional algorithms are tail-recursive, you will blow your stack very quickly without this. It's even in GCC, meaning that C is better suited to functional programming than Python.

      --
      I am TheRaven on Soylent News
  5. Which is more likely? by That's+Unpossible! · · 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."

    --
    Ironically, the word ironically is often used incorrectly.
  6. Thermodynamic computing by CustomDesigned · · Score: 5, Funny

    Pure functional programming removes all side effects. This make memory optimization (critical to efficient multiprocessing) much easier. It also makes garbage collection easier - but that is pretty much canceled by an increase in garbage.

    But beyond functional programming is thermodynamic computing. This starts with functional, but requires all operations to be reversible. Ideally, the total electrons are conserved - you can never clear a bit - just exchange bits (and of course more complex operations like add, mul, etc - but all reversible and charge conserving). Of course real hardware will still need to make up for losses, but power consumption and heat go way down.

    The fascinating thing is that thermodynamic programming requires a pool of known 0 bits and known 1 bits. As the algorithm progresses, you can't just throw away results you aren't interested in - you collect the unwanted results in an entropy pool. Eventually, you run out of known bits, and need to clear some entropy bits in order to continue. This takes lots more power (like erasing a flash block). The analogy to real world entropy is striking.

  7. An brief introduction to functional programming by sentientbrendan · · 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.