Undoing unwanted sharing in Haskell: An STG transformation

Abstract

This thesis addresses a long-standing issue in lazy functional programming: excessive memory retention due to compiler optimizations such as let-floating and the use of updatable thunks in GHC. We propose a targeted transformation at the STG level that marks certain closures as non-updatable, thereby enforcing recomputation rather than sharing.

Our evaluation shows that this intervention can restore constant-space execution in several representative scenarios, including stream processing and search problems. However, the transformation is not universally applicable: it may increase execution time due to recomputation, and in programs where sharing is essential it can significantly harm performance.

While not a general solution, our approach contributes a principled intervention mechanism that clarifies the trade-off between time and space in lazy evaluation, and opens a path towards more selective, automated strategies for controlling sharing in Haskell.

Esta tesis aborda un problema recurrente en la programación funcional perezosa: la retención excesiva de memoria debido a optimizaciones del compilador, como let-floating y el uso de thunks actualizables en GHC. Proponemos una transformación específica a nivel STG que marca ciertas clausuras como no actualizables, lo que impide que dichas clausuras se compartan. Nuestra evaluación muestra que esta intervención puede restaurar la ejecución en espacio constante en varios escenarios representativos, incluidos el procesamiento de flujos y los problemas de búsqueda. Sin embargo, la transformación no es de aplicación universal: puede aumentar el tiempo de ejecución debido a tener que recomputar ciertos valores, y en programas en los que el sharing de memoria es esencial, puede perjudicar significativamente el rendimiento. Aunque no es una solución completa, nuestro enfoque contribuye un mecanismo que aclara la relación entre tiempo y espacio en la evaluación perezosa, y abre un camino hacia estrategias más selectivas y automatizadas para controlar el sharing en Haskell.