Я работаю над языком выражения, основанным на генеалогии ML, поэтому, естественно, требуется вывод типа> :)
Теперь я пытаюсь расширить решение на основе ограничений для определения типов, основанное на простой реализации в EOPL (Фридман и Ванд), но они элегантно обходят алгебраические типы данных.
То, что у меня есть, работает плавно; если выражение eявляется a + b, e : Int, a : Intи b : Int. Если eэто совпадение,
match n with
| 0 -> 1
| n' -> n' * fac(n - 1)`,
Я могу справедливо сделать вывод о том , что t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1)и так далее ...
Но я очень не уверен, когда дело доходит до алгебраических типов данных. Предположим, что функция похожа на фильтр:
let filter pred list =
match list with
| Empty -> Empty
| Cons(e, ls') when pred e -> Cons (e, filter ls')
| Cons(_, ls') -> filter
Чтобы тип списка оставался полиморфным, необходимо, чтобы тип Cons был типом a * a list -> a list. Итак, при установлении этих ограничений, мне, очевидно, нужно искать эти типы моих алгебраических конструкторов - проблема, которую я сейчас имею, - это «контекстно-зависимая» многократного использования алгебраических конструкторов - как я могу выразить в своих уравнениях ограничений, что aв каждый случай должен быть одинаковым?
У меня проблемы с поиском общего решения, и я не могу найти много литературы по этому вопросу. Всякий раз, когда я нахожу что-то похожее - язык, основанный на выражениях, с логическим выводом на основе ограничений - они не дотягивают до алгебраических типов данных и полиморфизма.
Любой вклад очень ценится!
Ответы:
См. Mini ML, в частности, раздел «Вывод типа».
Он содержит пример кода на F # для полного синтаксического анализатора простого функционального языка. Более того, в разделе «Вывод типа» реализован алгоритм Хиндли-Милнера, который можно найти в большинстве систем вывода типов. Автор также предоставляет ссылки на два других важных документа, помогающих понять Хиндли-Милнера; один из них представляет собой своего рода введение высокого уровня, а другой - документ, описывающий реализацию алгоритма в коде.
источник