Forma corretta di letrec nel sistema di tipo Hindley-Milner?

Question

Sto avendo difficoltà a capire la definizione letrec per HM sistema che viene data su Wikipedia, qui: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Recursive_definitions

Per me, la regola si traduce approssimativamente il seguente algoritmo:

1. tipi inferire su tutto a la parte letrec definizione
   1. assegnare variabili di tipo temporanee per ogni identificatore definito
   2. processare ricorsivamente tutte le definizioni delle tipologie temporanee
   3. a coppie, unificare i risultati con le variabili temporanee originali
2. stretta (con forall) i tipi suggeriti, aggiungerli alla base (contesto) e dedurre tipi della parte espressione con esso

ho problemi con un programma come questo:

letrec 
p = (+)  --has type Uint -> Uint -> Uint 
x = (letrec 
     test = p 5 5 
    in test) 
in x 

Il comportamento che sto osservando è la seguente:

• definizione di p ottiene tipo temporaneo a
• definizione di x ottiene un certo tipo temporaneo troppo, ma che è fuori del nostro ambito adesso
• in x, definizione di test ottiene un tipo temporaneo t
• p ottiene il tipo temporaneo a dall'ambito, utilizzando la regola HM per una variabile
• (f 5) viene elaborato dalla regola HM per l'applicazione, il tipo risultante è b (e l'unificazione (a unifica con Uint -> b)
• ((p 5) 5) viene processato dalla stessa norma, con conseguente più unificazione e digitare c, a ora in seguito unifica con Uint -> Uint -> c
• ora, prova viene chiuso per digitare forall c.c
• prova variabile in test ottiene l'istanza tipo (o forall c.c) con variabili freschi, accrodingly alla regola HM per variabile, con conseguente test :: d (che è unificato con test::t proprio sulla)
• risultante x ha effettivamente digitare d (o t, a seconda dell'umore di unificazione)

Il problema: x dovrebbe ovviamente avere tipo Uint, ma non vedo nessun modo quei due potevano mai unificare per produrre il tipo. C'è una perdita di informazioni quando il tipo di test viene chiuso e ripetuto di nuovo che non sono sicuro di come superare o connettersi con sostituzioni/unificazioni.

Qualche idea su come correggere l'algoritmo per produrre x::Uint digitando correttamente?O è una proprietà del sistema HM e semplicemente non scriverà un caso del genere (di cui dubito)?

Si noti che questo sarebbe perfettamente OK con lo standard let, ma non volevo offuscare l'esempio con definizioni ricorsive che non possono essere gestite da let.

Grazie in anticipo

Answer 1

rispondere alla mia domanda proprio:

La definizione sul Wiki è sbagliato, anche se funziona in qualche misura almeno per il controllo dei tipi.

Il modo più semplice e corretto per aggiungere la ricorsione al sistema HM è utilizzare il predicato fix, con la definizione fix f = f (fix f) e digitare forall a. (a->a) -> a. La ricorsione reciproca viene gestita da un doppio punto di correzione, ecc.

L'approccio Haskell al problema (descritto a https://gist.github.com/chrisdone/0075a16b32bfd4f62b7b#binding-groups) è (approssimativamente) per ricavare un tipo incompleto per tutte le funzioni e quindi eseguire nuovamente la derivazione per controllarle l'una contro l'altra.