FP /


Efficient Generic Libraries

(added 081103)

New development: a related paper has been published: http://portal.acm.org/citation.cfm?id=1706366


Programs which work uniformly over many different datastructures (such as lists, database tables, family trees) are called generic programs. Examples: traversing a datastructure to perform the same transformation on all parts, printing, parsing, compressing or decompressing datastructures, comparing two structures for equality, etc. Generics extend the power of polymorphism to allow classes of related algorithms to be described in one definition. Thus generic programs are very well suited for building program libraries.

Currently, Haskell is the language with the best support for generic programming but C++ is the language which has the most efficient generic libraries.

Project goal

Set up an open benchmark of generic algorithms (based on the GP Benchmark) with realistic test data and use this to investigate what can be improved to obtain better run-time behaviour. Preliminary investigation (by Patrik Jansson) indicates that the main source of inefficiency in some of the Haskell libraries is the run-time passing of dictionaries. Applying rewrite rules and specialisation techniques to the compilation of generic programs should result in optimised code as good as (or better) than hand-written instances.

FP (Haskell), Algorithms, Programming Paradigms (or Programming Languages), Software Constraints (or Types for Programs and Proofs)