Calcul des constructions

Carte Commune · n° 355539

Le calcul des constructions (CoC de l'anglais calculus of constructions) est un lambda-calcul typé d'ordre supérieur dans lequel les types sont des valeurs de première classe. Il est par conséquent possible, dans le CoC, de définir des fonctions qui vont des entiers vers les entiers, mais aussi des entiers vers les types, des types vers les entiers ou des types vers les types. Le CoC est fortement normalisant, bien que, d'après le théorème d'incomplétude de Gödel, il soit impossible de démontrer cette propriété dans le CoC lui-même, puisqu'elle implique sa cohérence. Le CoC a été développé initialement par Thierry Coquand. Le CoC a été à l'origine des premières versions de l'assistant de preuves Rocq. Les versions suivantes, ainsi que dans l'assistant de preuve Lean, ont été construites à partir du calcul des constructions inductives qui est une extension du CoC qui intègre des types de données inductives. Dans le CoC originel, les types de données inductives devaient être émulés via un...

Lire sur Wikipédia