Programação genérica usando o sistema CT

Abstract

The last decade has seen a number of approaches to datatype-generic programming: PolyP, Scrap Your Boilerplate, Derivable Type-Classes, Generic Haskell, Generics for the Masses, etc. The approaches vary in sophistication and target audience: some propose fullblown programming languages, others suggestlibraries. Most of these approaches uses a structural representation of the definition of an algebraic data type, with generic functions defined over this structural representation and automatically instantiated for data types defined in the program. In this case, instances of a generic function for different types are overloaded. SYB adopts a different approach, by defining a library of generic combinators for the traversal of values of complex data types. These generic functions can be used to define functions that operate on specific components of these complex types, avoiding the boilerplate code involved on the traversal of the structureof values of these types.This work presents a summary of the various approaches for generic programming in Haskell and compares the most relevant ones. Based on this analysis, we propose an approach for generic programming in a language similar to Haskell, but based on System CT. System CT extends the Damas-Milner type system with support for overloading, without the need for type class declarations, as inHaskell. As part of this work, a compiler for the language Haskell-CT has been implemented, by integrated system CT's front-end with the back-end of Haskell's compiler GHC. Two fundamental extensions to System CT are identified in order to provide support for generic programming: high order polymorphism and thedefinition of specialized poli rphic functions. This last extension is based on the ideia of overlapped definitions for a function.