Algebraic Specialization of Generic Functions for Recursive Types

• Type: Article in International Scientific Journal
• Date: 2011

Authors

Cunha, A (Author) Other; Pacheco, H (Author) Other

Journal

Title: Electronic Notes in Theoretical Computer Science

Vol. 229

Pages: 57-74

ISSN: 1571-0661

Publisher: Elsevier

Indexing

Scopus - 1 Citation

Other information

Authenticus ID: P-007-XPX

DOI: 10.1016/j.entcs.2011.02.016

Abstract (EN): Defining functions over large, possibly recursive, data structures usually involves a lot of boilerplate. This code simply traverses non-interesting parts of the data, and rapidly becomes a maintainability problem. Many generic programming libraries have been proposed to address this issue. Most of them allow the user to specify the behavior just for the interesting bits of the structure, and provide traversal combinators to "scrap the boilerplate". The expressive power of these libraries usually comes at the cost of efficiency, since runtime checks are used to detect where to apply the type-specific behavior. In previous work we have developed an effective rewrite system for specialization and optimization of generic programs. In this paper we extend it to also cover recursive data types. The key idea is to specialize traversal combinators using well-known recursion patterns, such as folds or paramorphisms. These are ruled by a rich set of algebraic laws that enable aggressive optimizations. We present a type-safe encoding of this rewrite system in Haskell, based on recent language extensions such as type-indexed type families.

Language: English

Type (Professor's evaluation): Scientific