Algoritmo Hindley-Milner: utilizzando i tipi per garantire che i Bindings siano applicati

Question

Implemendo l'algoritmo di inferenza del tipo Hindley-Milner, seguendo i tutorial di Mark Jones e Oleg Kiselyov . Entrambi questi hanno un funzionamento "Applica Bindings" con un tipo approssimativamente del modulo

applyBindings :: TyEnv -> Type -> Type

.

Che applica i Binding tyvar -> ty in TyEnv al Type indicato. Ho trovato un errore comune nel mio codice per dimenticare di chiamare applyBindings e non ottengo alcun aiuto dal sistema di tipo Haskell, poiché ty ha lo stesso tipo di applyBindings tyenv ty. Sto cercando un modo per far rispettare il seguente invariante nel sistema Tipo:

.

Quando si esegue l'inferenza del tipo, le associazioni devono essere applicate prima di restituire un risultato 'finale'

Quando si esegue il tipo di inferenza per una lingua monomorfica dell'oggetto, c'è un modo naturale per far ciò, come implementato in Wren NG Thornton's Pacchetto unificabile-fd : Definiamo due tipi di dati per 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 dare applyBindings il tipo

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

.

(questa funzione è in realtà freeze . applyBindings in UniFister-FD). Ciò impone il nostro invariante - se dimentichiamo di generarecodicitagcode, allora otterremo un errore di tipo.

Questo è il tipo di soluzione che sto cercando, ma per le lingue degli oggetti con polimorfismo. L'approccio di cui sopra, poiché si trova, non si applica, poiché i nostri tipi di linguaggio dell'oggetto possono avere variabili di tipo - in effetti, se ci sono variabili gratuite dopo aver applicato i binding, non vogliamo restituire applyBindings, ma vogliamo generalizzare su queste variabili.

C'è una soluzione lungo le linee che descrivo, cioè uno che dà Nothing un tipo diverso da applyBindings? I veri compilatori usano lo stesso pungente (tra variabili di unificazione e variabili di tipo di linguaggio oggetto) che fanno i tutorial di Mark's e Oleg?

Answer 1

Sto prendendo una pugnalata nel buio qui, perché penso che ci siano altri problemi con la soluzione che proponi, ma posso affrontare almeno una difficoltà:

.
• Il tuo tipo di controllo dovrebbe avere differenziazione rappresentazioni per unificazione tipo variabili e Variabili del tipo di linguaggio dell'oggetto .

Questa variazione non è difficile da implementare, e in effetti penso che il controllo del tipo GHC abbia funzionato in questo modo, almeno in una volta.Potresti voler controllare la carta Inferenza di tipo pratico per arbitrario-Ri tipi ;L'appendice contiene un sacco di codice molto utile.