David Peixotto, Low-Level Behavior of Lazy Functional Programs

Lazy functional programming languages are well known for their expressiveness, clean semantics, and slow execution time. While many years of research have been invested to bring the efficiency of these high-level languages closer to that of traditional complied languages such as Fortran and C, much of this past work relies on high-level transformations made possible by the functional semantics of the input language. In our research we investigate how traditional compilation techniques can be leveraged to improve the performance of high-level lazy functional programming languages.

Traditional compiler optimizations were developed for imperative languages and it is not clear whether they can be applied in the back-end of a compiler for a lazy functional language. In order to shed some light on whether we can hope to apply these optimizations, we examine several low-level characteristics of lazy functional programs. In this talk we present our investigation of programs written in Haskell, a state-of-the-art lazy functional programming language. We attempt to quantify the similarity of Haskell programs to C programs based on the execution metrics of dynamically instrumented binaries.

We draw three conclusions from our experiments. First, traditional Haskell programs exhibit low-level behavior that is readily distinguished from C programs. Second, modern Haskell programs written explicitly for efficient parallel execution show behavior much similar to traditional C programs. Third, our results indicate that traditional compiler optimizations may find more opportunities when performed as link-time and run-time optimizations. The results of these experiments suggest that traditional optimizations can have a place in a Haskell compiler, particularly as parallel programs become more common with the rise of multi-core computing.