Andreas Bauer

Compilation of Functional Programming Languages using GCC - Tail Calls

Master's Thesis (Diplomarbeit)


Keywords: Tail Calls, Tail Recursion, GCC, Haskell, GHC, Functional Programming Languages


Abstract

In the late 1980s, functional programming language implementations commonly translated a program into a C output file which could then be processed by an independent C back end. Those functional language front ends were either faced with the complexity of a single large C function that contained the functionality of the entire program, or they were constrained by the lack of support for proper tail calls in C. Even today, a lot of functional programming language implementations use C to gain native binary executables for various target platforms. Using this technique, they are still faced with the same problems as their early predecessors were; proper tail calls are still missing as a feature of modern C back ends.
This work gives the technical background and rationale as to why it is so difficult to implement proper tail call support in a system's C compiler and it discusses different approaches to overcome this traditional problem in the widespread and freely available GNU Compiler Collection (GCC), so that functional language front ends like The Glasgow Haskell Compiler (GHC), which use GCC, gain a greater amount of flexibility. It also shows how many C compiler constraints which make tail call support such a difficult feature in terms of implementation, date back to design issues made in early versions of the UNIX operating system.
In order to address, in particular, GHC's need for support of indirect tail calls in the GCC back end, a series of GCC source code changes are described which have become integral parts of the compiler suite. The changes enable the open source compiler to optimise a class of indirect tail calls on Intel-based 32 and 64-bit platforms and are designed to be portable to any other platform which is not bound by its ABI to not support this notion. A GCC test suite to verify such future ports has been developed and is described as well.
Furthermore, this work examines the GCC project in general, whose ever growing core exceeds 500,000 lines of code, and it explains how this huge open source product is being developed and driven forward by a worldwide community of programmers. In doing so, a special emphasis is placed on the process of becoming involved in the community and how to start contributing ideas and code that implements them. Because of the remarkable number of over 200 supported hardware and software platforms, this work also explains the compiler's highly portable internals in detail and it shows how GCC can be used to bootstrap a variety of different cross compilers.


Body

The body of this thesis is available as PDF (1.12 MB) or as Postscript (376 KB, gzipped) file.


BibTeX Entry

@mastersthesis{ baueran:mthesis:2003,
   author = {Andreas Bauer},
    title = {Compilation of Functional Programming Languages
             using {GCC}---{T}ail Calls},
     year = {2003},
   school = {Institut f\"ur Informatik, Technische Universit\"at
             M\"unchen},
      url = {http://home.in.tum.de/~baueran/thesis/}
}

In Cooperation with...

TUM Logo Technische Universität München, Germany

MSR Logo Microsoft Research, Cambridge, UK

ANU Logo Australian National University, Canberra, Australia

This work was supported by an Abroad Scholarship of the
DAAD Logo


Andreas Bauer, <baueran@in.tum.de>
Last modified: Tue Nov 21 13:21:31 2006
Valid HTML 4.0