Hindley-Milner algoritmo:o uso de tipos para garantir ligações são aplicadas

Question

Estou implementando o Hindley-Milner inferência de tipo de algoritmo, seguindo os tutoriais de Mark Jones e Oleg Kiselyov.Ambos têm uma "aplicar ligações" operação com um tipo de aproximadamente de forma

applyBindings :: TyEnv -> Type -> Type

que se aplica a tyvar -> ty ligações em TyEnv para o dado Type.Eu achei um erro comum no meu código para esqueça de chamar applyBindings, e eu não recebo ajuda de Haskell tipo de sistema, pois ty tem o mesmo tipo applyBindings tyenv ty.Eu estou procurando uma maneira de aplicar os seguintes invariantes no tipo de sistema:

ao fazer a inferência de tipo, as ligações devem ser aplicados antes de devolver um 'final' resultado

Ao fazer a inferência de tipo para um monomorphic objeto de linguagem, não há uma maneira natural de impor isso, como implementado no wren ng thornton unificação-fd pacote:podemos definir dois tipos de dados para Types:

-- | Types not containing unification variables
type Type = ...          -- (Fix TypeF) in wren's package

-- | Types possibly containing unification variables
type MutType = ...       -- (MutTerm IntVar TypeF) in wren's package

e dar applyBindings o tipo de

-- | Apply all bindings, returning Nothing if there are still free variables
-- otherwise just
applyBindings :: TyEnv -> MutType -> Maybe Type

(esta função é, na verdade, freeze . applyBindings na unificação-fd).Isso reforça nossa invariável - se nós se esqueça de applyBindings, e , em seguida, teremos um tipo de erro.

Este é o tipo de solução que eu estou procurando, mas para o objeto de idiomas com o polimorfismo.A abordagem acima, como está, não se aplica, uma vez que nosso objeto-linguagem de tipos podem ter variáveis de tipo -- de fato, se as variáveis livres após a aplicação de ligações, nós não quero voltar Nothing, mas nós queremos generalizar sobre estas variáveis.

Existe uma solução ao longo das linhas e descrever, por exemplo,aquele que dá applyBindings um tipo diferente de const id?Fazer real compiladores usam o mesmo punning (entre unificação e variáveis de objeto-tipo de idioma de variáveis) que Marcos e Oleg do tutoriais fazer?

Answer 1

Eu estou tomando uma facada no escuro aqui, porque eu acho que pode haver outros problemas com a solução que você propõe, mas posso abordar, no mínimo, uma dificuldade:

• O seu tipo verificador deve ter diferentes representações para unificação de variáveis do tipo e objeto-linguagem de variáveis do tipo.

Esta variação não é difícil de implementar, e na verdade eu acho que o GHC tipo verificador trabalhou desta forma, pelo menos uma vez.Você pode querer verificar para o papel Prático Tipo de Inferência Arbitrária-Classificação de Tipos de;o apêndice contém uma grande quantidade de código útil.