Quels sont les principaux problèmes de complexité de calcul ouverts qui découlent des langages de programmation, en particulier l'analyse et la compilation de programmes? Je recherche des problèmes du type "la complexité temporelle de l'inférence de type Hindley-Milner" ou "la complexité temporelle de 0CFA" (bien que les deux soient des problèmes résolus).
17
Réponses:
Pippenger (1) de 1996 montre que (sous certaines hypothèses) les langages de programmation fonctionnels stricts (CBV) sont asympotiquement plus lents que les langages impératifs. Il est possible de savoir si le résultat de Pippenger peut être généralisé aux langages fonctionnels paresseux , comme cela a été souligné dans (2).
Pippenger impose deux hypothèses simplificatrices (calcul en ligne, et une certaine atomicité d'entrée). Il est possible de savoir s'ils peuvent être supprimés. Pippenger conjecture que cela peut être fait, mais prévient: "[u] ne tel résultat [...] semble bien au-delà de la portée des méthodes actuellement disponibles dans la théorie de la complexité computationnelle" .
Voir également la réponse de Campbell dans (3), et les notes de Ben-Amram (4).
1. N. Pippenger, Pure Versus Impure Lisp .
2. R. Bird, G. Jones, O. De Moor, Plus de hâte, moins de vitesse: évaluation paresseuse contre avide .
3. Débordement de pile, efficacité de la programmation purement fonctionnelle .
4. AM Ben-Amram, Notes sur la comparaison de Pippenger entre LISP pur et impur .
la source