Cost models for complexity analyses of higher-order programming languages – COCA_HOLA

The COCA HOLA project aims at developping complexity analyses of higher-order computations, i.e. that approach to computation where the inputs and outputs of a program are not simply numbers, strings, or compound datatypes but programs themselves. The focus is not on algorithms, i.e. fixed programs, but on whole programming languages. The problem is the identification of adequate units of measurement for time and space, i.e. what are called reasonable cost models. The problem is non-trivial because the evaluation of higher-order languages is defined abstractly, via high-level operations, leaving the implementation unspecified. Concretely, the project will analyse different implementation schemas, measuring precisely their computational complexity with respect to the number of high-level operations, and eventually develop more efficient new ones. The goal is to obtain a complexity-aware theory of implementations of higher-order languages with both theoretical and practical downfalls.

The projects stems from recent advances on the theory of time cost models for the lambda-calculus, the computational model behind the higher-order approach, obtained by the principal investigator and his collaborators (who are included in the project).

COCA HOLA will span over three years and it is organized around three work packages, essentially:

1) extending the current results to encompass realistic languages;
2) explore the gap between the positive and negative results in the literature;
3) use ideas from linear logic to explore space cost models, about which almost nothing is known.