Ulrich Schöpp (LMU, Munich), On the Relation of Interaction Semantics to Continuations and Defunctionalization

Schedule

Abstract

In Game Semantics, the Geometry of Interaction and related approaches to programming language semantics, programs are modelled by interactive processes. Such interactive semantic models have been used in the design of new compilation methods, e.g. for hardware synthesis or for programming with sublinear space. This talk is about how such semantically motivated non-standard compilation methods relate to more standard techniques in the compilation of functional programming languages, namely continuation passing and defunctionalization. The interpretation of the lambda-calculus in a model of computation by interaction is related to a call-by-name CPS-translation followed by a defunctionalization procedure that takes into account control-flow information. I will describe the relation first for the linear lambda-calculus, then extend this to the simply-typed lambda-calculus and consider extensions, such as recursion.