Algebraic Specialization of Generic Functions for Recursive Types

• Tipo: Artigo em Revista Científica Internacional
• Data: 2011

Autores

Cunha, A (Autor) Outra; Pacheco, H (Autor) Outra

Revista

Título: Electronic Notes in Theoretical Computer Science

Vol. 229

Páginas: 57-74

ISSN: 1571-0661

Editora: Elsevier

Indexação

Scopus - 1 Citação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica