Modèles de coût pour les analyses de complexité des langages de programmation d'ordre supérieur – COCA_HOLA

Le projet COCA HOLA a pour but d'analyser la complexité des calculs d'ordre supérieur, c'est-à-dire ceux dont les entrés et les sorties sont des programmes plutôt que des nombres, des mots, ou plus généralement des combinaisons de types de base. L'attention sera portée sur les langages de programmation dans leur ensemble plutôt que sur des programmes particuliers. L'objectif est de trouver des unités de mesure de temps et d'espace adéquates, que l'on appellera modèles de coût raisonnable. Le problème est délicat car l'évaluation des langages d'ordre supérieur est définie de façon abstraite, à l'aide d'opération dite de "haut niveau", et dont l'implémentation n'est pas spécifiée. Concrètement, on se propose d'analyser différents schémas d'implémentation en mesurant avec précision leur complexité calculatoire en termes d'opération de haut niveau, afin d'en développer éventuellement de plus efficaces. L'ambition du projet est d'obtenir une théorie des implémentations des langages d'ordre supérieur basée sur la complexité, avec des retombées à la fois théoriques et pratiques.

Le projet trouve ses racines dans de récents progrès en théorie des modèles de coût pour le lambda-calcul, notamment le modèle de calcul pour l'ordre supérieur, obtenus par l'investigateur principal et ses collaborateurs (inclus dans le projet).

COCA HOLA s'organise sur trois ans et autour des trois directions de travail, qui sont essentiellement:

1) étendre les résultats courants à des langages plus concrets;
2) explorer l'écart entre les résultats positifs et le résultats négatifs dans la littérature;
3) utiliser des idées issues de la logique lineaire pour étudier les modèles de coût pour l'espace, par rapport auxquelles il n'y a presque aucun résultat.