%include paper.fmt

\hsdef{uniplate,descend}

\chapter{Conclusions}
\label{chp:conclusions}

In this thesis we have presented a boilerplate reduction library (Uniplate), an optimiser (Supero), a defunctionalisation method (Firstify) and an analysis tool (Catch), all for the Haskell language. In this chapter we first describe some of the high-level contributions we have made in \S\ref{secE:contributions}, give areas for future work in \S\ref{secE:future_work}, then summarise our approach in \S\ref{secE:the_end}.


\section{Contributions}
\label{secE:contributions}

Specific technical contributions have been given in each chapter. In this section we instead focus on the higher-level contributions -- the overall results that are of benefit to functional programmers.

\subsection{Shorter Programs}

Some of our work enables programmers to write shorter programs. In particular the Uniplate library defines a small set of operations to perform queries and transformations. We have illustrated by example that the boilerplate required in our system is less than in other systems (\S\ref{secU:results_boilerplate}).

\subsection{Faster Programs}

Some of our work helps programs execute faster. Using Supero in conjunction with GHC we obtain an average runtime improvement of 16\% for the imaginary section of the nofib suite. To quote Simon Peyton Jones, ``an average runtime improvement of 10\%, against the baseline of an already well-optimised compiler, is an excellent result'' \cite{spj:specconstr}. The Programming Language Shootout\footnote{\url{http://shootout.alioth.debian.org/}} has shown that low-level Haskell can compete with low-level imperative languages such as C. We hope that our optimiser will allow programs to be written in a high-level declarative style, yet still perform competitively.

We have also invested effort in optimising the Uniplate library. As a result we can express concise traversals without sacrificing speed (\S\ref{secU:results_speed}). In particular, we show a substantial speed up over the SYB library \cite{lammel:syb}.

We developed the Firstify tool for analysis, not performance. However, for many simple examples, the resultant program performs better than the original. If we restricted rules that reduce sharing, our defunctionalisation method may be appropriate for integration into an optimising compiler.

\subsection{Safer Programs}

The Catch tool allows programs to have non-exhaustive patterns, yet still have verifiable pattern-match safety. In practical use the Catch tool has found real bugs in real programs, which have subsequently been fixed (see \S\ref{secC:hscolour}). The XMonad developers found that using the Catch tool encouraged a safer style of programming, paying more attention to partial functions (see \S\ref{secC:xmonad}).

The Uniplate library also encourages a style of programming which can lead to fewer errors. By reducing the volume of code, particularly repetitive code, bugs become easier to spot.

\section{Future Work}
\label{secE:future_work}

\subsection{Robust and Widely Applicable Tools}

We have implemented all the tools described in this thesis. The Uniplate library is already robust and used in real programs. The other tools serve more as prototypes, and have not seen sufficient real-world use to declare them production ready. With the exception of Uniplate, the tools are based around the core language from the Yhc compiler. Currently this core language is generated by the Yhc compiler, as described in \S\ref{secB:generating_core}. Yhc restricts our input programs to the Haskell 98 language. By making use of the GHC front end, we would be able to deal with many language extensions.

Supero, Firstify and Catch all operate on a whole program at a time, requiring sources for all function definitions. This requirement both increases the time required, and precludes the use of closed source libraries. We may be able to relax this requirement, precomputing partial results of libraries, or permitting some components of the program to be ignored. We already supply abstractions of IO functions for Catch, and this mechanism could be extended.

\subsection{Uniplate}

The use of boilerplate reduction strategies in Haskell is not yet ubiquitous, as we feel it should be. The ideas behind the Uniplate library have been used extensively, in projects including the Yhc compiler \citep{me:yhc_core}, the Catch tool, the Reach tool \cite{naylor:reach} and the Reduceron \cite{naylor:reduceron}. In previous versions of Catch there were over 100 Uniplate traversals.

There is scope for further speed improvements: for example, use of continuation passing style may eliminate tuple construction and consumption, and enhanced fusion may be able to eliminate some of the intermediate structures in the |uniplate| function. We have made extensive practical use of the Uniplate library, but there may be other traversals which deserve to be added.

Another area of future work, which others have already begun to explore, is the implementation of Uniplate in other languages. So far, we are aware of versions in ML\footnote{\url{http://mlton.org/cgi-bin/viewsvn.cgi/*checkout*/mltonlib/trunk/com/ssh/generic/unstable/public/value/uniplate.sig}} \cite{ml} and Curry\footnote{\url{http://www.informatik.uni-kiel.de/~pakcs/lib/CDOC/Traversal.html}} \cite{curry}. People have also proposed variations on Uniplate, including merging the Uniplate/Biplate distinction\footnote{\url{http://www-ps.informatik.uni-kiel.de/~sebf/projects/traversal.html}}, and using |descend| as the underlying basis for the library\footnote{\texttt{http://tomschrijvers.blogspot.com/2007/11/\\extension-proposal-for-uniplate.html}}.

\subsection{Supero}

Within Supero, there are three main areas for future work. Firstly, we would like to obtain results for larger programs, including all the remaining benchmarks in the nofib suite. Additional benchmarks will give further insight into the performance benefits that Supero provides.

Secondly, we would like to increase the runtime performance. Earlier versions of Supero \cite{me:supero_ifl} managed to obtain substantial speed ups on benchmarks such as exp3\_8. The Bernouilli benchmark is currently problematic. There is still scope for improvement.

Finally, we would like to increase compilation speed. The compilation times are tolerable for benchmarking and a final optimised release, but not for general use. We have described the major bottlenecks in \S\ref{secS:compile_time}, along with possible strategies for alleviating them.

\subsection{Firstify}

The Firstify library currently meets all the needs of the Catch tool. Within the algorithm, the use of a numeric termination bound in the homeomorphic embedding is regrettable, but practically motivated. We need further research to determine if such a numeric bound is necessary, or if other measures could be used.

\subsection{Catch}

The Catch tool has been applied to a range of benchmarks, and has shown promising results. However, there are obviously safe programs (for example Bernouilli in \S\ref{secC:imaginary}) which cannot be proven safe using MP-constraints. In addition to having insufficient power for some examples, MP-constraints also lack a normal form, requiring simplification rules. While MP-constraints are useful, we suspect there exist better constraint models which still fit into the Catch framework. One option would be to combine constraint models, allowing different constraint models to check different error calls.

The tests so far have not included any particularly large applications, such as the darcs program, a Haskell compiler, or even Catch itself. Further evaluation on large programs would give a better idea of what limits within Catch are most pressing. While we have released the Catch tool, it has not seen much use outside of our evaluation -- end users are likely to have additional requests.

\section{Concluding Remarks}
\label{secE:the_end}

Throughout this thesis we have been motivated by the idea of simplicity. We have attempted to reduce the complexity of our methods, both for implementation and for use. In particular, none of our tools requires any annotations to programs.

The Uniplate library restricts traversals to a uniformly typed value set, allowing the power of well-developed techniques for list processing such as list-comprehensions to be exploited. We feel this decision plays to Haskell's strengths, without being limiting in practice. Hopefully by not requiring complicated language features (particularly `scary' types) we will allow a wider base of users to enjoy the benefits of boilerplate-free programming.

Our supercompiler is simple -- the Core transformation is expressed in just 300 lines of Haskell. Yet it replicates many of the performance enhancements of GHC in a more general way. By simplifying the design, we are able to reduce the unintended interactions between optimisations, a problem that has been referred to as ``swings and roundabouts'' \cite{marlow:fast_curry}.

Many analysis methods, in fields such as strictness analysis and termination analysis, start out first-order and are gradually extended to work on a higher-order language. Defunctionalisation offers an alternative approach: instead of extending the analysis method, we transform the functional values away. The analysis method can remain simple, and still work on all programs.

For the Catch tool we have made two decisions that significantly simplify the design: (1) the target of analysis is a very small, first-order core language; (2) there are finitely many value-set-defining constraints per type. Decision (1) allows for a much simpler analysis method, without the added complexity of higher-order programs. Decision (2) inevitably limits the expressive power of constraints; yet it does not prevent the expression of uniform recursive constraints on the deep structure of values, as in MP-constraints.

Functional programs are well suited to analysis and transformation. In this thesis we have presented a number of techniques, which have been refined in response to practical experiments. We hope that the ideas presented will be of real benefit to functional programmers.