All Outputs (48)

Compact fusion (2006)
Presentation / Conference Contribution
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.-W. 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.

Calculating an Exceptional Machine (2005)
Presentation / Conference Contribution
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.

Accurate Step Counting (2005)
Presentation / Conference Contribution
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.

Compiling Exceptions Correctly (2004)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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.