Here is a well-written introductory paper on lambda lifting in Scheme that I just found: http://sciris.shu.edu/masplas2004/MASPLAS%20Papers/Paper%208.pdf. If you are interested in learning about compilers, I think it is a worthwhile paper to read. Lambda lifting is a technique for compiling closures.
In other news, I recently wrote an article at DobbsCodeTalk.com called The Concurrent Future is not Multi-Threaded. I found the discussion interesting.
So an interesting problem in compilation is taking advantage of commutativity (or associativity) of functions for reordering instructions. In some cases this can allow a compiler to completely execute something in parallel. So how do you you tell the compiler an operator or function is associative? One obvious option would be to let programmers tag their functions. This is bound to introduce subtle and nasty errors in to the code if the programmer makes a mistake. Not to mention it is inelegant and it isn’t the kind of thing I want to see in people’s code (optimization hints that is).
So the big question is, how do we automatically recognize properties of functions like commutativity? In Cat there is already have a system for expressing rewriting rules (e.g. rule { $a $b f } => { $b $a f } ). This fairly obviously shows us the commutativity of ‘f’. In fact if we can follow any sequence of rewriting rules to arrive at this equality even if it isn’t explicit (which is a simple graph search problem), then we can deduce commutativity.
This indicates to me the usefulness of rewriting systems (like the Haskell rewriting system) that are exposed to the programmer and that guide optimization.
If anyone is familiar with related research please let me know, thanks!
[Follow-up: some interesting discussion on the subject is unfolding at http://lambda-the-ultimate.org/node/2752]
I currently have several projects on the go. Here is a quick overview of what I am up to: