- Ulrich Schoepp (LMU Munich)
Computation by Interaction for Structuring Resource Bounded Computation
ABSTRACT: Implicit computational complexity studies the characterisation of complexity classes without reference to machine models. The focus has therefore often been on the complexity aspects of high-level languages, e.g. higher-order functional languages. Here I will argue that the study of the structure and complexity aspects of low-level languages can also be of interest. While low-level languages, such as machine code or compiler intermediate languages, are often considered mere implementation devices, there has been increasing interest in their mathematical structure. The aim is to study the low-level structure used in the implementation of high-level languages and to consider the complexity implications of the various constructions used therein. In this talk I will consider computation by interaction as an example of an approach to organising and structuring resource bounded low-level computation. I will consider its role in the characterisation of space complexity classes as well as connections to low-level languages and compilation techniques.
- Neelakantan R. Krishnaswami (MPI)
Implicit Complexity for Functional Reactive Programs
ABSTRACT: Interactive programs, such as graphical user interfaces, have long been very challenging programs to write and to verify, relying as they do on intricate combinations of continuation-passing style, higher-order store, and concurrency. Functional reactive programming is a proposal (now over 15 years old) to simplify these programs by modelling interactive systems as synchronous stream transducers. The idea is that programs written in this style can be structured using familiar higher-order functionals such as maps and unfolds, and understood using the simple equational theory of functional programming. However, while FRP offers an elegant extensional view of reactive programs, intensional problems have slowed its uptake. Namely, FRP implementations are notorious for unexpected deadlocks and unwanted memory leaks. In this talk, we will see how some ideas from implicit complexity can solve these problems, giving a language that has both a simple semantic model and an efficient implementation.