Extending Implicit Computational Complexity and Abstract Machines to Languages with Control

Giulio Pellitta 1, 2
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Résumé : L'isomorphisme de Curry-Howard est l'idée que les preuves en déduction naturelle peuvent être mises en correspondance avec lambda-termes de telle manière que cette correspondance est préservée par la normalisation. Le concept peut être étendu à partir intuitionniste Logique à d'autres systèmes, tels que la logique linéaire. Une des belles conséquences de cet isomorphisme est que nous pouvons raisonner sur des programmes fonctionnels avec des outils formels qui sont typiques des systèmes de preuve: une telle analyse peut également inclure qualités quantitatives de programmes, tels que le nombre d'étapes nécessaires pour la terminaison. Un autre est la possibilité de décrire l'exécution de ces programmes en termes de machines abstraites.En 1990, Griffin a prouvé que la correspondance peut être étendue à des opérateurs logiques et de contrôle classiques. Ce est à dire, la logique classique ajoute la possibilité de manipuler des continuations. Dans cette thèse, nous voyons comment les choses que nous décrites ci-dessus travail dans ce contexte plus large.
Type de document :
Thèse
Programming Languages [cs.PL]. Università di Bologna, 2014. English
Liste complète des métadonnées

Littérature citée [171 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01090624
Contributeur : Giulio Pellitta <>
Soumis le : mercredi 3 décembre 2014 - 18:31:27
Dernière modification le : jeudi 11 janvier 2018 - 16:31:49
Document(s) archivé(s) le : lundi 9 mars 2015 - 05:52:59

Fichier

Identifiants

  • HAL Id : tel-01090624, version 1

Collections

Citation

Giulio Pellitta. Extending Implicit Computational Complexity and Abstract Machines to Languages with Control. Programming Languages [cs.PL]. Università di Bologna, 2014. English. 〈tel-01090624〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

129