Unboxed Function Closures

Abstract

In Haskell, both thunks and values are generally represented as a heap-allocated closure [18]. This introduces overhead, as the heap generally is much slower than the stack. To combat this inefficiency, programmers can use unboxed types [19]. These types are represented directly on the stack, and therefore do not carry such overhead.

So far, only data values such as Int and Char can be unboxed. In this thesis we explore the possibility of extending this notion, allowing for function values to be unboxed as well.

As functions can close over variables, they must be represented as a closure. Therefore, unboxing function values requires representing closures on the stack. This introduces a significant challenge, as variations in the set of closed over variables now affect the stack representation.

We propose an extension to function types, where the types of the closed over variables are annotated on the function arrow. These annotations make it possible to reason about the exact runtime representation of a closure at compile time. We do so by presenting two languages, L and M, and a compilation function L → M. Furthermore, we identify the key correctness criteria of L → M, and proof that they hold.