Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/14888
Título: | Algebraic specialization of generic functions for recursive types |
Autor(es): | Cunha, Alcino Pacheco, Hugo |
Palavras-chave: | Generic programming Recursion patterns Rewrite systems Specialization Type families |
Data: | 8-Mar-2011 |
Editora: | Elsevier |
Revista: | Electronic Notes in Theoretical Computer Science |
Citação: | Cunha, A., & Pacheco, H. (2011, March). Algebraic Specialization of Generic Functions for Recursive Types. Electronic Notes in Theoretical Computer Science. Elsevier BV. http://doi.org/10.1016/j.entcs.2011.02.016 |
Resumo(s): | 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. |
Tipo: | Artigo |
URI: | https://hdl.handle.net/1822/14888 |
DOI: | 10.1016/j.entcs.2011.02.016 |
ISSN: | 1571-0661 |
Versão da editora: | http://dx.doi.org/10.1016/j.entcs.2011.02.016 |
Arbitragem científica: | yes |
Acesso: | Acesso aberto |
Aparece nas coleções: | DI/CCTC - Artigos (papers) |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
msfp08.pdf | 522,2 kB | Adobe PDF | Ver/Abrir |