3 ms·
No one addressed the parallelization claim, so here goes: The ability to parallelize purely functional code comes from the Church-Rosser theorem (http://en.wik
by sedachv 16y ago
No one addressed the parallelization claim, so here goes:
The ability to parallelize purely functional code comes from the Church-Rosser theorem (http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem), which states that you can do beta reductions in any order in the lambda calculus and get the same term.
The thing with tail-recursive code is precisely that there is only one way to do a reduction - the function has to call itself at the end. That's what makes tail-recursive code "iterative."
As soon as you introduce multiple reduction paths, you need a stack for the intermediate results - think of for example a recursive divide-and-conquer algorithm.
This Kornelius Fuhrer dude shouldn't be writing articles on parallel programming, he should be reading books about it.
- barrkel 16y agoI can, however, see a compiler turning simple cases of tail recursion into recurrence relations, and re-extracting the loop, but it's a relatively long way to go to get back that iterative bit of the problem, especially as a language in which tail recursion is often used probably won't be working with mutable arrays as often - a loop over input and output arrays being probably the easiest parallelization candidate.
- sedachv 16y agoI never thought about it that way. That's quite clever and out of the box! Guy Steele gave a very good talk about the problem (basically, "tail recursion considered harmful") and solution ("divide and conquer") at ICFP last year: http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf+foldr+considered+harmful&hl=en&gl=ca&pid=bl&srcid=ADGEESiHWEmfK12_eOyYM0465fA2ltUZLfPwQxtlNADEVwhJgdiIFKB1_YRvSv064kacRgLtLX7CWHrBBi72WaPrlXcrQqRXaqJB6-DSA10Sej9jFkXJM7GVPVx-VUfkmho-s5sduHga&sig=AHIEtbTLZ4NCoMphAYt6CkQ7PuspHJqNCw http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:l... APL-style operators (map/reduce, paralations, NESL, etc.) are definitely the way to go. Not only do you get parallelization "for free," but optimizations like map fusion (see http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance http://www.randomhacks.net/articles/2007/02/10/map-fusion-an..., and Rich Waters' earlier work on SERIES: http://series.sourceforge.net/ http://series.sourceforge.net/) become easy - something like that is almost impossible to do with loop analysis. All that, and you end up with clearer, shorter code. Due to all these reasons, I'm convinced that automatic loop parallelization is the biggest waste of time in parallel computing research.