Guy Steele: "How to Think about Parallel Programming: Not"
infoq.com
infoq.com
When he showed that user-definable, verifiably associative combination operators can provide magnificent opportunities for automatic parallelization, I was ripped out of my head and found myself unable to squabble about the different features of my favorite languages. Even Lisp (the prototype [1]) falls significantly short, since linked lists are most naturally processed by a single thread of execution.
It's clear to me now that when the massively multicore era hits, there will be a significant opportunity for a totally new breed of PLs and for programmers to (re)implement a new wave of software. I hope to be ready when that time arrives.
"Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful" http://vimeo.com/6624203
[1]: Clojure does seem to be anticipating this future, however
Clojure looks like it could easily be made to support the kind of thing Steele is talking about: its immutable vectors are implemented as trees of array chunks, to which you could apply an associative operation in parallel.
Slides of "From Concurrency to Parallelism: an illustrated guide to multi-core parallelism in Clojure" by David Liebke at the first Clojure Conj. Video will eventually be up at clojure.blip.tv
I mean, while you can't generally prove that an operator is associative, you can have probably tell that they are associative by construction.
From the construction of matrix multiplication, it is far from obvious that it is associative. And this is a simple example.
To the extent that I have a programming style, I find myself increasingly thinking of it as Primitive-Oriented Programming. If you want your final program to have some desirable property, be it correctness, scaling, parallelizability, or even more complicated things like one I work on where the interface must have the property "able to be remoted across this certain protocol for various reasons", the best way to achieve that in general is to create primitives with this property, create ways to combine them that maintain the property, and build up from there.
It's very hard right now, because 1. modern machines and programming languages make it hard to create these properties in the first place, so many corner cases to cover because nobody pays any attention to this idea except by accident 2. modern languages tend to make it borderline impossible to verify that properties are being maintained (think things like type-level verification) and it's so easy to violate them that you need this help 3. if you're programming in a team environment the concept that there are certain properties that should be maintained and if you violate them things won't work is extremely foreign to pretty much everybody so in summation 4. you pretty much have no support for this from any angle, the way you can get languages that support and/or mandate OO or FP.
And as a special subcase of this, yes, if you want parallelizable programs the best way to get there is with primitives that embrace it at the bottom. This is why, for all Erlang's faults, it's so much more fun to write parallel programs in Erlang, for instance. The primitives support the concept and there are a number of ways in which you can't get yourself in trouble because there's simply no way to accidentally mutate a variable in a foreign process with the provided primitives. You can't even express it. This is also why Haskell is so exciting to me, because it both starts providing this verifiability to some extent and also shows me where my command of this is weaker than I'd like. (Designing usable primitives is hard because if you accidentally, say, make it impossible to "go up" then when you need to you're in real trouble. There's a reason why most languages make it so easy to break out of the constraints, because generally you have to if you want to get real work done.)
Anyhow, while to be honest the rest of Fortress has been unexciting to me, mostly because it's targeting programmers writing code the types of code I don't, this is one of the more exciting ideas that could come out of that effort and the need for multicore-capable languages in general, and I hope this sort of approach spreads.
I agree both about the power of this approach and the fact that virtually no one does it. Even once one grasps the rough idea it can be hard to see one's way forward building a system this way, not because it's intrinsically more difficult but because it's so out of step with most software culture and we're all profoundly influenced by our milieu.
It reminds me of a favorite Alan Kay quote: Take the hardest and most profound thing you need to do, make it great, and then build every easier thing out of it. We need more examples of systems like this.
Do you have any experience with the APLs? They also strive for this sort of functionality - they're based around a set of primitives which have implicit looping and high potential for parallelism. I have been experimenting a lot with k (kona) lately; it and J (http://jsoftware.com) are both definitely worth a look.
He's wrong when he said that machines of that vintage didn't know about stacks: the whole Burrough B5000 series of machines were entirely stack-based (and programmed in an extended Algol--decades ahead of their time).
The motivation at the beginning with the punchcards and the following PDP-10 "poem" for computing the sin() function left me skeptical about what was to follow, but it turned out to set an excellent stage for the remainder of the talk. By the time he got to the "big deal" ideas at the end, I was well prepared to accept his thesis.
Don't miss this talk. Take the time to watch it.
One nice bit: he admits that if he knew 7 years ago what he knows today, Fortress might have started with Haskell and been pushed 1/10th of the way towards fortran, rather than starting with an object-based foundation and writing side-effect-free functional domain-specific-languages on top of it.
And who makes the languages? Programmers!
I get what he's trying to say... He's trying to say that someone should stop and make it easy for the rest of us to do parallel programming.
And I think someone will eventually do just that. But as usual, I don't think someone writing a blog post about it is going to push someone into it. Either they have the drive to do it, or they don't. "Somebody else should do something about this!" never works.
The compiler could do it automatically but it's only a single line preprocessor directive.
A parallelizing compiler must do the latter before doing the former.