Prawidłowa forma letrec w systemie typu Hindley-Milner?

Question

mam problemy ze zrozumieniem letrec definicję systemu HM, który jest podany na Wikipedii, tutaj: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Recursive_definitions

Dla mnie zasada przekłada się mniej więcej z następującym algorytmem:

1. typy wywnioskować na wszystko w część letrec definicja
   1. przypisać zmienne typu tymczasowe do każdego zdefiniowanego identyfikatora
   2. rekurencyjnie przetwarza wszystkie definicje z tymczasowych typów
   3. w parach, ujednolicenie wyników z oryginalnych zmiennych tymczasowych
2. blisko (z forall) to wywnioskować typy, dodaj je do podstawy (kontekst) i wnioskować rodzajów części wypowiedzi z nim

mam problem z programem jak to:

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

zachowanie ja obserwując się następująco:

• definicja p dostaje typu CZASOWA a
• definicja x dostaje jakąś tymczasową typ też, ale to jest poza naszym zakresem teraz
• w x, definicja test dostaje tymczasowy typu t
• p Pobiera tymczasowy typ a z zakresu, przy użyciu reguły HM dla zmiennej
• (f 5) jest przetwarzany przez regułę HM dla aplikacji, wynikowy typ to b (i unifikujacą (a łączy z Uint -> b)
• ((p 5) 5) zostanie przetworzona przez tej samej zasady, co prowadzi do większej liczby unifikacji i typu c, a się w wyniku łączy z Uint -> Uint -> c
• teraz, test zostaje zamknięty typu forall c.c
• zmienna test in test dostaje instancję typu (lub forall c.c) ze zmiennymi świeżych, accrodingly z zasadą HM do zmiennej, w wyniku test :: d (który jest zjednoczony z test::t tuż)
• Powstały x skutecznie wpisać d (lub t, w zależności od nastroju unifikacji)

problem: x powinien oczywiście mieć typ Uint, ale nie widzę sposób tych dwóch może kiedykolwiek ujednolicenia produkować typ. Następuje utrata informacji, gdy typ test zostaje zamknięty i ponownie instancja, że ​​nie jestem pewien, jak pokonać lub połączyć się z zastąpieniami/unifikacjami.

Każdy pomysł, w jaki sposób należy poprawić algorytm, aby prawidłowo pisać poprawnie?Czy jest to własność systemu HM i po prostu nie wpisuje takiego przypadku (w co wątpię)?

Zauważ, że byłoby to całkowicie w porządku ze standardem let, ale nie chciałem zaciemniać przykładu rekurencyjnymi definicjami, które nie mogą być obsługiwane przez let.

góry dzięki

Answer 1

odpowiedzi na moje własne pytanie:

definicja na Wiki jest źle, chociaż to działa do pewnego stopnia przynajmniej dla typu kontroli.

Najprostszym i poprawnym sposobem dodania rekurencji do systemu HM jest użycie predykatu fix o definicji fix f = f (fix f) i typu forall a. (a->a) -> a. Wzajemna rekurencja jest obsługiwana przez podwójny punkt ustalania, itp.

Podejście Haskella do problemu (opisane w https://gist.github.com/chrisdone/0075a16b32bfd4f62b7b#binding-groups) polega na (w przybliżeniu) wyprowadzeniu niekompletnego typu dla wszystkich funkcji, a następnie ponownym uruchomieniu wyprowadzenia, aby sprawdzić je względem siebie.