Publications:A Monadic Approach for Avoiding Code Duplication when Staging Memoized Functions
From CERES
| Title | A Monadic Approach for Avoiding Code Duplication when Staging Memoized Functions |
|---|---|
| Author | Kedar Swadi and Walid Taha and Oleg Kiselyov and Emir Pasalic |
| Year | 2006 |
| PublicationType | Conference Paper |
| Journal | |
| HostPublication | PEPM '06 Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation |
| DOI | http://dx.doi.org/10.1145/1111542.1111570 |
| Conference | PEPM'06. International Symposium on Partial Evaluation and Semantics Based Program Manipulation, Charleston, South Carolina, USA, January 9–10 |
| Diva url | http://hh.diva-portal.org/smash/record.jsf?searchId=1&pid=diva2:588269 |
| Abstract | Building program generators that do not duplicate generated code can be challenging. At the same time, code duplication can easily increase both generation time and runtime of generated programs by an exponential factor. We identify an instance of this problem that can arise when memoized functions are staged. Without addressing this problem, it would be impossible to effectively stage dynamic programming algorithms. Intuitively, direct staging undoesthe effect of memoization. To solve this problem once and for all, and for any function that uses memoization, we propose a staged monadic combinator library. Experimental results confirm that the library works as expected. Preliminary results also indicate that the library is useful even when memoization is not used. |
