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.'"
With functional programming languages make a rather restrictive assumption, and that is all variables are immutable.
This is why functional programs are more suited for concurrency, and this is why your sequential algorithms will fail to work.
You speak London? I speak London very best.
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
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.
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.
And Gustafson's Law tells us that as the problem size increases the non-parallelizable portion of the program will shrink.
Functional variables are like mathematic variables - they're variable in that you may not have discovered their value yet, but once you discover their value it stays the same for the current instance of the problem. For the next instance of the problem (i.e. the next call to the function), you're talking about a different set of variables that potentially have different values.
-- The act of censorship is always worse than whatever is being censored. Always.
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.
I would say Haskell, but I think that's the language everyone should learn, so I'm biased. The typeclass system provides for some of the functionality of object oriented programming.
If Haskell scares you, Ocaml is another good choice. It's a multi-paradigm language with an emphasis on functional programming, but it also allows you to use mutable state wherever you like (whether this is a good thing or not is a matter of some debate). It even has some traditional object-oriented programming features, but they tend not to get used much in practice.
If you care about performance, they both have decent native-code compilers. My impression is that Ocaml is a bit faster for single-core tasks, but Haskell's parallel programming features are much better.
My response back then was to get excited about FP. My response now is: Where is the proof?
Whether functional programming is the best paradigm to use for parallel computing is undecided. But it does have a couple of advantages over imperative programming.
First, imperative programming specifies the order of evaluation, whilst functional programming does not. In Haskell, for instance, an expression can essentially be evaluated in any order. In Java, evaluation is strictly sequential; you have to evaluate line 1 before line 2.
Second, imperative languages like Java favour mutable data, whilst functional languages like Haskell favour immutable data structures. Mutability is the bane of parallel programming, because you have to have all sorts of locks and constraints to keep your data consistent between threads. Programming languages that do not allow mutable data don't have this problem.
Moore's law states that the number of transistors on a chip will double every two years. By definition it's a hardware problem.
Obviously, utilizing those transistors is a software problem, but Moore's law doesn't say anything about that.
The article sucks. The author seems to know FP about as well as he knows Moore's law.
Maybe not
I agree. I don't understand them very well, but fortunately one can make use of them without a complete understanding. For many programs, it suffices to understand that if you want to do IO, you need to do it within the IO monad (often in the IO action "main" which is equivalent to "int main() {...}" in C).
This doesn't mean you have to write whole file parsers in monadic fashion, which is what I thought until I actually had occasion to write a file parser in Haskell, and found that I could write the parser as a pure function that accepts a string and returns the parsed data structure. Then, in main, I just read the file in with hGetContents (which takes a filename and returns a string) and then pass that string to my pure file parser.
This would seem horribly inefficient for large files; what if there isn't enough memory to store the whole file as a string? But here, laziness comes to the rescue. The actual file IO doesn't happen until the file parser starts reading in the string. My pure function churns along, oblivious to the fact that it's causing deferred IO in the background, simply from forcing the evaluation of the string's value.
This is, perhaps, not a very great insight into the nature of monads, but I thought I would share my experience, and if not enlighten then at least show that one can write normal programs in a fairly straightforward manner without being fully enlightened.
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
Huh? Quicksort is pretty easy to parallelize, due to its divide and conquer nature: it splits its list into sublists and recurses on those sublists.
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
Notably, it's impossible to do a quicksort in a functional language
Some Haskell guy seems to disagree.
For a more lower-level example, almost any kind of query over some data set is an inherently parallelizable operation. This includes virtually all usages of list comprehensions, map and filter in Python, for example.