%include paper.fmt

\title{Transformation and Analysis \\ of Functional Programs}
\author{Neil Mitchell}
\date{\normalsize{
    \vspace{20mm}
    Submitted for the degree of Doctor of Philosophy \\
    \vspace{10mm}
    Department of Computer Science \\
    University of York \\
    June 2008}}

\maketitle

\setcounter{page}{2}

\chapter*{Abstract}

This thesis describes techniques for transforming and analysing functional programs. We operate on a core language, to which Haskell programs can be reduced. We present a range of techniques, all of which have been implemented and evaluated.

We make programs \textit{shorter} by defining a library which abstracts over common data traversal patterns, removing \textit{boilerplate} code. This library only supports traversals having value-specific behaviour for one type, allowing a simpler programming model. Our library allows concise expression of traversals with competitive performance.

We make programs \textit{faster} by applying a variant of \textit{supercompilation}. As a result of practical experiments, we have identified modifications to the standard supercompilation techniques -- particularly with respect to let bindings and the generalisation technique.

We make programs \textit{safer} by automatically checking for potential pattern-match errors. We define a transformation that takes a higher-order program and produces an equivalent program with fewer functional values, typically a first-order program. We then define an analysis on a first-order language which checks statically that, despite the possible use of partial (or non-exhaustive) pattern matching, no pattern-match failure can occur.


\tableofcontents
\listoffigures
\listoftables

\chapter*{Acknowledgements}

Throughout the PhD I have been supported by an EPSRC PhD studentship. I would like to thank Colin Runciman for his supervision throughout the last 6 years. Colin taught me Haskell, helped me with technical problems, and helped me to express myself more clearly in my writing. In addition to Colin's supervision, all the members of the PLASMA group have provided interesting discussions, lots of technical debate and answers to \LaTeX\ problems.

Many people in the Haskell community have provided ideas, encouragement, code and answers. Included in this list are Andres L\"{o}h, Bj\"{o}rn Bringert, Brandon Moore, Damien Sereni, Duncan Coutts, Eric Mertens, J\"{u}rgen Doser, Jules Bean, Koen Claessen, Matthew Danish, Peter Jonsson, Simon Marlow, Simon Peyton Jones, Stefan O'Rear, Tim Chevalier and the whole of the Haskell community, particularly \verb"#haskell". The vast number of people who have helped ensures that I have certainly forgotten many people.

While doing a PhD, I have appreciated the presence of many friends -- including all the members of the York University Karate Club, and the many residents of 232 Melrosegate. Thanks to Emily for making the last month of my PhD a fantastic year. Lastly, thanks to my family, who have given me the freedom to make my own decisions, and an occasional email to check on my wellbeing.

\chapter*{Declaration}

Chapter \ref{chp:background} has some overlap with material published in \cite{me:yhc_core}. Chapter \ref{chp:uniplate} is based on the paper \cite{me:uniplate}, which appeared at the Haskell Workshop 2007. Chapter \ref{chp:supero} is based on the paper \cite{me:supero_ifl} which was presented at IFL 2007, and the revised paper \cite{me:supero} from the post proceedings. Chapter \ref{chp:catch} builds on work from the papers \cite{me:catch_tfp_original,me:catch_tfp} presented at TFP 2005 and appearing in the post proceedings, and is based on the paper \cite{me:catch} from the Haskell Symposium 2008.

Apart from the above cases and where stated, all of the work contained within this thesis represents the original contribution of the author.