Компилятор для зависимого типа намного сложнее, чем интерпретатор?

11

Я изучил кое-что о реализации зависимых типов, как этот учебник , но большинство из них - реализация интерпретаторов. Мой вопрос, кажется, что реализация компилятора для зависимого типа намного сложнее, чем компилятор, потому что вы действительно можете оценить аргументы зависимого типа для проверки типа.

Так

  • Правильно ли мое наивное впечатление?
  • Если это правильно, какие-нибудь примеры / ресурсы о реализации статически проверенного языка, поддерживающего зависимый тип?
molikto
источник
Нет, поскольку вы можете свести проблему компиляции зависимых типов к известной проблеме: (1) проверьте тип программы с помощью интерпретатора; (2) распаковать программу в OCaml / Haskell / что угодно; (3) скомпилировать, используя ocamloptили GHC :-) (кстати, это подход Coq и Agda.)
xrq

Ответы:

12

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

Это подход, принятый Эдвином Брейди. Теперь это концептуально проще, но оно теряет преимущества компиляции по скорости при выполнении проверки типов. Это было решено несколькими способами.

Во-первых, можно реализовать виртуальную машину, которая на лету компилирует термины в байт-код для проверки преобразования. Эта идея vm_computeреализована в Coq Бенджамином Грегуаром . По-видимому, есть и этот тезис Дирка Клеблатта на эту конкретную тему, но на самом деле о машинном коде, а не о виртуальной машине.

Во-вторых, можно генерировать код на более традиционном языке, который после выполнения проверяет все преобразования, необходимые для проверки типа программы с зависимой типизацией. Это означает, что мы можем использовать Haskell, скажем, для проверки типа модуля Agda. Код может быть скомпилирован и запущен, и, если он его принимает, можно предположить, что код на языке зависимого типа является хорошо типизированным (за исключением ошибок реализации и компиляции). Впервые я услышал об этом подходе, предложенном Матье Боесфлюгом .

*

Коди
источник
1
Немного насмешка: зачем вам писать компилятор, если у вас есть интерпретатор, выполняющий проверку типов? В конце концов, большинство (все?) Серьезных пользователей языков программирования с зависимой типизацией заботятся только о средствах проверки типов, используя язык в качестве корректора. Я, конечно, никогда не запускал ни одну из своих программ Agda или Coq. Так что, если вы заботитесь о скорости, не хотите ли вы скомпилировать преобразования типов?
Мартин Бергер
2
Решения 2 и 3 решают эту проблему: вы компилируете код, который проверяет правильность типизации (и, в частности, выполняет преобразование типов). Мое второе замечание: вы действительно хотите запускать код с зависимой типизацией в некоторых ситуациях (см. Idris, Ur / Web).
Коди
1
Также: в определенной степени решение 1 также обращается к нему, стирая грани между интерпретатором и компилятором.
Коди
1
Интересно, можно ли использовать технику проекций футурамы, чтобы ускорить работу интерпретатора, эффективно заканчивая компилятором?
Стивен Шоу
1
Единственное, что я видел, это Unison unisonweb.org/2017-10-13/scala-world.html
Стивен Шоу
10

Кандидатская диссертация Эдвина Брэди обрисовывает в общих чертах, как построить компилятор для зависимо типизированного языка программирования. Я не эксперт, но я бы сказал, что это не намного сложнее, чем реализация System F-подобного компилятора. Многие принципы очень похожи, а некоторые - одинаковы (например, компилятор суперкомбинаторов). Тезис охватывает многие другие вопросы.

Энтони
источник