Guy Steele Says: Don't Iterate, Recurse, and Get rid of lisp cons!

By Xah Lee. Date: . Last updated: .

Tips on Writing Parallel Programs: Don't Iterate, Recurse, Fold, Pipe, Foreach, Get Rid of Linked List

The followings are items from Guy Steele's slide.

Things to Avoid

Conclusion

Elegant Functional Style, Recursion, Fold, Piping, is Bad for Parallelism

I've been doing functional programing for since 1993, pretty much ever since i started programing with my first language Mathematica. Two paradigms i use frequently, is sequencing functions (aka chaining functions, piping) and recursion (e.g. fold, nest). In some sense, most of my programs is one single sequence of function chain. The input is feed to a function, then its output to another, then another, until the last function spits out the desired output. It is extremely elegant, no state whatsoever, and often i even take the extra mile to avoid using any local temp variables or constants in my functions. But after watching this video, i learned, that function chaining is NOT good for parallelism, despite it is considered a very elegant functional paradigm.

As a functional programer, typically we are familiar with all the FP style constructs, and we strive for such elegance. The important thing i learned from this video is that, elegance in functional style does not mean it will be good for parallelism. Similarly, software written with purely functional language such as Haskell, does not imply it'll be good for parallelism. (but will be a lot better than procedural langs, of course.) FP and Automatic Parallelism certainly share some aspects, such as declarative code and not maintaining states, but is not the same issue.

Guy Steele's Talk: How to Think About Parallel Programming: Not!

A fascinating talk by the computer scientist Guy Steele. (well known as one of the author of Scheme Lisp, and emacs (before Richard Stallman))

[How to Think about Parallel Programming: Not! By Guy Steele. At http://www.infoq.com/presentations/Thinking-Parallel-Programming , accessed on 2011-02-05 ]

Guy Steele parallel programing lisp cons
Guy Steele on LISP cons

The talk is a bit long, at 70 minutes. The first 26 minutes he goes thru 2 computer programs written for 1970s machines. It's quite interesting to see how software on punch card works. For most of us, we've never seen a punch card. He goes thru it “line by line”, actually “hole by hole”. Watching it, it gives you a sense of how computers are like in the 1970s.

At 00:27, he starts talking about “automating resource management”, and quickly to the main point of his talk, about what sort of programing paradigms are good for parallel programing. Here, parallel programing means solving a problem by utilizing multiple CPUs. This is important today, because CPU don't get much faster anymore; instead, each computer is getting more CPU (multi-core).

In the rest 40 min of the talk, he steps thru 2 programs that solve a simple problem of splitting a sentence into words. First program is typical procedural style, using do-loop (accumulator). The second program is written in his language Fortress, using functional style. He then summarizes a few key problems with traditional programing patterns, and itemize a few functional programing patterns that he thinks is critical for programing languages to automate parallel computing.

In summary, as a premise, he believes that programers should not worry about parallelism at all, but the programing language should automatically do it. Then, he illustrates that there are few programing patterns that we must stop using, because if you write your code in such paradigm, then it would be very hard to parallelize the code, either manually or by machine AI.

If you are a functional programer and read FP news in the last couple of years, his talk doesn't seem much new. However, i find it very interesting, because:

In much of 2000s, i did not understand why compilers couldn't just automatically do parallelism. My thought have always been that a piece of code is just a concrete specification of algorithm and machine hardware is irrelevant. But i realized, that any concrete specification of algorithm is specific to a particular hardware, by nature. [see Why Must Software be Rewritten for Multi-Core Processors?]

Parallel Computing vs Concurrency Problems

Note that parallel programing and concurrency problem are related but not the same thing.

Fortress and Unicode

Parallel Programing Exercise

Here is a interesting Parallel Programing Exercise: Parallel Programing Problem: asciify-string .

Organizing Functional Code for Parallel Execution (or, foldl and foldr Considered Slightly Harmful)

Here is a paper written by Guy Steele, on the same topic, in 2009, but with lots lisp and Fortress code.

At the end of the document, he says, in big red letters: “Get rid of cons!”.

ICFPAugust2009Steele.pdf