[Pl-seminar] Fritz Henglein at NU PRL: Monday 29 April 11:45am

[Matthias Felleisen]

FINAL ANNOUNCEMENT: The NU PRL seminar is pleased to host Fritz Henglein on MONDAY, 29 APRIL 2013 @ 11:45am in 366 WVH. 




The Quest for GAS: Genericity, Abstraction and Scalability---simultaneously

Fritz Henglein
Department of Computer Science, University of Copenhagen (DIKU)

Abstract:

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.  

Biography:

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).