Quels sont les défis liés à la saisie dans l'écriture d'un compilateur pour un langage typé dynamiquement?

Dans cette conférence , Guido van Rossum parle (27:30) de tentatives d'écriture d'un compilateur pour le code Python, commentant en disant:

s'avère qu'il n'est pas si facile d'écrire un compilateur qui conserve toutes les belles propriétés de frappe dynamique et maintient également l'exactitude sémantique de votre programme, de sorte qu'il fait en fait la même chose, peu importe le genre de bizarrerie que vous faites quelque part sous les couvertures et s'exécute réellement plus vite

Quels sont les défis (possibles) liés à la saisie en écriture d'un compilateur pour un langage typé dynamiquement comme Python?

Vous avez simplifié la déclaration de Guido en formulant votre question. Le problème n'est pas d'écrire un compilateur pour un langage à typage dynamique. Le problème est d'en écrire un qui est (critère 1) toujours correct, (critère 2) conserve un typage dynamique et (critère 3) est sensiblement plus rapide pour une quantité significative de code.

Il est facile d'implémenter 90% (critère 1 en échec) de Python et d'être toujours rapide. De même, il est facile de créer une variante Python plus rapide avec un typage statique (échec du critère 2). La mise en œuvre à 100% est également facile (dans la mesure où la mise en œuvre d'un langage aussi complexe est facile), mais jusqu'à présent, chaque moyen facile de le mettre en œuvre s'avère relativement lent (critère 3 défaillant).

L'implémentation d'un interpréteur plus JIT qui est correct, implémente l'intégralité du langage et est plus rapide pour certains codes s'avère réalisable, bien que beaucoup plus difficile (cf. PyPy) et seulement si vous automatisez la création du compilateur JIT (Psyco s'en est débarrassé) , mais était très limité dans quel code il pouvait accélérer). Mais notez que cela est explicitement hors de portée, car nous parlons de statique(aka à l'avance) des compilateurs. Je mentionne seulement cela pour expliquer pourquoi son approche ne fonctionne pas pour les compilateurs statiques (ou du moins il n'y a pas de contre-exemple existant): il doit d'abord interpréter et observer le programme, puis générer du code pour une itération spécifique d'une boucle (ou un autre code linéaire chemin), puis optimisez l'enfer à partir de cela sur la base d'hypothèses uniquement vraies pour cette itération spécifique (ou du moins, pas pour toutes les itérations possibles). L'attente est que de nombreuses exécutions ultérieures de ce code correspondront également à l'attente et bénéficieront ainsi des optimisations. Certains contrôles (relativement bon marché) sont ajoutés pour garantir l'exactitude. Pour faire tout cela, vous avez besoin d'une idée de ce pour quoi vous spécialiser et d'une implémentation lente mais générale. Les compilateurs AOT n'ont ni l'un ni l'autre. Ils ne peuvent pas du tout se spécialiserbasé sur du code qu'ils ne peuvent pas voir (par exemple du code chargé dynamiquement), et se spécialiser négligemment signifie générer plus de code, ce qui pose un certain nombre de problèmes (utilisation d'icache, taille binaire, temps de compilation, branches supplémentaires).

L'implémentation d'un compilateur AOT qui implémente correctement l' ensemble du langage est également relativement facile: Générez du code qui appelle dans le runtime pour faire ce que l'interprète ferait lorsqu'il serait alimenté avec ce code. Nuitka fait (principalement) cela. Cependant, cela ne donne pas beaucoup d'avantages en termes de performances (critère 3 en échec), car vous devez toujours faire autant de travail inutile qu'un interprète, à l'exception de l'envoi du bytecode au bloc de code C qui fait ce que vous avez compilé. Mais ce n'est qu'un coût assez faible - suffisamment important pour être optimisé dans un interpréteur existant, mais pas assez important pour justifier une toute nouvelle implémentation avec ses propres problèmes.

Que faudrait-il pour remplir les trois critères? Nous n'en avons aucune idée. Il existe des schémas d'analyse statique qui peuvent extraire des informations sur les types concrets, le flux de contrôle, etc. à partir des programmes Python. Ceux qui fournissent des données précises au-delà de la portée d'un seul bloc de base sont extrêmement lents et doivent voir l'ensemble du programme, ou du moins la plupart. Pourtant, vous ne pouvez pas faire grand-chose avec ces informations, à part peut-être optimiser quelques opérations sur les types intégrés.

Pourquoi ça? Pour le dire franchement, un compilateur supprime la possibilité d'exécuter du code Python chargé au moment de l'exécution (échec du critère 1), ou il ne fait aucune hypothèse qui puisse être invalidée par n'importe quel code Python. Malheureusement, cela inclut à peu près tout ce qui est utile pour optimiser les programmes: les globaux, y compris les fonctions, peuvent être rebondis, les classes peuvent être mutées ou remplacées entièrement, les modules peuvent également être modifiés arbitrairement, l'importation peut être détournée de plusieurs façons, etc. Une seule chaîne transmise à eval, exec, __import__ou de nombreuses autres fonctions, peuvent faire tout cela. En effet, cela signifie quasiment aucune optimisation importante ne peut être appliquée, ce qui donne peu d'avantages en termes de performances (critère 3 en échec). Revenons au paragraphe ci-dessus.

Le problème le plus difficile est de déterminer de quel type tout est doté à un moment donné.

Dans un langage statique comme C ou Java, une fois que vous avez vu la déclaration de type, vous savez ce qu'est cet objet et ce qu'il peut faire. Si une variable est déclarée int, c'est un entier. Ce n'est pas, par exemple, une référence de fonction appelable.

En Python, ça peut l'être. C'est horrible Python, mais légal:

i = 2
x = 3 + i

def prn(s):
    print(s)

i = prn
i(x)

Maintenant, cet exemple est assez stupide, mais il illustre l'idée générale.

Plus réaliste, vous pouvez remplacer une fonction intégrée par une fonction définie par l'utilisateur qui fait quelque chose de légèrement différent (comme une version qui enregistre ses arguments lorsque vous l'appelez).

PyPy utilise la compilation Just-In-Time après avoir regardé ce que fait réellement le code, ce qui permet à PyPy d'accélérer beaucoup les choses. PyPy peut regarder une boucle et vérifier que chaque fois que la boucle s'exécute, la variable fooest toujours un entier; PyPy peut alors optimiser le code qui recherche le type de foochaque passage dans la boucle, et peut même souvent se débarrasser de l'objet Python qui représente un entier, et foopeut simplement devenir un nombre assis dans un registre sur le CPU. C'est ainsi que PyPy peut être plus rapide que CPython; CPython effectue la recherche de type aussi rapidement que possible, mais même pas la recherche est encore plus rapide.

Je ne connais pas les détails, mais je me souviens qu'il y avait un projet appelé Unladen Swallow qui essayait d'appliquer la technologie du compilateur statique pour accélérer Python (en utilisant LLVM). Vous voudrez peut-être rechercher Google Unladen Swallow et voir si vous pouvez trouver une discussion sur les raisons pour lesquelles cela n'a pas fonctionné comme ils l'espéraient.

Comme le dit l'autre réponse, le problème clé est de déterminer les informations de type. Dans la mesure où vous pouvez le faire statiquement, vous pouvez générer directement un bon code.

Mais même si vous ne pouvez pas le faire statiquement, vous pouvez toujours générer du code raisonnable, juste au moment de l'exécution, lorsque vous obtenez des informations de type réelles . Ces informations s'avèrent souvent stables, ou ont au plus quelques valeurs différentes pour une entité particulière à un point de code particulier. Le langage de programmation SELF a lancé de nombreuses idées de collecte agressive de types d'exécution et de génération de code d'exécution. Ses idées sont largement utilisées dans les compilateurs modernes basés sur JIT comme Java et C #.