Каковы пределы вывода типа?

Ответ 1

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

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

Ответ 2

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

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

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