[Pl-seminar] preliminary announcement -- Fritz Henglein at NUPRL
matthias at ccs.neu.edu
Wed Apr 24 20:58:15 EDT 2013
The NUPRL seminar is pleased to host Fritz Henglein on MONDAY, 29 APRIL 2013 @ 11:45am in 366 WVH. [Warning: the time is tentative. Please watch for the final announcement.]
The Quest for GAS:
Genericity, Abstraction and Scalability---simultaneously
Department of Computer Science, University of Copenhagen (DIKU)
In this talk we investigate the fundamental problems of sorting and partitioning, identify an apparent trade-off between scalability (performance) and data abstraction, and discuss which side present programming languages seem to favor.
The trade-off is not inherent, however. We exhibit a functional abstraction we call discriminators that achieves full abstraction and asymptotically optimal (worst-case linear-time) performance for user-specifiable orders (for sorting) and equivalences (for partitioning)---simultaneously. This even holds for sorting/partitioning complex data such as trees, multisets, sets and arbitrarily nested combinations. This suggests that built-in and abstract data types with observable equality or ordering should come equipped with discriminators instead of (just) binary comparison functions or hash functions.
Fritz Henglein is professor of programming languages and systems at DIKU, the Department of Computer Science at the University of Copenhagen. His research interests are in semantic, logical and algorithmic aspects of programming languages, specifically type inference, type-based program analysis, algorithmic functional programming and domain-specific languages; and the application of programming language technology, presently in enterprise systems (3gERP.org), health care processes (trustcare.eu) and finance (hiperfit.dk).
More information about the pl-seminar