Мета-циклический оценщик

В вычислениях метациклический оценщик ( MCE ) или метациклический интерпретатор ( MCI ) — это интерпретатор , который определяет каждую особенность интерпретируемого языка, используя аналогичные возможности основного языка интерпретатора. Например, интерпретация лямбда-приложения может быть реализована с использованием приложения-функции. [1] Метациклическое вычисление наиболее заметно в контексте Lisp . [1] [2] Самопереводчик — это метациклический переводчик, в котором интерпретируемый язык почти идентичен основному языку ; эти два термина часто используются как синонимы. [3]

В диссертации Коррадо Бема [4]описана конструкция автономного компилятора.[5] Из-за сложности компиляции функций высшего порядка многие языки вместо этого определялись через интерпретаторы, в первую очередь Lisp. [1] [6] Сам термин был придуман Джоном К. Рейнольдсом [ 1] и популяризирован благодаря его использованию в книге « Структура и интерпретация компьютерных программ» . [3] [7]

Самопереводчик — это метациркулярный интерпретатор, в котором основной язык также является интерпретируемым языком. [8] Самопереводчик выполняет универсальную функцию для рассматриваемого языка и может быть полезен в изучении определенных аспектов языка. [2] Самоинтерпретатор дает замкнутое, бессодержательное определение большинства языковых конструкций и, таким образом, дает мало информации о семантике интерпретируемого языка, например, о стратегии оценки . Решение этих проблем приводит к более общему понятию «определенного интерпретатора». [1]

Вот ядро ​​самооценки исчисления . Абстрактный синтаксис исчисления реализован в OCaml следующим образом , представляя переменные с ихиндексом де Брёйна , т. е. с их лексическим смещением (начиная с 0):

Значения (типа value) объединяют выражаемые значения (результат вычисления выражения в среде) и обозначаемые значения (значения, обозначаемые переменными в среде), терминология, придуманная Кристофером Стрейчи .[10] [11]

Этот вычислитель является композиционным , поскольку каждый из его рекурсивных вызовов выполняется над соответствующей частью данного термина. Это также более высокий порядок , поскольку область значений представляет собой функциональное пространство.