The documents contained in these pages are included to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Here are my papers that have been submitted for publication.
The Worker Wrapper Transformation, Andy Gill and Graham Hutton, Submitted to the Journal of Functional Programming, 2008
| The worker/wrapper transformation is a technique for changing the type of a computation, usually with the aim of improving its performance. It has been used by compiler writers for many years, but the technique is little-known in the wider functional programming community, and has never been formalised. In this article we explain, formalise, and explore the generality of the worker/wrapper transformation. We also provide a systematic recipe for its use, and illustrate the power of this recipe using a range of examples. | |
| [Details] [pdf] [www.workerwrapper.com] [BibTeX] |
Unrestricted call-by-value recursion, Johan Nordlander and Magnus Carlsson and Andy Gill, Submitted to the Workshop on ML, 2008
| Call-by-value languages commonly restrict recursive definitions by only allowing functions and syntactically explicit values in the right-hand sides. As a consequence, some very appealing programming patterns that work well in lazy functional languages are hard to apply in a call-by-value setting, even though they might not be using laziness for any other purpose than to enable the desired form of recursion. In this paper we present an operational semantics as well as an efficient implementation technique for unrestricted recursion under call-by-value. On that basis we are able to demonstrate that highly recursive programming idioms such as combinator-based parsing are indeed compatible with call-by-value evaluation. | |
| [Details] [pdf] [BibTeX] |
Here are my publications.
Asynchronous Exceptions as an Effect, William L. Harrison and Gerard Allwein and Andy Gill and Adam Procter, Ninth International Conference on Mathematics of Program Construction, July 2008
| Asynchronous interrupts abound in computing systems, yet they remain a thorny concept for both programming and verification practice. The ubiquity of interrupts underscores the importance of developing programming models to aid the development and verification of interrupt-driven programs. The research reported here recognizes asynchronous interrupts as a computational effect and encapsulates them as a building block in modular monadic semantics. The resulting integrated semantic model can serve as both a guide for functional programming with interrupts and as a formal basis for reasoning about interrupt-driven computation as well. | |
| [Details] [pdf] [BibTeX] |
Haskell Program Coverage, Andy Gill and Colin Runciman, Proceedings of the 2007 ACM SIGPLAN Workshop on Haskell, September 2007
| We describe the design, implementation and use of HPC, a tool-kit to record and display Haskell Program Coverage. HPC includes tools that instrument Haskell programs to record program coverage, run instrumented programs, and display information derived from coverage data in various ways. | |
| [Details] [pdf] [slides (pdf)] [google video] [BibTeX] |
A lightweight interactive debugger for Haskell, Simon Marlow and José Iborra and Bernard Pope and Andy Gill, Proceedings of the 2007 ACM SIGPLAN Workshop on Haskell, September 2007
| This paper describes the design and construction of a Haskell source-level debugger built into the GHCi interactive environment. We have taken a pragmatic approach: the debugger is based on the traditional stop-examine-continue model of online debugging, which is simple and intuitive, but has traditionally been shunned in the context of Haskell because it exposes the lazy evaluation order. We argue that this drawback is not as severe as it may seem, and in some cases is an advantage. The design focuses on availability: our debugger is intended to work on all programs that can be compiled with GHC, and without requiring the programmer to jump through additional hoops to debug their program. The debugger has a novel approach for reconstructing the type of runtime values in a polymorphic context. Our implementation is light on complexity, and was integrated into GHC without significant upheaval. | |
| [Details] [pdf] [BibTeX] |
Automated translation of legacy code for ATE, Andrew Moran and Jim Teisher and Andrew Gill and Emir Pasalic and John Veneruso, Proceedings of the IEEE International Test Conference, 2001
| When an Automated Testing Equipment (ATE) company designs a new system, the issue of backward compatibility is always a major concern, both for the company and its customers. If backward compatibility is maintained, the ATE application engineers face the difficult task of trying to support new features on an aging system. The alternative is to face the problem of converting old test programs to the new environment. Translation of legacy code involves an automatic translation tool, and some application effort applied to those problems the translator couldn't resolve. To minimize the amount of work required from the application engineers, the tool needs to be semantically aware; that is, the tool must contain domain specific knowledge and use that knowledge when translating. The more knowledge a tool has at its disposal, the less code an application engineer is forced to translate by hand. Until recently, it has been difficult to perform automatic translation satisfactorily because it was not cost effective to write a translator that possessed such semantic understanding of the test programs. By making good use of Functional Programming techniques and tools, we were able to construct a cost effective, semantically aware translation tool in a fraction of the time needed by traditional methods. Based upon its performance during testing, we believe the tool to correctly translate the majority of test programs, thereby greatly easing the applications engineers' burden. | |
| [Details] [pdf] [BibTeX] |
Debugging Haskell by observing intermediate data structures, Andy Gill, Proceedings of the 2000 Workshop on Haskell, Technical report of the University of Nottingham, 2000
| Haskell has long needed a debugger. Although there has been much research into the topic of debugging lazy functional programs, no robust tool has yet come from the Haskell community that can help debug full Haskell - until now. This paper describes a portable debugger for full Haskell, building only on commonly implemented extensions. It is based on the concept of observation of intermediate data structures, rather than the more traditional stepping and variable examination paradigm used by traditional imperative debuggers. | |
| [Details] [pdf] [ps] [citeseer] [Hood Home Page] [BibTeX] |
Fast mergeable integer maps, Chris Okasaki and Andy Gill, Workshop on ML, September 1998
| Finite maps are ubiquitous in many applications, but perhaps nowhere more so than in compilers and other language processors. In these applications, three operations on finite maps dominate all others: looking up the value associated with a key, inserting a new binding, and merging two finite maps. Most implementations of finite maps in functional languages are based on balanced binary search trees, which perform well on the first two, but poorly on the third. We describe an implementation of finite maps with integer keys that performs well in practice on all three operations. This data structure is not new-indeed, it is thirty years old this year-but it deserves to be more widely known. | |
| [Details] [pdf] [ps] [citeseer] [BibTeX] |
The technology behind a graphical user interface for an equational reasoning assistant, Andy Gill, Proceedings of the 1995 Glasgow Workshop on Functional Programming, Electronic Workshops in Computing, Ullapool, Scotland, 1995
| The Haskell Equational Reasoning Assistant (HERA) is an application written in Haskell that helps users construct and present equational reasoning style proofs. In this paper we discuss the technology behind HERA's graphical user interface. | |
| [Details] [pdf] [ps] [citeseer] [BibTeX] |
Cheap Deforestation in Practice: An Optimizer for Haskell, Andrew Gill and Simon Peyton Jones, IFIP Congress (1), 1994
| We present a simple, automatic transformation - the foldr/build transformation - which successfully removes many intermediate lists from programs written in non-strict functional programming languages. While the idea is simple and elegant, it turns out that some care is needed in the compiler to set up the right conditions for the foldr/build transformation to be applicable. We report on this practical experience, and present results which quantify the benefits that can in practice be achieved. | |
| [BibTeX] |
A short cut to deforestation, Andrew Gill and John Launchbury and Simon Peyton Jones, FPCA '93: Proceedings of the conference on Functional Programming Languages and Computer Architecture, 1993
| Lists are often used as "glue" to connect separate parts of a program together. We propose an automatic technique for improving the efficiency of such programs, by removing many of these intermediate lists, based on a single, simple, local transformation. We have implemented the method in the Glasgow Haskell compiler. | |
| [Details] [pdf] [ps] [citeseer] [BibTeX] |
Avoiding Unnecessary Updates, John Launchbury and Andrew Gill and John Hughes and Simon Marlow and Simon Peyton Jones and Philip Wadler, Glasgow Workshop on Functional Programming, Workshops in Computing, 1992
| Graph reduction underlies most implementations of lazy functional languages, allowing separate computations to share results when sub-terms are evaluated. Once a term is evaluated, the node of the graph representing the computation is updated with the value of the term. However, in many cases, no other computation requires this value, so the update is unnecessary. In this paper we take some steps towards an analysis for determining when these updates may be omitted. | |
| [Details] [pdf] [ps] [citeseer] [BibTeX] |
A Novel Approach Towards Peephole Optimisations, Andrew Gill, Proceedings of the 1991 Glasgow Workshop on Functional Programming, August 1991
| In this paper we examine alternative approaches towards the traditional optimisation technique of peepholing. Three simple methods of generating quality code are given. The first method improves poor juxtapositions while generating code, the second is an alternative usage of a solution to the knapsack problem. A third hybrid algorithm combines the strong points of both these solutions, and is presented as an alternative to conventional peepholing. | |
| [Details] [citeseer] [BibTeX] |
Here is my dissertation.
Cheap deforestation for non-strict functional languages, Andrew Gill, The University of Glasgow, January 1996
| In functional languages intermediate data structures are often used as "glue" to connect separate parts of a program together. Deforestation is the process of automatically removing intermediate data structures. In this thesis we present and analyse a new approach to deforestation. This new approach is both practical and general. We analyse in detail the problem of list removal rather than the more general problem of arbitrary data structure removal. This more limited scope allows a complete evaluation of the pragmatic aspects of using our deforestation technology. We have implemented our list deforestation algorithm in the Glasgow Haskell compiler. Our implementation has allowed practical feedback. One important conclusion is that a new analysis is required to infer function arities and the linearity of lambda abstractions. This analysis renders the basic deforestation algorithm far more effective. We give a detailed assessment of our implementation of deforestation. We measure the effectiveness of our deforestation on a suite of real application programs. We also observe the costs of our deforestation algorithm. | |
| [Details] [pdf] [pdf (2up)] [ps] [ps (2up)] [citeseer] [BibTeX] |
Here is a short writeup for a tool demonstration.
Introducing the Haskell Equational Reasoning Assistant, Andy Gill, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, 2006
| We introduce the new, improved version of the Haskell Equational Reasoning Assistant, which consists of an Ajax application for rewriting Haskell fragments in their context, and an API for scripting non-trivial rewrites. | |
| [Details] [pdf] [HERA Wiki Page] [BibTeX] |