Question:

"Certaines propriétés d'un langage de programmation peuvent nécessiter que le seul moyen d'obtenir l'exécution du code qui y est écrit soit par interprétation. En d'autres termes, la compilation en code machine natif d'un processeur traditionnel n'est pas possible. Quelles sont ces propriétés?"

Les compilateurs: principes et pratique par Parag H. Dave et Himanshu B. Dave (2 mai 2012)

Le livre ne donne aucune idée de la réponse. J'ai essayé de trouver la réponse sur les concepts de langages de programmation (SEBESTA), mais en vain. Les recherches sur le Web ont également été peu utiles. Avez-vous un indice?

La distinction entre code interprété et compilé est probablement une fiction, comme le souligne Raphaël dans ses commentaires :

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

Le fait est que le code est toujours interprété, par un logiciel, par le matériel ou par une combinaison des deux, et le processus de compilation ne peut pas dire lequel il sera.

Ce que vous percevez comme compilation est un processus de traduction d'une langue (pour la source) vers une autre langue (pour la cible). Et, l'interprète de est généralement différent de l'interprète pour .T S $S$$T$$S$$T$

Le programme compilé est traduit d’une forme syntaxique à une autre forme syntaxique , de sorte que, compte tenu de la sémantique voulue des langages et , et aient le même comportement informatique, jusqu’à un certain nombre de choses que vous essayez habituellement de faire. changer, éventuellement à optimiser, comme la complexité ou l'efficacité simple (temps, espace, surface, consommation d'énergie). J'essaie de ne pas parler d'équivalence fonctionnelle, car cela exigerait des définitions précises.P T S T P S P $P_S$$P_T$$S$$T$$P_S$$P_T$

Certains compilateurs ont été utilisés simplement pour réduire la taille du code, pas pour "améliorer" l'exécution. C'était le cas du langage utilisé dans le système Plato (bien qu'ils ne l'appelaient pas la compilation).

Vous pouvez envisager votre code entièrement compilé si, après le processus de compilation, vous ne avez plus besoin de l'interprète pour . Du moins, c’est la seule façon pour moi de lire votre question, en tant que question technique plutôt que théorique (puisque, en théorie, je peux toujours reconstruire l’interprète).$S$

Une chose qui peut poser problème, autant que je sache, est la méta-circularité . C'est à ce moment qu'un programme manipulera des structures syntaxiques dans son propre langage source , créant ainsi des fragments de programme qui seront ensuite interprétés comme s'ils faisaient partie du programme d'origine. Étant donné que vous pouvez produire des fragments de programme arbitraires dans le langage à la suite de calculs arbitraires manipulant des fragments syntaxiques sans signification, je suppose que vous pouvez rendre presque impossible (d’un point de vue technique) de compiler le programme dans le langage , de sorte que il génère maintenant des fragments de . Par conséquent, l’interprète de sera nécessaire, ou du moins le compilateur de àS T T S S T $S$$S$$T$$T$$S$$S$$T$ pour la compilation à la volée des fragments générés en (voir aussi ce document ).$S$

Mais je ne sais pas comment cela peut être formalisé correctement (et je n’ai pas le temps de le faire pour le moment). Et impossible est un gros mot pour un problème qui n’est pas formalisé.

Autres remarques

Ajouté après 36 heures. Vous voudrez peut-être éviter cette très longue suite.

Les nombreux commentaires sur cette question montrent deux points de vue sur le problème: un point de vue théorique qui le considère comme dépourvu de sens et un point de vue technique qui, malheureusement, n'est pas aussi facilement formalisé.

Il existe de nombreuses manières d’interpréter et de compiler, et j’essaierai d’en esquisser quelques-unes. Je vais essayer d'être aussi informel que possible

Le diagramme de pierre tombale

L'une des premières formalisations (du début des années 1960 à la fin de 1990) concerne les diagrammes en T ou de Tombstone . Ces diagrammes présentent sous forme d'éléments graphiques composables le langage d'implémentation de l'interpréteur ou du compilateur, le langage source interprété ou compilé et le langage cible dans le cas des compilateurs. Des versions plus élaborées peuvent ajouter des attributs. Ces représentations graphiques peuvent être considérées comme des axiomes, des règles d'inférence, utilisables pour dériver mécaniquement la génération de processeurs d'une preuve de leur existence à partir des axiomes, à la Curry-Howard (bien que je ne sois pas sûr que cela ait été fait dans les années soixante :).

Évaluation partielle

Le paradigme de l’ évaluation partielle est un autre point de vue intéressant . Je considère simplement les programmes comme une sorte d’implémentation de fonction qui calcule une réponse à partir de données d’entrée. Ensuite , un interprète pour la langue est un programme qui prend un programme écrit en et les données pour ce programme, et calcule le résultat en fonction de la sémantique de . L'évaluation partielle est une technique permettant de spécialiser un programme de deux arguments et , lorsqu'un seul argument, par exemple , est connu. L'intention est d'avoir une évaluation plus rapide lorsque vous obtenez enfin le deuxième argument S p S S d S a 1 a 2 a 1 a 2 a 2 a 1 a 1 a $I_S$$S$$p_S$$S$$d$$S$$a_1$$a_2$$a_1$$a_2$ . C'est particulièrement utile si change plus souvent que car le coût d'une évaluation partielle avec peut être amorti sur tous les calculs pour lesquels seul est en train de changer.$a_2$$a_1$$a_1$$a_2$

Il s'agit d'une situation fréquente dans la conception d'algorithmes (souvent le sujet du premier commentaire sur SE-CS), lorsqu'une partie plus statique des données est prétraitée, de sorte que le coût du prétraitement puisse être amorti sur toutes les applications. de l'algorithme avec des parties plus variables des données d'entrée.

C'est également la situation même des interprètes, car le premier argument est le programme à exécuter et est généralement exécuté plusieurs fois avec des données différentes (ou comporte des sous-parties exécutées plusieurs fois avec des données différentes). Il devient donc naturel de spécialiser un interprète pour une évaluation plus rapide d’un programme donné en l’évaluant partiellement comme argument principal. Cela peut être considéré comme un moyen de compiler le programme, et d'importants travaux de recherche ont été menés pour compiler par évaluation partielle un interprète de son premier argument (programme).

Le théorème de Smn

Le point positif de l'approche d'évaluation partielle est qu'elle prend ses racines dans la théorie (bien que la théorie puisse être un menteur), notamment dans le théorème Smn de Kleene . J'essaie ici de donner une présentation intuitive de celle-ci, en espérant que cela ne dérangera pas les théoriciens purs.

Étant donné une numérotation Gödel de fonctions récursives, vous pouvez afficher tant que votre matériel, de sorte que, étant donné le nombre Gödel (lire le code objet ) d’un programme, est la fonction définie par (calculée par le code objet votre matériel).φ p φ p$\varphi$$\varphi$$p$$\varphi_p$$p$

Dans sa forme la plus simple, le théorème est énoncé dans wikipedia comme suit (avec un léger changement de notation):

Étant donné une numérotation de Gödel de fonctions récursives, il existe une fonction récursive primitive de deux arguments avec la propriété suivante: pour chaque nombre de Gödel d’une fonction partiellement calculable avec deux arguments, les expressions et sont définis pour les mêmes combinaisons de nombres naturels et , et leurs valeurs sont égales pour toute combinaison de ce type. En d’autres termes, l’égalité d’extension suivante des fonctions est valable pour tout : $\varphi$$\sigma$$q$$f$$\varphi_{\sigma(q,x)}(y)$$f(x,y)$$x$$y$$x$$\;\;\varphi_{\sigma(q,x)} \simeq \lambda y.\varphi_q(x,y).\,$

Maintenant, en prenant comme interprète , comme code source d'un programme et comme donnée pour ce programme, nous pouvons écrire: $q$$I_S$$x$$p_S$$y$$d$$\;\;\varphi_{\sigma(I_S,p_S)} \simeq \lambda d.\varphi_{I_S}(p_S,d).\,$

$\varphi_{I_S}$ peut être considérée comme l'exécution de l'interprète sur le matériel, par exemple, comme une boîte noire prête à interpréter des programmes écrits en langage .$I_S$$S$

La fonction peut être vue comme une fonction spécialisée dans l'interpréteur pour le programme , comme dans l'évaluation partielle. Ainsi, le numéro de Gödel peut être vu avec un code objet qui est la version compilée du programme .$\sigma$$I_S$$P_S$$\sigma(I_S,p_S)$$p_S$

Ainsi, la fonction peut être vue comme une fonction prenant en argument le code source d'un programme écrit en langage et la version du code objet de ce programme Donc, est ce qu'on appelle habituellement un compilateur.$\;C_S = \lambda q_S.\sigma((I_S,q_S)$$q_S$$S$$C_S$

Quelques conclusions

Cependant, comme je l'ai dit: "la théorie peut être un menteur" ou semble en être un. Le problème est que nous ne savons rien de la fonction . Il existe en fait de nombreuses fonctions de ce type, et j’imagine que la démonstration du théorème peut utiliser une définition très simple, qui n’est peut-être pas meilleure, du point de vue de l’ingénierie, que la solution proposée par Raphael: regrouper simplement le théorème. le code source avec l'interpréteur . Cela peut toujours être fait pour que nous puissions dire: la compilation est toujours possible.$\sigma$I $q_S$$I_S$

Formaliser une notion plus restrictive de ce qu’est un compilateur nécessiterait une approche théorique plus subtile. Je ne sais pas ce qui a pu être fait dans cette direction. Le très réel travail effectué sur l’évaluation partielle est plus réaliste du point de vue de l’ingénierie. Et il y a bien sûr d'autres techniques pour écrire des compilateurs, notamment extraire des programmes de la preuve de leur spécification, développés dans le contexte de la théorie des types, basés sur l'isomorphisme de Curry-Howard (mais je sort de mon domaine de compétence) .

Mon but ici est de montrer que la remarque de Raphaël n'est pas "folle", mais un rappel sensé que les choses ne sont pas évidentes, ni même simples. Dire que quelque chose est impossible est une déclaration forte qui nécessite des définitions précises et une preuve, ne serait-ce que pour comprendre exactement comment et pourquoi c'est impossible . Mais construire une formalisation appropriée pour exprimer une telle preuve peut être assez difficile.

Cela dit, même si une fonctionnalité spécifique n'est pas compilable, au sens où l'entendent les ingénieurs, les techniques de compilation standard peuvent toujours être appliquées à des parties des programmes qui n'utilisent pas une telle fonctionnalité, comme le remarque la réponse de Gilles.

Pour faire suite aux remarques clés de Gilles selon lesquelles, en fonction de la langue, certaines actions peuvent être effectuées au moment de la compilation, tandis que d'autres doivent l'être au moment de l'exécution, ce qui nécessite un code spécifique. Nous pouvons donc voir que le concept de compilation est en réalité mal défini et n'est probablement pas définissable de manière satisfaisante. La compilation n'est qu'un processus d'optimisation, comme j'ai essayé de le montrer dans la section d' évaluation partielle , lorsque je l'ai comparé au prétraitement de données statiques dans certains algorithmes.

En tant que processus d'optimisation complexe, le concept de compilation appartient en réalité à un continuum. Selon les caractéristiques de la langue ou du programme, certaines informations peuvent être disponibles de manière statique et permettre une meilleure optimisation. D'autres choses doivent être reportées à l'exécution. Lorsque les choses vont vraiment mal, tout doit être fait au moment de l'exécution, au moins pour certaines parties du programme, et vous ne pouvez faire qu'encoder le code source avec l'interpréteur. Ce regroupement n’est donc que le bas de ce continuum de compilation. Une grande partie de la recherche sur les compilateurs consiste à trouver des moyens de faire de manière statique ce qui était fait de manière dynamique. La récupération de place au moment de la compilation semble un bon exemple.

Notez que dire que le processus de compilation devrait produire du code machine n’est pas une aide. C’est précisément ce que le groupement peut faire car l’interprète est un code machine (enfin, la compilation croisée peut compliquer un peu les choses).

La question n’est pas que la compilation soit impossible . Si une langue peut être interprétée¹, elle peut être compilée de manière triviale, en regroupant l'interprète avec le code source. La question est de savoir quelles caractéristiques linguistiques font de ce choix le seul moyen.

Un interpréteur est un programme qui prend le code source en entrée et qui se comporte comme spécifié par la sémantique de ce code source. Si un interprète est nécessaire, cela signifie que le langage comprend un moyen d'interpréter le code source. Cette fonctionnalité s'appelle eval. Si un interprète est requis dans le cadre de l'environnement d'exécution du langage, cela signifie que le langage comprend eval: soit il evalexiste sous forme de primitive, soit il peut être codé d'une manière ou d'une autre. Les langues connues sous le nom de langages de script incluent généralement une evalfonctionnalité, comme le font la plupart des dialectes Lisp .

Ce evaln'est pas parce qu'un langage inclut que la majeure partie ne peut être compilée en code natif. Par exemple, il existe des compilateurs Lisp optimisant, qui génèrent un bon code natif et qui supportent néanmoins eval; evalLe code peut être interprété ou peut être compilé à la volée.

evalest la fonctionnalité ultime besoins-un-interprète, mais il existe d'autres fonctionnalités qui nécessitent un interprète. Considérons quelques phases typiques d'un compilateur:

1. L'analyse
2. Vérification de type
3. Génération de code
4. Mise en relation

evalsignifie que toutes ces phases doivent être exécutées au moment de l'exécution. Il existe d'autres fonctionnalités qui rendent difficile la compilation native. En partant du bas, certains langages encouragent les liaisons tardives en fournissant des moyens permettant aux fonctions (méthodes, procédures, etc.) et aux variables (objets, références, etc.) de dépendre de modifications de code non locales. Cela rend difficile (mais pas impossible) la génération de code natif efficace: il est plus facile de conserver les références d'objet en tant qu'appels dans une machine virtuelle et de laisser le moteur de machine virtuelle gérer les liaisons à la volée.

De manière générale, la réflexion tend à rendre les langages difficiles à compiler en code natif. Une primitive eval est un cas extrême de réflexion; beaucoup de langues ne vont pas aussi loin, mais ont néanmoins une sémantique définie en termes de machine virtuelle, permettant par exemple au code de récupérer une classe par son nom, d'inspecter son héritage, de lister ses méthodes, d'appeler une méthode, etc. Java avec JVM et C # avec .NET sont deux exemples célèbres. Le moyen le plus simple d'implémenter ces langages est de les compiler en code octet , mais il existe néanmoins des compilateurs natifs (de nombreux juste à temps ) qui compilent au moins des fragments de programme qui n'utilisent pas de fonctions de réflexion avancées.

La vérification de type détermine si un programme est valide. Différentes langues ont des normes différentes quant au nombre d'analyses effectuées au moment de la compilation par rapport à l'exécution: une langue est dite "typée de manière statique" si elle effectue plusieurs vérifications avant de commencer à exécuter le code et "typée de manière dynamique" si ce n'est pas le cas. Certaines langues incluent une fonctionnalité de diffusion dynamique ou une fonctionnalité unmarshall-and-typecheck; ces fonctionnalités nécessitent l'intégration d'un vérificateur de type dans l'environnement d'exécution. Ceci est orthogonal aux exigences d'inclusion d'un générateur de code ou d'un interpréteur dans l'environnement d'exécution.

¹ _{Exercice: définissez un langage qui ne peut pas être interprété.}

Je pense que les auteurs supposent que la compilation signifie

• le programme source n'a pas besoin d'être présent au moment de l'exécution, et
• aucun compilateur ou interprète n'a besoin d'être présent au moment de l'exécution.

Voici quelques exemples de fonctionnalités qui le rendraient problématique, voire "impossible" pour un tel schéma:

1. Si vous pouvez interroger la valeur d'une variable au moment de l'exécution, en faisant référence à la variable par son nom (qui est une chaîne), vous aurez besoin du nom des variables lors de l'exécution.

2. Si vous pouvez appeler une fonction / procédure au moment de l'exécution, en y faisant référence par son nom (qui est une chaîne), vous aurez besoin du nom de la fonction / procédure au moment de l'exécution.

3. Si vous pouvez construire un morceau de programme au moment de l'exécution (sous forme de chaîne), par exemple en exécutant un autre programme ou en le lisant à partir d'une connexion réseau, etc., vous aurez alors besoin d'un interprète ou d'un compilateur au moment de l'exécution. lancez ce morceau de programme.

Lisp a les trois caractéristiques. Ainsi, les systèmes Lisp ont toujours un interpréteur chargé au moment de l'exécution. Les langages Java et C # ont des noms de fonction disponibles au moment de l'exécution et des tables pour rechercher leur signification. Des langages comme Basic et Python ont probablement aussi des noms de variables au moment de l'exécution. (Je ne suis pas sûr à 100% à ce sujet).

il est possible que les réponses actuelles "sur-pensent" la déclaration / réponses. peut-être que les auteurs font référence au phénomène suivant. beaucoup de langues ont un "eval" comme commande; Voir, par exemple, javascript eval et son comportement est généralement étudié comme une partie spéciale de la théorie de CS (par exemple, Lisp). la fonction de cette commande est d'évaluer la chaîne dans le contexte de la définition du langage. donc, en réalité, il ressemble à un "compilateur intégré". le compilateur ne peut pas connaître le contenu de la chaîne avant l'exécution. par conséquent, compiler le résultat de l'évaluation en code machine n'est pas possible au moment de la compilation.

D'autres réponses soulignent que la distinction entre les langages interprétés et compilés peut s'estomper considérablement dans de nombreux cas, en particulier avec des langages plus modernes, comme Java par exemple, avec un compilateur "juste à temps", également appelé "Hotspot" (les moteurs javascript, par exemple, V8 utilisent de plus en plus cette même technique). La fonctionnalité "eval-like" est certainement l'une d'entre elles.

LISP est un exemple terrible, car il a été conçu comme une sorte de langage "machine" de niveau supérieur servant de base à un "vrai" langage. Ce "vrai" langage ne s'est jamais matérialisé. Les machines LISP ont été construites sur l'idée de faire (une grande partie) du LISP en matériel. Comme un interprète LISP n’est qu’un programme, il est en principe possible de l’implémenter dans des circuits. Pas pratique, peut-être; mais loin d'être impossible.

De plus, il existe de nombreux interpréteurs programmés en silicium, généralement appelés "CPU". Et il est souvent utile d’interpréter les codes de machine (pas encore existants, pas à portée de main, ...). Par exemple, Linux 'x86_64 a été écrit et testé sur des émulateurs. Lorsque les puces sont arrivées sur le marché, la distribution était complète, même pour les premiers utilisateurs / testeurs. Java est souvent compilé en code JVM, qui est un interpréteur qui ne serait pas trop difficile à écrire en silicium.

La plupart des langages "interprétés" sont compilés dans un formulaire interne, qui est optimisé puis interprété. C'est par exemple ce que Perl et Python font. Il existe également des compilateurs pour les langages destinés à être interprétés, comme le shell Unix. Il est par contre possible d'interpréter des langages compilés de manière traditionnelle. Un exemple un peu extrême que j'ai vu est celui d'un éditeur qui interprétait C comme langage d'extension. C'est C pourrait fonctionner normal, mais simple, des programmes sans problèmes.

D'autre part, les CPU modernes prennent même l'entrée "langage machine" et la traduisent en instructions de niveau inférieur, qui sont ensuite réorganisées et optimisées (c'est-à-dire "compilées") avant d'être transférées pour exécution.

Toute cette distinction entre "compilateur" et "interprète" est vraiment discutable, quelque part dans la pile, il y a un interprète ultime qui prend le "code" et l'exécute "directement". L'entrée du programmeur subit des transformations le long de la ligne, celle qui s'appelle "compiler" ne fait que tracer une ligne arbitraire dans le sable.

La réalité est qu'il existe une grande différence entre l'interprétation d'un programme de base et l'exécution de l'assembleur. Et il existe des zones intermédiaires entre P-code / octet-code avec ou sans compilateurs (juste à temps). Je vais donc essayer de résumer certains points dans le contexte de cette réalité.

• Si la manière dont le code source est analysé dépend des conditions d'exécution, l'écriture d'un compilateur peut devenir impossible, ou tellement difficile que personne ne s'en souciera.

• Le code qui se modifie est dans le cas général impossible à compiler.

• Un programme qui utilise une fonction semblable à eval ne peut généralement pas être complètement compilé à l'avance (si vous considérez que la chaîne qui lui est transmise fait partie du programme), bien que, si vous exécutez le code de manière répétée, il se peut qu'il reste Il est utile que votre fonction de type eval appelle le compilateur. Certaines langues fournissent une API au compilateur pour rendre cela facile.

• La possibilité de faire référence à des choses par leur nom n’empêche pas la compilation, mais vous avez besoin de tableaux (comme mentionné). Appeler des fonctions par leur nom (comme IDispatch) nécessite beaucoup de travail de plomberie, au point que je pense que la plupart des gens conviendraient que nous parlons en réalité d'un interprète d'appel de fonction.

• Une frappe faible (quelle que soit votre définition) rend la compilation plus difficile et peut-être le résultat moins efficace, mais pas impossible, à moins que des valeurs différentes ne déclenchent des analyses différentes. Il y a une échelle mobile ici: si le compilateur ne peut pas déduire le type réel, il devra émettre des branches, des appels de fonction et des éléments qui n'existeraient pas autrement, incorporant effectivement des bits d'interpréteur dans l'exécutable.

Je présumerais que la caractéristique principale d'un langage de programmation qui rend un compilateur impossible (au sens strict, voir aussi auto-hébergement ) est la fonctionnalité d' auto-modification . Cela signifie que le langage permet de changer le code source pendant l'exécution (un compilateur générant, fixe et statique, le code objet ne peut pas le faire). Lisp est un exemple classique (voir aussi Homoiconicity ). Des fonctionnalités similaires sont fournies à l'aide d'une construction de langage telle que eval , incluse dans de nombreux langages (par exemple, javaScript). Eval appelle en fait l'interpréteur (en tant que fonction) au moment de l'exécution .

En d'autres termes, le langage peut représenter son propre méta-système (voir aussi Métaprogrammation )

Notez que la réflexion du langage , dans le sens de l'interrogation sur les méta-données d'un certain code source, et éventuellement la modification des méta-données uniquement (sth comme le mécanisme de réflexion de Java ou de PHP) ne pose pas de problème pour un compilateur, puisqu'il en possède déjà méta-données au moment de la compilation et peuvent les mettre à la disposition du programme compilé, si nécessaire, si nécessaire.

Une autre caractéristique qui rend la compilation difficile ou pas la meilleure option (mais pas impossible) est le schéma de typage utilisé dans la langue (par exemple, typage dynamique contre typage statique et typage fort contre typage en vrac). Cela rend difficile pour le compilateur d’avoir toute la sémantique au moment de la compilation, aussi une partie du compilateur (en d’autres termes, un interprète) devient-elle une partie du code généré qui gère la sémantique au moment de l’ exécution . En d’autres termes, ce n’est pas une compilation mais une interprétation .

Je pense que la question initiale n'est pas bien formée. Les auteurs de la question ont peut-être eu l’intention de poser une question quelque peu différente: quelles propriétés d’un langage de programmation facilitent l’écriture d’un compilateur?

Par exemple, il est plus facile d'écrire un compilateur pour un langage sans contexte qu'un langage sensible au contexte. La grammaire qui définit une langue peut également présenter des problèmes de compilation, tels que des ambiguïtés. De tels problèmes peuvent être résolus mais nécessitent un effort supplémentaire. De même, les langages définis par des grammaires non restreintes sont plus difficiles à analyser que les langages contextuels (voir Hiérarchie de Chomsky ). À ma connaissance, les langages de programmation procéduraux les plus utilisés sont quasiment dépourvus de contexte, mais comportent quelques éléments sensibles au contexte, ce qui les rend relativement faciles à compiler.

La question a une réponse correcte si évidente qu'elle est généralement négligée. Mais cela compte dans de nombreux contextes et constitue la principale raison pour laquelle les langages interprétés existent:

Compiler le code source en code machine est impossible si vous ne possédez pas encore le code source.

Les interprètes ajoutent de la flexibilité, et en particulier de la possibilité d'exécuter du code qui n'était pas disponible lors de la compilation du projet sous-jacent.