3 ms·
I 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 g
by barrkel 16y ago
I 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.