Мета-круговой оценщик

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

История

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

Самоинтерпретаторы

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

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

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

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

тип  term  =  IND  int (  *  индекс де Брёйна *)  |  АБС  срока  |​  Приложение срока * срока​     

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

тип  значение  =  FUN  из  ( значение  ->  значение )пусть  получит  eval  ( t  :  term )  ( e  :  valuelist  ) : value = сопоставить t с 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 ) и применить ( FUN f : value ) ( a : value ) = f a                                                пусть  main  ( t  :  term )  :  value  =  eval  t  []

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

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

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

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

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

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

В "Definitional Interpreters" Рейнольдс сделал самоинтерпретатора хорошо определенным, сделав его независимым от стратегии оценки его определяющего языка. Он исправил стратегию оценки, преобразовав самоинтерпретатор в Continuation-Passing Style , который независим от стратегии оценки, как позже было зафиксировано в теоремах независимости Гордона Плоткина . ^[12]

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

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

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

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

Использует

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

Примеры

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

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

• Шепелявость , 1958
  • Схема , 1975
    • Пико , 1997 ^[23]
    • ActorScript, 2009?
  • Кложур , 2007
• Форт , 1968
  • Постскриптум , 1982
• Пролог , 1972
• TeX , основанный на Virgin TeX, 1978
• Разговор , 1980
• Ребол , 1997
  • Красный , 2011
• Фактор , 2003

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

• Java через Jikes RVM , Squawk , Maxine или GraalVM's Espresso
• Scala через Metascala
• JavaScript через Narcissus или JS-Interpreter
• Оз через Глинду
• Питон через PyPy
• Руби через Рубиниус
• Lua через Metalua

Смотрите также

• М-выражение
• Гомоиконичность
• Самостоятельно размещаемый компилятор

Ссылки

1. Рейнольдс, Джон К. (1972). "Определительные интерпретаторы для языков программирования высшего порядка". Труды ежегодной конференции ACM по - ACM '72 (PDF) . Том 2. Труды 25-й Национальной конференции ACM. стр. 717–740. doi :10.1145/800194.805852 . Получено 14 апреля 2017 г. .
2. Reynolds, John C. (1998). "Definitional Interpreters Revisited" (PDF) . Higher-Order and Symbolic Computation . 11 (4): 355–361. doi :10.1023/A:1010075320153. S2CID  34126862 . Получено 21 марта 2023 г. .
3. "The Metacircular Evaluator". Структура и интерпретация компьютерных программ . MIT.
4. Бём, Коррадо (1954). «Цифровые вычисления. Вы разгадываете логико-математические формулы для машины в рамках концепции программы». Энн. Мат. Приложение Pura . 4 (37): 1–51.
5. Кнут, Дональд Э .; Пардо, Луис Трабб (август 1976 г.). Раннее развитие языков программирования. стр. 36.
6. Маккарти, Джон (1961). "Универсальная функция LISP" (PDF) . Руководство программиста Lisp 1.5 . стр. 10.
7. Харви, Брайан. «Почему важны структура и интерпретация компьютерных программ». people.eecs.berkeley.edu . Получено 14 апреля 2017 г.
8. Брейтуэйт, Реджинальд (2006-11-22). "Значение мета-кругового интерпретатора" . Получено 2011-01-22 .
9. Дэнви, Оливье (2006). Аналитический подход к программам как объектам данных (диссертация). doi :10.7146/aul.214.152. ISBN 9788775073948.
10. Стрейчи , Кристофер (1967). Основные концепции языков программирования (технический отчет). doi :10.1023/A:1010000313106.
11. Моссес, Питер Д. (2000). «Предисловие к «Основным концепциям языков программирования»". Высшие порядки и символьные вычисления . 13 (1/2): 7–9. doi :10.1023/A:1010048229036. S2CID  39258759.
12. Плоткин, Гордон Д. (1975). «Вызов по имени, вызов по значению и лямбда-исчисление». Теоретическая информатика . 1 (2): 125–159. doi : 10.1016/0304-3975(75)90017-1 .
13. Феллейзен, Маттиас ; Фридман, Дэниел (1986). Операторы управления, машина SECD и лямбда-исчисление (PDF) . Формальное описание концепций программирования III, Elsevier Science Publishers BV (Северная Голландия). стр. 193–217.
14. Шмидт, Дэвид А. (1980). "Машины перехода состояний для выражений лямбда-исчисления". Машины перехода состояний для выражений лямбда-исчисления . Lecture Notes in Computer Science. Vol. 94. Semantics-Directed Compiler Generation, LNCS 94. pp. 415–440. doi : 10.1007/3-540-10250-7_32 . ISBN 978-3-540-10250-2.
15. Дэнви , Оливье (2004). Рациональная деконструкция машины SECD Ландина (PDF) . Реализация и применение функциональных языков, 16-й международный семинар, IFL 2004, пересмотренные избранные статьи, Lecture Notes in Computer Science 3474, Springer. стр. 52–71. ISSN  0909-0878.
16. Ager, Mads Sig; Biernacki, Dariusz; Danvy, Olivier ; Midtgaard, Jan (2003). «Функциональное соответствие между оценщиками и абстрактными машинами». Brics Report Series . 10 (13). 5-я международная конференция ACM SIGPLAN по принципам и практике декларативного программирования (PPDP'03): 8–19. doi : 10.7146/brics.v10i13.21783 .
17. Риоло, Рик; Ворцель, Уильям П.; Котанчек, Марк (4 июня 2015 г.). Теория и практика генетического программирования XII. Springer. стр. 59. ISBN 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. doi :10.1145/2837614.2837623. ISBN 9781450335492. S2CID  14781370.
21. Браун, Мэтт; Палсберг, Йенс (январь 2017 г.). «Типизированная самооценка через интенсиональные функции типа». Труды 44-го симпозиума ACM SIGPLAN по принципам языков программирования . стр. 415–428. doi : 10.1145/3009837.3009853 . ISBN 9781450346603.
22. Oriol, Manuel; Meyer, Bertrand (2009-06-29). Объекты, компоненты, модели и шаблоны: 47-я международная конференция TOOLS EUROPE 2009, Цюрих, Швейцария, 29 июня - 3 июля 2009 г., Труды. Springer Science & Business Media. стр. 330. ISBN 9783642025716. Получено 14 апреля 2017 г. .
23. Мета-циклическая реализация языка программирования Pico

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

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