09/11/2000: Peter Selinger, Stanford University
Control categories and the lambda-mu calculus

Résumé

I will describe a class of categorical models for functional programming languages with control operators, and specifically for Parigot's lambda mu calculus. The beauty of these models is that they generalize the well-known correspondence between the simply-typed lambda calculus and cartesian-closed categories. I will introduce the class of "control categories", which is based on Power and Robinson's premonoidal categories. I will show that the call-by-name lambda mu calculus forms an internal language for these categories. Moreover, the call-by-value lambda mu calculus forms an internal language for the dual co-control categories. As a consequence, one obtains a syntactic, isomorphic translation between call-by-name and call-by-value which preserves the operational semantics, answering a question of Streicher and Reus. This result makes precise the intuitive duality between data-driven and demand-driven computation.