Lambda the Ultimate

inactiveTopic Instruction scheduling and imperative functional programming
started 10/23/2001; 1:55:32 PM - last post 10/24/2001; 1:28:57 PM
Ehud Lamm - Instruction scheduling and imperative functional programming  blueArrow
10/23/2001; 1:55:32 PM (reads: 1824, responses: 2)
Instruction scheduling and imperative functional programming
The article makes the case that a transformation of a typical imperative code into functional code is similar to the data and control dependency analyses in compilers for modern CPUs. By typical imperative code we mean a "typical numerical" code that involves nested loops and updateable arrays....

...The analysis of data and control dependencies across loop iterations, scheduling of instructions and interlocking of their results, pre-fetching of data -- is the job of an advanced compiler or the CPU. On the other hand, we have to do the same kind of analyses to separate the functional part of a computation from its imperative part. It appears functional programming is closer to "the bare metal" as one would have thought.


Posted to implementation by Ehud Lamm on 10/23/01; 1:55:51 PM

Noel Welsh - Re: Instruction scheduling and imperative functional programming  blueArrow
10/24/2001; 2:12:56 AM (reads: 733, responses: 0)
SSA (Static Single Assignment) is an intermediate language form used by compilers to make data and control dependency analysis easier. Andrew Appel makes the point (http://www.cs.princeton.edu/~appel/papers/ssafun.ps) that SSA form is really equivalent to the lambda calculus form used in many functional compilers. I like the quote "the SSA conversion algorithm is really...converting a C or Fortran procedure into a well-structured functional program with nested scope".

Oleg - Re: Instruction scheduling and imperative functional programming  blueArrow
10/24/2001; 1:28:57 PM (reads: 700, responses: 0)
It is worth continuing Andrew Appel's quote:
The SSA algorithm ... is automatically converting a FORTRAN or C procedure into a well-structured functional program with nested scope. Actually, I've only shown what to do with scalar variables. Arrays are handled in high-powered (parallelizing) compilers using sophisticated dependence analysis techniques [15], which is another way of extracting the functional program inside the imperative one.

The last part of the quote is precisely what the article "Instruction scheduling and imperative functional programming" aimed to demonstrate! The article dealt with arrays updated in-place. The article gave several examples that dependency analyses done by optimizing compilers (as well as by instruction-issue circuits of CPUs) in effect extract a pure-functional part of an imperative program. The rest requires serialization and can be handled by an ST monad.