Войти
В вычислении, мета-круговой вычислитель ( МКЭ) или мета-круговой интерпретатор ( MCI) является интерпретатором, который определяет каждую особенность интерпретируемого языка с использованием аналогичного объекта языка хоста интерпретатора. Например, интерпретация лямбда-приложения может быть реализована с использованием приложения-функции. Метациклическое вычисление наиболее заметно в контексте Lisp. Самоинтерпретатор является мета-интерпретатором круговой, где интерпретируемый язык почти идентичен языку хозяина; эти два термина часто используются как синонимы.
В диссертации Коррадо Бема описана конструкция компилятора с собственным хостом. Из-за сложности компиляции функций высшего порядка многие языки вместо этого определялись через интерпретаторы, в первую очередь Лисп. Сам термин был придуман Джоном С. Рейнольдсом и популяризирован благодаря его использованию в книге « Структура и интерпретация компьютерных программ».
Самоинтерпретатор - это мета-круговой интерпретатор, в котором основной язык также является языком, который интерпретируется. Самоинтерпретатор выполняет универсальную функцию для рассматриваемого языка и может быть полезен при изучении определенных аспектов языка. Самоинтерпретатор предоставит циклическое, бессмысленное определение большинства языковых конструкций и, таким образом, дает мало информации о семантике интерпретируемого языка, например о стратегии оценки. Решение этих проблем дает более общее понятие «дефиниционный интерпретатор».
Полные функциональные языки программирования, которые строго нормализуют, не могут быть полными по Тьюрингу, иначе можно было бы решить проблему остановки, проверив, проверяет ли программа тип. Это означает, что есть вычислимые функции, которые нельзя определить на языке в целом. В частности, невозможно определить самоинтерпретатор в общем языке программирования, например, в любой из типизированного лямбда - исчислений, такие как простого типизированного лямбда - исчисления, Жан-Ив Жирар «s System F, или Тьерри Кокан » s исчисления конструкции. Здесь под «самоинтерпретатором» мы подразумеваем программу, которая принимает исходное представление термина в некотором простом формате (например, строку символов) и возвращает представление соответствующего нормализованного термина. Этот результат о невозможности не распространяется на другие определения «самоинтерпретатора». Например, некоторые авторы называют функции типа самоинтерпретаторами, где - это тип представления терминов с типом. Чтобы избежать путаницы, мы будем называть эти функции самораспознавающими. Браун и Палсберг показали, что самораспознаватели могут быть определены в нескольких строго нормализующих языках, включая Систему F и Систему F ω. Это оказалось возможным, потому что типы закодированных терминов, отраженные в типах их представлений, препятствуют построению диагонального аргумента. В своей статье Браун и Палсберг утверждают, что опровергают «общепринятое мнение» о том, что самоинтерпретация невозможна (и они ссылаются на Википедию как на пример общепринятой мудрости), но на самом деле они опровергают невозможность самопознания. отличная концепция. В своей последующей работе они переключаются на более конкретную терминологию «самопознания», используемую здесь, в частности, отделяя их от типа «самооценки». Они также признают, что реализация самооценки кажется сложнее, чем самопознание, и оставляют реализацию первой на строго нормализующем языке как открытую проблему.
В сочетании с существующей реализацией языка мета-циклические интерпретаторы предоставляют базовую систему, от которой можно расширить язык, либо вверх, добавляя дополнительные функции, либо вниз, скомпилировав функции, а не интерпретируя их. Они также полезны для написания инструментов, тесно интегрированных с языком программирования, таких как сложные отладчики. Язык, разработанный с учетом мета-круговой реализации, часто больше подходит для создания языков в целом, даже если они полностью отличаются от основного языка.
Многие языки имеют одну или несколько мета-циклических реализаций. Вот неполный список.
Некоторые языки с мета-круговой реализацией, разработанной снизу вверх в сгруппированном хронологическом порядке:
Некоторые языки с мета-циклической реализацией через третьих лиц:
