Guy Steele: Fold Considered (Slightly) Harmful

Another thought on this video:

Both cons lisp and conc lisp share the same physical structure: a pair of words. The difference between them is the convention of how this is used.

cons lisp assumes pairs are typically head, rest, and so the natural form of most functions is linear recursion: an expression involving some function of head and a single recursive call on rest with a base case handling the empty list.

conc lisp instead assumes pairs are typically left, right and so the natural form of most functions is binary recursion: an expression that is a function of recursive calls on both left and right with a similar base case.

Which prompts some thoughts: are there optimizations similar to constant space tail calls for binary recursion? What about n-way recursion? What would a lisp built of n-tuples (perhaps cache line sized) look like?

I was recently reminded of this video in the comments on Guy Steele's recent presentation (http://news.ycombinator.com/item?id=2105661). I think it's one of the most clear and interesting perspectives on what programing needs to look like in our parallel future.