Soft Machine³ - Arts Tech and Other

Alternate title:  Mary had a little λ (kidding!)

Guy Steele: Organizing Functional Code for Parallel Execution

CONS (or “Lisp”) lists are inherently linear and sequential. One of CAR, CDR is constant-time, and the other is linear (on the length of the list). For a given list, there is only one CONS representation.

CONC primitives are null <>, singleton <42>, and “concatenation” a || b

CONC trees can represent CONS style lists, or balanced binary trees, or sparse trees, or other structures.

• CAR CDR and CONS are compared to CONC primitives… and rather than use accessors left, right Guy prefers a SPLIT functional accessor which calls the second argument (a function) with the left and right parts as parameters.
  
• Guy says this somewhere later on, and it’s easy to miss:
  
      “We are going to use CONC trees to optimize delay”
  

• An important goal is a corollary to the equivalence 

  (cons (car xs (cdr xs)) = xs

• It’s not this:

  (conc (left xs) (right xs)) = xs

• but this functional gem:

  (split xs (λ (ys zs) (conc ys zs))) = xs

• Think of the lambda λ as a continuation, and a way to keep the left and right together. In practice, split does not have to behave uniformly, but for the sake of this talk,  consider split to be purely functional with no side effects. You will notice we now have a corollary to the most low-level CONS equivalence, but one which is expressed functionally, recursively, by “binary decomposition and reassembly”
  

Having taken care of the basics, Guy breaks down the implementations of  MAP, REDUCE, MAPREDUCE, LENGTH, FILTER, QUICKSORT and MERGESORT for both CONS lists and the new CONC trees.

…. Almost done! ….

RANT ON

If you are on Windows searching the Unicode characters looking for “LAMBDA”, you should STOP IMMEDIATELY. Search for “LAMDA” (no B). Microsoft doesn’t know how to spell “LAMBDA” much less describe its purpose in binding new variables dynamically, so the lambda (and its children) have a protected scope that hides variables in outer scopes, until the lambda completes and its scope goes away. Anyway HTML for the λ is ” &lambda; ” — that’s ampersand lambda semicolon  (no spaces)