Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка 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ω. Это оказалось возможным, поскольку типы закодированных термов, отражающиеся в типах их представлений, препятствуют построению диагонального аргумента. В своей статье Браун и Палсберг утверждают, что опровергают "общепринятое мнение" о невозможности самоинтерпретации (и они ссылаются на Википедию как пример общепринятого мнения), но на самом деле они опровергают невозможность самораспознавания, являющегося отдельным понятием. В своих последующих работах они переходят к более специфической терминологии "самораспознающая функция", используемой здесь, в частности, отличая их от "самооценивающих функций" типа . Они также признают, что реализация самооценки представляется более сложной, чем самораспознавание, и оставляют реализацию первой в строго нормализующем языке как открытую проблему.
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.