Flow Inference, Code Generation, and Garbage Collection for Lazy Functional Languages

Lazy functional languages such as LML [4], Haskell [21], and Concurrent Clean [35] typically feature first class functions, polymorphic type systems, and automatic garbage collection. These powerful mechanisms translate into short, readable, and reusable programs at a high level of abstraction. They do however lead to quite a lot of run-time bookkeeping and make the dynamic flow of control rather unpredictable. This overhead increases execution time by as much as a factor of twenty in some cases. This thesis describes some techniques that can be used to reduce this overhead. Specifically, we eliminate thunk and eval operations, use unboxed data representations and try to avoid updating thunks. These optimizations depend on information gained by a program-wide dataflow analysis which is based on a polymorphic subtype inference system. The techniques have been implemented in a compiler for a simple lazy functional language called Plain, and this implementation is described in some detail..