Technische Universität München, Germany
Keywords: Tail Calls, Tail Recursion, GCC, Haskell, GHC, Functional Programming Languages
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.
The body of this thesis is available as PDF (1.12 MB) or as Postscript (376 KB, gzipped) file.
@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/}
}
Technische Universität München, Germany
Microsoft Research, Cambridge, UK
Australian National University, Canberra, Australia
This work was supported by an Abroad Scholarship of the
| Andreas Bauer, <baueran@in.tum.de> Last modified: Tue Nov 21 13:21:31 2006 |
|