Я изучил кое-что о реализации зависимых типов, как этот учебник , но большинство из них - реализация интерпретаторов. Мой вопрос, кажется, что реализация компилятора для зависимого типа намного сложнее, чем компилятор, потому что вы действительно можете оценить аргументы зависимого типа для проверки типа.
Так
- Правильно ли мое наивное впечатление?
- Если это правильно, какие-нибудь примеры / ресурсы о реализации статически проверенного языка, поддерживающего зависимый тип?
type-systems
compilers
dependent-type
molikto
источник
источник
ocamloptили GHC :-) (кстати, это подход Coq и Agda.)Ответы:
Это интересный вопрос! Как подсказывает ответ Энтони, можно использовать обычные подходы к составлению независимого функционального языка, если у вас уже есть переводчик для оценки терминов для проверки типов .
Это подход, принятый Эдвином Брейди. Теперь это концептуально проще, но оно теряет преимущества компиляции по скорости при выполнении проверки типов. Это было решено несколькими способами.
Во-первых, можно реализовать виртуальную машину, которая на лету компилирует термины в байт-код для проверки преобразования. Эта идея
vm_computeреализована в Coq Бенджамином Грегуаром . По-видимому, есть и этот тезис Дирка Клеблатта на эту конкретную тему, но на самом деле о машинном коде, а не о виртуальной машине.Во-вторых, можно генерировать код на более традиционном языке, который после выполнения проверяет все преобразования, необходимые для проверки типа программы с зависимой типизацией. Это означает, что мы можем использовать Haskell, скажем, для проверки типа модуля Agda. Код может быть скомпилирован и запущен, и, если он его принимает, можно предположить, что код на языке зависимого типа является хорошо типизированным (за исключением ошибок реализации и компиляции). Впервые я услышал об этом подходе, предложенном Матье Боесфлюгом .
источник
Кандидатская диссертация Эдвина Брэди обрисовывает в общих чертах, как построить компилятор для зависимо типизированного языка программирования. Я не эксперт, но я бы сказал, что это не намного сложнее, чем реализация System F-подобного компилятора. Многие принципы очень похожи, а некоторые - одинаковы (например, компилятор суперкомбинаторов). Тезис охватывает многие другие вопросы.
источник