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

Question

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

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

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

Кроме того, часто говорят, что этот алгоритм выполняет вывод типа.Действительно ли это система вывода?Я думал, это всего лишь вывод типов.

Сопутствующие вопросы:

• Кто такой Хиндли Миллер?
• Вывод типа к проблеме объединения

Answer 1

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

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

Кроме того, часто говорят, что этот алгоритм выполняет вывод типа.Действительно ли это система вывода?Я думал, это всего лишь вывод типов.

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

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

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

Answer 2

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

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