Section: Highlights of the Year

Highlights of the Year

The paper [21] published at the International Conference on Functional Programming (ICFP 2015) has given a positive answer to an open problem, conjectured to be true for a long time: the question is to know whether inductive and coinductive data types can be added to light logic based systems without breaking the complexity of the system (i.e. staying within the class of polynomial time computable functions). This issue is analog to the issue of adding inductive and coinductive data types to system F without breaking normalization, which is known to hold for a long time. To tackle this challenging question, we have studied the problem of defining algebras and coalgebras in the Light Affine Lambda Calculus, a system characterizing the complexity class FPTIME. In this system, the principle of stratification limits the ways we can use parametric polymorphism, and in general the way we can write our programs. We have shown that while stratification poses some issues to the standard System F encodings, it still permits to encode some weak form of algebra and coalgebra. Using the algebra encoding one can define in the Light Affine Lambda Calculus the traditional inductive types. Unfortunately, the corresponding coalgebra encoding permits only a very limited form of coinductive data types. To extend this class, we have studied an extension of the Light Affine Lambda Calculus by distributive laws for the modality $\S$.

Awards

Hugo Férée has received the Ackermann award for his PhD thesis “complexité d'ordre supérieur et analyse récursive”.