Here's the final version of the paper describing my Master's research at Brown: Lowering: A Static Optimization Technique for Transparent Functional Reactivity. It will be presented at PEPM'07 in January.
The work was very successful: I managed to get a speedup of 7810% for a program that had about 6000 lines of code. The abysmal performance of that program was what motivated the project in the first place.
I'll explain what the title of the paper means.
First, "Functional Reactivity" means a programming language that automatically updates its outputs whenever the value of a variable changes -- kind of like a spreadsheet. Check out Fran for a simple introduction to the idea.
Second, the "Static Optimization" part means that I'm manipulating program source code, without running it. In particular, I'm manipulating FrTime code. The hope is that the result of the manipulation will be a program that behaves identically to the original program, but runs faster and uses less memory.
Third, the "Transparent" part means that the functional reactivity is implicit. All the language constructs have been replaced so that they just Do The Right Thing whenever you start working with time-varying values. This is different from the haskell-based versions of functional reactivity, which use the type system to distinguish between time-varying values and constants.
Finally, "Lowering" is the word I made up for this particular kind of optimization. The name comes from the fact that it's the opposite of lifting. "Lifting" means adding support for functional reactivity to an arbitrary function. "Lift" is also the name of the Haskell function that gives monadic features to an arbitrary function. Indeed, the lowering optimization should apply to any monad where lift distributes across function composition.
That's fine, you say, but what does lowering actually mean? The idea is that instead of doing a whole lot of simple operations on time-varying values, you can temporarily stop the values from changing, do a whole lot of operations on constant values, and then let the values start changing again. Operating on constant values is faster than operating on time-varying values, so this can yield big performance improvements. Read the paper if you want to know the details.
Posted on December 19, 2006 12:53 PM
More school articles