Lambda the Ultimate

Jason L. Eckhardt, Roumen Kaiabachev, Kedar N. Swadi, Walid Taha and Oleg Kiselyov (draft)

Abstract. High-level languages offer abstraction mechanisms that can reduce development time and improve software quality. But abstraction mechanisms often have an accumulative runtime overhead that can discourage their use.

Multi-stage programming (MSP) languages offer constructs that make it possible to use abstraction mechanisms without paying a runtime overhead. This paper studies applying MSP to implementing dynamic programming (DP) problems. The study reveals that staging high-level implementations of DP algorithms naturally leads to a code explosion problem.

In addition, it is common that high-level languages are not designed to deliver the kind of performance that is desirable in implementations of such algorithms. The paper proposes a solution to each of these two problems. Staged memoization is used for code explosion, and a kind of “offshoring” translation is used to address the second. For basic DP problems, the performance of the resulting specialized C implementations is almost always better than the hand-written generic C implementations.

Since I know at least one of the authors reads LTU fairly regularly, perhaps they'll comment?
Posted to implementation by Bryn Keller on 3/4/04; 10:02:51 AM