Об алгоритме вывода типов рекурсивных функций

#рекурсия #scala #f# #ocaml #теория_типов

В Scala не реализован вывод типов для рекурсивных функций, в качестве аргумента Кей
Хорстман в своей книжки пишет что "Алгоритм Хиндли-Милнера не стабильно себя ведёт
в языках с ООП". Но, например, в F# и OCaml реализован вывод типов для рекурсивных
функций и возникают вопросы: что же тогда имел ввиду Кей Хорстман? Есть ли примеры
программ на ООП языке в которых алгоритм даёт сбой(ошибка согласованности типов в рантайме
при успешно пройденной проверке типов на этапе компиляции)? Или косяк именно в каких-то
особенностях Scala?
    

Ответы

Ответ 1

Система типов Scala однозначно содержит F \sub.
Вероятно содержит намного больше (это сейчас активное направление исследований у нас)
но уже в F \sub многие вопросы, и в том числе этот - неразрешимая задача.

Ссылка на статью 

Если честно, я не знаю как это работает в F# и OCaml. Думаю они делают best-effort.