Outputs (51)

Quotient Haskell: Lightweight Quotient Types for All (2024)
Journal Article
Hewer, B., & Hutton, G. (2024). Quotient Haskell: Lightweight Quotient Types for All. Proceedings of the ACM on Programming Languages, 8(POPL), 785-815. https://doi.org/10.1145/3632869

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
Bahr, P., & Hutton, G. (2023). Calculating Compilers for Concurrency. Proceedings of the ACM on Programming Languages, 7(ICFP), 740-767. https://doi.org/10.1145/3607855

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, P., & Hutton, G. (2022). Monadic compiler calculation (functional pearl). Proceedings of the ACM on Programming Languages, 6(ICFP), 80-108. https://doi.org/10.1145/3547624

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
Pickard, M., & Hutton, G. (2021). Calculating dependently-typed compilers (functional pearl). Proceedings of the ACM on Programming Languages, 5(ICFP), 1-27. https://doi.org/10.1145/3473587

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
Bahr, P., & Hutton, G. (2020). Calculating correct compilers II: Return of the register machines. Journal of Functional Programming, 30, https://doi.org/10.1017/s0956796820000209

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.

Liquidate your assets: reasoning about resource usage in liquid Haskell (2019)
Journal Article
Handley, M., Vazou, N., & Hutton, G. (2019). Liquidate your assets: reasoning about resource usage in liquid Haskell. Proceedings of the ACM on Programming Languages, 4, 1-27. https://doi.org/10.1145/3371092

Liquid Haskell is an extension to the type system of Haskell that supports formal reasoning about program correctness by encoding logical properties as refinement types. In this article, we show how Liquid Haskell can also be used to reason about pro... Read More about Liquidate your assets: reasoning about resource usage in liquid Haskell.

Call-by-need is clairvoyant call-by-value (2019)
Journal Article
Hackett, J., & Hutton, G. (2019). Call-by-need is clairvoyant call-by-value. Proceedings of the ACM on Programming Languages, 3(ICFP), 1-21. https://doi.org/10.1145/3341718

Call-by-need evaluation, also known as lazy evaluation, provides two key benefits: compositional programming and infinite data. The standard semantics for laziness is Launchbury’s natural semantics, which uses a heap to memoise the results of delayed... Read More about Call-by-need is clairvoyant call-by-value.

AutoBench: comparing the time performance of Haskell programs (2018)
Conference Proceeding
HANDLEY, M., & HUTTON, G. (2018). AutoBench: comparing the time performance of Haskell programs. In Proceedings of the 11th ACM SIGPLAN Haskell Symposium (Haskell '18). , (26-37). https://doi.org/10.1145/3242744.3242749

Two fundamental goals in programming are correctness (producing the right results) and efficiency (using as few resources as possible). Property-based testing tools such as QuickCheck provide a lightweight means to check the correctness of Haskell pr... Read More about AutoBench: comparing the time performance of Haskell programs.

Theorem proving for all: equational reasoning in Liquid Haskell (Functional Pearl) (2018)
Conference Proceeding
Vazou, N., Breitner, J., Kunkel, R., Van Horn, D., & Hutton, G. (2018). Theorem proving for all: equational reasoning in Liquid Haskell (Functional Pearl). In Proceedings of the 11th ACM SIGPLAN Haskell Symposium (Haskell '18) (132-144). https://doi.org/10.1145/3242744.3242756

Equational reasoning is one of the key features of pure functional languages such as Haskell. To date, however, such reasoning always took place externally to Haskell, either manually on paper, or mechanised in a theorem prover. This article shows ho... Read More about Theorem proving for all: equational reasoning in Liquid Haskell (Functional Pearl).

Parametric polymorphism and operational improvement (2018)
Journal Article
Hackett, J., & Hutton, G. (2018). Parametric polymorphism and operational improvement. Proceedings of the ACM on Programming Languages, 2(ICFP), 1-24. https://doi.org/10.1145/3236763

Parametricity, in both operational and denotational forms, has long been a useful tool for reasoning about program correctness. However, there is as yet no comparable technique for reasoning about program improvement, that is, when one program uses f... Read More about Parametric polymorphism and operational improvement.

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.

Failing faster: overlapping patterns for property-based testing (2017)
Conference Proceeding
Fowler, J., & Hutton, G. (2017). Failing faster: overlapping patterns for property-based testing. In Practical Aspects of Declarative Languages: 19th International Symposium, PADL 2017, Paris, France, January 16-17, 2017: Proceedings (103-119). https://doi.org/10.1007/978-3-319-51676-9-7

In property-based testing, a key problem is generating input data that satisfies the precondition of a property. One approach is to attempt to do so automatically, from the definition of the precondition itself. This idea has been realised using the... Read More about Failing faster: overlapping patterns for property-based testing.

Contractive Functions on Infinite Data Structures (2016)
Conference Proceeding
Capretta, V., Hutton, G., & Jaskelioff, M. (2016). Contractive Functions on Infinite Data Structures. In IFL 2016: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages (1-13). https://doi.org/10.1145/3064899.3064900

Coinductive data structures, such as streams or infinite trees, have many applications in functional programming and type theory, and are naturally defined using recursive equations. But how do we ensure that such equations make sense, i.e. that they... Read More about Contractive Functions on Infinite Data Structures.

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.

Cutting out continuations (2016)
Conference Proceeding
Hutton, G., & Bahr, P. (2016). Cutting out continuations.

In the field of program transformation, one often transforms programs into continuation-passing style to make their flow of control explicit, and then immediately removes the resulting continuations using defunctionalisation to make the programs firs... Read More about Cutting out continuations.

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.

Programs for cheap! (2015)
Conference Proceeding
Hackett, J., & Hutton, G. (2015). Programs for cheap!. In Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (115-126). https://doi.org/10.1109/LICS.2015.21

Write down the definition of a recursion operator on a piece of paper. Tell me its type, but be careful not to let me see the operator’s definition. I will tell you an optimization theorem that the operator satisfies. As an added bonus, I will also g... Read More about Programs for cheap!.

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.

Worker/wrapper/makes it/faster (2014)
Conference Proceeding
Hackett, J., & Hutton, G. (2014). Worker/wrapper/makes it/faster.

Much research in program optimization has focused on formal approaches to correctness: proving that the meaning of programs is preserved by the optimisation. Paradoxically, there has been comparatively little work on formal approaches to efficiency:... Read More about Worker/wrapper/makes it/faster.

The under-performing unfold: a new approach to optimising corecursive programs (2013)
Conference Proceeding
Hackett, J., Hutton, G., & Jaskelioff, M. (2013). The under-performing unfold: a new approach to optimising corecursive programs.

This paper presents a new approach to optimising corecursive programs by factorisation. In particular, we focus on programs written using the corecursion operator unfold. We use and expand upon the proof techniques of guarded coinduction and unfold f... Read More about The under-performing unfold: a new approach to optimising corecursive programs.

Towards modular compilers for effects (2012)
Conference Proceeding
Day, L., & Hutton, G. (2012). Towards modular compilers for effects.

Compilers are traditionally factorised into a number of separate phases, such as parsing, type checking, code generation, etc. However, there is another potential factorisation that has received comparatively little attention: the treatment of separa... Read More about Towards modular compilers for effects.

Compiling concurrency correctly: cutting out the middle man (2010)
Conference Proceeding
Hu, L., & Hutton, G. (2010). Compiling concurrency correctly: cutting out the middle man.

The standard approach to proving compiler correctness for concurrent languages requires the use of multiple translations into an intermediate process calculus. We present a simpler approach that avoids the need for such an intermediate language, usin... Read More about Compiling concurrency correctly: cutting out the middle man.

Programming in Haskell (2007)
Book
Hutton, G. (2007). Programming in Haskell. Cambridge University Press

Compact fusion (2006)
Conference Proceeding
Hope, C., & Hutton, G. (2006). Compact fusion.

There are many advantages to writing functional programs in a compositional style, such as clarity and modularity. However, the intermediate data structures produced may mean that the resulting program is inefficient in terms of space. These may be r... Read More about Compact fusion.

Calculating an exceptional machine (2006)
Book Chapter
Hutton, G., & Wright, J. (2006). Calculating an exceptional machine. In H. Loidl (Ed.), Trends in functional programming. Volume 5. Intellect

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.

Accurate Step Counting (2005)
Conference Proceeding
Hope, C., & Hutton, G. (2005). Accurate Step Counting.

Starting with an evaluator for a language, an abstract machine for the same language can be mechanically derived using successive program transformations. This has relevance to studying both the space and time properties of programs because these ca... Read More about Accurate Step Counting.

Calculating an Exceptional Machine (2005)
Conference Proceeding
Hutton, G., & Wright, J. (2005). Calculating an Exceptional Machine.

In previous work we showed how to verify a compiler for a small language with exceptions. In this article we show how to calculate, as opposed to verify, an abstract machine for this language. The key step is the use of Reynold's defunctionalizatio... Read More about Calculating an Exceptional Machine.

Compiling Exceptions Correctly (2004)
Conference Proceeding
Hutton, G., & Wright, J. (2004). Compiling Exceptions Correctly.

Exceptions are an important feature of modern programming languages, but their compilation has traditionally been viewed as an advanced topic. In this article we show that the basic method of compiling exceptions using stack unwinding can be explain... Read More about Compiling Exceptions Correctly.

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.

When is a function a fold or an unfold? (2001)
Conference Proceeding
Gibbons, J., Hutton, G., & Altenkirch, T. (2001). When is a function a fold or an unfold?.

We give a necessary and sufficient condition for when a set-theoretic function can be written using the recursion operator fold, and a dual condition for the recursion operator unfold. The conditions are simple, practically useful, and generic in the... Read More about When is a function a fold or an unfold?.

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.

Proof methods for structured corecursive programs (1999)
Conference Proceeding
Gibbons, J., & Hutton, G. (1999). Proof methods for structured corecursive programs.

Corecursive programs produce values of greatest fixpoint types, in contrast to recursive programs, which consume values of least fixpoint types. There are a number of widely used methods for proving properties of corecursive programs, including fixp... Read More about Proof methods for structured corecursive programs.

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.

Fold and Unfold for Program Semantics (1998)
Conference Proceeding
Hutton, G. (1998). Fold and Unfold for Program Semantics.

In this paper we explain how recursion operators can be used to structure and reason about program semantics within a functional language. In particular, we show how the recursion operator fold can be used to structure denotational semantics, how th... Read More about Fold and Unfold for Program Semantics.

Monadic parser combinators (1996)
Book
Hutton, G., & Meijer, E. (1996). Monadic parser combinators. School of Computer Science and IT

In functional programming, a popular approach to building recursive descent parsers is to model parsers as functions, and to define higher-order functions (or combinators) that implement grammar constructions such as sequencing, choice, and repetitio... Read More about Monadic parser combinators.

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.

Bananas in space: extending fold and unfold to exponential types (1995)
Conference Proceeding
Meijer, E., & Hutton, G. (1995). Bananas in space: extending fold and unfold to exponential types.

Fold and unfold are general purpose functionals for process-ing and constructing lists. By using the categorical approach of modelling recursive datatypes as fixed points of functors, these functionals and their algebraic properties were generalised... Read More about Bananas in space: extending fold and unfold to exponential types.

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),

Categories, Allegories, and Circuit Design (1994)
Conference Proceeding
Brown, C., & Hutton, G. (1994). Categories, Allegories, and Circuit Design.

Languages based upon binary relations offer an appealing setting for constructing programs from specifications. For example, working with relations rather than functions allows specifications to be more abstract (for example, many programs have a na... Read More about Categories, Allegories, and Circuit Design.

The Ruby Interpreter (1993)
Book
Hutton, G. (1993). The Ruby Interpreter. Department of Computing Science

Ruby is a relational calculus for designing digital circuits. This document is a guide to the Ruby interpreter, which allows a special class of $quot;implementable$quot; Ruby programs to be executed. The Ruby interpreter is written in the functional... Read More about The Ruby Interpreter.

Between functions and relations in calculating programs (1992)
Thesis
Hutton, G. M. Between functions and relations in calculating programs. (Thesis). University of Glasgow. Retrieved from https://nottingham-repository.worktribe.com/output/1164861

This thesis is about the calculational approach to programming, in which one derives programs from specifications. One such calculational paradigm is Ruby, the relational calculus developed by Jones and Sheeran for describing and designing circuits.... Read More about Between functions and relations in calculating programs.

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.

A Calculational Theory of Pers as Types (1992)
Book
Hutton, G., & Voermans, E. (1992). A Calculational Theory of Pers as Types. Department of Computing Science

In the calculational approach to programming, programs are derived from specifications by algebraic reasoning. This report presents a calculational programming framework based upon the notion of binary relations as programs, and partial equivalence... Read More about A Calculational Theory of Pers as Types.

A Relational Derivation of a Functional Program (1992)
Conference Proceeding
Hutton, G. (1992). A Relational Derivation of a Functional Program.

This article is an introduction to the use of relational calculi in deriving programs. Using the relational caluclus Ruby, we derive a functional program that adds one bit to a binary number to give a new binary number. The resulting program is uns... Read More about A Relational Derivation of a Functional Program.

Making Functionality More General (1992)
Conference Proceeding
Hutton, G., & Voermans, E. (1992). Making Functionality More General.

The definition for the notion of a "function" is not cast in stone, but depends upon what we adopt as types in our language. With partial equivalence relations (pers) as types in a relational language, we show that the functional relations are preci... Read More about Making Functionality More General.

Functional Programming With Relations (1991)
Conference Proceeding
Hutton, G. (1991). Functional Programming With Relations.

While programming in a relational framework has much to offer over the functional style in terms of expressiveness, computing with relations is less efficient, and more semantically troublesome. In this paper we propose a novel blend of the function... Read More about Functional Programming With Relations.

Modularity and implementation of mathematical operational semantics
Conference Proceeding
Jaskelioff, M. J., Ghani, N., & Hutton, G. Modularity and implementation of mathematical operational semantics.

Structural operational semantics is a popular technique for specifying the meaning of programs by means of inductive clauses. One seeks syntactic restrictions on those clauses so that the resulting operational semantics is well-behaved. This approa... Read More about Modularity and implementation of mathematical operational semantics.

A tool for relational programmers
Book
Hutton, G., Meijer, E., & Voermans, E. A tool for relational programmers. Chalmers University, Sweden