Каковы пределы вывода типа? - PullRequest
20 голосов
/ 09 августа 2009

Каковы пределы вывода типа? Какие системы типов не имеют общего алгоритма вывода?

Ответы [ 2 ]

11 голосов
/ 09 августа 2009

Джо Уэллс показал, что вывод типа неразрешим для Системы F, которая является самым основным полиморфным лямбда-исчислением, независимо обнаруженным Жираром и Рейнольдсом. Это самый важный результат, показывающий пределы вывода типа.

Вот важная проблема, которая все еще остается открытой: каков наилучший способ интеграции Обобщенных алгебраических типов данных в вывод типа Хиндли-Милнера? Каждый год Саймон Пейтон Джонс предлагает новые ответы, которые, предположительно, лучше, чем ответы предыдущего года. Я не читал мартовскую версию 2009 года и поэтому не могу сказать, верю ли я, что она будет окончательной.

5 голосов
/ 09 августа 2009

Система зависимого от значения типа (или, короче говоря, система зависимого типа) может описывать типы, которые говорят что-то вроде: «Во время оценки (времени выполнения) значение этой переменной всегда будет равно значению этой переменной , который вычисляется с другим процессом оценки ". Автоматическое выведение этого типа из кода влечет за собой автоматическое доказательство теорем. Если набор теорем, которые вы можете выразить, ограничен автоматически доказываемыми, это не будет проблемой, но в случае языков с зависимой типизацией это обычно не так.

Таким образом, у систем с зависимой типизацией не может быть общего (и полного) вывода типа.

Я уверен, что кто-то может дать моральный формальный и полный ответ ...

...