An Optimal Staging Algorithm.
Takuma Murakami, Zhenjiang Hu, Masato Takeichi · 2002
Staging is an alternative approach for binding-time analysis and program specialization, making some pieces of code dynamic. Tim Sheard and Nathan Linger showed a search-based algorithm for automated staging. The problems remained are unclear computation complexity and no e#cient way to take optimal solutions. In this paper, we propose a linear algorithm to derive optimally staged programs with concrete implementation. The key point of our approach is to make use of the optimization theorem for solving multi-marking problem by regarding staging as marking.