Datatype-Generic Programming

Aim

Workshops and Spring School

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

Jeremy Gibbons

Principal investigator

Bruno Oliveira

DPhil student

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

• Polytypic programming at Chalmers
• Template Haskell
• Functional C++
• PolyO
• Scrap your boilerplate

Mailing list

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