All Outputs (19)

Beyond Trees: Calculating Graph-Based Compilers (2024)
Journal Article

Bahr and Hutton recently developed an approach to compiler calculation that allows a wide range of compilers to be derived from specifications of their correctness. However, a limitation of the approach is that it results in compilers that produce tr... Read More about Beyond Trees: Calculating Graph-Based Compilers.

Quotient Haskell: Lightweight Quotient Types for All (2024)
Journal Article

Subtypes and quotient types are dual type abstractions. However, while subtypes are widely used both explicitly and implicitly, quotient types have not seen much practical use outside of proof assistants. A key difficulty to wider adoption of quotie... Read More about Quotient Haskell: Lightweight Quotient Types for All.

Calculating Compilers for Concurrency (2023)
Journal Article

Choice trees have recently been introduced as a general structure for defining the semantics of programming languages with a wide variety of features and effects. In this article we focus on concurrent languages, and show how a codensity version of c... Read More about Calculating Compilers for Concurrency.

Monadic compiler calculation (functional pearl) (2022)
Journal Article

Bahr and Hutton recently developed a new approach to calculating correct compilers directly from specifications of their correctness. However, the methodology only considers converging behaviour of the source language, which means that the compiler c... Read More about Monadic compiler calculation (functional pearl).

Calculating dependently-typed compilers (functional pearl) (2021)
Journal Article

Compilers are difficult to write, and difficult to get right. Bahr and Hutton recently developed a new technique for calculating compilers directly from specifications of their correctness, which ensures that the resulting compilers are correct-by-co... Read More about Calculating dependently-typed compilers (functional pearl).

Calculating correct compilers II: Return of the register machines (2020)
Journal Article

In ‘Calculating Correct Compilers’ (Bahr & Hutton, 2015), we developed a new approach to calculating compilers directly from specifications of their correctness. Our approach only required elementary reasoning techniques and has been used to calculat... Read More about Calculating correct compilers II: Return of the register machines.

Compiling a 50-year journey (2017)
Journal Article
Hutton, G., & Bahr, P. (2017). Compiling a 50-year journey. Journal of Functional Programming, 27, Article e20

Fifty years ago, John McCarthy and James Painter (1967) published the first paper on compiler verification, in which they showed how to formally prove the correctness of a compiler that translates arithmetic expressions into code for a register-based... Read More about Compiling a 50-year journey.

Towards a theory of reach (2016)
Journal Article
Fowler, J., & Hutton, G. (2016). Towards a theory of reach. Lecture Notes in Artificial Intelligence, 9547, https://doi.org/10.1007/978-3-319-39110-6

When testing a program, there are usually some parts that are rarely executed and hence more difficult to test. Finding inputs that guarantee that such parts are executed is an example of a reach problem, which in general seeks to ensure that targete... Read More about Towards a theory of reach.

Calculating correct compilers (2015)
Journal Article
Bahr, P., & Hutton, G. (2015). Calculating correct compilers. Journal of Functional Programming, 25, Article e14. https://doi.org/10.1017/S0956796815000180

© 2016 Cambridge University Press. In this article, we present a new approach to the problem of calculating compilers. In particular, we develop a simple but general technique that allows us to derive correct compilers from high-level semantics by sy... Read More about Calculating correct compilers.

Work it, wrap it, fix it, fold it (2014)
Journal Article
Sculthorpe, N., & Hutton, G. (2014). Work it, wrap it, fix it, fold it. Journal of Functional Programming, 24(1), https://doi.org/10.1017/S0956796814000045

The worker/wrapper transformation is a general-purpose technique for refactoring recursive programs to improve their performance. The two previous approaches to formalising the technique were based upon different recursion operators and different cor... Read More about Work it, wrap it, fix it, fold it.

Report on BCTCS 2005 (2005)
Journal Article
Hutton, G. (2005). Report on BCTCS 2005

This report contains edited abstracts from BCTCS 2005, which was held on 22nd to 24th March 2005 in Nottingham, England.

Proof Methods for Corecursive Programs (2005)
Journal Article
Hutton, G., & Gibbons, J. (2005). Proof Methods for Corecursive Programs

Recursion is a well-known and powerful programming technique, with a wide variety of applications. The dual technique of corecursion is less well-known, but is increasingly proving to be just as useful. This article is a tutorial on the four main m... Read More about Proof Methods for Corecursive Programs.

The Countdown Problem (2002)
Journal Article
Hutton, G. (2002). The Countdown Problem. Journal of Functional Programming, 12(6),

We systematically develop a functional program that solves the countdown problem, a numbers game in which the aim is to construct arithmetic expressions satisfying certain constraints. Starting from a formal specification of the problem, we present... Read More about The Countdown Problem.

The Generic Approximation Lemma (2001)
Journal Article
Hutton, G., & Gibbons, J. (2001). The Generic Approximation Lemma. Information Processing Letters, 79(4),

The approximation lemma is a simplification of the well-known take lemma, and is used to prove properties of programs that produce lists of values. We show how the approximation lemma, unlike the take lemma, can naturally be generalised from lists t... Read More about The Generic Approximation Lemma.

A Tutorial on the Universality and Expressiveness of Fold (1999)
Journal Article
Hutton, G. (1999). A Tutorial on the Universality and Expressiveness of Fold. Journal of Functional Programming, 9(4),

In functional programming, fold is a standard operator that encapsulates a simple pattern of recursion for processing lists. This article is a tutorial on two key aspects of the fold operator for lists. First of all, we emphasize the use of the uni... Read More about A Tutorial on the Universality and Expressiveness of Fold.

Monadic parsing in Haskell (1998)
Journal Article
Hutton, G., & Meijer, E. (1998). Monadic parsing in Haskell. Journal of Functional Programming, 8(4),

This paper is a tutorial on defining recursive descent parsers in Haskell. In the spirit of one-stop shopping, the paper combines material from three areas into a single source. The three areas are functional parsers, the use of monads to structure... Read More about Monadic parsing in Haskell.

Back to Basics: Deriving Representation Changers Functionally (1996)
Journal Article
Hutton, G., & Meijer, E. (1996). Back to Basics: Deriving Representation Changers Functionally. Journal of Functional Programming, 6(1),

Many functional programs can be viewed as representation changers, that is, as functions that convert abstract values from one concrete representation to another. Examples of such programs include base-converters, binary adders and multipliers, and... Read More about Back to Basics: Deriving Representation Changers Functionally.

Review of Mike Gordon and Tom Melham (editors), An Introduction to HOL, a Theorem Proving Environment for Higher Order Logic (1994)
Journal Article
Hutton, G. (1994). Review of Mike Gordon and Tom Melham (editors), An Introduction to HOL, a Theorem Proving Environment for Higher Order Logic. Journal of Functional Programming, 4(4),

Higher-Order Functions for Parsing (1992)
Journal Article
Hutton, G. (1992). Higher-Order Functions for Parsing. Journal of Functional Programming, 2(3),

In combinator parsing, the text of parsers resembles BNF notation. We present the basic method, and a number of extensions. We address the special problems presented by white-space, and parsers with separate lexical and syntactic phases. In partic... Read More about Higher-Order Functions for Parsing.