Fortress, a programming language funded by DARPA and developed by Sun, aimed at solving this very issue by parallelizing core operations. For example, 'for' loops in the language are parallel operations that do not guarantee linear iteration. Unfortunately, development wound down this summer due to incompatibility with VM type systems.

I'm surprised that the author did not mention join lists in his discussion of parallelizable functional program structure. A join list is either empty, a single element, or contains two join lists. In a normal list, you recur on a list that is only one smaller. In a join list, each recursion passes half of the list to a new processor.

The switch to easy parallelization will require data structures that do not guarantee linear iteration but gain scalability "for free." In my experience, this is easy to add to lisp dialects, but difficult to implement and use in imperative languages.