OXFORD UNIVERSITY COMPUTING LABORATORY

Datatype-Generic Programming

Roland Backhouse at the University of Nottingham and Jeremy Gibbons at the University of Oxford have a joint EPSRC-supported project entitled Datatype-Generic Programming, running for three years and starting on 1st October 2003.

Aim

The project is to develop a novel mechanism for parametrizing programs, namely parametrization by a datatype or type constructor. The mechanism is related to parametric polymorphism, but of higher order. We aim to develop a calculus for constructing datatype-generic programs, with the ultimate goal of improving the state of the art in generic object-oriented programming, as occurs for example in the C++ Standard Template Library. further details of the project can be obtained from the contacts listed below.

Workshops and Spring School

Informal workshops were held in Oxford (June 2004) and Utrecht (August 2005).

We will be holding a spring school in Nottingham from the 24th to the 27th of April 2006. This school is a successor to the Summer School and Workshop on Generic Programming, held in Oxford in August 2002 (lecture notes appeared as volume 2793 of LNCS). The Symposium on Trends in Functional Programming (TFP 2006), and the Conference of the Types Project (TYPES 2006) will be held in Nottingham the week before this spring school.

Personnel

The local personnel involved in this project are:
Jeremy Gibbons
Principal investigator
Bruno Oliveira
DPhil student
Collaborators on this project are:
Roland Backhouse
Principal investigator on associated project at Nottingham
Fermin Reig
Research assistant on associated project at Nottingham
Johan Jeuring
Principal investigator on Generic Haskell project at Utrecht
Ralf Hinze
Principal investigator on Generic Haskell project at Bonn
Apart from these collaborators, related projects include:

Mailing list

There is a mailing list, intended for announcements of project-related meetings, posing of problems, pointers to interesting articles, and so on. Membership of the list is intended to be for members and associates of the project; but if you think you should be included, let me know. Posting is restricted to members of the list. To post to the list, send your message to the list posting address To subscribe to the list, send an email message containing (only) the command `subscribe' to the list request address. For further information, send a message containing the command `help' to the Majordomo address.

Publications

[Gibbons2006:Iterator]
Jeremy Gibbons and Bruno C. d. S. Oliveira (2006). The Essence of the Iterator Pattern. Submitted for publication.

Abstract: The Iterator pattern gives a clean interface for element-by-element access to a collection. Imperative iterations using the pattern have two simultaneous aspects: mapping and accumulating. Various functional iterations model one or other of these, but not both simultaneously. We argue that McBride and Paterson's idioms, and in particular the corresponding traverse operator, do exactly this, and therefore capture the essence of the Iterator pattern. We present some axioms for traversal, and illustrate with a simple example, the repmin problem.
Fetch the PDF file (18 pages).

[Oliveira2006:Generics]
Bruno C. d. S. Oliveira, Ralf Hinze and Andres Löh (2006). Generics as a Library. Submitted for publication.

Abstract: A generic function is a function that is defined on the structure of data types: with a single definition, we obtain a function that works for many data types. In contrast, an ad-hoc polymorphic function requires a separate implementation for each data type. Previous work by Hinze on lightweight generic programming has introduced techniques that allow the definition of generic functions directly in Haskell. A severe drawback of these approaches is that generic functions, once defined, cannot be extended with ad-hoc behaviour for new data types, precluding the design of a customizable generic programming library based on the se techniques. In this paper, we present a revised version of Hinze's Generics for the masses approach that overcomes this limitation. Using our new technique, writing a customizable generic programming library in Haskell 98 is possible.
Fetch the PDF file (15 pages). Source code can be found here and there is also an extended abstract available here.

[Gibbons2006:Design]
Jeremy Gibbons (2006). Design Patterns as Higher-Order Datatype-Generic Programs. Submitted for publication.

Abstract: Design patterns are reusable abstractions in object-oriented software. However, using current programming languages, these elements can only be expressed extra-linguistically: as prose, pictures, and prototypes. We believe that this is not inherent in the patterns themselves, but evidence of a lack of expressivity in the languages of today. We expect that, in the languages of the future, design patterns will be expressible as reusable library code. Indeed, we claim that the languages of tomorrow will suffice; the future is not far away. The necessary features are higher-order and datatype-generic constructs; these features are already or nearly available now. We argue the case by presenting higher-order datatype-generic programs capturing Origami, a small pattern language of recursive data structures.
pdf (18 pages).

[Hinze2005:SYB]
Ralf Hinze, Andres Löh, and Bruno C. d. S. Oliveira (2005) "Scrap Your Boilerplate" Reloaded. Accepted at FLOPS 2006

Abstract: The paper "Scrap your boilerplate" (SYB) introduces a combinator library for generic programming that offers generic traversals and queries. Classically, support for generic programming consists of two essential ingredients: a way to write (type-)overloaded functions, and independently, a way to access the structure of data types. SYB seems to lack the second. As a consequence, it is difficult to compare with other approaches such as PolyP or Generic Haskell. In this paper we reveal the structural view that SYB builds upon. This allows us to define the combinators as generic functions in the classical sense. We explain the SYB approach in this changed setting from ground up, and use the understanding gained to relate it to other generic programming approaches. Furthermore, we show that the SYB view is applicable to a very large class of data types, including generalized algebraic data types.
Fetch the PDF file (17 pages). Extended version, source code and useful other information can be found here.

[Oliveira2005:TypeCase]
Bruno C. d. S. Oliveira and Jeremy Gibbons (2005), TypeCase: A Design Pattern for Type-Indexed Functions. To appear in Haskell Workshop, 30th September 2005.
Abstract: A type-indexed function is a function that is defined for each member of some family of types. Haskell's type class mechanism provides open type-indexed functions, in which the indexing family can be extended at any time by defining a new type class instance. The purpose of this paper is to present TypeCase: a design pattern that allows the definition of closed type-indexed functions. It is inspired by Cheney and Hinze's work on lightweight approaches to generic programming. We generalise their techniques as a design pattern. Furthermore, we show that type-indexed functions with type-indexed types, and consequently generic functions with generic types, can also be encoded in a lightweight manner, thereby overcoming one of the main limitations of the lightweight approaches.
pdf (12 pages).

[Reig2004:Generic]
Fermin Reig, Generic proofs for combinator-based generic programs. To appear in TFP 2004 - Fifth Symposium on Trends in Functional Programming, Munich, 25-26th November 2004.

Abstract:Generic programming can bring important benefits to software engineering. In particular, it reduces the burden of verification, since generic proofs can be instantiated at many types. Reasoning about programs that use type classes does not enjoy the benefits of generic reasoning, as it requires providing proofs for an arbitrary number of type instances. This makes the process very impractical. We describe a useful method to reason about a class of programs that use type classes, based on the idea that generic functions implemented using overloading can also be expressed polytypically. We demonstrate the method on functions from the 'scrap-your-boilerplate' library, a collection of combinators for generic programming that has been proposed and implemented recently.
pdf (18 pages).

[Gibbons2003:Patterns]
Jeremy Gibbons, Patterns in Datatype-Generic Programming. To appear in Declarative Programming in the Context of Object-Oriented Languages, Uppsala, 25th August 2003.

Abstract: Generic programming consists of increasing the expressiveness of programs by allowing a wider variety of kinds of parameter than is usual. The most popular instance of this scheme is the C++ Standard Template Library. Datatype-generic programming is another instance, in which the parameters take the form of datatypes. We argue that datatype-generic programming is sufficient to express essentially all the genericity found in the Standard Template Library, and to capture the abstractions motivating many design patterns. Moreover, datatype-generic programming is a precisely-defined notion with a rigorous mathematical foundation, in contrast to generic programming in general and the C++ template mechanism in particular, and thereby offers the prospect of better static checking and a greater ability to reason about generic programs. This paper describes work in progress.
pdf (13 pages).

Internal area

This part of the website is for members of the project only.


Jeremy Gibbons (Jeremy.Gibbons@comlab.ox.ac.uk)

[Oxford Spires]



Oxford University Computing Laboratory Courses Research People About us News