Heap Recycling Analysis in Helium

Abstract

Pure functional programming languages, such has Haskell, preclude destructive updates of heap-allocated data. To update a newly computed algebraic value, fresh heap space is allocated to store the result. This causes idiomatic programs to be notoriously inefficient when compared to their imperative and impure counterparts. J. Hage and S. Holdermans describe in `Heap Recycling for Lazy Languages` a way to partly overcome this shortcoming. We implement the described analysis in the Haskell compiler Helium and analyze the memory usage of various programs.