27. august 2009

Artikel af Fritz Henglein nomineret til CACM research highlights

Fritz Hengleins artikel Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time som blev fremlagt på konferencen ICFP 2008, er af SIGPLAN, Special Interest Group for Programming Languages, blevet nomineret til CACM research highlights.

Artikler udvælges fra alle programmeringssprogskonferencer, som ACM (verdens førende datalogforening) sponsorerer. Der er samlet blevet nomineret 10 artikler i de seneste 3 år. SIGPLAN har således vurderet Fritz's arbejde til at være blandt de absolut mest signifikante, som er kommet frem inden for feltet i de sidste par år.

SIGPLANS indstilling lyder:

Everyone knows that sorting a collection of n elements requires a number of comparisons proportional to n log n. Distribution sort over certain kinds of data works in time linear in the number of elements, but is a "specialty" sort, useful only in special circumstances. After reading this paper, you may reverse this idea. Henglein shows how to generalize distribution sort to a wide range of data. Assuming a base type is suitable for distribution sort, he shows how products, sums, and lists of such data are also suitable for distribution sort, relegating n log n sorts to the "specialty" case. Henglein argues convincingly that the right interface for an abstract data type to supply is not comparison and not sorting, but a mild generalization of sorting which he calls a discriminator, in terms of which the other two may be defined. While the technique may be applied in any programming language, it fits particularly well with a functional language where it is easy to compose sort operators on component types to build sort operators on structures, and where advanced type systems allow one to ensure type safety while doing so. Henglein presents complete code in Haskell. We should expect the technique to spread to other languages; the new notion of C++ concepts, which resemble Haskell type classes, are well suited for supporting defining functions based on type structure. The paper is a joy to read.

Læs mere om

SIGPLAN is a Special Interest Group of ACM that focuses on Programming Languages. In particular, SIGPLAN explores the design, implementation, theory, and efficient use of programming languages and associated tools. Its members are programming language users, developers, implementers, theoreticians, researchers and educators.