System typu Hindleya-Milnera

	Wyrażenia
	Typy
	Kontekst i
	zmienne typu

System typów Hindleya -Milnera ( HM ) jest klasycznym systemem typów dla rachunku lambda z polimorfizmem parametrycznym . Jest również znany jako Damas-Milner lub Damas-Hindley-Milner . Po raz pierwszy został opisany przez J. Rogera Hindleya , a później ponownie odkryty przez Robina Milnera . Luis Damas wniósł do swojej pracy doktorskiej szczegółową analizę formalną i dowód metody.

Wśród bardziej godnych uwagi właściwości HM jest jego kompletność i zdolność do wnioskowania o najbardziej ogólnym typie danego programu bez adnotacji typu dostarczanych przez programistę lub innych wskazówek. Algorytm W jest wydajną metodą wnioskowania typu w praktyce i został z powodzeniem zastosowany na dużych bazach kodu, chociaż ma dużą złożoność teoretyczną . HM jest preferowany dla języków funkcjonalnych . Po raz pierwszy został zaimplementowany jako część systemu typów języka programowania ML . Od tego czasu HM był rozszerzany na różne sposoby, przede wszystkim z klas typów , takimi jak te w Haskell .

Wstęp

Jako metoda wnioskowania o typach Hindley – Milner jest w stanie wydedukować typy zmiennych, wyrażeń i funkcji z programów napisanych w stylu całkowicie bez typów. Ponieważ zakres jest wrażliwy, nie ogranicza się do wyprowadzania typów tylko z niewielkiej części kodu źródłowego, ale raczej z kompletnych programów lub modułów. Możliwość radzenia sobie również z typami parametrycznymi jest podstawą systemów typów wielu funkcjonalnych języków programowania . Po raz pierwszy zastosowano go w ten sposób w ML .

Źródłem jest algorytm wnioskowania typu dla prostego rachunku lambda , który został opracowany przez Haskella Curry'ego i Roberta Feysa w 1958 r. ^{[ Potrzebne źródło ]} W 1969 r. J. Roger Hindley rozszerzył tę pracę i udowodnił, że ich algorytm zawsze wnioskował o najbardziej ogólnym typie . W 1978 roku Robin Milner , niezależnie od prac Hindleya, dostarczył równoważny algorytm, Algorithm W . W 1982 roku Luis Damas ostatecznie udowodnił, że algorytm Milnera jest kompletny i rozszerzył go, aby obsługiwał systemy z odniesieniami polimorficznymi.

Monomorfizm a polimorfizm

W rachunku lambda o prostym typie typy $T$ są albo stałymi typu atomowego, albo typami funkcji postaci ${\ displaystyle T \ rightarrow T}$ . Takie typy są monomorficzne . Typowymi przykładami są typy używane w wartościach arytmetycznych:

3 : Dodaj liczbę 3 4 : Dodaj liczbę : Liczba -> Liczba -> Liczba

W przeciwieństwie do tego, nietypowany rachunek lambda jest w ogóle neutralny dla pisania, a wiele jego funkcji można sensownie zastosować do wszystkich typów argumentów. Trywialnym przykładem jest funkcja tożsamości

id ≡ λ x . X

który po prostu zwraca dowolną wartość, do której jest zastosowany. Mniej trywialne przykłady obejmują typy parametryczne, takie jak listy .

Podczas gdy polimorfizm ogólnie oznacza, że operacje akceptują wartości więcej niż jednego typu, zastosowany tutaj polimorfizm jest parametryczny. W literaturze spotyka się również notację schematów typów , podkreślającą parametryczny charakter polimorfizmu. Dodatkowo, stałe mogą być wpisywane za pomocą zmiennych typu (kwantyfikowanych). Np:

minusy: ogólnie a. a -> List a -> List a nil : forall a . Podaj identyfikator: forall a . za -> za

Typy polimorficzne mogą stać się monomorficzne poprzez konsekwentne zastępowanie ich zmiennych. Przykładami instancji monomorficznych są:

id' : String -> String nil' : Numer listy

Mówiąc bardziej ogólnie, typy są polimorficzne, gdy zawierają zmienne typu, podczas gdy typy bez nich są monomorficzne.

W przeciwieństwie do systemów typów używanych na przykład w Pascalu (1970) lub C (1972), które obsługują tylko typy monomorficzne, HM jest zaprojektowany z naciskiem na polimorfizm parametryczny. Następcy wspomnianych języków, jak C++ (1985), koncentrowali się na różnych typach polimorfizmu, a mianowicie podtypowaniu w połączeniu z programowaniem obiektowym i przeciążaniu . Chociaż podtypowanie jest niezgodne z HM, wariant systematycznego przeciążania jest dostępny w opartym na HM systemie typów Haskell.

Niech polimorfizm

Rozszerzając wnioskowanie o typ dla prostego rachunku lambda w kierunku polimorfizmu, należy określić, kiedy dopuszczalne jest wyprowadzenie egzemplarza wartości. Idealnie byłoby to dozwolone przy dowolnym użyciu zmiennej powiązanej, jak w:

(λ id . ... (id 3) ... (id "tekst") ... ) (λ x . x)

Niestety, wnioskowanie typu w polimorficznym rachunku lambda nie jest rozstrzygalne. Zamiast tego HM zapewnia let-polimorfizm formy

  niech  id = λ x . x   w  ... (identyfikator 3) ... (identyfikator "tekst") ...

ograniczenie mechanizmu wiązania w rozszerzeniu składni wyrażenia. Tylko wartości związane w konstrukcie let podlegają instancji, czyli są polimorficzne, podczas gdy parametry w abstrakcjach lambda są traktowane jako monomorficzne.

Przegląd

Pozostała część tego artykułu przebiega w następujący sposób:

Zdefiniowano system typu HM. Odbywa się to poprzez opisanie systemu dedukcji, który precyzuje, jakie wyrażenia mają jaki typ, jeśli w ogóle.
Stamtąd działa w kierunku implementacji metody wnioskowania o typie. Po wprowadzeniu wariantu powyższego systemu dedukcyjnego opartego na składni, szkicuje wydajną implementację (algorytm J), odwołując się głównie do metalologicznej intuicji czytelnika.
Ponieważ pozostaje kwestią otwartą, czy algorytm J rzeczywiście realizuje początkowy system dedukcji, wprowadza się mniej wydajną implementację (algorytm W) i sugeruje się jej zastosowanie w dowodzie.
Na koniec omówiono dalsze tematy związane z algorytmem.

Ten sam opis systemu dedukcji jest używany przez cały czas, nawet dla dwóch algorytmów, aby różne formy, w których metoda HM jest przedstawiona, były bezpośrednio porównywalne.

System typów Hindleya-Milnera

System typów można formalnie opisać za pomocą reguł składni , które ustalają język dla wyrażeń, typów itp. Prezentacja takiej składni nie jest tutaj zbyt formalna, ponieważ nie jest spisana w celu studiowania gramatyki powierzchniowej , ale raczej gramatyka głębi i pozostawia pewne szczegóły składniowe otwarte. Taka forma prezentacji jest normalna. Opierając się na tym, reguły pisania są używane do definiowania, w jaki sposób wyrażenia i typy są powiązane. Tak jak poprzednio, zastosowana forma jest nieco liberalna.

Składnia

Wyrażenia, które należy wpisać, są dokładnie tymi z rachunku lambda rozszerzonego o wyrażenie let, jak pokazano w sąsiedniej tabeli. Aby ujednoznacznić wyrażenie, można użyć nawiasów. Aplikacja jest lewostronna i wiąże się silniej niż abstrakcja lub konstrukcja typu let-in.

Typy są składniowo podzielone na dwie grupy, monotypy i politypy.

Monotypy

Monotypy zawsze oznaczają określony typ. Monotypy $terminy$ reprezentowane składniowo jako .

Przykłady monotypów obejmują $takie$ $,$ oraz , ${\ Displaystyle {\ mathtt {Mapa \ (zestaw \ ciąg) \ int}}}$ . Te ostatnie typy to przykłady zastosowań funkcji typu, na przykład ze zbioru ${\ Displaystyle \ {{\ mathtt {Mapa ^ {2}, \ Set^{1},\ string^{0},\ int^{0}}},\ \rightarrow ^{2}\}}$ , gdzie indeks górny wskazuje liczbę parametrów typu. Kompletny zestaw funkcji typu $dowolny$ w HM, z wyjątkiem tego, że jest musi zawierać co $.$ funkcji Dla wygody jest często zapisywany w notacji infiksowej. $_$ funkcja _ Ponownie, nawiasy mogą być użyte do ujednoznacznienia wyrażenia typu. Aplikacja wiąże się mocniej niż strzałka wrostka, która jest łączona w prawo.

Zmienne typu są akceptowane jako monotypy. Monotypów nie należy mylić z typami monomorficznymi, które wykluczają zmienne i dopuszczają tylko warunki podstawowe.

Dwa monotypy są równe, jeśli mają identyczne terminy.

Politypy

Politypy (lub schematy typów ) to typy zawierające zmienne ograniczone przez zero lub więcej kwantyfikatorów dla wszystkich, np. ${\ Displaystyle \ forall \ alfa. \ alfa \ rightarrow \ alfa}$ .

Funkcja z politypem ${\ Displaystyle \ forall \ alfa . \ alfa \ rightarrow \ alfa}$ może odwzorować na siebie dowolną wartość tego samego typu, a funkcja tożsamości jest wartością dla tego typu.

Jako inny przykład, ${\ Displaystyle \ forall \ alfa . ({\ mathtt {zbiór}} \ \ alfa) \ rightarrow {\ mathtt {int}}} jest typem$ funkcji odwzorowującej wszystkie zbiory skończone do liczb całkowitych. Funkcja, która zwraca liczność zbioru, byłaby wartością tego typu.

Kwantyfikatory mogą pojawiać się tylko na najwyższym poziomie. Na przykład typ ${\ Displaystyle \ forall \ alfa . \ alfa \ rightarrow \ forall \ alfa . \ alfa}$ jest wykluczone przez składnię typów. Do politypów zaliczamy również monotypy, a więc typ ma postać ogólną ${\ Displaystyle \ forall \ alpha _ {1} \ kropki \ forall \ alpha _ {n}. \ tau, n \ geq 0}$ , gdzie ${\ displaystyle \ tau}$ jest monotypem.

$-konwersja$ zależy od zmiany kolejności kwantyfikacji i zmiany nazwy skwantyfikowanych zmiennych ( ). Ponadto można odrzucić zmienne ilościowe, które nie występują w monotypie.

Kontekst i pisanie

Aby sensownie połączyć ze sobą wciąż rozłączne części (wyrażenia składniowe i typy), potrzebna jest trzecia część: kontekst. Składniowo $których$ to lista par $,$ przypisaniami założeniami lub powiązaniami , z każda para określa, że zmienna typ ${\ Displaystyle \ sigma _ {i}.}$ Wszystkie trzy części łącznie dają ocenę pisania na temat formy $\ e: \ sigma}$ $vdash$ , stwierdzając, że przy założeniach wyrażenie ma typ $\ sigma}$ $displaystyle$ .

Wolne zmienne typu

W typie $\ forall \ alfa _ {n}. \ tau} ,$ $\ alpha _ {i}}$ symbol jest kwantyfikatorem wiążącym zmienne typu $Displaystyle$ w monotypii ${\ Displaystyle \ tau}$ . Zmienne nazywane są ilościowymi $,$ zmiennej typu ilościowego w ${\ displaystyle \ tau}$ nazywa się związanymi , a wszystkie niezwiązane zmienne typu w ${\ displaystyle \ tau}$ nazywane są wolnymi . Oprócz kwantyfikacji $politypach$ , zmienne typu mogą być również wiązane przez występowanie w kontekście, ale z odwrotnym efektem po prawej stronie ⊢ $vdash}$ . Takie zmienne zachowują się wtedy jak stałe typu. Wreszcie zmienna typu może zgodnie z prawem występować niezwiązana podczas pisania, w którym to przypadku są one niejawnie określane ilościowo.

Obecność zarówno powiązanych, jak i niezwiązanych zmiennych typu jest nieco rzadka w językach programowania. Często wszystkie zmienne typu są niejawnie traktowane w całości ilościowo. Prologu nie ma klauzul z wolnymi zmiennymi . Podobnie w Haskell, gdzie wszystkie zmienne typu implicite występują skwantyfikowane, tj. typ Haskella a -> a oznacza ${\ Displaystyle \ forall \ alfa. \ alfa \ rightarrow \ alpha}$ tutaj. Powiązany, a także bardzo rzadki, jest wiążący efekt prawej strony ${\ displaystyle \ sigma}$ zadań.

Zazwyczaj połączenie zmiennych typu związanego i niezwiązanego pochodzi z użycia zmiennych wolnych w wyrażeniu. Stała funkcja K = ${\ displaystyle \ lambda x. \ lambda yx}$ zawiera przykład. Ma monotyp ${\ Displaystyle \ alfa \ rightarrow \ beta \ rightarrow \ alpha}$ . Można wymusić polimorfizm przez ${\ Displaystyle \ mathbf {nie} \ k = \ lambda x. (\ mathbf {nie} \ f = \ lambda yx \ \ mathbf {w} \ f) \ \ mathbf {w} \k}$ . Tutaj ${\ displaystyle f}$ ma typ ${\ Displaystyle \ forall \ gamma. \ gamma \ rightarrow \ alfa}$ . Wolna zmienna monotypowa ${\ displaystyle \ alpha}$ pochodzi od typu zmiennej $otaczającym$ zakresem. ${\ displaystyle k}$ ma typ ${\ Displaystyle \ forall \ alpha \ forall \ beta. \ alpha \ rightarrow \ beta \ rightarrow \ alpha}$ . Można sobie $,$ że zmienna typu wolnego $typie$ jest związana przez ${\ displaystyle \ forall \ alpha}$ w typie ${\ displaystyle k}$ . Ale takiego zakresu nie można wyrazić w HM. Wiązanie jest raczej realizowane przez kontekst.

Wpisz kolejność

Polimorfizm oznacza, że jedno i to samo wyrażenie może mieć (być może nieskończenie) wiele typów. Ale w tym systemie typów te typy nie są całkowicie niepowiązane, ale raczej zaaranżowane przez polimorfizm parametryczny.

Na przykład tożsamość ${\ Displaystyle \ lambda xx}$ może mieć ${\ Displaystyle \ forall \ alfa . \ alfa \ rightarrow \ alfa}$ jako jego typ, a także ${\ Displaystyle {\ texttt {string}} \ rightarrow {\ texttt {string}}}$ lub ${\ Displaystyle {\ texttt {int}} \ rightarrow {\ texttt {int}}}$ i wiele innych, ale nie ${\ Displaystyle {\ texttt {int}} \ rightarrow {\ texttt {string}}}$ . Najbardziej ogólnym typem dla tej funkcji jest ${\ Displaystyle \ forall \ alfa . \ alfa \ rightarrow \ alpha}$ , podczas gdy inne są bardziej szczegółowe i można je wyprowadzić z ogólnego, konsekwentnie zastępując inny typ parametru typu , tj. Zmienną ilościową ${\ styl wyświetlania \alpha}$ . Kontrprzykład kończy się niepowodzeniem, ponieważ zamiana nie jest spójna.

Konsekwentne zastępowanie można uczynić formalnym, stosując podstawienie ${\ Displaystyle S = \ lewo \ {\ a_ {i} \ mapsto \ tau _ {i}, \ \ kropki \ \ prawo \}}$ do terminu typu $}$ napisanego ${\ Displaystyle S \ tau$ . Jak sugeruje przykład, podstawienie jest nie tylko silnie związane z porządkiem, który wyraża, że dany typ jest mniej lub bardziej wyjątkowy, ale także z całą kwantyfikacją, która pozwala na zastosowanie podstawienia.

$\ sqsubseteq \ sigma} ,$ typ jest bardziej ogólny niż , formalnie ${\ Displaystyle \$ $sigma$ jakaś zmienna ilościowa w ${\ displaystyle \ sigma '} jest$ $konsekwentnie$ zastępowany tak, że zyskuje się, pokazano na pasku bocznym. Ta kolejność jest częścią definicji typu systemu typów.

$_$ ${\ Displaystyle \ forall \ alfa. \ alfa \ rightarrow \ alfa \ sqsubseteq {\ texttt {ciąg}} \ rightarrow {\ texttt {ciąg}}}$ podstawienia ∀ .

Podczas gdy zastąpienie zmiennej ilościowej typem monomorficznym (podstawowym) jest proste, zastąpienie politypu wiąże się z pewnymi pułapkami spowodowanymi obecnością wolnych zmiennych. W szczególności niezwiązane zmienne nie mogą być zastępowane. Są one tutaj traktowane jako stałe. Ponadto kwantyfikacje mogą zachodzić tylko na najwyższym poziomie. Zastępując typ parametryczny, należy podnieść jego kwantyfikatory. Tabela po prawej stronie precyzuje regułę.

Alternatywnie, rozważ równoważną notację dla politypów bez kwantyfikatorów, w których skwantyfikowane zmienne są reprezentowane przez inny zestaw symboli. W takiej notacji specjalizacja sprowadza się do zwykłego, spójnego zastępowania takich zmiennych.

Relacja $porządkiem$ częściowym i $najmniejszym$ _ jest elementem.

Główny typ

Chociaż specjalizacja schematu typów jest jednym z zastosowań kolejności, odgrywa ona kluczową drugą rolę w systemie typów. Wnioskowanie o typie z polimorfizmem staje przed wyzwaniem podsumowania wszystkich możliwych typów, jakie może mieć wyrażenie. Kolejność gwarantuje, że takie podsumowanie istnieje jako najbardziej ogólny typ wyrażenia.

Podstawy w typowaniach

Zdefiniowaną powyżej kolejność typów można rozszerzyć na typowanie, ponieważ implikowana pełna kwantyfikacja wpisów umożliwia spójną wymianę:

{\ Displaystyle \ Gamma \ vdash e: \ sigma \ quad \ Longrightarrow \ quad S \ Gamma \ vdash e: S \ sigma}

W przeciwieństwie do reguły specjalizacji, nie jest to częścią definicji, ale podobnie jak ukryta wszechkwantyfikacja jest raczej konsekwencją reguł typów zdefiniowanych dalej. Zmienne typu wolnego w typowaniu służą jako symbole zastępcze dla ewentualnego udoskonalenia. Wiążący wpływ środowiska na zmienne typu wolnego po prawej stronie, $specjalizacji,$ ponownie polega na tym, że zamiana musi być spójna i musiałaby obejmować całe typowanie.

W tym artykule omówimy cztery różne zestawy reguł:

system deklaratywny ${\ displaystyle \ vdash _ {D}}$
$_$ składniowy
${\ Displaystyle \ vdash _ {J}}$ algorytm
${\ Displaystyle \ vdash _ {W}}$ algorytm

System dedukcyjny

Składnia HM jest przenoszona do składni reguł wnioskowania , które tworzą ciało systemu formalnego , poprzez użycie typowania jako sądów . Każda z reguł określa, jaki wniosek można wyciągnąć z jakich przesłanek. Oprócz orzeczeń jako przesłanek można użyć również niektórych dodatkowych przesłanek wprowadzonych powyżej.

Dowód z wykorzystaniem reguł to taka sekwencja sądów, w której wszystkie przesłanki są wymienione przed konkluzją. Poniższe przykłady pokazują możliwy format dowodu. Od lewej do prawej, każda linia pokazuje wniosek, zastosowaną regułę i przesłanki, odnosząc się do wcześniejszej linii (liczby), jeśli $Displaystyle [{\ mathtt {Nazwa}}]}$ przesłanką jest osąd lub wyraźne sformułowanie orzeczenia.

Zasady pisania

System reguł
${\ Displaystyle {\ rozpocząć {tablica} {cl} \ Displaystyle {\ Frac {x: \ sigma \ in \ Gamma}} {\ Gamma \ vdash _ {D} x: \ sigma}} i [{\ mathtt {Var} }] \\\\\ Displaystyle {\ Frac {\ Gamma \ vdash _ {D} e_ {0}: \ tau \ rightarrow \ tau '\ quad \ quad \ Gamma \ vdash _ {D} e_ {1}: \ tau }{\ Gamma \ vdash _ {D} e_ {0} \ e_ {1}: \ tau '}} & [{\ mathtt {aplikacja}}] \\\\\ Displaystyle {\ frac {\ gamma, \ ;x:\tau \vdash _{D}e:\tau '}{\Gamma \vdash _{D}\lambda \ x\ .\ e:\tau \rightarrow \tau '}}&[{\mathtt { Abs}}] \\\\\\ Displaystyle {\ Frac {\ Gamma \ vdash _ {D} e_ {0}: \ sigma \ quad \ quad \ Gamma, \, x: \ sigma \ vdash _ {D} e_ { 1}:\tau }{\Gamma \vdash _{D}{\mathtt {let}}\ x=e_{0}\ {\mathtt {w}}\ e_{1}:\tau }}&[{ \mathtt {Niech}}] \\\\\\\ Displaystyle {\ Frac {\ Gamma \ vdash _ {D} e: \ sigma '\ quad \ sigma ' \ sqsubseteq \ sigma } {\ Gamma \ vdash _ {D } e: \ sigma }} & [{\ mathtt {Inst}}] \\\\\ Displaystyle {\ Frac {\ Gamma \ vdash _ {D} e: \ sigma \ quad \ alfa \ notin {\ text {free }}(\Gamma )}{\Gamma \vdash _{D}e:\forall \ \alpha \ .\ \sigma }}&[{\mathtt {Gen}}]\\\\\end{array}} }$

Ramka boczna pokazuje zasady dedukcji systemu typu HM. Zasady można z grubsza podzielić na dwie grupy:

Pierwsze cztery reguły $\$ $aplikacja}}]}$ Displaystyle ( aplikacja , tj. wywołanie funkcji z jednym parametrem), ${\ Displaystyle [{\ mathtt {Abs}}]}$ ( abstrakcja , tj. deklaracja funkcji) i ${\ Displaystyle [{\ mathtt {Niech}} ]}$ (deklaracja zmiennej) są skupione wokół składni, prezentując jedną regułę dla każdej z form wyrażeń. Ich znaczenie jest oczywiste na pierwszy rzut oka, ponieważ rozkładają każde wyrażenie, udowadniają ich podwyrażenia i ostatecznie łączą poszczególne typy znalezione w przesłankach z typem we wniosku.

$\ mathtt {Gen}$ tworzą pozostałe dwie reguły $}$ [ . Zajmują się specjalizacją i uogólnieniem typów. gdy reguła $powyższej$ sekcji [ ] ${\ displaystyle [{\ mathtt {Gen}}]}$ uzupełnia poprzednie, działając w przeciwnym kierunku. Pozwala na uogólnienie, tj. kwantyfikację zmiennych monotypowych niezwiązanych z kontekstem.

Poniższe dwa przykłady ilustrują działanie systemu reguł. Ponieważ podane jest zarówno wyrażenie, jak i typ, są one sprawdzaniem typów przy użyciu reguł.

Przykład : dowód na gdzie ${\ Displaystyle \ Gamma \ vdash _ {D} id (n): int}$ gdzie ${\ Displaystyle \ Gamma = id: \ forall \ alfa . \ alfa \ rightarrow \ alfa, \ n: int}$ , można zapisać

{\ Displaystyle {\ rozpocząć {tablica} {llll} 1: & \ Gamma \ vdash _ {D} id: \ forall \ alfa. \ alfa \ rightarrow \ alfa & [{\ mathtt {Var}}] & (id: \forall \alpha .\alpha \rightarrow \alpha \in \Gamma )\\2:&\Gamma \vdash _{D}id:int\rightarrow int&[{\mathtt {Inst}}]&(1),\ (\forall \alpha .\alpha \rightarrow \alpha \sqsubseteq int\rightarrow int)\\3:&\Gamma \vdash _{D}n:int&[{\mathtt {Var}}]&(n:int\ w \Gamma )\\4:&\Gamma \vdash _{D}id(n):int&[{\mathtt {aplikacja}}]&(2),\ (3)\\\end{array}}}

Przykład : Aby zademonstrować uogólnienie, ${\ Displaystyle \ vdash _ {D} \ {\ textbf {niech}} \, id = \ lambda xx \ {\ textbf {w}} \ id \,: \, \ dla wszystkich \ alfa. \ alfa \ strzałka w prawo \alpha }$ jest pokazana poniżej:

{\ Displaystyle {\ rozpocząć {tablica} {llll} 1:& x: \ alfa \ vdash _ {D} x: \ alfa i [{\ mathtt {Var}}] i (x: \ alfa \ w \ lewo \ { x:\alpha \right\})\\2:&\vdash _{D}\lambda xx:\alpha \rightarrow \alpha &[{\mathtt {Abs}}]&(1)\\3:&\ vdash _{D}\lambda xx:\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Gen}}]&(2),\ (\alpha \not \in free(\epsilon ))\ \4:&id:\forall \alpha .\alpha \rightarrow \alpha \vdash _{D}id:\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Var}}]&(id:\ forall \alpha .\alpha \rightarrow \alpha \in \left\{id:\forall \alpha .\alpha \rightarrow \alpha \right\})\\5:&\vdash _{D}{\textbf {niech }}\,id=\lambda xx\ {\textbf {w}}\ id\,:\,\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Niech}}]&(3), \ (4)\\\koniec{tablica}}}

Niech polimorfizm

Niewidoczny od razu, zestaw reguł koduje regulację, w jakich okolicznościach typ może zostać uogólniony lub nie przez nieco zmieniające się użycie mono- i politypów w regułach. [ ZA b s ] {\ ${Abs}}] }$ i ${\ Displaystyle [{\ mathtt {Niech}}]}$ . Pamiętaj, że $i$ odpowiednio $.$ i monotypy

W $_$ , ${\ Displaystyle \ lambda xe}$ jest dodawany do kontekstu z typem monomorficznym poprzez założenie $\ Displaystyle \ Gamma, \ x: \ tau \ vdash _ {D} e: \tau '}$ , podczas gdy w regule ${\ Displaystyle [{\ mathtt {Niech}}]}$ , zmienna wchodzi do środowiska w postaci polimorficznej ${\ Displaystyle \ Gamma, \ x: \ sigma \ vdash _ {D} e_{1}:\tau }$ . Chociaż w obu przypadkach obecność $użycie$ reguły uogólnienia dla dowolnej wolnej zmiennej w przypisaniu, ta regulacja wymusza typ parametru $x}$ λ $\lambda }$ $displaystyle$ -expression, aby pozostać monomorficznym, podczas gdy w let-expression zmienną można wprowadzić jako polimorficzną, umożliwiając specjalizacje.

W konsekwencji tej regulacji ${\ Displaystyle \ lambda f. (f \, {\ textrm {true}}, f \, {\ textrm {0}})} nie można$ wpisać, ponieważ parametr ${\ displaystyle f}$ jest w pozycji monomorficznej, natomiast ${\ Displaystyle {\ textbf {niech}} \ f = \ lambda xx \ {\ textbf {w}} \ (f \ {\ textrm {prawda}}, f \, {\textrm {0}})}$ ma typ ${\ Displaystyle (bool, int)}$ $,$ ponieważ wprowadzony w wyrażeniu let i dlatego jest traktowany jako polimorficzny.

Reguła uogólnienia

Warto również bliżej przyjrzeć się zasadzie uogólnienia. Tutaj cała kwantyfikacja zawarta w przesłance jest po prostu przenoszona $}$ prawą stronę ${\ Displaystyle \ Gamma \ vdash e: \$ wniosek. Jest to możliwe, ponieważ ${\ displaystyle \ alpha}$ nie występuje swobodnie w kontekście. Ponownie, chociaż czyni to regułę uogólnienia wiarygodną, tak naprawdę nie jest to konsekwencją. Wręcz przeciwnie, reguła uogólnienia jest częścią definicji systemu typów HM, a niejawna kwantyfikacja jest jej konsekwencją.

Algorytm wnioskowania

Teraz, gdy system dedukcji HM jest już pod ręką, można przedstawić algorytm i zweryfikować go pod względem reguł. Alternatywnie, możliwe może być wyprowadzenie tego poprzez bliższe przyjrzenie się, w jaki sposób reguły wchodzą w interakcje i powstają dowody. Jest to zrobione w dalszej części tego artykułu, skupiając się na możliwych decyzjach, które można podjąć, udowadniając pisanie na klawiaturze.

Stopnie swobody wybór reguł

Wyodrębniając punkty w dowodzie, gdzie żadna decyzja nie jest w ogóle możliwa, pierwsza grupa reguł skupionych wokół składni nie pozostawia wyboru, ponieważ każdej regule składniowej odpowiada unikalna reguła typowania, która określa część dowodu, natomiast pomiędzy konkluzją $Gen}}$ przesłanki tych stałych łańcuchów części $\$ { może się zdarzyć. Taki łańcuch mógłby również istnieć między konkluzją dowodu a regułą najwyższego wyrażenia. Wszystkie odbitki muszą mieć tak naszkicowany kształt.

Ponieważ jedynym wyborem w dowodzie w odniesieniu do wyboru reguł są ${\ Displaystyle [{\ mathtt {Inst}}]}$ i ${\ Displaystyle [{\ mathtt {Gen}} ]}$ łańcuchów, forma dowodu nasuwa pytanie, czy można go uściślić tam, gdzie łańcuchy te mogą nie być potrzebne. Jest to w rzeczywistości możliwe i prowadzi do wariantu systemu reguł bez takich reguł.

System reguł sterowanych składnią

${\ Displaystyle {\ rozpocząć {tablica} {cl} \ Displaystyle {\ Frac {x: \ sigma \ in \ Gamma \ quad \ sigma \ sqsubseteq \ tau} {\ Gamma \ vdash _ {S} x: \ tau}} & [{\ mathtt {Var}}] \\\\\ Displaystyle {\ Frac {\ Gamma \ vdash _ {S} e_ {0}: \ tau \ strzałka w prawo \ tau '\ quad \ quad \ Gamma \ vdash _ { S}e_{1}:\tau}{\Gamma \vdash _{S}e_{0}\ e_{1}:\tau '}}&[{\mathtt {aplikacja}}]\\\\\displaystyle {\frac {\Gamma ,\;x:\tau \vdash _{S}e:\tau '}{\Gamma \vdash _{S}\lambda \ x\ .\ e:\tau \rightarrow \tau ' }}& [{\ mathtt {Abs}}] \\\\\ Displaystyle {\ Frac {\ Gamma \ vdash _ {S} e_ {0}: \ tau \ quad \ quad \ Gamma, \, x: {\ bar {\Gamma }}(\tau )\vdash _{S}e_{1}:\tau '}{\Gamma \vdash _{S}{\mathtt {let}}\ x=e_{0}\ { \mathtt {w}}\ e_{1}:\tau '}}&[{\mathtt {Niech}}]\end{tablica}}}$
składniowych
Uogólnienie
${\ Displaystyle {\ bar {\ Gamma}} (\ tau) = \ forall \ {\ kapelusz {\ alfa}} \ \ \ tau \ quad \ quad { \hat {\alpha}}={\textrm {wolne}}(\tau)-{\textrm {wolne}}(\Gamma)}$

Współczesne podejście do HM wykorzystuje jako krok pośredni system reguł oparty wyłącznie na składni, dzięki Clementowi. W tym systemie specjalizacja znajduje się bezpośrednio po oryginalnej $\ Displaystyle [{\ mathtt {Var$ $} styl wyświetlania [{\mathtt {niech}}]}$ połączona, podczas gdy uogólnienie staje się częścią reguły [ reguła. Tam uogólnienie jest również zdeterminowane, aby zawsze generować najbardziej ogólny typ przez wprowadzenie funkcji ${\ Displaystyle {\ bar {\ Gamma}} (\ tau)}$ , który określa ilościowo wszystkie zmienne monotypowe niezwiązane w ${\ displaystyle \ Gamma}$ .

Formalnie, aby potwierdzić, że ten nowy system reguł jest równoważny $displaystyle \ vdash _ {D}}$ oryginalnym $\$ , trzeba pokazać, ${\ Displaystyle \ Gamma \ vdash _ {D} \ e: \ sigma \ Leftrightarrow \ Gamma \ vdash _ {S} \ e: \ sigma} , który$ rozkłada się na dwa dowody podrzędne:

$_$ _ _ _
$_$ _ _ _

$]}$ , rozkładając reguły i $mathtt {Var$ $displaystyle \ vdash _ {S}}$ ⊢ ${$ $,$ $w$ prawdopodobnie widać, że niekompletny, ponieważ nie można pokazać ${\ Displaystyle \ lambda \ xx: \ forall \ alfa . \ alfa \ rightarrow \ alfa}$ w ${\ Displaystyle \ vdash _ {S}}$ , na przykład, ale tylko ${\ Displaystyle \ lambda \ xx: \ alfa \ rightarrow \ alfa}$ . Możliwa jest jednak udowodnienie tylko nieco słabszej wersji kompletności, a mianowicie

$\ Displaystyle \ Gamma \ vdash _ {D} \ e: \ sigma \ Strzałka w prawo \ Gamma \ vdash _ {S} \ e: \tau \klin {\bar {\Gamma}}(\tau)\sqsubseteq \sigma}$

sugerując, że można wyprowadzić główny typ wyrażenia w, $pozwala$ ostatecznie uogólnić dowód.

Porównując i ${\ displaystyle \$ $vdash _ {S}} teraz tylko monotypy pojawiają$ w ocenach wszystkich reguł Dodatkowo kształt każdego możliwego dowodu z systemem dedukcji jest teraz identyczny z kształtem wyrażenia (oba widziane jako drzewa ). Zatem wyrażenie w pełni określa kształt dowodu. ⊢ ${\ displaystyle \ vdash _ {D}}$ kształt zostałby prawdopodobnie określony w odniesieniu do wszystkich reguł z ${\ Displaystyle [{\ mathtt {Inst}}]}$ i $\ displaystyle [{\ mathtt {Gen}}]}$ , które pozwalają budować dowolnie długie gałęzie (łańcuchy) między innymi węzłami.

Stopnie swobody określające reguły

Teraz, gdy znany jest kształt dowodu, jesteśmy już blisko sformułowania algorytmu wnioskowania typu. Ponieważ każdy dowód dla danego wyrażenia musi mieć ten sam kształt, można założyć, że monotypy w sądach dowodu są nieokreślone i zastanowić się, jak je określić.

Tutaj wchodzi w grę kolejność zastępowania (specjalizacji). Chociaż na pierwszy rzut oka nie da się określić typów lokalnie, jest nadzieja, że uda się je udoskonalić za pomocą kolejności podczas przechodzenia przez drzewo dowodowe, dodatkowo zakładając, że wynikowy algorytm ma stać się metodą wnioskowania, że w jakimkolwiek założeniu zostanie określona jako najlepsza z możliwych. sugeruje patrząc na zasady : ${\ displaystyle \ vdash _ {S}}$

$[Abs]$ : Krytycznym wyborem jest $τ$ . W tym momencie nic nie wiadomo o $τ$ , więc można przyjąć tylko najbardziej ogólny typ, którym jest ${\ Displaystyle \ dla wszystkich \ alfa. \ alfa}$ . Plan polega na specjalizacji typu, jeśli okaże się to konieczne. Niestety polityp nie jest w tym miejscu dozwolony, więc trochę $α$ chwilowo musi zrobić. Aby uniknąć niechcianych przechwyceń, bezpiecznym wyborem jest zmienna typu, której jeszcze nie ma w dowodzie. Dodatkowo należy pamiętać, że ta monotypia nie jest jeszcze ustalona, ale może zostać dopracowana.
$[Var]$ : Wybór polega na tym, jak udoskonalić $σ$ . Ponieważ każdy wybór typu $τ$ zależy tutaj od użycia zmiennej, która nie jest lokalnie znana, najbezpieczniejszy jest zakład najbardziej ogólny. Korzystając z tej samej metody, co powyżej, można utworzyć instancje wszystkich skwantyfikowanych zmiennych w $σ$ ze świeżymi zmiennymi monotypowymi, ponownie pozostawiając je otwarte na dalsze udoskonalenie.
$[Let]$ : Reguła nie pozostawia żadnego wyboru. Zrobione.
$[Aplikacja]$ : Tylko reguła aplikacji może wymusić uściślenie zmiennych „otwartych” do tej pory.

Pierwsza przesłanka wymusza, aby wynik wnioskowania miał postać ${\ Displaystyle \ tau \ rightarrow \ tau '}$ .

Jeśli tak jest, to dobrze. Można później wybrać jego $τ'$ jako wynik.
Jeśli nie, może to być zmienna otwarta. Następnie można to udoskonalić do wymaganej postaci za pomocą dwóch nowych zmiennych, jak poprzednio.
W przeciwnym razie sprawdzanie typu kończy się niepowodzeniem, ponieważ pierwsza przesłanka wywnioskowała typ, który nie jest i nie może być przekształcony w typ funkcji.

Druga przesłanka wymaga, aby wywnioskowany typ był równy $τ$ pierwszej przesłanki. Teraz istnieją dwa prawdopodobnie różne typy, być może ze zmiennymi typu otwartego, pod ręką, aby porównać i wyrównać, jeśli to możliwe. Jeśli tak, zostaje znalezione uściślenie, a jeśli nie, ponownie wykrywany jest błąd typu. Znana jest skuteczna metoda „zrównywania dwóch terminów” przez podstawienie, Unifikacja Robinsona w połączeniu z tak zwanym algorytmem Union-Find .

Krótko podsumowując algorytm znajdowania sumy, biorąc pod uwagę zbiór wszystkich typów w dowodzie, pozwala on pogrupować je razem w klasy równoważności za pomocą procedury sumowania i wybrać przedstawiciela dla każdej takiej klasy za pomocą procedury znajdowania . Podkreślając słowo procedura w znaczeniu efektu ubocznego , wyraźnie wychodzimy poza sferę logiki w celu przygotowania skutecznego algorytmu. związku ${\ Displaystyle {\ mathtt {union}} (a, b)}$ jest określony w taki sposób, że jeśli zarówno $a,$ jak i $b$ są zmiennymi typu, to reprezentant jest arbitralnie jedną z nich, ale łącząc zmienną i termin, termin staje się przedstawiciel. Zakładając implementację znaleziska unii pod ręką, można sformułować unifikację dwóch monotypów w następujący sposób:

     unify(ta, tb):  ta = find(ta) tb = find(tb)  jeśli  oba ta,tb są wyrazami postaci D p1..pn z identycznym D,n  to  unify(ta[i], tb[i ]) dla każdego odpowiadającego  i  -tego parametru  w przeciwnym  razie, jeśli  co najmniej jeden z ta,tb jest zmienną typu,  to  union(ta, tb)  w przeciwnym razie  błąd „typy nie pasują”

Teraz, mając pod ręką szkic algorytmu wnioskowania, w następnej sekcji podano bardziej formalną prezentację. Jest to opisane w Milner P. 370 ff. jako algorytm J.

algorytm j

Algorytm J
${\ Displaystyle {\ rozpocząć {tablica} {cl} \ Displaystyle {\ Frac {x: \ sigma \ in \ Gamma \ quad \ tau = {\ mathit {inst}} (\ sigma)} {\ Gamma \ vdash _ { J} x: \ tau}} & [{\ mathtt {Var}}] \\\\\ Displaystyle {\ frac {\ Gamma \ vdash _ {J} e_ {0}: \ tau _ {0} \ quad \ Gamma \vdash _{J}e_{1}:\tau _{1}\quad \tau '={\mathit {newvar}}\quad {\mathit {unify}}(\tau _{0},\ \ tau _{1}\rightarrow \tau ')}{\Gamma \vdash _{J}e_{0}\ e_{1}:\tau '}}&[{\mathtt {aplikacja}}]\\\\ \ Displaystyle {\ Frac {\ tau = {\ mathit {newvar}} \ quad \ Gamma, \; x: \ tau \ vdash _ {J} e: \ tau '} {\ Gamma \ vdash _ {J} \ lambda \ x\ .\ e: \ tau \ rightarrow \ tau '}} & [{\ mathtt {Abs}}] \\\\\ Displaystyle {\ frac {\ Gamma \ vdash _ {J} e_ {0}: \ tau \quad \quad \Gamma ,\,x:{\bar {\Gamma }}(\tau )\vdash _{J}e_{1}:\tau '}{\Gamma \vdash _{J}{\ mathtt {let}}\ x=e_{0}\ {\mathtt {in}}\ e_{1}:\tau '}}&[{\mathtt {let}}]\end{tablica}}}$

Prezentacja algorytmu J jest nadużyciem zapisu reguł logicznych, ponieważ zawiera efekty uboczne, ale umożliwia bezpośrednie porównanie z $równoczesnym$ implementacji. Reguły określają $.$ procedurę z parametrami $, w którym$ wniosek przesłanek przebiega od lewej do prawej

Procedura $konsekwentnie$ , $i$ zastępując zmienne typu związanego nowymi zmiennymi ' ${\ displaystyle newvar}$ ' tworzy nową zmienną jednotypową. Γ ${\ Displaystyle {\ bar {\ Gamma}} (\ tau)$ musi skopiować typ, wprowadzając nowe zmienne do kwantyfikacji, aby uniknąć niechcianych przechwyceń. Ogólnie rzecz biorąc, algorytm postępuje teraz zawsze dokonując najbardziej ogólnego wyboru, pozostawiając specjalizację unifikacji, która sama w sobie daje najbardziej ogólny wynik. Jak wspomniano powyżej , ostateczny wynik musi zostać uogólniony na koniec, aby uzyskać najbardziej ogólny typ $)$ ${\ Displaystyle {\ bar {\ Gamma}} (\ tau$ dla danego wyrażenia.

Ponieważ procedury stosowane w algorytmie mają koszt prawie O(1), całkowity koszt algorytmu jest zbliżony do liniowego pod względem wielkości wyrażenia, dla którego typ ma być wywnioskowany. Stoi to w silnym kontraście z wieloma innymi próbami wyprowadzenia algorytmów wnioskowania typu, które często okazywały się być NP-trudne , jeśli nie nierozstrzygalne w odniesieniu do zakończenia. W ten sposób HM działa tak dobrze, jak najlepsze w pełni poinformowane algorytmy sprawdzania typu. Sprawdzanie typu oznacza tutaj, że algorytm nie musi znaleźć dowodu, a jedynie zweryfikować dany dowód.

$jest nieco$ powiązanie zmiennych typu w kontekście musi być zachowane, aby umożliwić i umożliwić występowania , aby zapobiec budowanie typów rekurencyjnych podczas ${\ Displaystyle union (\ alfa, \ tau)}$ . Przykładem takiego przypadku jest ${\ Displaystyle \ lambda \ x. (x \ x)}$ , dla których nie można wyprowadzić żadnego typu za pomocą HM. W praktyce typy są tylko małymi terminami i nie tworzą rozwijających się struktur. Zatem w analizie złożoności porównywanie ich można traktować jako stałą, zachowującą koszty O(1).

Udowodnienie algorytmu

W poprzedniej sekcji, podczas szkicowania algorytmu, wskazywano na jego dowód argumentacją metalologiczną. Chociaż prowadzi to do wydajnego algorytmu J, nie jest jasne, czy algorytm właściwie odzwierciedla systemy dedukcji D lub S, które służą jako semantyczna linia bazowa.

Najbardziej krytycznym punktem w powyższej argumentacji jest uściślenie zmiennych monotypowych związanych z kontekstem. Na przykład algorytm odważnie zmienia kontekst, wnioskując np. ${\ Displaystyle \ lambda f. (f \ 1)}$ , ponieważ zmienna monotypowa dodana do kontekstu dla parametru $później$ zostać dopracowana do ${\ displaystyle int \rightarrow \beta }$ podczas obsługi aplikacji. Problem polega na tym, że zasady odliczeń nie pozwalają na takie uściślenie. Argumentowanie, że udoskonalony typ mógł zostać dodany wcześniej zamiast zmiennej monotypowej, jest co najwyżej celowe.

Kluczem do uzyskania formalnie satysfakcjonującej argumentacji jest właściwe uwzględnienie kontekstu w udoskonaleniu. Formalnie pisanie jest kompatybilne z podstawieniem zmiennych typu wolnego.

{\ Displaystyle \ Gamma \ vdash _ {S} e: \ tau \ quad \ Longrightarrow \ quad S \ Gamma \ vdash _ {S} e: S \ tau }

Doprecyzowanie wolnych zmiennych oznacza zatem doprecyzowanie całego typowania.

Algorytm W

Algorytm W
${\ Displaystyle {\ rozpocząć {tablica} {cl} \ Displaystyle {\ Frac {x: \ sigma \ in \ Gamma \ quad \ tau = {\ mathit {inst}} (\ sigma)} {\ Gamma \ vdash _ { W} x: \ tau, \ pusty zbiór}} i [{\ mathtt {Var}}] \\\\\ Displaystyle {\ frac {\ rozpocząć {tablica} {ll} \ Gamma \ vdash _ {W} e_ {0 }:\tau _{0},S_{0}&S_{0}\Gamma \vdash _{W}e_{1}:\tau _{1},S_{1}\\\tau '={\mathit {newvar}}&S_{2}={\mathsf {mgu}}(S_{1}\tau _{0},\ \tau _{1}\rightarrow \tau ')\end{tablica}}{\Gamma \vdash _{W}e_{0}\ e_{1}:S_{2}\tau ',S_{2}S_{1}S_{0}}}&[{\mathtt {aplikacja}}]\\ \\\ Displaystyle {\ Frac {\ tau = {\ mathit {newvar}} \ quad \ Gamma, \; x: \ tau \ vdash _ {W} e: \ tau ', S} {\ Gamma \ vdash _ { W} \ lambda \ x \ . \ e: S \ tau \ rightarrow \ tau ', S}} i [{\ mathtt {Abs}}] \\\\\ Displaystyle {\ frac {\ Gamma \ vdash _ {W }e_{0}:\tau ,S_{0}\quad S_{0}\Gamma,\,x:{\overline {S_{0}\Gamma }}(\tau)\vdash _{W}e_{ 1}:\tau ',S_{1}}{\Gamma \vdash _{W}{\mathtt {let}}\ x=e_{0}\ {\mathtt {w}}\ e_{1}:\ tau ',S_{1}S_{0}}}&[{\mathtt {Niech}}]\end{tablica}}}$

Stamtąd dowód algorytmu J prowadzi do algorytmu W, który jedynie uwidacznia efekty uboczne narzucone przez procedurę ${\ displaystyle {\ textit {union}}}$ , wyrażając jej szeregowy skład za pomocą podstawień ${\ styl wyświetlania S_{i}}$ . Prezentacja algorytmu W na pasku bocznym nadal wykorzystuje efekty uboczne w operacjach zaznaczonych kursywą, ale teraz ograniczają się one do generowania świeżych symboli. $Gamma \ vdash e: \ tau, S}$ mi , oznaczający funkcję z kontekstem i wyrażeniem jako parametrem tworzącym monotyp wraz z substytucją. ${\ displaystyle {\ textsf {mgu}}}$ jest wolną od skutków ubocznych wersją ${\ displaystyle {\ textit {union}}},$ tworzącą podstawienie, które jest najbardziej ogólnym unifikatorem .

Chociaż algorytm W jest zwykle uważany za algorytm HM i często jest przedstawiany w literaturze bezpośrednio po systemie reguł, jego cel został opisany przez Milnera na stronie 369 w następujący sposób:

W obecnym stanie W nie jest wydajnym algorytmem; zamienniki są stosowane zbyt często. Został sformułowany, aby pomóc w udowodnieniu solidności. Przedstawimy teraz prostszy algorytm J, który symuluje W w precyzyjnym sensie.

Chociaż uważał W za bardziej skomplikowane i mniej wydajne, przedstawił je w swojej publikacji przed J. Ma to swoje zalety, gdy skutki uboczne są niedostępne lub niepożądane. Nawiasem mówiąc, W jest również potrzebny do udowodnienia kompletności, co jest przez niego uwzględniane w dowodzie solidności.

Obowiązki dowodowe

Przed sformułowaniem obowiązków dowodowych należy podkreślić rozbieżność między systemami reguł D i S a przedstawionymi algorytmami.

Podczas gdy powyższy rozwój w pewnym sensie niewłaściwie wykorzystywał monotypy jako „otwarte” zmienne dowodowe, możliwość, że właściwe zmienne monotypowe mogą zostać naruszone, została pominięta przez wprowadzenie nowych zmiennych i nadzieję na najlepsze. Ale jest pewien haczyk: jedną z obietnic było to, że te nowe zmienne będą „pamiętane” jako takie. Algorytm nie spełnia tej obietnicy.

$_$ kontekst wyrażenia $_$ $ani$ w ${D}}$ lub $Displaystyle \ vdash _ {S}}$ $\$ , ale algorytmy wymyślają typ gdzie W dodatkowo zapewnia podstawienie ${\ displaystyle \ lewo \ {\ alfa \ mapsto int \ rightarrow \ beta \ prawo \}}$ , co oznacza, że algorytm nie wykrywa wszystkich błędów typu. To pominięcie można łatwo naprawić, dokładniej rozróżniając zmienne dowodowe i zmienne monotypowe.

Autorzy doskonale zdawali sobie sprawę z problemu, ale postanowili go nie naprawiać. Można przypuszczać, że kryje się za tym pragmatyczny powód. Chociaż bardziej poprawne wdrożenie wnioskowania o typie umożliwiłoby algorytmowi radzenie sobie z abstrakcyjnymi monotypami, nie były one potrzebne do zamierzonego zastosowania, w którym żaden z elementów w istniejącym wcześniej kontekście nie ma wolnych zmiennych. W tym świetle zrezygnowano z niepotrzebnej komplikacji na rzecz prostszego algorytmu. Pozostałym minusem jest to, że dowód algorytmu w odniesieniu do systemu reguł jest mniej ogólny i można go przeprowadzić tylko dla kontekstów ${\ displaystyle free (\ Gamma) = \ pusty zbiór}$ jako warunek uboczny.

${\ Displaystyle {\ rozpocząć {tablica} {lll} {\ tekst {(poprawność)}} i \ Gamma \ vdash _ {W} e: \ tau, S & \ quad \ Longrightarrow \ quad \ Gamma \ vdash _ {S} e:\tau \\{\text{(Dopełnienie)}}&\Gamma \vdash _{S}e:\tau &\quad \Longrightarrow \quad \Gamma \vdash _{W}e:\tau ',S \quad \quad {\text{dla wszystkich}}\ \tau \ {\text{gdzie}}\ {\overline {\emptyset}}(\tau ')\sqsubseteq \tau \end{tablica}}}$

Warunek poboczny w obowiązku kompletności odnosi się do tego, w jaki sposób odliczenie może dać wiele typów, podczas gdy algorytm zawsze tworzy jeden. Jednocześnie warunek poboczny wymaga, aby wywnioskowany typ był w rzeczywistości najbardziej ogólny.

Aby właściwie udowodnić zobowiązania, należy je najpierw wzmocnić, aby umożliwić aktywację lematu o podstawieniu przeplatającego podstawienie przez i $\ vdash _ {S}}$ $Displaystyle$ i $_ {W }}$ . Stamtąd dowody są przez indukcję nad wyrażeniem.

Innym obowiązkiem dowodowym jest sam lemat podstawieniowy, czyli podstawienie typowania, które ostatecznie ustala wszechkwantyfikację. Późniejszego nie można formalnie udowodnić, ponieważ taka składnia nie jest pod ręką.

Rozszerzenia

Definicje rekurencyjne

Aby programowanie było praktyczne, potrzebne są funkcje rekurencyjne. Główną właściwością rachunku lambda jest to, że definicje rekurencyjne nie są bezpośrednio dostępne, ale zamiast tego można je wyrazić za pomocą kombinatora punktów stałych . Niestety, kombinator punktów stałych nie może zostać sformułowany w maszynowej wersji rachunku lambda bez katastrofalnego wpływu na system, jak opisano poniżej.

Reguła pisania

Oryginalna praca pokazuje, że rekurencję można zrealizować za pomocą kombinatora ${\ Displaystyle {\ mathit {fix}}: \ forall \ alpha. (\ alfa \ rightarrow \ alpha) \ rightarrow \ alpha}$ . Możliwą definicję rekurencyjną można zatem sformułować jako ${\ Displaystyle {\ mathtt {rec}} \ v = e_ {1} \ {\ mathtt {w}} \ e_ {2} \ :: = {\ mathtt { niech}}\ v={\mathit {poprawka}}(\lambda v.e_{1})\ {\mathtt {w}}\ e_{2}}$ .

Alternatywnie możliwe jest rozszerzenie składni wyrażenia i dodatkowa reguła wpisywania:

{\ Displaystyle \ Displaystyle {\ Frac {\ Gamma, \ Gamma '\ vdash e_ {1}: \ tau _ {1} \ quad \ kropki \ quad \ Gamma, \ Gamma '\ vdash e_{n}:\tau _{n}\quad \Gamma ,\Gamma ''\vdash e:\tau }{\Gamma \ \vdash \ {\mathtt {rec}}\ v_{1}=e_{1 }\ {\mathtt {i}}\ \dots \ {\mathtt {i}}\ v_{n}=e_{n}\ {\mathtt {w}}\ e:\tau }}\quad [{\ mathtt {Rec}}]}

Gdzie

${\ Displaystyle \ Gamma '= v_ {1}: \ tau _ {1}, \ \ kropki, \ v_ {n}: \ tau _ {n }}$
${\ Displaystyle \ Gamma '' = v_ {1}: {\ bar {\ Gamma}} (\ \ tau _ {1}\ ),\ \kropki ,\ v_{n}:{\bar {\Gamma}}(\ \tau _{n}\ )}$

zasadniczo łącząc ${\ Displaystyle [{\ mathtt {Abs}}]}$ i ${\ Displaystyle [{\ mathtt {Niech}}]}$ , jednocześnie włączając rekurencyjnie zdefiniowane zmienne w pozycjach monotypowych, gdzie $występują$ po lewej stronie, politypy po prawej stronie.

Konsekwencje

Chociaż powyższe jest proste, ma swoją cenę.

Teoria typów łączy rachunek lambda z obliczeniami i logiką. Powyższa łatwa modyfikacja ma wpływ na oba:

Właściwość silnej normalizacji jest unieważniona, ponieważ można sformułować terminy niekończące.
Logika załamuje się , ponieważ typ ${\ displaystyle \ forall aa}$ zostaje zamieszkany .

Przeciążenie

Przeciążenie oznacza, że różne funkcje mogą być definiowane i używane pod tą samą nazwą. Większość języków programowania przynajmniej zapewnia przeładowanie wbudowanymi operacjami arytmetycznymi (+, <, itd.), aby umożliwić programiście pisanie wyrażeń arytmetycznych w tej samej postaci, nawet dla różnych typów liczbowych, takich jak int lub real . Ponieważ połączenie tych różnych typów w ramach tego samego wyrażenia również wymaga konwersji niejawnej, przeciążenie, zwłaszcza w przypadku tych operacji, jest często wbudowane w sam język programowania. W niektórych językach ta cecha jest uogólniona i udostępniona użytkownikowi, np. w C++.

Podczas gdy w programowaniu funkcjonalnym uniknięto przeciążania ad hoc ze względu na koszty obliczeń zarówno przy sprawdzaniu typów, jak i wnioskowaniu ^{[ potrzebne źródło ]} , wprowadzono sposób usystematyzowania przeciążania, który przypomina zarówno pod względem formy, jak i nazewnictwa programowanie zorientowane obiektowo, ale działa o jeden poziom w górę . „Instancje” w tej systematyce nie są przedmiotami (tj. na poziomie wartości), ale raczej typami. Wspomniany na wstępie przykład quicksort wykorzystuje przeciążanie w zamówieniach, mając w Haskell następującą adnotację typu:

        quickSort  ::  Sortuj  a  =>  [  a  ]  ->  [  a  ]

Tutaj typ a jest nie tylko polimorficzny, ale także ograniczony do bycia instancją jakiejś klasy typu Ord , która zapewnia predykaty kolejności < i >= używane w treści funkcji. Właściwe implementacje tych predykatów są następnie przekazywane do quicksorts jako dodatkowe parametry, gdy tylko quicksort zostanie użyty na bardziej konkretnych typach, zapewniając pojedynczą implementację przeciążonej funkcji quickSort.

Ponieważ „klasy” dopuszczają tylko jeden typ jako argument, wynikowy system typów może nadal zapewniać wnioskowanie. Dodatkowo klasy typów można wtedy wyposażyć w pewnego rodzaju porządek przeciążający, który pozwala na ułożenie klas w kratę .

Typy wyższego rzędu

Polimorfizm parametryczny oznacza, że same typy są przekazywane jako parametry, tak jakby były wartościami właściwymi. Przekazywane jako argumenty do odpowiednich funkcji, ale także do „funkcji typu”, jak w przypadku stałych typu „parametrycznego”, prowadzi do pytania, jak poprawniej typować same typy. Typy wyższego rzędu służą do tworzenia jeszcze bardziej wyrazistego systemu typów.

Niestety, unifikacja nie jest już rozstrzygalna w obecności metatypów, co uniemożliwia wnioskowanie o typie w tym zakresie ogólności. Dodatkowo przyjęcie typu wszystkich typów, który obejmuje siebie jako typ, prowadzi do paradoksu, jak w zbiorze wszystkich zbiorów, więc trzeba postępować etapami poziomów abstrakcji. Badania w rachunku lambda drugiego rzędu , o jeden krok w górę, wykazały, że wnioskowanie o typie jest nierozstrzygalne w tej ogólności.

Części jednego dodatkowego poziomu zostały wprowadzone do Haskella o nazwie rodzaj , gdzie jest on używany jako pomoc przy wpisywaniu monad . Rodzaje pozostają ukryte, pracując za kulisami w wewnętrznej mechanice rozszerzonego systemu typów.

Podtypowanie

Próby połączenia podtypów i wnioskowania o typach spowodowały sporo frustracji. Łatwo jest gromadzić i propagować ograniczenia podtypów (w przeciwieństwie do ograniczeń równości typów), czyniąc wynikające z nich ograniczenia częścią wywnioskowanych schematów typowania, na przykład $\ forall \ alfa . \ (\ alfa \ równoważnik T) \ Strzałka w prawo \ alfa \ strzałka w prawo \ alfa$ $,$ jest a ograniczenie zmiennej typu ${\ Displaystyle \ alfa}$ . Ponieważ jednak zmienne typu nie są już chętnie ujednolicane w tym podejściu, ma tendencję do generowania dużych i nieporęcznych schematów typowania zawierających wiele bezużytecznych zmiennych typu i ograniczeń, co utrudnia ich odczytanie i zrozumienie. Dlatego włożono znaczny wysiłek w uproszczenie takich schematów typowania i ich ograniczeń, stosując techniki podobne do uproszczenia niedeterministycznego automatu skończonego (NFA) (przydatne w obecności wywnioskowanych typów rekurencyjnych). Niedawno Dolan i Mycroft sformalizowali związek między uproszczeniem schematu pisania a uproszczeniem NFA i wykazali, że algebraiczne podejście do formalizacji podtypów pozwoliło na wygenerowanie zwartych głównych schematów pisania dla języka podobnego do ML (zwanego MLsub). Warto zauważyć, że proponowany przez nich schemat typowania wykorzystywał ograniczoną formę typów unii i przecięć zamiast wyraźnych ograniczeń. Parreaux twierdził później, że to sformułowanie algebraiczne jest równoważne stosunkowo prostemu algorytmowi przypominającemu algorytm W i że użycie typów sumy i przecięcia nie jest niezbędne.

Z drugiej strony wnioskowanie o typie okazało się trudniejsze w kontekście zorientowanych obiektowo języków programowania, ponieważ metody obiektowe zwykle wymagają polimorfizmu pierwszej klasy w stylu Systemu F (gdzie wnioskowanie o typie jest nierozstrzygalne) oraz z powodu cech takich jak F -ograniczony polimorfizm . W $podtypami umożliwiającymi$ obiektowe, takie jak system Cardelli , nie obsługują wnioskowania typu w stylu HM .

Polimorfizm wierszy może być używany jako alternatywa dla podtypów do obsługi funkcji językowych, takich jak zapisy strukturalne. Chociaż ten styl polimorfizmu jest pod pewnymi względami mniej elastyczny niż podtypowanie, w szczególności wymaga więcej polimorfizmu niż jest to absolutnie konieczne, aby poradzić sobie z brakiem kierunkowości w ograniczeniach typu, ma tę zaletę, że można go dość łatwo zintegrować ze standardowymi algorytmami HM.

Notatki

Mairson, Harry G. (1990). „Decydowanie o typowości ML jest zakończone dla deterministycznego czasu wykładniczego”. Materiały z 17. sympozjum ACM SIGPLAN-SIGACT Zasady języków programowania - POPL '90 . Materiały z 17. Sympozjum ACM SIGPLAN-SIGACT na temat zasad języków programowania . POPL '90. ACM. s. 382–401. doi : 10.1145/96709.96748 . ISBN 978-0-89791-343-0 . S2CID 75336 .
Kfoury, AJ; Tiuryn, J.; Urzyczyn, P. (1990). Typowalność ML to dexptime-complete . Notatki z wykładów z informatyki . CAAP '90. Tom. 431. s. 206–220. doi : 10.1007/3-540-52590-4_50 . ISBN 978-3-540-52590-5 .

Linki zewnętrzne

Wyrażenia
${\ Displaystyle {\ rozpocząć {tablica} {lrll} \\ e&=&x& {\ textrm {zmienna}} \\&\ vert & e_ {1}\ e_ {2}& {\ textrm {aplikacja}} \\&\ vert &\lambda \ x\ .\ e&{\textrm {abstrakcja}}\\&\vert &{\mathtt {let}}\ x=e_{1}\ {\mathtt {in}}\ e_{2} &\\\\\end{array}}}$
Typy
${\ Displaystyle {\ rozpocząć {tablica} {llrll} \\ {\ textrm {mono}} & \ tau & = & \ alfa & \ {\ textrm {zmienna}} \\&&\ vert & C \ \ tau \ kropki \ tau &\ {\textrm {aplikacja}}\\{\textrm {poly}}&\sigma &=&\tau \\&&\vert &\forall \ \alpha \ .\ \sigma &\ {\textrm {kwantyfikator }}\\\\\end{array}}}$
Kontekst i
${\ Displaystyle {\ rozpocząć {tablica} {llrl} \\ {\ tekst {kontekst}} & \ Gamma & = i \ epsilon \ {\ mathtt {(pusty)}} \\&&\ vert & \ Gamma, \ x :\sigma \\{\text{wpisywanie}}&&=&\Gamma \vdash e:\sigma \\\\\end{array}}} Dowolne$
zmienne typu
${\ Displaystyle {\ rozpocząć {tablica} {ll} \\ {\ tekst {wolny}} (\ \ alfa \ ) & = \ lewo \ {\ alfa \ prawo \} \\ {\ tekst wolny}} ( \ C\ \tau _{1}\dots \tau _{n}\ )&=\ \bigcup \limits _{i=1}^{n}{{\text{free}}(\ \tau _{ i}\ )}\\{\text{free}}(\ \Gamma \ )&=\ \bigcup \limits _{x:\sigma \in \Gamma }{\text{free}}(\ \sigma \ )\\\\{\text{free}}(\ \forall \ \alpha \ .\ \sigma \ )&=\ {\text{free}}(\ \sigma \ )\ -\ \left\{\ alpha \right\}\\{\text{free}}(\ \Gamma \vdash e:\sigma \ )&=\ {\text{free}}(\ \sigma \ )\ -\ {\text{free }}(\ \Gamma \ )\\\\\end{tablica}}}$

Składnia
${\ Displaystyle {\ rozpocząć {tablica} {lrl} {\ text {orzeczenie}} & = & \ sigma \ sqsubseteq \ sigma '\\& \ vert \ & \ alfa \ nie \ w wolnym (\ Gamma) \\& \vert \ &x:\alpha \in \Gamma \\\\{\text{Wyrok}}&=&{\text{Wpisywanie}}\\{\text{Przesłanka}}&=&{\text{Wyrok} }\ \vert \ {\text{Orzeczenie}}\\{\text{Wniosek}}&=&{\text{Wyrok}}\\\\{\text{Reguła}}&=&\displaystyle {\frac {{\textrm {przesłanka}}\ \dots }{\textrm {wniosek}}}\quad [{\mathtt {nazwa}}]\end{tablica}}}$