Évaluateur méta-circulaire

En informatique , un évaluateur méta-circulaire ( MCE ) ou un interprète méta-circulaire ( MCI ) est un interprète qui définit chaque caractéristique du langage interprété en utilisant une fonctionnalité similaire du langage hôte de l’interprète. Par exemple, l’interprétation d’une application lambda peut être mise en œuvre à l’aide de la fonction application. ^[1] L’évaluation méta-circulaire est la plus importante dans le contexte de Lisp . ^[1] Un auto-interprète est un interprète méta-circulaire où la langue interprétée est presque identique à la langue d’accueil ; les deux termes sont souvent utilisés comme synonymes. ^[2]

Histoire

La thèse de Corrado Böhm ^[3] décrit la conception d’un compilateur auto-hébergé . ^[4] En raison de la difficulté de compiler des fonctions d’ordre supérieur , de nombreux langages ont été définis à la place via des interpréteurs, principalement Lisp. ^{[1] [5]} Le terme lui-même a été inventé par John C. Reynolds , ^[1] et popularisé par son utilisation dans le livre Structure and Interpretation of Computer Programs . ^{[2] [6]}

Auto-interprètes

Un auto-interprète est un interprète méta-circulaire où la langue hôte est également la langue interprétée. ^[7] Un auto-interprète affiche une fonction universelle pour la langue en question et peut être utile pour apprendre certains aspects de la langue. ^[8] Un auto-interprète fournira une définition circulaire et Vide de la plupart des constructions de langage et fournira ainsi peu d’informations sur la sémantique du langage interprété, par exemple la stratégie d’évaluation . Aborder ces questions produit la notion plus générale d’un “interprète définitionnel”. ^[1]

Auto-interprétation dans tous les langages de programmation

Les langages de programmation fonctionnels totaux qui se normalisent fortement ne peuvent pas être complets de Turing , sinon on pourrait résoudre le problème d’arrêt en voyant si le type de programme vérifie. Cela signifie qu’il existe des fonctions calculables qui ne peuvent pas être définies dans le langage total. ^[9] En particulier il est impossible de définir un auto-interpréteur dans un langage de programmation total, par exemple dans aucun des calculs lambda typés comme le calcul lambda simplement typé , le Système F de Jean-Yves Girard , ou Thierry Coquand . s calcul des constructions . ^{[10] [11]}Ici, par “auto-interpréteur”, nous entendons un programme qui prend une représentation de terme source dans un format simple (comme une chaîne de caractères) et renvoie une représentation du terme normalisé correspondant. Ce résultat d’impossibilité ne vaut pas pour les autres définitions de “l’auto-interprète”. Par exemple, certains auteurs ont fait référence à des fonctions de type π τ → τ {displaystyle pi ,tau to tau } en tant qu’auto-interprètes, où π τ {displaystyle pi,tau } est le type de représentations de τ {displaystyletau} -termes typés. Pour éviter toute confusion, nous appellerons ces fonctions des auto-reconnaissances . Brown et Palsberg ont montré que les auto-reconnaissances pouvaient être définies dans plusieurs langages fortement normalisants, y compris le système F et le système F _ω . ^[12] Cela s’est avéré possible parce que les types de termes codés reflétés dans les types de leurs représentations empêchent de construire un argument diagonal. Dans leur article, Brown et Palsberg prétendent réfuter la « sagesse conventionnelle » selon laquelle l’auto-interprétation est impossible (et ils se réfèrent à Wikipédia comme un exemple de la sagesse conventionnelle), mais ce qu’ils réfutent en réalité, c’est l’impossibilité de se reconnaître soi-même, un notion distincte. Dans leur travail de suivi, ils recourent à la terminologie plus spécifique “auto-reconnaissance” utilisée ici, en les distinguant notamment des “auto-évaluateurs”, de type π τ → π τ {displaystyle pi ,tau to pi ,tau } . ^[13] Ils reconnaissent également que la mise en œuvre de l’auto-évaluation semble plus difficile que l’auto-reconnaissance, et laissent la mise en œuvre de la première dans un langage Fortement normalisant comme un problème ouvert.

Les usages

En combinaison avec une implémentation de langage existante, les interpréteurs méta-circulaires fournissent un système de base à partir duquel étendre un langage, soit vers le haut en ajoutant plus de fonctionnalités, soit vers le bas en compilant des fonctionnalités plutôt qu’en les interprétant. ^[14] Ils sont également utiles pour écrire des outils étroitement intégrés au langage de programmation, tels que des débogueurs sophistiqués. ^{[ citation nécessaire ]} Un langage conçu avec une implémentation méta-circulaire à l’esprit est souvent plus adapté à la construction de langages en général, même ceux qui sont complètement différents du langage hôte. ^{[ citation nécessaire ]}

Exemples

De nombreux langages ont une ou plusieurs implémentations méta-circulaires. Voici ci-dessous une liste partielle.

Quelques langages avec une implémentation méta-circulaire conçue de bas en haut, par ordre chronologique groupé :

• Lips , 1958
  • Régime , 1975
    • Pic , 1997 ^[15]
    • ActorScript , 2009 ?
  • Clojure , 2007
• Quatrième , 1968
  • PostScript , 1982
• Prologue , 1972
• TeX , basé sur du TeX vierge, 1978
• Petite conversation , 1980
• Rébol , 1997
  • Rouge , 2011
• Facteur , 2003

Quelques langages avec une implémentation méta-circulaire via des tiers :

• Java via Jikes RVM , Squawk , Maxine ou GraalVM’s Espresso
• Scala via Metascala
• JavaScript via Narcissus ou JS-Interpreter
• Oz via Glinda
• Python via PyPy
• Rubis via Rubinius
• Lua via Metalua

Voir également

• Expression M
• Homoiconicité
• Compilateur auto-hébergé

Références

1. ^ ^{un bcde Reynolds , John C.} (août 1972). “Interprètes définitionnels pour les langages de programmation d’ordre supérieur” (PDF) . Calcul d’ordre supérieur et symbolique . 11 (4): 363–397. doi : 10.1023/A:1010027404223 . S2CID 43352033 . Archivé de l’original (PDF) le 9 août 2017 . Récupéré le 14 avril 2017 .
2. ^ ^{un b} “L’Évaluateur Métacirculaire” . Structure et interprétation des programmes informatiques . MIT.
3. ^ C. Böhm, Calculatrices digitales. Du déchiffrage des formules logico-mathématiques par la machine même dans la conception du programme, Ann. Tapis. Pura Appl. (4) 37 (1954) 1-51
4. ^ Knuth, Donald E. ; Pardo, Luis Trabb (août 1976). Le développement précoce des langages de programmation . p. 36.
5. ^ McCarthy, John (1961). “Une fonction LISP universelle” (PDF) . Manuel du programmeur Lisp 1.5 . p. dix.
6. ^ Harvey, Brian. “Pourquoi la structure et l’interprétation des programmes informatiques sont importantes” . people.eecs.berkeley.edu . Récupéré le 14 avril 2017 .
7. ^ Braithwaite, Reginald (2006-11-22). “La signification de l’interprète méta-circulaire” . Récupéré le 22/01/2011 .
8. ^ Reynolds, John C. (1998). “Les interprètes définitionnels revisités” (PDF) . Calcul d’ordre supérieur et symbolique . 11 (4) : 356–7. doi : 10.1023/A:1010075320153 . S2CID 34126862 . Récupéré le 14 avril 2017 .
9. ^ Riolo, Rick; Worzel, William P.; Kotanchek, Mark (4 juin 2015). Théorie et pratique de la programmation génétique XII . Springer. p. 59. ISBN 978-3-319-16030-6. Récupéré le 8 septembre 2021 .
10. ^ Conor McBride (mai 2003), “en résiliation” (publié sur la liste de diffusion Haskell-Cafe).
11. ^ Andrej Bauer (juin 2014), Réponse à: Un langage total que seul un langage complet de Turing peut interpréter (publié sur le site Theoretical Computer Science StackExchange )
12. ^ Marron, Mat; Palsberg, Jens (11 janvier 2016). “Briser la barrière de normalisation: un auto-interprète pour f-omega” (PDF) . Actes du 43e Symposium annuel ACM SIGPLAN-SIGACT sur les principes des langages de programmation : 5–17. doi : 10.1145/2837614.2837623 . ISBN 9781450335492. S2CID 14781370 .
13. ^ Marron, Mat; Palsberg, Jens (janvier 2017). “Auto-évaluation typée via des fonctions de type intensionnel” . Actes du 44e Symposium ACM SIGPLAN sur les principes des langages de programmation : 415–428. doi : 10.1145/3009837.3009853 . ISBN 9781450346603.
14. ^ Oriol, Manuel; Meyer, Bertrand (2009-06-29). Objects, Components, Models and Patterns: 47th International Conference, TOOLS EUROPE 2009, Zurich, Suisse, 29 juin-3 juillet 2009, Actes . Springer Science et médias d’affaires. p. 330. ISBN 9783642025716. Récupéré le 14 avril 2017 .
15. ^ Implémentation méta-circulaire du langage de programmation Pico

Liens externes

• Structure et interprétation des programmes informatiques (SICP) , version en ligne du livre complet, consulté le 18/01/2009.
• Métascala