home · mobile · calendar · colloquia · 2006-2007 · 

Colloquium - Siek

Knights' Tours, Religious Wars, and Built to Order BLAS
Department of Computer Science

Can a knight jump around a chess board touching every square exactly once? This can be reduced to a graph problem: find a Hamiltonian path. But can we easily implement a program to solve the Knight's tour using a software library of graph algorithms? We can, so long as the graph library is generic. Until recently, it was difficult to implement generic libraries because programming languages lacked the appropriate abstraction mechanisms. I present an extension to the C++ programming language, based on my PhD thesis, that provides language support for generic programming.

A classic religious war in programming languages is static versus dynamic type checking. Should type errors be caught during compilation or during program execution? I claim that static checking is better for some situations and dynamic checking is better in others. Towards verifying this claim, and to support programming using a mixture of static and dynamic checking, I developed a type system, called gradual typing, that seamlessly integrates the two in the same language.

Computational scientists stitch together the most expensive portions of their numeric codes using procedures from the Basic Linear Algebra Subprograms (BLAS). But in doing so they miss out on cross-procedure optimizations that reduce memory traffic. Including these optimizations would require a combinatorial explosion in the number of procedures provided by the BLAS. I present an alternative solution: a compiler specialized for linear algebra that "builds to order" high performance implementations of linear algebra kernels.

What is the thread that ties these themes together? The conventional wisdom in programming language design suggests there is tension between flexibility and safety and between abstraction and performance. A language can be flexible, like Python, or safe, like Standard ML. A language can provide abstractions, such as objects, or it can be high-performance and provide only low-level programming constructs. The overarching goal of my research is to learn the root causes of these tensions in language design and discover how to resolve them.

Jeremy Siek is a Visiting Assistant Professor in the Department of Computer Science at the University of Colorado Boulder and a Research Scientist at LogicBlox, Inc. His research interests are in programming languages, type systems, generic programming, and high-performance software libraries. Jeremy is the author of the Boost Graph Library, a member of the ANSI/ISO C++ Standards Committee, and one of the architects of the "concepts" extension planned for the next revision of the C++ Standard (C++200X). His publications have been cited over 500 times (per Google Scholar). Jeremy earned a PhD at Indiana University in 2005 and a BS and MS at the University of Notre Dame in 1997 and 1999 respectively.

Hosted by Amer Diwan.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)