ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
1–10 of 31 posts
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#2On p73: Use tree branching factors larger than 2. (Example: Rich Hickey’s
Clojure is a JVM-based Lisp that represents lists as 64-ary trees.)
This is awesome and I had no idea!
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#3On p73: Use tree branching factors larger than 2. (Example: Rich Hickey’s Clojure is a JVM-based Lisp that represents lists as 64-ary trees.) This is awesome and I had no idea!
Take a look at http://blog.higher-order.net/2009/02/01/understanding-clojur... for details of Clojure's persistent vector implementation.
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#4I think the way parallelisism changes the established trade-offs in code "optimization" is summarised by his lines:
Don’t split a problem into “the first” and “the rest.” Instead, split a problem into roughly equal pieces; recursively solve subproblems, then combine subsolutions.
A tree can be processed breadth-first (parallel) or depth-first (sequential), or both.
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#5The language (and the features) presented in this presentation are from Fortress, which Guy and other Sun researchers have worked on for some time. On the project page one can download Fortress 1.0 and also check out Fortress 1.0 specification:
http://projectfortress.sun.com/Projects/Community/
It's a pretty ambitious project and it looks like they are going to succeed. The focus of the language is to create a new Fortran, but personally, I think the scope and the ambition of Fortress are bigger. Viva la Guy Steele :)
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#6The language (and the features) presented in this presentation are from Fortress, which Guy and other Sun researchers have worked on for some time. On the project page one can download Fortress 1.0 and also check out Fortress 1.0 specification: http://projectfortress.sun.com/Projects/Community/ It's a pretty ambitious project and it looks like they are going to succeed. The focus of the language is to create a new Fo…
From Fortress and a few other languages. Like Scheme. In the talk at ICFP he said, he did this, because he likes them all.
The video should come online soon. I hope ACM won't put it behind a pay wall.
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#7Clojure tries to address this problem. First and rest are still fundamental concepts in its data structures, but underneath the hood is properly written concurrent Java code. Hickey wrote it once, and now you don't have to.
I highly recommend the Clojure videos, available at: http://clojure.blip.tv/. Watch them online or download them via iTunes. There are a two videos on Clojure data structures, and a set of introductions for both Lisp and Java programmers
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#8I think the way parallelisism changes the established trade-offs in code "optimization" is summarised by his lines: Don’t split a problem into “the first” and “the rest.” Instead, split a problem into roughly equal pieces; recursively solve subproblems, then combine subsolutions. A tree can be processed breadth-first (parallel) or depth-first (sequential), or both.
That would be OK if Lisp wasn't list-based. In Lisp you always start at the beginning of the list: any processing requires going through that list somehow.
Prolog allows some workaround to this problem by using difference lists.
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#9I think the way parallelisism changes the established trade-offs in code "optimization" is summarised by his lines: Don’t split a problem into “the first” and “the rest.” Instead, split a problem into roughly equal pieces; recursively solve subproblems, then combine subsolutions. A tree can be processed breadth-first (parallel) or depth-first (sequential), or both.
That would be OK if Lisp wasn't list-based. In Lisp you always start at the beginning of the list: any processing requires going through that list somehow. Prolog allows some workaround to this problem by using difference lists.
Did you not read the talk? You can provide the car/cdr interface on top of tree-based implementations. Yes, you pay a cost to use that interface...but you pay a different (Guy Steele would argue more expensive) cost if you write your algorithms using car/cdr instead of, say, empty/singleton/conc.
Moreover, as is pointed out on the slides, a lot of processing can happen without ever having to talk about car/cdr, e.g., using higher-order functions like map and filter.
Re: ICFP '09: "Get rid of cons!" Guy Steele on parallel algorithms & data structures
#10On p73: Use tree branching factors larger than 2. (Example: Rich Hickey’s Clojure is a JVM-based Lisp that represents lists as 64-ary trees.) This is awesome and I had no idea!
Take a look at http://blog.higher-order.net/2009/02/01/understanding-clojur... for details of Clojure's persistent vector implementation.
And here is the code for it: http://github.com/richhickey/clojure/blob/270185aba54cef1d8c...