4 ms·

When I watched Guy Steele's earlier talk on the same subject (below), the scales fell from my PL eyes. When he showed that user-definable, verifiably associati

by guns 16y ago

When I watched Guy Steele's earlier talk on the same subject (below), the scales fell from my PL eyes. 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 http://vimeo.com/6624203 [1]: Clojure does seem to be anticipating this future, however

pjscott 16y ago
The operators don't have to be verifiably associative -- I'm pretty sure that's impossible to verify, in general, thanks to the halting problem -- but it would be nice to be able to declare operators associative. 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.
- scottjad 16y ago
  http://incanter.org/downloads/fjclj.pdf http://incanter.org/downloads/fjclj.pdf 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
- riffraff 16y ago
  aren't verification and definition of associative operators two different problems? I mean, while you can't generally prove that an operator is associative, you can have probably tell that they are associative by construction.
  - btilly 16y ago
    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.
jerf 16y ago
"When he showed that user-definable, verifiably associative combination operators can provide magnificent opportunities for automatic parallelization..." 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.

by guns 16y ago

pjscott 16y ago

The operators don't have to be verifiably associative -- I'm pretty sure that's impossible to verify, in general, thanks to the halting problem -- but it would be nice to be able to declare operators associative. 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.

scottjad 16y ago
http://incanter.org/downloads/fjclj.pdf http://incanter.org/downloads/fjclj.pdf 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
riffraff 16y ago
aren't verification and definition of associative operators two different problems? I mean, while you can't generally prove that an operator is associative, you can have probably tell that they are associative by construction.
- btilly 16y ago
  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.

jerf 16y ago

"When he showed that user-definable, verifiably associative combination operators can provide magnificent opportunities for automatic parallelization..." 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.