Я реализую алгоритм вывода типа Hindley-Milner, следуя учебникам Mark Jones и Олег Киселев. Оба они имеют операцию "применить привязки" с типом грубо формы
applyBindings :: TyEnv -> Type -> Type
который применяет привязки tyvar -> ty в TyEnv к данному Type. Я нашел ошибку в моем коде, чтобы забыть позвонить applyBindings, и я не получаю никакой помощи от системы типа Haskell, так как ty имеет тот же тип, что и applyBindings tyenv ty. Я ищу способ обеспечить следующий инвариант в системе типов:
при выполнении вывода типа привязки должны применяться перед возвратом "окончательного" результата
При выполнении вывода типа для мономорфного объектного языка существует естественный способ обеспечения этого, как реализовано в wren ng thornton унификация-fd package: мы определяем два типа данных для Type s:
-- | Types not containing unification variables
type Type = ... -- (Fix TypeF) in wren package
-- | Types possibly containing unification variables
type MutType = ... -- (MutTerm IntVar TypeF) in wren package
и дайте applyBindings тип
-- | Apply all bindings, returning Nothing if there are still free variables
-- otherwise just
applyBindings :: TyEnv -> MutType -> Maybe Type
(эта функция фактически freeze . applyBindings в унификации-fd). Это обеспечивает наш инвариант - если мы забудем applyBindings, тогда мы получим ошибку типа.
Это то решение, которое я ищу, но для объектных языков с полиморфизмом. Вышеупомянутый подход, поскольку он существует, не применяется, так как наши типы объектного языка могут иметь переменные типа - действительно, если переменные свободны после применения привязок, мы не хотим возвращать Nothing, но мы хотим для обобщения по этим переменным.
Есть ли решение вдоль строк, которые я описываю, т.е. тот, который дает applyBindings другой тип из const id? Используют ли реальные компиляторы одни и те же казни (между переменными унификации и переменными типа объекта), которые делают учебники Mark и Oleg?
