HaskellImplementorsWorkshop/2011/Takano

Reusing Thunks for Recursive Data Structures in Lazy Functional Programs

Yasunao TAKANO*, Hideya IWASAKI, Tomoharu UGAWA

Lazy evaluation helps programmers write clear programs. However, it has significant run-time overheads for building many as-yet unevaluated expressions, or thunks. Because thunk allocation is a time- and space-consuming task, it is important to reduce the number of thunks in order to improve the performance of a lazy functional program. We propose static analysis algorithms that achieve the thunk reuse technique. Thunk generation is suppressed by reusing and updating an already allocated thunk at the tail of a list, on the condition that the thunk is singly referred, i.e., pointed to only from the tail field of a cons cell. This method guarantees that reused thunks definitely satisfy this singly referred condition on the basis of a static analysis with program transformations. We are implementing our method in the Glasgow Haskell Compiler by modifying the code generation and the runtime system. In this workshop, we will talk about the current status of our implementation and the results of some benchmarks.