Existe-t-il une optimisation complète des compilateurs pour terminer les programmes?

Dans le livre d'Andrew W. Appel, Modern Compiler Implementation in ML , il dit au chapitre 17 que la théorie de la calculabilité montre qu'il sera toujours possible d'inventer de nouvelles transformations d'optimisation et procède pour prouver qu'un compilateur entièrement optimisé résoudra le problème d'arrêt: un programme Q qui ne produit aucune sortie et ne s'arrête jamais peut facilement être remplacé par sa représentation optimale, Opt (Q) , étant "L: goto L". Un compilateur entièrement optimisé peut donc résoudre le problème d'arrêt.

Ma question est donc la suivante: existe- t-il un compilateur entièrement optimisé pour terminer les programmes? Mes seules pensées sont les suivantes: même si un programme est garanti de se terminer, il peut toujours être arbitrairement complexe, et pour tout compilateur d'optimisation concret, C, on pourrait peut-être construire un programme qui prend C en entrée et produit en quelque sorte un programme pire que une sorte de cas d'angle.

En outre, quelles sont les implications de se limiter à mettre fin aux programmes?

computability compilers program-optimization Simon 'Reinstate Monica' Shine
la source

Il est même difficile de trouver la séquence d'instructions optimale pour un seul bloc de code sans aucun flux de contrôle. L' article sur la superoptimisation sur Wikipédia donne une bonne introduction (avec des citations.)

Wandering Logic

L'article de Wikipédia mentionne que la superoptimisation examine les séquences d'instructions sans boucle. Ne pas avoir de boucles, je suppose, est une autre façon de dire que cela se termine. En examinant brièvement les références disponibles, il semble possible mais extrêmement coûteux.

Simon 'Reinstate Monica' Shine

Quelle est la signification de «optimiser» ici? Durée d'exécution plus petite? Si oui, lesquels: pire des cas, cas moyen, tous les cas, certains cas, ...?

Raphael

Réponses:

Je suppose que vous êtes intéressé par l'optimisation de l'exécution. Comme je l'ai écrit dans mon commentaire, cela ne précise pas suffisamment l'objectif: une optimisation réduit-elle le temps d'exécution sur n'importe quelle entrée, chaque entrée, toutes les entrées du pire des cas ou même en moyenne ?

Je montrerai que tous sont impossibles. La preuve s'étend à l'optimisation de la durée du programme.

Rappelez-vous que le problème suivant n'est pas calculable:

Étant donné une grammaire sans contexte avec un alphabet terminal , décider si $G$ $\Sigma$ $\mathcal{L}(G) = \Sigma^*$ .

Notez en outre que, étant donné une grammaire sans contexte , nous pouvons coder en dur, disons, l'algorithme CYK pour cette grammaire; désigner cet algorithme en . On observe que termine pour toutes les entrées (à partir de ). $G$ $\mathrm{CYK}_G$ $\mathrm{CYK}_G$ $\Sigma^*$

Supposons maintenant qu'il existe un optimiseur qui, étant donné un algorithme toujours terminé , génère un algorithme équivalent au résultat qui est optimal par rapport à l'exécution. Clairement, $\operatorname{Opt}$ $A$

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'} \iff \mathcal{L}(G) = \Sigma^*$

et nous avons donc construit un décideur pour un problème non calculable, contredisant l'hypothèse.

Raphael
la source

Merci pour cet argument. Quelques questions de clarification: Qu'est-ce que

? Je suppose que

est le langage engendré par la grammaire

Σ *

$\Sigma*$

L (G)

$\mathcal{L}(G)$

G

$G$

Simon 'Reinstate Monica' Shine

@Simon:

est l'ensemble de tous les mots. Raphael: Belle preuve. En fait, vous n'avez pas besoin de grammaires sans contexte; à la place, étant donné une machine de Turing

vous pouvez créer un programme

qui simule

pour

étapes et renvoie vrai si la machine atteint un état d'acceptation. Alors

serait

ne s'arrête pas.

Σ^{*}

$\Sigma^{\ast}$

M

$M$

P_{M} (i)

$\mathrm{P}_M(i)$

M

$M$

i

$i$

OPT (P_{M})

$\operatorname{OPT}(\mathrm{P}_M)$

' r e t u r n f a l s e;'

$\text{'}\mathtt{return\ false;}\text{'}$

M

$M$

sdcvvc