Мета тілміштер мен өзін-өзі түсіндіретін бағдарламалар
Meta-circular evaluator
Мета-циркулярлық бағалаушы (MCE) – түсіндіргіш тілдің мүмкіндіктерін хост тілі арқылы анықтайтын интерпретатор. Lisp-те жиі қолданылады, өзін-өзі түсіндіретін компиляторлармен байланысты.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік есепте мета айналымды бағалаушы (MCE) немесе мета айналымды интерпретатор (MCI) – интерпретатордың өз тіліндегі ұқсас мүмкіндіктерді пайдаланып, интерпретацияланатын тілдің әрбір мүмкіндігін анықтайтын интерпретатор. Мысалы, лямбда-қосымшаны интерпретациялау функция қосымшасын пайдалану арқылы іске асырылуы мүмкін. Мета айналымды бағалау ең көбінесе Lisp тілінің контекстінде кездеседі. Өз-интерпретатор – интерпретацияланатын тіл үй тіліне жақын болғандағы мета айналымды интерпретатор; екі термин көбінесе синоним ретінде қолданылады. Өздігінен жұмыс істейтін компилятордың құрылымын сипаттайды. Жоғары ретті функцияларды компиляциялаудың қиындығына байланысты көптеген тілдер интерпретаторлар арқылы анықталды, ең бастысы – Lisp. Бұл терминнің авторы Джон К. Рейнольдс.
In computing, a meta circular evaluator (MCE) or meta circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta circular evaluation is most prominent in the context of Lisp. A self interpreter is a meta circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously. describes the design of a self hosting compiler. Due to the difficulty of compiling higher order functions, many languages were instead defined via interpreters, most prominently Lisp. The term itself was coined by John C. Reynolds,
Жалпы бағдарламалау тілдеріндегі өзіндік интерпретация
Толық функционалдық бағдарламалау тілдері, қатаң нормалданатын тілдер, Тьюринг толықтығына ие бола алмайды, әйтпесе бағдарламаның типі тексеріліп, тоқтату мәселесін шешуге болар еді. Бұл, есептеуге болатын кейбір функцияларды осы толық тілде анықтау мүмкін емес дегенді білдіреді. Атап айтқанда, толық бағдарламалау тілінде өзіндік интерпретаторды анықтау мүмкін емес, мысалы, қарапайым типтелген лямбда есептеуі, Жан-Ив Жирардың F жүйесі немесе Тьерри Кокванның конструкциялар есептеуі сияқты типтелген лямбда есептеулерінің кез келгенінде. Мұнда «өзіндік интерпретатор» дегеніміз – бастапқы терминнің белгілі бір қарапайым форматтағы (мысалы, символдар тізбегі) ұсынысын қабылдап, сәйкес нормаланған терминнің ұсынысын қайтаратын бағдарлама. Бұл мүмкін емес нәтиже «өзіндік интерпретатордың» басқа анықтамаларына қатысты емес. Мысалы, кейбір авторлар типіндегі функцияларды өзіндік интерпретаторлар деп атайды, мұнда типтелген терминдердің ұсыныстарының типі. Сандарды шатастырудан сақтау үшін біз осы функцияларды өзіндік танушылар деп атаймыз. Браун мен Палсберг өзіндік танушыларды бірнеше қатаң нормалданатын тілдерде, соның ішінде F жүйесі мен Fω жүйесінде анықтауға болатынын көрсетті. Бұл мүмкін болды, себебі кодталған терминдердің типтері олардың ұсыныстарының типтерінде көрінеді, бұл диагональдық аргумент құруға кедергі келтіреді. Браун мен Палсберг өз мақалаларында өзіндік интерпретация мүмкін емес деген «қалыпты көзқарасты» жоққа шығарамыз деп мәлімдейді (және олар дәстүрлі көзқарас мысалы ретінде Wikipedia-ны келтіреді), бірақ олар шын мәнінде өзіндік танудың мүмкін еместігін жоққа шығарады, бұл ерекше ұғым. Олардың келесі жұмыстарында олар мұнда қолданылатын «өзіндік танушы» терминологиясына көшеді, атап айтқанда, оларды «өзіндік бағалаушылар» типінен ажыратады. Олар сондай-ақ өзіндік бағалауды іске асыру өзіндік танудан қиын көрінетінін мойындайды және біріншісін қатаң нормалданатын тілде іске асыруды ашық мәселе ретінде қалдырады.
Total functional programming languages that are strongly normalizing cannot be Turing complete, otherwise one could solve the halting problem by seeing if the program type checks. That means that there are computable functions that cannot be defined in the total language. In particular it is impossible to define a self interpreter in a total programming language, for example in any of the typed lambda calculi such as the simply typed lambda calculus, Jean Yves Girard's System F, or Thierry Coquand's calculus of constructions. Here, by "self interpreter" we mean a program that takes a source term representation in some plain format (such as a string of characters) and returns a representation of the corresponding normalized term. This impossibility result does not hold for other definitions of "self interpreter". For example, some authors have referred to functions of type as self interpreters, where is the type of representations of typed terms. To avoid confusion, we will refer to these functions as self recognizers. Brown and Palsberg showed that self recognizers could be defined in several strongly normalizing languages, including System F and System Fω. This turned out to be possible because the types of encoded terms being reflected in the types of their representations prevents constructing a diagonal argument. In their paper, Brown and Palsberg claim to disprove the "conventional wisdom" that self interpretation is impossible (and they refer to Wikipedia as an example of the conventional wisdom), but what they actually disprove is the impossibility of self recognizers, a distinct concept. In their follow up work, they switch to the more specific "self recognizer" terminology used here, notably distinguishing these from "self evaluators", of type They also recognize that implementing self evaluation seems harder than self recognition, and leave the implementation of the former in a strongly normalizing language as an open problem.
Қолданылуы
Қолданыстағы тілдің іске асырылуымен біріктірілгенде, мета-циклдық интерпретаторлар тілді кеңейтуге арналған базалық жүйені ұсынады, мүмкіндіктерді қосу арқылы жоғары деңгейге көтерілуге немесе оларды интерпретациялаудың орнына компиляциялау арқылы төмен деңгейге түсіруге мүмкіндік береді. Олар сонымен қатар бағдарламалау тілімен тығыз байланысты құралдарды, мысалы, күрделі отладчиктерді (дебаггерлерді) жазу үшін де пайдалы. Мета-циклдық іске асырылуды ескере отырып жобаланған тіл, тіпті бастапқы тілден мүлдем өзгеше тілдерді құруға да көбінесе ыңғайлы болады.
In combination with an existing language implementation, meta circular interpreters provide a baseline system from which to extend a language, either upwards by adding more features or downwards by compiling away features rather than interpreting them. They are also useful for writing tools that are tightly integrated with the programming language, such as sophisticated debuggers. A language designed with a meta circular implementation in mind is often more suited for building languages in general, even ones completely different from the host language.