Thesis: Garbage collection, and memory efficiency, in lazy functional languages

Abstract

Automatic memory management is an important concept in many high order languages. It improves productivity by abstracting away from memory management, but it is not free! The cost can sometimes be much higher than the programmer thought. This is especially true for lazy functional languages where it is not always obvious when things are evaluated. This thesis describes two ways to decrease the overhead. Faster garbage collectors and tools to aid programmers writing more efficient programs.

The first two papers are examples of improved garbage collectors. One is intended for a parallel machine, the other is for sequential machines. Both use generational garbage collectors to decrease the garbage collection time. Neither of them need the usual test-before-update used in other generational collectors. The test could be avoided by taking advantage of the fact that only redexes are updated in functional languages, and then only after they have been evaluated.

The third paper describes an extended version of heap profiling. This is a tool that helps programmers produce more memory efficient programs. In the extended version not only static information can be profiled, but also some dynamic properties can be observed. This aids the programmer in writing even faster and more space efficient programs. The gain in speed can be higher than using an infinitely fast garbage collector, since also the time to allocate the memory goes away. The last two papers are examples of memory efficient implementations. The first of these papers describes a fast and space efficient implementation of parsing combinators, the second gives an overview of a Haskell compiler. This Haskell compiler is not only written in a memory efficient manner, 1Git also tries to produce space efficient code. Some of the methods to decrease memory usage in the compiler can be used in other lazy functional programs, not only compilers.

This thesis is based on work contained in the following papers:
  1. Niklas Röjemo, A concurrent garbage collector for the <v,G>-machine Licentiate Thesis, Chalmers University of Technology and University of Göteborg, 1991 Sweden.

    A revised version was published in International Workshop on Memory Mangement volume 637 of Lecture Notes in Computer Science, pages 440--453. Springer-Verlag, September 1992.

  2. Niklas Röjemo, Generational garbage collection, for lazy functional languages, without temporary space leaks A revised version was published in International Workshop on Memory Mangement, pages ?-? . Springer-Verlag, 1995.

  3. Colin Runciman and Niklas Röjemo, New dimensions in heap profiling

  4. Niklas Röjemo, Efficient parsing combinators

  5. Niklas Röjemo, nhc - a space-efficient Haskell compiler

    This is an extended version of Highlights from nhc - a space-efficient Haskell compiler in Proceedings of the 1995 International Conference on Functional Programming Languages and Computer Architecture, pages ?-? . ACM Press 1995.

    An earlier version of the extended paper was published in Proceedings of the workshop on Implementation of Functional Languages School of Information Systems, Univiversity of East Anglia, pages 30.1-30.29, Norwich September 1994.

Other papers

Papers done after the thesis that might be of intrerest:
  1. Lag, drag, void and use - heap profiling and space-efficient compilation revisited (ICFP'96, paper done in collaboration with Colin Runciman)
  2. Two-pass heap profiling: a matter of life and death (IFL'96, paper done in collaboration with Colin Runciman)