via MetaOcaml list
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