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

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

История

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

Самопереводчики

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

От самоинтерпретатора к абстрактной машине

Эта часть основана на разделе 3.2.4 диссертации Дэнви. ^[9]

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

type term = IND of int    (* de Bruijn index *)
          | ABS of term
          | APP of term * term

Оценщик использует среду:

type value = FUN of (value -> value)

let rec eval (t : term) (e : value list) : value =
  match t with
    IND n ->
     List.nth e n
  | ABS t' ->
     FUN (fun v -> eval t' (v :: e))
  | APP (t0, t1) ->
     apply (eval t0 e) (eval t1 e)
and apply (FUN f : value) (a : value) =
  f a

let main (t : term) : value =
  eval t []

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

Окружения представлены в виде списков обозначаемых значений.

Основной оценщик состоит из трех пунктов:

Он сопоставляет переменную (представленную индексом де Брёйна) со значением в текущей среде по этому индексу.
Он отображает синтаксическую функцию в семантическую функцию. (Применение семантической функции к аргументу сводится к вычислению тела соответствующей синтаксической функции в ее лексическом окружении, расширенном аргументом.)
Он отображает синтаксическое приложение в семантическое приложение.

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

В «Определительных интерпретаторах» Рейнольдс ответил на вопрос, четко ли определен такой самоинтерпретатор. Он ответил отрицательно, потому что стратегия оценки определяемого языка (исходного языка) определяется стратегией оценки определяющего языка (мета-языка). Если метаязык следует за вызовом по значению (как это делает OCaml), исходный язык следует за вызовом по значению. Если метаязык следует за вызовом по имени (как это делает Алгол 60 ), исходный язык следует за вызовом по имени. И если метаязык следует за вызовом по необходимости (как это делает Haskell ), то исходный язык следует за вызовом по необходимости.

В «Определительных интерпретаторах» Рейнольдс четко определил самоинтерпретатор, сделав его независимым от стратегии оценки его определяющего языка. Он исправил стратегию оценки, преобразовав самоинтерпретатор в стиль продолжения-передачи , который не зависит от стратегии оценки, как позже было отражено в Гордона Плоткина «Теоремах независимости» . ^[12]

Более того, поскольку логические отношения еще не были обнаружены, Рейнольдс сделал полученный вычислитель, передающий продолжение, первым порядком путем (1) преобразования замыкания и (2) дефункционализации продолжения. Он указал на «машинное качество» полученного интерпретатора, которое является источником машины CEK, поскольку преобразование CPS Рейнольдса предназначалось для вызова по значению. ^[13] Для вызова по имени эти преобразования сопоставляют самоинтерпретатор с ранним экземпляром машины Кривина . ^[14] машины . Таким образом можно получить машину SECD и многие другие абстрактные ^[15] ^[16]

Примечательно, что три самые известные абстрактные машины $\lambda$ исчисление функционально соответствуют одному и тому же самоинтерпретатору.

Самоинтерпретация на общих языках программирования

Языки тотального функционального программирования , которые строго нормализуются, не могут быть полными по Тьюрингу , иначе можно было бы решить проблему остановки, проверив, проверяет ли программа тип. Это означает, что существуют вычислимые функции, которые невозможно определить на общем языке. ^[17] В частности, невозможно определить самоинтерпретатор в общем языке программирования, например, в любом типизированном лямбда-исчислении, таком как просто типизированное лямбда-исчисление , Жан-Ива Жирара или система F исчисление Коканда . Тьерри конструкции . ^[18]^[19] Здесь под «самоинтерпретатором» мы подразумеваем программу, которая принимает представление исходного термина в некотором простом формате (например, строку символов) и возвращает представление соответствующего нормализованного термина. Этот результат невозможности не справедлив для других определений «самоинтерпретатора». Например, некоторые авторы ссылались на функции типа $\pi \,\tau \to \tau$ как самопереводчики, где $\pi \,\tau$ это тип представления $\tau$ -типизированные термины. Чтобы избежать путаницы, мы будем называть эти функции самораспознавателями . Браун и Палсберг показали, что средства самораспознавания могут быть определены в нескольких строго нормализуемых языках, включая System F и System F _ω . ^[20] Это оказалось возможным потому, что типы закодированных термов, отраженные в типах их представлений, не позволяют построить диагональный аргумент . В своей статье Браун и Палсберг заявляют, что опровергают «традиционное мнение», согласно которому самоинтерпретация невозможна (и они ссылаются на Википедию как на пример общепринятого мнения), но на самом деле они опровергают невозможность самопознания, отдельное понятие. В своей последующей работе они переходят на более конкретную терминологию «самопознающих», используемую здесь, заметно отличая их от «самооценщиков» типа $\pi \,\tau \to \pi \,\tau$ . ^[21] Они также признают, что реализация самооценки кажется более сложной, чем самопознание, и оставляют реализацию первой на строго нормализующем языке открытой проблемой.

Использование

В сочетании с существующей языковой реализацией метациклические интерпретаторы предоставляют базовую систему, на основе которой можно расширять язык либо вверх, добавляя больше функций, либо вниз, компилируя функции, а не интерпретируя их. ^[22] Они также полезны для написания инструментов, тесно интегрированных с языком программирования, например сложных отладчиков. ^{[ нужна ссылка ]} Язык, разработанный с учетом метациклической реализации, часто больше подходит для создания языков в целом, даже тех, которые полностью отличаются от основного языка. ^{[ нужна ссылка ]}

Примеры

Многие языки имеют одну или несколько метациклических реализаций. Ниже приведен неполный список.

Некоторые языки с метациклической реализацией, разработанные снизу вверх, в сгруппированном хронологическом порядке:

Лисп , 1958 год.
- Схема , 1975 год.
  - Пико , 1997 год. ^[23]
  - АктерСкрипт , 2009?
- Кложур , 2007 г.
Четвертый , 1968 год.
- Постскриптум , 1982 г.
Пролог , 1972 год.
TeX , на основе чистого TeX, 1978 г.
Смолток , 1980
Ребол , 1997 год.
- Красный , 2011
Фактор , 2003

Некоторые языки с метациклической реализацией через третьих лиц:

Java через Jikes RVM , Squawk , Maxine или GraalVM's Espresso
Скала через Метаскала
JavaScript через Narcissus или JS-Interpreter
Оз через Глинду
Питон через PyPy
Руби через Рубиниус
Второй через Металуа

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Рейнольдс, Джон К. (1972). «Определенные интерпретаторы языков программирования высшего порядка». Материалы ежегодной конференции ACM - ACM '72 (PDF) . Том. 2. Материалы 25-й Национальной конференции ACM. стр. 717–740. дои : 10.1145/800194.805852 . Проверено 14 апреля 2017 г.
^ Jump up to: ^а ^б Рейнольдс, Джон К. (1998). «Возвращение к дефинициональным интерпретаторам» (PDF) . Вычисления высшего порядка и символьные вычисления . 11 (4): 355–361. дои : 10.1023/А:1010075320153 . S2CID 34126862 . Проверено 21 марта 2023 г.
^ Jump up to: ^а ^б «Метациркулярный оценщик» . Структура и интерпретация компьютерных программ . Массачусетский технологический институт.
^ Бём, Коррадо (1954). «Цифровые калькуляторы. Расшифровка логико-математических формул самой машиной в разработке программы». Энн. Мачта. Приложение Pura . 4 (37): 1–51.
^ Кнут, Дональд Э .; Пардо, Луис Трабб (август 1976 г.). Раннее развитие языков программирования . п. 36.
^ Маккарти, Джон (1961). «Универсальная функция LISP» (PDF) . Руководство программиста Lisp 1.5 . п. 10.
^ Харви, Брайан. «Почему структура и интерпретация компьютерных программ имеют значение» . люди.eecs.berkeley.edu . Проверено 14 апреля 2017 г.
^ Брейтуэйт, Реджинальд (22 ноября 2006 г.). «Значение метациркулярного интерпретатора» . Проверено 22 января 2011 г.
^ Дэнви, Оливье (2006). Аналитический подход к программам как объектам данных (Диссертация). дои : 10.7146/аул.214.152 . ISBN 9788775073948 .
^ Стрейчи , Кристофер (1967). Фундаментальные концепции языков программирования (Технический отчет). дои : 10.1023/А:1010000313106 .
^ Моссес, Питер Д. (2000). «Предисловие к «Фундаментальным понятиям языков программирования» ». Вычисления высшего порядка и символьные вычисления . 13 (1/2): 7–9. дои : 10.1023/А:1010048229036 . S2CID 39258759 .
^ Плоткин, Гордон Д. (1975). «Вызов по имени, вызов по значению и лямбда-исчисление» . Теоретическая информатика . 1 (2): 125–159. дои : 10.1016/0304-3975(75)90017-1 .
^ Феллизен, Матиас ; Фридман, Дэниел (1986). Операторы управления, машина SECD и лямбда-исчисление (PDF) . Формальное описание концепций программирования III, Elsevier Science Publishers BV (Северная Голландия). стр. 193–217.
^ Шмидт, Дэвид А. (1980). «Машины переходов состояний для выражений лямбда-исчисления». Машины перехода состояний для выражений лямбда-исчисления . Конспекты лекций по информатике. Том. 94. Генерация компилятора, управляемая семантикой, LNCS 94. стр. 415–440. дои : 10.1007/3-540-10250-7_32 . ISBN 978-3-540-10250-2 .
^ Дэнви , Оливье (2004). Рациональная деконструкция машины SECD Ландина (PDF) . Реализация и применение функциональных языков, 16-й международный семинар, IFL 2004, Пересмотренные избранные статьи, Конспекты лекций по информатике 3474, Springer. стр. 52–71. ISSN 0909-0878 .
^ Агер, Мэдс Сиг; Бернацкий, Дариуш; Дэнви, Оливье ; Мидтгаард, январь (2003). «Функциональное соответствие между вычислителями и абстрактными машинами» . Серия отчетов БРИКС . 10 (13). 5-я Международная конференция ACM SIGPLAN по принципам и практике декларативного программирования (PPDP'03): 8–19. дои : 10.7146/brics.v10i13.21783 .
^ Риоло, Рик; Ворзель, Уильям П.; Котанчек, Марк (4 июня 2015 г.). Теория и практика генетического программирования XII . Спрингер. п. 59. ИСБН 978-3-319-16030-6 . Проверено 8 сентября 2021 г.
^ Конор МакБрайд (май 2003 г.), «при прекращении деятельности» (размещено в списке рассылки Haskell-Cafe).
^ Андрей Бауэр (июнь 2014 г.), Ответ на: Общий язык, который может интерпретировать только полный по Тьюрингу язык (опубликовано на сайте Theoretical Computer Science StackExchange )
^ Браун, Мэтт; Палсберг, Йенс (11 января 2016 г.). «Прорыв через барьер нормализации: самопереводчик f-omega» (PDF) . Материалы 43-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . стр. 5–17. дои : 10.1145/2837614.2837623 . ISBN 9781450335492 . S2CID 14781370 .
^ Браун, Мэтт; Палсберг, Йенс (январь 2017 г.). «Типизированная самооценка с помощью функций интенсионального типа». Материалы 44-го симпозиума ACM SIGPLAN по принципам языков программирования . стр. 415–428. дои : 10.1145/3009837.3009853 . ISBN 9781450346603 .
^ Ориоль, Мануэль; Мейер, Бертран (29 июня 2009 г.). Объекты, компоненты, модели и шаблоны: 47-я международная конференция Tools EUROPE 2009, Цюрих, Швейцария, 29 июня – 3 июля 2009 г., Материалы . Springer Science & Business Media. п. 330. ИСБН 9783642025716 . Проверено 14 апреля 2017 г.
^ Метациклическая реализация языка программирования Pico.

Внешние ссылки

Структура и интерпретация компьютерных программ (SICP) , онлайн-версия полной книги, по состоянию на 18 января 2009 г.
Метаскала

[HOP-1] Jump up to: ^а ^б ^с ^д ^и Рейнольдс, Джон К. (1972). «Определенные интерпретаторы языков программирования высшего порядка». Материалы ежегодной конференции ACM - ACM '72 (PDF) . Том. 2. Материалы 25-й Национальной конференции ACM. стр. 717–740. дои : 10.1145/800194.805852 . Проверено 14 апреля 2017 г.

[reynolds_98-2] Jump up to: ^а ^б Рейнольдс, Джон К. (1998). «Возвращение к дефинициональным интерпретаторам» (PDF) . Вычисления высшего порядка и символьные вычисления . 11 (4): 355–361. дои : 10.1023/А:1010075320153 . S2CID 34126862 . Проверено 21 марта 2023 г.

[SICP-3] Jump up to: ^а ^б «Метациркулярный оценщик» . Структура и интерпретация компьютерных программ . Массачусетский технологический институт.

[boehm_54-4] Бём, Коррадо (1954). «Цифровые калькуляторы. Расшифровка логико-математических формул самой машиной в разработке программы». Энн. Мачта. Приложение Pura . 4 (37): 1–51.

[5] Кнут, Дональд Э .; Пардо, Луис Трабб (август 1976 г.). Раннее развитие языков программирования . п. 36.

[6] Маккарти, Джон (1961). «Универсальная функция LISP» (PDF) . Руководство программиста Lisp 1.5 . п. 10.

[7] Харви, Брайан. «Почему структура и интерпретация компьютерных программ имеют значение» . люди.eecs.berkeley.edu . Проверено 14 апреля 2017 г.

[8] Брейтуэйт, Реджинальд (22 ноября 2006 г.). «Значение метациркулярного интерпретатора» . Проверено 22 января 2011 г.

[danvy_06-9] Дэнви, Оливье (2006). Аналитический подход к программам как объектам данных (Диссертация). дои : 10.7146/аул.214.152 . ISBN 9788775073948 .

[strachey_67-10] Стрейчи , Кристофер (1967). Фундаментальные концепции языков программирования (Технический отчет). дои : 10.1023/А:1010000313106 .

[mosses_00-11] Моссес, Питер Д. (2000). «Предисловие к «Фундаментальным понятиям языков программирования» ». Вычисления высшего порядка и символьные вычисления . 13 (1/2): 7–9. дои : 10.1023/А:1010048229036 . S2CID 39258759 .

[plotkin_tcs-75-12] Плоткин, Гордон Д. (1975). «Вызов по имени, вызов по значению и лямбда-исчисление» . Теоретическая информатика . 1 (2): 125–159. дои : 10.1016/0304-3975(75)90017-1 .

[felleisen_friedman_fdpc3-13] Феллизен, Матиас ; Фридман, Дэниел (1986). Операторы управления, машина SECD и лямбда-исчисление (PDF) . Формальное описание концепций программирования III, Elsevier Science Publishers BV (Северная Голландия). стр. 193–217.

[schmidt_80-14] Шмидт, Дэвид А. (1980). «Машины переходов состояний для выражений лямбда-исчисления». Машины перехода состояний для выражений лямбда-исчисления . Конспекты лекций по информатике. Том. 94. Генерация компилятора, управляемая семантикой, LNCS 94. стр. 415–440. дои : 10.1007/3-540-10250-7_32 . ISBN 978-3-540-10250-2 .

[danvy_ifl-04-15] Дэнви , Оливье (2004). Рациональная деконструкция машины SECD Ландина (PDF) . Реализация и применение функциональных языков, 16-й международный семинар, IFL 2004, Пересмотренные избранные статьи, Конспекты лекций по информатике 3474, Springer. стр. 52–71. ISSN 0909-0878 .

[ager_et_al_03-16] Агер, Мэдс Сиг; Бернацкий, Дариуш; Дэнви, Оливье ; Мидтгаард, январь (2003). «Функциональное соответствие между вычислителями и абстрактными машинами» . Серия отчетов БРИКС . 10 (13). 5-я Международная конференция ACM SIGPLAN по принципам и практике декларативного программирования (PPDP'03): 8–19. дои : 10.7146/brics.v10i13.21783 .

[17] Риоло, Рик; Ворзель, Уильям П.; Котанчек, Марк (4 июня 2015 г.). Теория и практика генетического программирования XII . Спрингер. п. 59. ИСБН 978-3-319-16030-6 . Проверено 8 сентября 2021 г.

[18] Конор МакБрайд (май 2003 г.), «при прекращении деятельности» (размещено в списке рассылки Haskell-Cafe).

[19] Андрей Бауэр (июнь 2014 г.), Ответ на: Общий язык, который может интерпретировать только полный по Тьюрингу язык (опубликовано на сайте Theoretical Computer Science StackExchange )

[20] Браун, Мэтт; Палсберг, Йенс (11 января 2016 г.). «Прорыв через барьер нормализации: самопереводчик f-omega» (PDF) . Материалы 43-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . стр. 5–17. дои : 10.1145/2837614.2837623 . ISBN 9781450335492 . S2CID 14781370 .

[21] Браун, Мэтт; Палсберг, Йенс (январь 2017 г.). «Типизированная самооценка с помощью функций интенсионального типа». Материалы 44-го симпозиума ACM SIGPLAN по принципам языков программирования . стр. 415–428. дои : 10.1145/3009837.3009853 . ISBN 9781450346603 .

[22] Ориоль, Мануэль; Мейер, Бертран (29 июня 2009 г.). Объекты, компоненты, модели и шаблоны: 47-я международная конференция Tools EUROPE 2009, Цюрих, Швейцария, 29 июня – 3 июля 2009 г., Материалы . Springer Science & Business Media. п. 330. ИСБН 9783642025716 . Проверено 14 апреля 2017 г.

[23] Метациклическая реализация языка программирования Pico.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]