EfficientGenericLibraries

Efficient Generic Libraries

(added 081103)

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

Background:

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.

Study this comparison of gen.prg.libraries in Haskell
Learn more about the GP Benchmark
Improve the benchmark
Identify bottlenecks:
- Why is Scrap Your Boilerplate (SYB) so inefficient compared to other generic programming libraries in Haskell?
Possibly remove some of them
Write it up as a technical report (perhaps aim for sending it to the workshop on generic programming 2009?).

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

EfficientGenericLibraries