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.'"
You mean oo isn't the only option?
Modding me -1 troll doesn't make me wrong.
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?
I don't see why an algorithm would break just because you're changing language type, the whole point of an algorithm is that it's programming language independent.
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.
(have I (feeling ((become popular Scheme) again)))
Colin Dean Go a year without DRM
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
i'm a great programmer, but i don't think i'm good enough to increase the number of transistors on an IC.
The answer is that FP languages store state in function parametersâ"that is, on the stack. ....
Everything is a function.
I think of FP programming as if it were a multithreaded program with some threads having their own core. I write threaded programs didn't use global variables, OK, maybe a semaphore, but nothing like variables. I don't see what the big deal is. I don't think this is going to cause programmers as many problems as he is saying.
This reminds me about the /. article "Twenty Years of Dijkstra's Cruelty", 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.
#
#\ @ ? Colonize Mars
#
So a quick question before I go and master FP...does the compiler automatically compile the code that can be done in parallel in the proper "way", or do I have to specify something?
Also, if I rewrote an app written in an imperative language to a FP one like Haskell, would I see a that much of a difference on a multi-core processor?
Fortunately, people are also getting better and better at the comparably diffficult task of writing good books about FP. ;-) See the new book on Haskell.
I don't quite see why algorithm should break. I would say the opposite is true, functional languages allow you to write an algorithm down much more clearly and compactly, leading to fewer bugs and better code.
The problem I have with functional programming is more that most programming isn't about clear well specified algorithms, but about routing UI events around, connecting framework components and simple batch processing, i.e. areas where functional programming doesn't provide an obvious advantage.
And of course functional programming doesn't make your algorithms magically parallel, it can help sometimes, but there is still plenty of manual work involved.
How is maintaining the rate of increase in the number of transistors that can be economically placed on an integrated circuit a software problem?
Some things are easy to parallelize because they don't need mutable shared data (known as embarassingly parallel problems), other things are hard because they do need it.
Functional programming prohibits using mutable data... so parallelization in FP is easy, but not because FP actually makes anything easier - it's because the only things you can do in FP are the embarassingly parallel problems.
If you think perl is unreadable, wait till you read FP code.. it's even more compact and complicated than perl one-liners
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.
I am TheRaven on Soylent News
I can't find a job. So don't worry, your non functional programming will lend you jobs at least fro another 30-50 years.
If they want people to use their goddamned chips, then THEY can bloody well develop the necessary software tools.
Buying a 16-core chip that does not have adequate software support is like buying a cadillac in a part of the world that has no gasoline. Most people won't do it!
My suggestion is: boycott. Just don't buy the damned things until there IS adequate software support. (There isn't yet, even for 4-core chips!)
Then watch the chipmakers jump to hire lots of programmers!
Lisp! NO!!!!!!!!!!!!!!!!
Rolls over and dies...
(added to make filter happy)
This space is not for rent.
So I think I'll just switch from Java to that.
I suppose its hard for someone whose done lots of lots of programming and none of it in a functional style, much less a functional language, and who is used to artifacts of other languages as if they were fundamental elements of programming.
Algorithms don't break. The algorithms that have a simple, concise realization in an FP language may not be the same ones that do so in, e.g., C, and the implementation of an algorithm, even one that is similarly easy in the FP language and C, may be very different, but changing programming paradigms doesn't do anything remotely like breaking algorithms.
I've recently gotten into FP. I started with Erlang and then branched into ML and Haskell. In case you're interested, here are the best books I've encountered for each language:
Programming Erlang
Programming Haskell
ML for the Working Programmer
Also, I'd definitely recommend starting with Erlang, because the Programming Erlang book made for a very easy introduction to functional programming.
The big problem won't be moving to FP. The big problem will be that many common programs simply aren't massively parallel. If your job doesn't involve many parallel tasks, you can't take advantage of multiple cores in it.
Of course, you don't have to move to FP to take advantage of multiple cores. You just need to move to multi-threaded programming. I've been doing that for 20 years now. It takes a different approach to breaking down problems into implementable units, that's all. Certain algorithms are easier to expess in a functional language, but that's more a matter of the algorithm than multi-threaded vs. single-threaded. And multi-threaded is hard. It's not a matter of the language, it's a matter of having to remember that other things may have their fingers in your data, or of designing things so they don't. That's what gives most programmers fits, and I don't see FP making that any easier because it happens before you've gotten to the code.
http://www.ni.com/multicore/
While I think every programmer worth their salt should know at least one functional language, I think the ALGOL-like (or C-like if you will) imperative languages will continue to dominate. I believe they work more like the human mind. More like the way we do elementary math. I think we will just get better compilers and libraries that will help with the parallelism.
Another thing that is interesting is that scripting languages and virtual machines really seem to be the future for programming. The problem is currently very few of these languages even support threads, let alone anything more sophisticated.
The ratio of people to cake is too big
man pthread_create(3) and quit pretending the sky is falling.
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.
Look at the table of contents of this BYTE magazine from 1985. In a nutshell it said the same thing as this article: Functional languages are the great hope for solving the parallel programming problem. Only then the languages were different: Hope, Linda, and Prolog were among them.
My response back then was to get excited about FP. My response now is: Where is the proof? Can anyone name a single instance where a functional paradigm has yielded the best measured performance on a parallel computing problem? In other words, take the best functional programmers in the world, and pair them up with the best tools in existence. Can they actually create something superior, on any problem running on any hardware? This is a very low bar, but until it's demonstrated FP will be confined mostly to the lab.
IMHO the path forward is to treat parallel programming like just another optimization. As we know, the vast majority of your code doesn't need to run fast, and you get most of the performance benefit by optimizing small bits of code that really matter. I suspect the same thing will happen with parallel programming: In a given application only a few areas will benefit much from parallelism, and these tasks will probably be very similar across applications. Graphics rendering, large matrix math, video encoding/decoding, and speech recognition would be examples. People will treat these as special cases, and either develop special-purpose hardware (e.g., GPUs), or libraries that encapsulate the nitty-gritty details. The interesting question to me is what is the best runtime model to support this.
As an example of the learning curve, I wanted to learn a little OCaml. I played around with this insertion sort example. I used it to sort a list of 10,000 integers, and it took 10 seconds, versus <1 second in C with linked lists. Not too horrible. But changing it to 100,000 integers made it die with a stack overflow, so I'm guessing that its memory use goes like n^2. However, it's not at all obvious to me from looking at the code that this would be the case. I think if I wanted to do a lot of OCaml programming I'd have to develop "FP Eye for the Straight Guy." Probably if you wanted to make it perform better on big arrays you'd want to make it tail-recursive, but it's not totally obvious to me from the code that it's *not* tail-recursive; although the recursive call isn't the very last line of code in the function, it is the very last thing in its clause...?
I know of at least one well known OSS project in Haskell, written by a very smart guy, that is really struggling with performance issues. I wonder whether bad performance is to FP as null-pointer bugs are to C. Sure, a sufficiently skilled programmer should theoretically never write code that will dereference a null pointer, but nevertheless my Ubuntu system needs a dozen security patches every month, many of which are due to null pointers, buffer overflows, etc.
Find free books.
I read a book not too long ago called Higher Order Perl, which highlights how natural functional programming in Perl is. That's right. Perl has pretty nice syntactical support for functional programming, too. The object-oriented stuff is bolted on, clumsily, in my opinion. But functional Perl is just as natural as imperative Perl. I've been writing Perl for eight years, although much less in the last few years, but this familiarity makes the transition from imperative (or what most programmers actually do, which is combine imperative and OOP styles, esp. in languages where the OOP part is bolted on, like Perl and PHP) to functional pretty simple. I had meant to use functional Perl as a stepping stone to OCaml and Haskell. But now I'm having too much fun with functional Perl...there's just no way this can end well... =D
I Want To Believe
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 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.)
This is probably a stupid question but,
Shouldn't it be possible for the operating system to provide a milticore framework-layer that will allow normal single core algorithms and applications to run in a quasi virtual mode by splitting or taking advantage of the paralel processing and reporting it back as if a single processor?
I mean if it could be done on a low enough level, and I believe most operating system provide that level by taking over the processing control from the BIOS, but it should be possible to create a sort of layer that would take advantage of the multiple cores directly allowing old school programs to function as normal but seeing the advantage of multiple cores. I'm sure it would be slower then a true multi-threaded application but would the overhead make it worse then a regular application that can only take care of one processor?
I probably used quite a few terms wrong in that. That is why I am asking, I don't pretend to be an expert here. Anyways, I was thinking that if it was a framework, then small alterations could be made to implement the ability and that too could limit exactly how much differently an application could run and thereby eliminate some of the problems in the process. My guess is the problem would be getting information back before the subsequent instruction had returned in which a modified scheduler could help with. But then again, I don't know.
Not all tasks can be made parallel. Monte Carlo simulations, or any task that requires knowing the outcome of the previous task is not able to be made parallel.
In a lot of industries many people are doing very hard jobs and making world go around. its not the problem.
the problem is feasibility. up to this point, from what it seems, mainstream computer users and even non-niche I.T. world didnt have the need for multi cores' increased performance. what do they do daily runs on existing stuff already.
and if multi core programming takes longer time, which is the main cost in programming and development projects, its a no go. huge time, small efficiency gain that little number of people care about -> infeasible.
check out games. its one of the most cutting edge areas of mainstream computer usage, and what ? crysis uses 2 cores and its still the most loaded game in demand for performance. how many 4 core games are there ? none ?
there.
this may work for supercomputing, and then again a niche part of it, but i dont see it for mainstream computer usage or i.t. industry work.
Read radical news here
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.
"...at least fro another..."
Because it had a good solution to this problem. Basically it presented the compiler with the opportunity to launch several parallel operations.
That's where this problem should be solved. Convincing all the software people to change how they do things to make up for the inability of the hardware people to design good hardware isn't the way to solve the problem.
The Itanic (erm some people might call it the Itanium) had an architecture that was ostensibly designed to fix this. But in reality it was a horrible failure for a number of reasons that I think had more to do with Intel's hubris and temporary failure to realize that good marketing is no subsitute for good engineering in the 2002-2006 timeframe.
Though, I also think that a reason for its failure is that radical new chip architectures basically require Open Source software to succeed because otherwise you have to get too many proprietary software vendors on board to porting their software. For example, the port to the x86_64 architecture was essentially complete about 2.5 years ago for Linux and still isn't really done for Windows.
Need a Python, C++, Unix, Linux develop
finish my port of XEmacs to BeOS and Haiku, and update the define of B_MAX_CPU_COUNT from 8 to 256 :)
sadly :-(
I would say rather that the nice thing about Haskell is its type system. I haven't programmed in Erlang, so I can't compare the two, but I find type inference and strong type checking make for easy refactoring, not a whole lot of unnecessary typing, and very robust code.
Many functional languages do not allow the program to manipulate shared state, which removes that whole class of problems; information sharing is limited to letting the run time system fork threads and copy function arguments and return values back and forth.
However, if you really do need shared mutable state (and there are plenty of algorithms that do), in Haskell there's software transactional memory, which provides a restricted API for manipulating shared mutable state with the STM monad. Since the code within an STM transaction is not allowed to cause side effects or access any shared mutable state outside of STM, the runtime system is able to stop and replay transactions whenever it detects conflicts. This is one area where FP actually can make things easier, by enabling the same sorts of operations you might do in an imperative multithreaded program, but doing it in a much safer way.
And, if you don't need shared mutable state, sometimes parallelism can be achieved just by replacing "map" with "parMap" in the right places and recompiling with the appropriate options. It doesn't get much easier than that.
Auto-parallelization of functional programs has been proposed for decades now, and every attempt has fallen on its face as the overhead has killed any gains. Current parallel FP research isn't even putting that much effort into auto-parallelization, because most PLs researchers consider it a dead end---taking a random FP and evaluating all its thunks in parallel as futures, or some similar mechanism, is not going to solve the problem.
Instead, most of the current research is in programmer-level primitives for designing and specifying inherently parallel algorithms. There is some of this in both the FP and non-FP communities.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Poppycock. functional programming is a different axis to parallelism. Functional purity makes extraction of implicit parallelism easier, but what's by far the most successful parallel paradigm in use today on the largest, most complex problems on earth in the HPC field?
Explicit Message passing between processes. And that works just fine on multicore chips (consider the shared memory an optimisation allowing message passing by reference). Why? Humans seem to have a knack for it, maybe some built-in "wetware support" because we're social apes that have to model apes talking to eachother to get along.
It's notionally less simple than some models, but it seems to me it takes years of compsci training for someone to actually prefer anything else to MPI in practice
The old practice of getting customers to buy new chips or PCs because it would immediately improve the performance of their existing applications will no longer be possible.
From a business perspective, that's going to be more of a problem for chip makers than software companies. In fact, if applications start acting up because their multi-threaded design didn't consider multiple cores, it's the new PC that will be blamed by the typical customer, not the software (e.g. "I bought this new multicore PC and now my applications aren't working right. Don't buy these machines until they get the bugs out")
Despite any theoretical beliefs, we haven't seen enough real-world applications converted to be multicore aware to know what (if any) improvement in performance will be seen.
For many applications there may not be a good business case for rewriting legacy software.
First, the scope for mono-processors is now strictly limited and we _will_not_ see x2/18 months again, there may be x10 to x100 possible within this basic technology but thats just a few Moor's law cycles; second, the (commercial) problems, as described elsewhere, involve the solution of partial differtial (Heat, Navier Stokes, Elasticity) Equations or Stochastic Simulations --- all of which are inherently clusterable, but not gridable).
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.
While I do think FP is going to be a big help with multicore, a problem I haven't heard anyone talking about is that when you have several cores allocating heavily, it's going to be a lot of work to clean up after them. I think we're going to need hardware garbage collection, or at least hardware support for GC. It will be nasty and complex because of the concurrency, but I just don't see how else we're going to deal with the allocation rates.
Hardware GC is not new: the Lisp Machines had it, though of course it wasn't concurrent. Everything old is new again...
Your god may be dead, but mine aren't!
The Moore's Law has absolutely nothing to do with software. The Moore's Law states that the economically optimal level of integration doubles each set period of time. There's absolutely no way software can fit into this picture. Another ignorant but creative interpreter of Moore's Law, apparently...
At the cost of replying to myself:
Academic and other work has often focused on language design with incremental language facility addition eg C -> C++ -> (java, C#) or Dr.N Worth's Pascal, Modula-x.
This is the exact opposite of what we need, we have C as a given, and we need to make the code generated for parallelisable cases _much_ better.
>>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.
You seem to have some serious misunderstandings here.
Uh, no. By removing side effects functional programming removes the need to copy anything. If I'm trying to evaluate f(X) + g(X) for some complicated X, f, and g by evaluating f(X) and g(X) in parallel and adding the results, I don't need two copies of X because I know that neither f nor g will modify it. That's the whole point.
It only seems counter intuitive if you've swallowed the procedural programming paradigm and adopted it as your own to the point where you've forgotten how counter intuitive "X = X + 1" seemed at first.
And saying it's non-deterministic is just nuts. Sure, you could add non-deterministic semantics to any language, but there's nothing inherently non-deterministic about functional programming. In fact, I think you'd typically have to work a lot harder to make a functional language non-deterministic.
FP has nothing to do with threads, apart from the fact that functional programs could be executed by a large number of threads in parallel (or independent cores, or...?) without changing the outcome. And what exactly is the mess we're in? I can't think of another industry that has succeeded so spectacularly in such a short time.
And so on...did I just feed a troll?
--MarkusQ
Lisp, for real men.
However, there are some real world reasons why people don't always prove their algorithms, and almost no one uses functional languages.
First, most programming problems in the real world are so intellectually tedious that proving the correctness of their algorithms would be waste of time. Many algorithms *should* be proven, but consider how much of you code is just boilerplate, and doesn't really do anything algorithmically interesting. Usually around 99%.
Second, functional programming doesn't allow state manipulation, so a lot of algorithms can't be done in them.
Actually, I can see a whole lot of potential parallelism in compiling C. (Think map-reduce).
--MarkusQ
The article doesn't mention that you can do functional programming in python. For someone who uses python already, is there any reason to try haskell etc (i.e., beside just the interest in learning another language)? Python use is pretty widespread these days.
Python has some features inspired by FP languages including Haskell, but is not anything like real functional programming. Haskell is far more powerful and serious, but also a heck of a lot more difficult to use. Python has a "practicality beats purity" mantra; you could think of Haskell as "purity strikes back".
Stuff Haskell gets you:
Serious native-code compiler whose output can beat compiled C code for some programs (and does darn well on average, see the Alioth shootout)
Ability to use multi-core parallelism, with a library module that treats shared memory as a transactional database, allowing use of shared data between threads while getting rid of all the lock management headaches of languages like Java. This can work because Haskell's functional purity guarantees that the threads won't clobber each other except under circumstances precisely controlled by the library.
Data parallelism allowing computations of list comprehensions to automatically be done in parallel on multiple CPU's
Rigorous type system (nothing like the broken ones like in C or Java that you might be used to) lets you express complex invariants in your datatypes so that errors can be caught by the compiler. This greatly decreases the amount of runtime debugging required.
I could go on, but you get the idea.
Good tutorial: http://learnyouahaskell.com/
More detailed book (full text online): http://book.realworldhaskell.org/
Haskell has a very steep learning curve compared with other languages (or "unlearning curve", as some put it, since you have to forget everything you knew), but learning it (a still ongoing process for me) is one of the most interesting and mind-expanding things I've ever done as a programmer.
The Moore's Law has absolutely nothing to do with software. The Moore's Law states that the economically optimal level of integration doubles each set period of time. There's absolutely no way software can fit into this picture.
Another form of Moore's law is that it's price/performance that doubles in some set period of time. Up to about now the two have tracked, but now they're starting to diverge.
Their gripe is that single-chip gate counts have gotten large enough that they're bigger than a single core. You can't find anything interesting to do with many of the gates. So the "economically optimal level of integration" becomes multicore processors. But to use them effectively you have to modify your programming style - otherwise you end up with the performance of a single core, which didn't go up in proportion to the POTENTIAL performance of the gang of cores.
Thus the two formulations keep tracking only if you go to parallelizable coding techniques. If you stay with serial coding only the price/performance formulation falls off the exponential curve.
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
The difference between 1985 and today is the end of the free lunch in clock rates. 1985 was roughly the middle of the last great clock rate stall - during the shift from minicomputers to micros, Moore's Law expressed itself not as speedup, but as decrease in cost per bit/gate.
Then we entered the great die-shrink and clock rate increase era, where for about 20 years processors really did get twice as fast every 12-18 months. Why expend the effort to bury a problem in parallel hardware when you can see faster serial hardware coming over the hill?
Clock rates have stalled again, and we're reaching physical limits for our current fabrication methods and physical chip designs. We're seeing renewed interest in functional programming because it looks like a way to make use of parallel hardware safely compared to imperative coding. Traditional coding methods are easier to understand, and are probably more efficient when they work, but...
how fast do you want the wrong answer?
To a Lisp hacker, XML is S-expressions in drag.
OpenMP makes it simple to write code that takes advantage of multiple threads, and it's supported by gcc 4.x, Visual Studio (just not the Express editions I think), and other compilers.
Let's say you have a few thousand (name, address) pairs and you want to be able to quickly look up a name to get the corresponding address, to add new names, etc. In imperative programming you'd probably use one of the mainstay data structures of CS 101, the good old hash table. To add a new name, you hash it and go and poke that address in the table to record the entry.
Well remember that stuff about values in functional programming being immutable? Right, no hash tables in functional programming. You'd instead use something like an AVL tree or red-black tree, that let you create a completely new structure that shares most of its content with the old one, except that the new one has this extra node. Of course FP language libraries come with modules for making those structures, and in practice you can use them at the API level sort like how you used to use hash tables, but they are completely different underneath, and if you want to program them yourself you are going to have to learn a lot of very basic techniques from scratch all over again. Chris Okasaki's book "Purely Functional Data Structures" is a good place to learn about this stuff in detail.
Even more basic: the good old "for" loop, which updates an index variable each time through. Whoops! You can't update the index in a functional language, so there's no "for" loop. You instead use recursion, or a "higher order function" (function that operates on other functions). So instead of
for (i = 0; i < n; i++) xs[i] = f(ys[i])
You'd write something like
ys = map f xs
("map" takes a function f and a list of values xs, applies the function to each item in the list, and gives you back a new list). There is also a "list comprehension" syntax that you might know from Python:
ys = [f(x) | x <- xs]
but for complicated functions you end up having to use higher order functions and recursion explicitly. You really have to think a lot harder to program 20 lines of Haskell than 20 lines of C. But those 20 lines can do an order of magnitude more.
(Aside:) In case you were wondering, yes, you can implement traditional hash tables and other mutable structures in functional languages, and there are times when it's necessary, but it's comparatively a pain in the ass and you give up some of the advantages that had you programming functionally in the first place. Here is an article about someone's experiences switching from a mutable structure to a functional structure in a large program, and the headaches the functional structure solved:
http://www.cs.tufts.edu/~nr/pubs/zipcfg-abstract.html
I think FORTRAN is going to stay the untouched leader in the fast and easy to program supercomputer / parallel mathematical simulations market. C is a very close second. Simply put, every supercomputer manufacturer makes sure its FORTRAN and C code is very quick, because that is what most of the customers use. I can't see Haskell competing in the supercomputer market / parallel processing market yet.
The next question is: Is Haskell going to be used in your next GUI based application that has a really processing intensive back end? Well functional programming is about finding a nice easy to program way to abstract and hopefully eliminate the serial aspects of your program. GUI code is about as serial as it gets. Users find it very confusing when programs pop up dialog boxes in parallel. This means a fundamental language-independent tension will exist in your program between the serial GUI code and the parallel back end code.
I don't think a good solution for the "easy parallel programming problem" is on the market yet. I would appreciate suggestions, because I am looking. I think Microsoft missed a big opportunity with .NET. Microsoft released a new programming architecture, but they omitted ground-up support for NUMA, supercomputing, and parallel processing architectures. The next big jump in computing will be the language that can smoothly harness various computing configurations ranging from single-core/single-computer to multi-core/multi-computer with no gaps in between.
Google may be the closest to the "parallel computing solution". They use Map-Reduce on server farms and then structure the program in a client/server architecture. Thus the client can have a procedural GUI, and the server can run parallel code. In Google's case the client is a web browser, and the server is a web server attached to a server farm. Maybe we just have to get used to client-server architectures for any programs running CPU intensive code.
The functional programming censorship squad is out in force, I see. LOL. Truth hurts, doesn't it?
Parallel programming is being facilitated in every modern OS by providing multithreading and multiprocessing capabilities. The programming language has to do jack with parallelism. That's what all those multithreading APIs are for! Read your system API documentation, then grab your favorite programming language and hack away!
10 cls
20 print "yep, this still sucks"
30 end
"It is counterintuitive because nature does not execute equations to do its thing. The human brain is orders of magnitude more complex than any program in existence and it does not perform equations. Nobody should be forced to use an unnatural notation for computer programming just because mathematicians are enamored with it. A computer is not a function evaluator. The proper context for computing is behavior and it comes from psychology, not mathematics."
The idea that any notation for computer programming is "natural" is quite funny to me, especially given the amount of time I've spent trying to grok oo. "Natural" is not an absolute -- people differ in their preference for expression. Some sing, some talk, some like music and some like programming. Pretending that the approach that has aligned best with your intuition is the only sensible way of programming a computer is nearsighted at best and pompous at worst. How do you explain the interest in functional programming? Are all these people just "unnaturally" attracted to these bizarre concepts, or have they also found a metaphor that aligns with their preference?
When you rail against someone with preferences expressed as truths, you are bound to tick off some people.
Also, when you talk about 'nature not executing equations' -- one of the most interesting things about most of the behaviours we have identified in nature is that they are best modelled using many simultaneous equations. Languages that are designed to model 'the real world' inevitably contain methods of specifying things that should happen simultaneously (have a look at for example Modelica). Almost all the advances we have made in predicting what happens around us to any degree of accuracy has gone via equations or sets of equations. I cannot see how I would get anything done without them. Definitely I cannot think of anything in nature as 'behaviours' in a way that enables calculations. Of course, if this is how it works for you, that's fine, just don't tell me the way I approach the world is totally wrong and unnatural when it works for me.
Languages aren't inherently fast -- implementations are efficient
Functional programming will NEVER take off in anything other than niches. It is too unfamiliar / hard / different for java monkeys. Low number of people with knowledge makes replacing people hard for managers, and nobody wants to be stuck with a project with no readly available resources at hand.
For parallelism, the issue is not functional programming, but single assignment. In a single-assignment language, each variable can only be changed once. Functional programming is one way of achieving this, but it's not the only way.
The idea is supposed to be that single assignment makes it easy to turn a program into a pipelined form at compile time. It's supposed to make automatic parallelization easier. In practice, compilers for single-assignment languages haven't been overly impressive in performance.
Good luck. As these wafers get smaller and smaller, the biggest limits to making these chips faster and faster are:
1) Transmission line theory -- since the information is so fast
2) RC -- the CPU lines have built in parasitic resistance and capacitance.
In combo the two are deadly:
CPU puts out a code for the ALU... clock is so fast that before the other end of the line at the ALU has reached the new value, ALU reads what's already on the line. Uh oh! Then with transmission lines, if the data moves at a certain frequency and the ALU and register are a certain distance apart, then it can be mathematically shown that the ALU will never read anything from the register.
The best way to overcome these right now is to simply throw more wattage at the problem... but that's not exactly a great solution, is it?
Python has terrible problems with concurrency. CPython can't use more than one CPU at all, even in multithreaded programs, because of the infamous "Global Interpreter Lock".
In Python, there's too much shared global state associated with binding. The dynamism that makes it possible to add a new function to an object during execution means constant access to object dictionaries shared across threads. Python not only has late binding, it has hidden late rebinding; some other thread can modify an object while control is within an object instance. This is rare, and usually avoidable, but because it's possible and can't be detected at compile time, the run time system has to make the worst case checks every time.
Apparently there isn't a magic fix for this. On a new found whim, I'd decided to look back into functional programing, since perhaps it would better utilize my multi-core machine. You know what I found out, parallel programing is hard. Ocaml, or at least the version I have a build script for, has a race condition in the parallel, make build. Trying to install a language that might do multi-tasking, breaks multi-tasking on install. I give up and go back to reading up on mutex's and trying to wrap my mind around debugging threads.
I think I just cashed out all my cool points.
A chip like Itanium requires parallelizing compilers. These do exist, but often cost a lot of money. Languages like Occam have builtin language features for parallelism, but even a multithreading library like pthread could be inlined by the compiler. It's all a matter of compiler design, that's why Itanium wasn't very populer, because there are only few compilers. CS students should be tought how to write HLL compilers, so that more people know how to do it and aren't afraid of it. It's really simple if you look underneath the apparent complexities. For instance, a recursive-descendant compiler is easier to implement by hand than a table-driven compiler. Tools like lex and yacc should be banned from compiler theory lessons. These are things that only increase the apparent complexity for the student. In fact, writing compilers is extremely simple if you know how; a good book has been "BCPL - The Language and Its Compiler", because it contained portions of a hand-written compiler. Lexical analyzers and syntax analyzers are very easy to implement. Basically, a BNF or EBNF already describes the layout of the syntax analyzer if its implemented in a recursion. I successfully implemented a number of compilers for specialized languages without even a CS background, just by writing solid recursive code.
Functionaly languages haven't taken off in a large part because garbage collectors have only rather recently become "good enough."
Your right that many programmers seem to have hard time grasping FP.
Now that's just false. Of course FP languages are deterministic, and try telling the trading companies using Ocaml that FP isn't suited for "mission critical" work. Or tell it to Intel and AMD who use ML and Scheme to verify their processor designs. The only thing close to what your were saying is that GC can introduce unpredictable pause times; not a problem for most apps but a killer for real-time systems. Of course, there's a lot of recent research into real-time garbage collectors with very good results.
Ok, now I'm convinced that your full of crap.
Can you imagine getting the average programmer to bang out Fizzbuzz in Haskell or Erlang? These guys are flat out finding the "PrintIfFizzbuzz" method on IntegerWithFizzbuzz class in the .Java IDE. Let alone grappling with functional concepts. I'm just saying ...
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.
VLC FOR MAC IS DYING! IF YOU DEVELOP, PLEASE SAVE IT!!
I cant believe what I read. Michael Swaine? I have been reading him for decades.
My algorythms paradidgm always starts with when in doubt, spawn, and let YOUR scheduler figure out wether its on your Core, your chip, FU, on your board or your network, or your local cluster/remote cluster...I remember reading Michael Swaine talk about budgeting and bargining processor units, to see which were faster, more efficent:
To whit: Both distrubuted web services, distCC image rendering and distrubuted database services, ALL can be set up on a "processing economy" to get a job divided, parelelled, and processed. Richard Feynman was able to do this with punched card jobs at Los Almos.
Its just with running with such gross schedulers as Windows has, no one is interested anymore in efficency, except as an academic excercise.
UNLAMBDA is going to have a new Life! I never really liked reusability anyway.
What about the approach taken by the language Fortress?
If the entire community has to move to a different paradigm, would it ever happen? I guess not.
People want to keep coming up with ways of fleecing the customer, keep them generally employed and apparently occupied, where each customer is only another link in a predatory chain like the biological food chain.
IMO another reason functional languages haven't taken off is because most lack decent (and well documented) _standard_ libraries for doing many common things, and even if there are decent libs there's typically no way to know which is the standard one to use.
;) ). So similarly who wants to deal with 10 different database abstraction modules, or 10 different networking libraries, or 10 different signal handling libs? Or worse, having to write and debug from scratch your own lib after spending time to find out the libs out there are crap.
Between picking a programming language that is powerful (expressive/concise) for all the code you have to write (insert random FP language here) and picking a programming language that is powerful for all the code you don't have to write (perl, python etc), I'd pick the latter in most cases.
Even if an FP language is 2x more concise than perl for a given task (AFAIK it isn't), without lots of decent libs, you usually have to write a lot more code.
The more code you have to write, the more code someone else later on has to read and understand. And worse the more code that has to be documented and maintained.
Standard libraries are important, even if they are only defacto standards because if you use a standard library, even if it's buggy, when an experienced programmer looks at your code, they know what the lib does (and hopefully its bugs), so they only need to read your code, they don't have spend time looking at the lib.
Whereas if you were writing your own custom libraries, or using one of 100 possible libraries (with no defacto standard) out on the internet, the person taking over or helping out will have to spend extra time trying to debug/understand it.
Some of the FP languages are catching up in terms of standard libraries, but for many you either have to write your own crap or have to waste lots of time finding and evaluating libraries to see if they are worth using.
Nobody in their right mind wants to deal with 10 different print commands (ok maybe the php people are different
I'd rather be able to get on with writing the more "interesting" bits ASAP.
I wonder if compiling eight C programs in parallel on an eight core CPU is faster than compiling them sequential, because one of the performance bottle-neck seems to be in the amouth of data to be read (searching for include files) and written. Not so long ago there was a long discussion on whether it is better to compile C programs separately or simply include them all in one single file.
What the parent says is true! Search "Reversible computing"
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?
I use Friend/Foe + mod-point modifiers as a karma/reputation system.
Not only wouldn't you have had to re learn a new language every 3 years, every time the current fashions changed, you still wouldn't have to learn a new language to exploit massively parallel systems.
Deleted
Forth, Lisp, Ada, Prolog ? These are good old concurrent language that proven to be useful ! For 20 years now, Erlang is used in industry, and it's a distributed concurrent fault tolerant programming language, it prooved it's efficiency, so there is no hype about it : http://en.wikipedia.org/wiki/Erlang_(programming_language)
Oh, and it's the programmers to adapt the new challenges. When multitask arised, they adapted, when Rational Roses made the UML a standart, it was new, the programmers adapted. Why wouldn't be able to adapt to functionnal language, aren't they paid enough ?
second everything in this post
why reinvent the wheel?
as 99% of programs rely on an
underlying OS that does all the
house-keeping (mostly), why shouldn't
a new multi-core-aware programming language
force you to "think for the machine"?
if the programming language is
good.smart enough, you can keep programming
the way you did on a single core machine, but
smartly distributing it to all available
resources.
it's like saying " please pile all these
stones ontop eachother so it is a pyramid"
instead of "take stone A give it to worker
crew A and move it to location XY, etc..."
the challenge isn't (shouldn't be) to write
multi-core aware assembler code(*), but a
OS.language that does all the heavy lifting;
which is aware of all the resources...
(*) cutting edge and expensive :P
And so on...did I just feed a troll?
No. You replied to someone you disagreed with, which is a rather different thing.
Get this into your head (and this goes for many others, too): disagreeing with your opinion is not the same as trolling. In fact, even playing advocatus diaboli (which may not even be what the GP was doing) is not the same as trolling, either, not at all, although the outward difference may be too subtle for some to grasp.
There's only so much the VM makers can do for you. The VM can't safely parallelise operations unless your operations are made of small, composable, side-effect free units... and that, my friend, *is* functional programming.
Of course, many of the parallelisable tasks can perhaps be done "behind" the scenes, not at the VM level, but, say, inside an application toolkit.
However, it is still up to the implementers to make use of parallel execution; and it's still up to you to do that, too, if your problem is one of those that can benefit from concurrency.
Not to mention that functional programs are much easier to reason about when writing concurrent programs: If you have a pure function, you only need to be concerned about the values it returns; any concurrency is irrelevant. In a well-structured program, operations with side-effects can be isolated and kept as minimal as possible.
The availability of multiple CPUs is a fundamental aspect of commodity architectures. If you try to let software people pretend it isn't there, you will get slow, crappy code. people really do need to embrace paralellism, but folks are making it a lot harder than it needs to be. Multi-core just gives us all kinds of flexibility that we never had before. as a straight-forward example, suddenly, the efficiency arguments of monolithic vs. microkernel, where running services with IPC now becomes a lot more exciting.
At the application level, people need to stop thinking about single programs. It's only natural because people were trained that way, but for the next generation, it will seem odd. Individual programs will be simpler. Forget multi-threading, don't try to build large single applications. This is right up the linux/unix tool based alley. Lots of communicating sequential processes (apologies to Hoare) with individually simple elements, and each component being easy to test individually.
Build algorithms with loosely coupled, asynchronous communications, and simple components. People get themselves tied into horrible knots because they try to get serialism out of multi-processing, and in doing so, they kill the very thing they are looking for: performance.
No, you don't need a single log file, 200 log files + dsh & grep will do. No you do not want to serialize writes into queues, just give the queue entries hashed indices, so that inserts don't clash. Etc... It's a bit of a mind flip, but the water is fine.
I don't think so. The reason that you don't have side effects is precisely because everything is copied to message channels.
What the hell are "message channels", and why would you need them when your data is immutable?
When people say that they want to learn "functional programming", they usually mean some functional programming language. Common functional programming languages (OCAML, SML, Haskell, Lisp, Scheme, etc.) are duds when it comes to performance: in principle, they encourage parallel-friendly programming, in practice, they get many basic language design and performance issues wrong.
It's also silly to rewrite large amounts of code when usually only a small percentage of the code is performance critical. If you need to speed up C code to run fast on a multicore machine, optimize the inner loops. All the "functional programming" you need for that is available right within C in the form of OpenMP. You'll understand OpenMP a little better if you have used a "real" functional programming language, but the concepts aren't rocket science and you can do just fine as a C programmer.
http://metpx.sf.net/
Each channel on which messages are received is a process. The receiving process decides what tasks need to be done, and "queues" (hard links the message into an input directory) it for downstream actions. This operation is daisy chained as needed. Each "queue" reader is a separate process. We run with a few dozen receivers, a few hundred senders, and half a dozen filters. so a single application with a few hundred tasks, that scales as we add load (additional load is additional senders or receivers.)
each process is just a normal python program, individually quite simple. It's multi-core ready, and dead simple. Testing of smaller programs is easier too. Parallelism is not a problem, it makes life easier, provided you approach it properly.
Either that, or it's because the lambda calculus has sent more than one geek running screaming off into the night.
What we need is concurrency-proof language like Erlang, merged with the simplicity and stateful object-orientedness of Python
Now if someone just cleaned up the syntax and became a DHH style, cool guy poster child for it, then we'd be talking.
Screw realty just hook me up another monitor!
I can't find a reading of this claim that isn't utter nonsense. Are you saying that it is inherently impossible to determine the results of any recursive calculation? Or that it is inherently impossible to prove a recursive calculation terminates? Or set a bound on its execution time? 'cause all of these are clearly wrong. Are you claiming that recursive calculations necessarily involve some sort of quantum weirdness? That seems hard to believe.
So what do you mean?
--MarkusQ
Those Chipmakers should pay attention to IEEE's opinion. Dealing with memory is a significant problem for processors as the number of cores increase. That sounds like a hardware problem to me.
Shoving responsibility from software to hardware or from hardware to software isn't going to solve anything. There's things that have to happen on both sides before we can go nuts with the number of cores we put on chips.
Dice results:
Haskell -- 8 matches
Erlang -- 18 matches
So... the answer is "no".
For Haskell, Real World Haskell is probably a better option (more like Programming Erlang, and practical).
In particular, it talks a lot about multicore programming.
Hmm... But compilers already parallelize. All the instructions in a pipeline could be said to be executing in parallel. Compilers already do a bunch to manage that parallelism. The kind of parallelism you get from having multiple ALUs and instruction molecules seems a lot closer to the kind of parallelism that you get from a pipeline than the sort of parallelism that requires you to launch several threads.
Am I wrong?
Need a Python, C++, Unix, Linux develop
Obviously not enough geeks are garbage collectors, and thus still not good enough.
I'll look past your abusive tone and know it all attitude and just address your main point.
You claim that it is not possible to bound stack usage in recursive algorithms. This is not true. By requiring tail recursion it can be limited to exactly zero bytes over that used by a non-recursive algorithm. By proper use of accumulators, the vast majority of useful algorithms can be converted to a tail recursive form.
Even without this, recursion depth is generally bounded by some property of the data structure, and can be limited to the same extent as any other property with a similar dependency. Def Stan explicitly acknowledges this: "recursion should not be used in the implementation. unless strict bounds on the depth of recursion can be defined and hence it can be shown that the permitted memory usage will not be exceeded."
Note that this isn't any harder (or more stringent) a limitation as the similar requirements on buffer size, queue length, loop termination, etc. all of which can vary in exactly the same way.
Finally, non-deterministic has a specific meaning, and it isn't the one you seem to be using. Something is non-deterministic if (and only if) it can't be determined in principle, by any one, no matter how clever. You seem to be using it to describe something which is hard to determine by people with your mindset, regardless of how tractable it may be in general.
There's a big difference between "I can't figure it out" and "it's non-deterministic." Recognizing the former doesn't in and of itself justify asserting the latter.
--MarkusQ
Some of this was tried in the Haskell community, with relatively unimpressive results---a lot of algorithms are mostly sequential, even in a parallel language, and the speedups, especially after futures/whatever overhead, aren't amazing, especially past 2 cores or so.
That's my understanding of why most current research is on adding primitives that let the programmer specify parallel algorithms at the source level, such as Parallel Haskell's par and seq primitives.
Basically the automatic reordering the compiler can do doesn't really suffice, at least with any method anyone's figured out so far; to get anything close to a 64x speedup with 64 cores, you really do need the programmer to write parallel algorithms explicitly.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Oh, Moore's Law. Never mind :-)
``Tension, apprehension & dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_
I have heard this from the functional programming community, but from my perspective, functional programming is just another threading strategy. The memory disambiguation problem, while real, isn't the limiting factor in the performance of programs.
If you look at the Wall paper, which was a limit study of instruction-level parallelism, and then the Lam paper, you will see that even with perfect memory disambiguation the amount of parallelism is fairly small. The small size of basic blocks and therefore frequency of conditional branches, is the greatest limiting factor to program performance. Only if you can enlarge basic blocks and/or execute speculatively are you going to see serious improvements on a single processor.
We know instruction-level parallelism on a single processor isn't large, the problem of writing multi-threaded code for multi-core processors, is identifying sufficiently large chunks of code to parallelize. In other words, where ILP occurs for free by the processor, now the compiler or language must identify the threads to take advantage of multiple cores. Further the compiler or language must wrap this code in threads that the operating system understands.
The traditional multi-threading technique is where you set a programmer at his computer and tell him parallelize stuff. The functional programmer will certainly identify parts of the code that can be executed in parallel, but I am not sure that is better than any other thread markup. All programmer threading techniques suffer from the fact that a programmer must see the parallelism in their program or algorithms to take advantage of it.
I believe we are going to see faster software from multi-threading on existing architectures if we find automatic thread identification techniques. Automatic thread identification, like any other compiler optimization, could yield the speed desired, by finding more parallelism in the program than what a human can.
Since SSA is Functional Programming there is no need to learn a language like Haskell or Erlang.
No, that's largely correct, but it's not that much of a difference. If a compiler knows how to handle parallelism, handling threads isn't much extra overhead. Probably, such compilers (for languages like C and C++) already exist, but are too expensive for most users. I don't know how good GCC is at generating Itanium code, but it has become far better in generating X86 code over the years. That makes GCC increasingly good even for cases in which optimization truly matters. If you look at medium-priced compilers like IBM C Set and IBM Visual Age for C/C++, you can see that even for a 4- to 5-figure sum, you can get pretty good optimizers. The best ones are in the 6- to 7-figure range however (b/c they're sold in small numbers by small companies). Applying every optimization strategy known to mankind in a reliable and robust manner costs a buck or two. That's an area in which GCC needs to be further improved (to make optimizers that always work), but 4.x has become quite good in that respect also. Still, if more people would know how to write compilers, there wouldn't be so many monopolies around.
It is counterintuitive because nature does not execute equations to do its thing. The human brain is orders of magnitude more complex than any program in existence and it does not perform equations. Nobody should be forced to use an unnatural notation for computer programming just because mathematicians are enamored with it. A computer is not a function evaluator. The proper context for computing is behavior and it comes from psychology, not mathematics. A computer program is a behaving machine, that is all. Functions and calculations are just types of behaviors, not the be-all of computing. They should not be the basis of how computers work (that was the problem from the beginning, Babbage and Lady Ada comes to mind). The correct (and highly intuitive) metaphors for programming and processor design are concepts like sensor/effector, stimulus/response, concurrent/sequential, predecessor/successor, etc. These are things that are readily understood by everybody, even kids.
The idea behind computers is to have them "behave" in ways that are not natural, but artificial. That is why we make them. If we want you "natural" behavior, we could just stick to humans.
Right now, the problem is not so much with the tools, but with the paradigm in which the chip makers are operating.
They are still focused on a parallel "paradigm"(god I hate that word.) that's thirty years old.
Synchronous processors are, IMHO, a better solution to this than just throwing piles of cores on a die. Look at Project COSA for example. http://www.rebelscience.org/Cosas/COSA.htm
Something like this would be far more appropriate. Yes?
"If GPU technology has taught me anything, it's that you can make gamers pay $700 for a graphics card and $200 for a new 600watt power supply as long as they're getting their shiny things fix, so power efficiency doesn't matter for the desktop market, laptops and servers being a different story."
Except that the latest crop of video hardware turns that argument on it's head. I can get more horsepower (dual GPU) now and for under $600 than ever before.* Even the $600 PSU isn't needed except for the most loaded, overclocked machines out there. And even that really isn't being done for performance reasons so much as it is economics. e.g buy cheap, overclock. Get the next hardware up for "free".
*Even IGPs are becoming respectable.
Shai Schticks:"You don't make peace with friends, you make peace with enemies"
"The average developer is an ignoramus."
Which one are you and why should that be exclusive to you?
Shai Schticks:"You don't make peace with friends, you make peace with enemies"
The traditional multi-threading technique is where you set a programmer at his computer and tell him parallelize stuff. The functional programmer will certainly identify parts of the code that can be executed in parallel, but I am not sure that is better than any other thread markup.
Perhaps multi-core is an intermediate step towards fine grained parallelism. Self-assembling carbon nanotubes sprayed on with ink-jets may suggest novel approaches to problem solving.
For instance, take the sorting problem, mentioned earlier in this thread. Instead of a sequence of unsorted numbers, you beam them onto a substrate all at once. Lets say that the substrate contains nodes that are arranged where any two vertically arrange nodes are min-max sorted to two horizontally arranged nodes like so:
max....min
Now, with some additional magic of redundancy and spin, a vertically arranged unsorted list could by sorted into a horizontally arranged list in O(N) time (albeit in a N^2 space). There is no separation of CPU and memory. Instead, you have a Cellular Automaton that is arranged along an octahedral lattice.
So, which language would best describe such a sort? I don't know. It seems that each language is an attempt to express a range of applications within a domain of op codes in the most compact way possible. Perhaps FP will better fit large-grained parallelism. But, I'm not sure what would best express the mindset of FPGA's, cellular automata, and the neural model of McCulloch and Pitts.
"When we do that, we notice that what goes on in the gaming industry, soon becomes standard everywhere else. And both modern platforms, the PS3 and XBox 360 (I'm not including the Wii as Nintendo has different goals that having bleeding edge tech.) have multi-core processors. Radically different architectures, but multi-core none-the-less. We are also seeing this, and have been for a while, multi-core entering the desktop."
You're leaving GPUs out of the equation. It doesn't completely leave out your "multi", but a multi-core CPU isn't the same as a multi-shader GPU. And with IGPs making an appearance in the chip sets GPGPU will become more common.
Shai Schticks:"You don't make peace with friends, you make peace with enemies"
Yes, I just got a wonderful new computer for under $200. It's got 216 cores. But they're all pretty small. It's called an Nvidia GTX 260 core 216. It's also a graphics card.
Which is all very nice until I look around and see that there's not all that much that's been done to optimize tasks for parallel execution, with the exception of graphics. But that's changing, and programmers need to realize this is where performance is going to come from in the future.
It's funny, though, sitting here running three virtual machines on my desktop on two cores (AMD) and how wonderful it would be if these could utilize the parallelism inherent in virtual machines. I am not expecting that vmware is going to be able to offer me the ability to run 216 instances of linux on my video card, but perhaps in the future some paradigm refinement will allow allocation of cores to problems which will take different courses towards parallelisation, either by creating virtual machines (very restricted and inefficient, but secure and easy) or by having more lightweight structures where the task is simple and repetitive and performance is important. Or even better, know when NOT to use the full GPU. How about knowing when to shut down certain cores, and use the freed resources of heat sink and power to dynamically increase the clock speed of the remaining cores..in such a way then, optimizing the tasks and the hardware both.
Well if this rambles a bit I am sorry. I am sorta thinking 'out loud'. Maybe I just need to get a blog and not subject slashdot readers to my madness.
I think it was funny because functional programming is already hard enough that adding the reversible requirement seems over the top. In actuality, a reversible computer can run non-reversible code just fine - it would just quickly accumulate "entropy" bits that need to be cleared. Algorithms adapted to reversibility would minimize the "entropy" generated.
This article seems to ignore the fact that many of our desktop apps are moving to the web. Spreadsheets, email, games, etc are more and more frequently available in web application form. Fortunately, web applications are fairly easy to scale with multi-core chips because each user can be running on it's own thread which occupies a single core. So, the most important apps (webservers, and database servers) are already designed well for dealing with multi-processors.
In today's world, any VB6 forms developer is automatically a .NET guru. Drag buttons onto a form, don't bother considering memory usage, declare lots of strings on the fly. The programming, over time, seems to outstretch the availability of cheap hardware produced in China's sweatshops and bought on credit, to keep up. Each new release of just about any system, is more bloated, not better.
I can't blame them, they know that their project will be outsourced to the Bangalores of the world, and that they will be laid off anyway, so who cares about quality?
It only seems counter intuitive if you've swallowed the procedural programming paradigm and adopted it as your own to the point where you've forgotten how counter intuitive "X = X + 1" seemed at first.
"X = X + 1" is only misleading because it uses the "=" symbol- normally associated with equality- as the assignment operator.
If we ignore that side issue, there's nothing inherently confusing about the operation itself. Pascal and COMAL use ":=" (becomes equal to) instead, and I wish that C and all its syntactical derivatives had done something like this instead of using "=" for assignment (possibly with "<>" for inequality to avoid mixing up ":=" and "!=").
(Ironically, BASIC's restrictions meant that despite using the "=" symbol for both purposes, there was never any confusion because it could only mean one or the other in a given context).
"Slashdot - News and Chat Sites Deviant". (Click "homepage" link above for details).
when I program unix scripts, I don't do it in perl or php or python. But in good old shell. Preferably ksh (or maybe zsh) but not bash (reply here if you wanna start a discussion on braindead pipe handling of bash).
Just doing a command line with lots of pipes one after the other automatically creates as many processes as you have pipes. It's beautifully simple.
In that respect, unix has had the multi core idea since it's beginnings.
Then came along the monolythic languages like perl where you have to jump through hoops to get that paralellism back which you have right away in good old shell.
How's that new Windows shell comparing? Monolytic or implicit thread/process creation?
Atari rules... ermm... ruled.
Itanic 1 was a fine IA-64 chip, and IA-64 is a fine EPIC ISA.
Itanic 1 was a weak IA-32 chip, and an expensive one. IA-32 is not a fine ISA, but it's pervasive.
The thinking: users would recompile higher-level-language source code to IA-64 assembly (and then on to machine language), and rewrite their performance-critical IA-32 assembly to IA-64 by hand.
The result: lots of IA-32 code continued to run unmodified because the users did not have the ability to recompile the hll source code, since it was not theirs. Lots of such source code was not portable, and the performance-critical assembly was especially difficult to reason about with respect to a port to IA-64. The expense of Itanic hurt it on two fronts: low adoption rates of IA-64 did not encourage proprietary software vendors to port their software that actually *did run* on Itanic 1 (since it handled IA-32 natively), and the computer buyers could get much better IA-32 cost-effectiveness with other chips, even from Intel.
Itanic 1 should have been priced lower, and it should not have pretended to be a competitive IA-32 implementation.
Modern Itanic is (relatively) cheaper, and does IA-32 in software using a system much like Apple's Rosetta.
And so on...did I just feed a troll?
No... you enfatuated him.
Your inefficient OO programming keeps us FPGA developers employed. Move along please.
Somebody give this man a prize!
WAY too late to the party here, but what the hell...
you've forgotten how counter intuitive "X = X + 1" seemed at first
I hate to admit it, but that's actually something I always liked from the B&D languages like Pascal. In those languages, "=" is an equality test (closer to what one would expect from grade school math), and ":=" is an assignment (usually pronounced "gets"). Thus, "X := X + 1" does not conflict with our analytical preconceptions.
Of course, I also remember how many times I accidentally typed ";=" or ":+" instead of ":="--but that's a different issue.