Опишите умозаключение типа Дамаса-Милнера так, чтобы студент CS101 мог понять

Хиндли-Милнер - это система типов, которая является основой систем типов многих известных языков функционального программирования. Damas-Milner - это алгоритм, который выводит (выводит?) Типы в системе типов Хиндли-Милнера.

Википедия дает описание алгоритма, который, насколько я могу судить, сводится к одному слову: "объединение". Это все, что нужно? Если это так, это означает, что интересной частью является сама система типов, а не система вывода типов.

Если Damas-Milner - это больше, чем объединение, я хотел бы описать Damas-Milner, который включает в себя простой пример и, в идеале, некоторый код.

Также часто говорят, что этот алгоритм делает вывод типа. Это действительно система логического вывода? Я думал, что это только вывод типов.

Смежные вопросы:

2 ответа

Решение

Damas Milner - это просто структурированное использование объединения.

Когда он возвращается в лямбда-выражение, он создает новое имя переменной. Когда вы в подслове находите эту переменную, используемую таким образом, который требует заданного типа, она записывает объединение этой переменной и этого типа. Если он когда-либо пытается объединить два типа, которые не имеют смысла, как, например, сказать, что отдельная переменная является одновременно Int и функцией из a -> b, то он кричит на вас за то, что вы сделали что-то плохое.

Также часто говорят, что этот алгоритм делает вывод типа. Это действительно система логического вывода? Я думал, что это только вывод типов.

Вывод типов является выводом типа. Проверка того, что аннотации типов действительны для данного термина, является проверкой типов. Это разные проблемы.

Если это так, это означает, что интересной частью является сама система типов, а не система вывода типов.

Обычно говорят, что системы стилей типа Хиндли-Милнера сбалансированы на острие. Если вы добавите гораздо больше функциональности, станет невозможно определить типы. Таким образом, расширения системы типов, которые вы можете наложить поверх системы типов стилей Хиндли-Милнера, не разрушая ее свойства вывода, действительно являются интересными частями современных функциональных языков. В некоторых случаях мы смешиваем вывод типов и проверку типов, например, в Haskell многие современные расширения не могут быть выведены, но могут быть проверены, поэтому они требуют аннотаций типов для расширенных функций, таких как полиморфная рекурсия.

Википедия дает описание алгоритма, который, насколько я могу судить, сводится к одному слову: "объединение". Это все, что нужно? Если это так, это означает, что интересной частью является сама система типов, а не система вывода типов.

IIRC, интересная часть алгоритма логического вывода типа Дамаса-Милнера W состоит в том, что он выводит самые общие возможные типы.

Другие вопросы по тегам