Globalne wnioskowanie typu w kompilatorze Schematu Stalin

Question

Zajmuję się kompilatorem Schematu Stalina. Jest duży i złożony. Ponadto, jeśli dobrze zrozumiałem, autor zamierzał napisać serię artykułów opisujących aspekty implementacji, ale nigdy tego nie robił.

Aspektem Stalina, którym jestem zainteresowany, jest wnioskowanie globalne: wnioskowanie o typach rzeczy w oparciu o ich wykorzystanie w innych miejscach programu. Czy rzeczywiście robi to Stalin? Jeśli tak, w jaki sposób i gdzie w bazie kodu? Czy używa on wariantu/rozszerzenia algorytmu Hindley-Milnera?

Answer 1

Z README:

Stalin robi globalnej analizy statycznej typu miękką system typu że obsługuje rekurencyjne rodzajów związków. Stalin może wyznaczyć wąski lub nawet monomorficzny typ dla każdej ekspresji kodu źródłowego w dowolnych programach Scheme bez deklaracji typu. To pozwala Stalinowi zredukować lub często eliminować, sprawdzać i wysyłać dane typu run-time. Stalin także dokonuje selekcji niskiego poziomu na podstawie wyrażenia. Pozwala to na użycie niezapakowanych reprezentacji danych maszyn podstawowych dla wszystkich typów monomorficznych, co skutkuje wyjątkowo wysokim wydajnością kodu numerycznego .

Z 1997 talk by Siskind:

Stalin wykonuje wpisać wnioskowanie stosując analizę opartą ustawić (SBA aka 0CFA). Ta analiza jest rozszerzona w celu wsparcia rozdzielania poliwariantów. Wyniki SBA są używane w celu skrócenia czasu sprawdzania i wysyłania typu. Wyniki SBA są również używane do dokonania niskiego poziomu wyboru reprezentacji na podstawie wyrażenia. To ma dwie zalety: . Po pierwsze, znaczniki typów można wyeliminować dla monotypii, , umożliwiając wykorzystanie reprezentacji maszyn podstawowych dla pierwotnych danych . Po drugie, boks można wyeliminować, zmniejszając koszty związane z bokserstwem, alokacją i rekultywacją o związaną z boksowaniem . Wyeliminowanie boksowania wymaga, aby organizacja czasu wykonywania pozwalała zmiennym, parametrom, szczelinom struktury i przedziałom wektorów mieć różne szerokości w zależności od typu danych, które mają one w stanie utrzymać. Ponadto struktury zdefiniowane przez użytkownika mogą być rozpakowane tylko wtedy, gdy struktury te są niezmienne. Rozszerzenia SBA są rozszerzane w celu określenia szerokości i zmienności danych w czasie kompilacji.

Rzeczywisty algorytm typu wnioskowanie wydaje się być głównie realizowane w pliku source/stalin3b.sc źródło .

Wygląda na to, że SBA/0CFA jest całkowicie oddzielnym algorytmem od Hindley-Milnera. Jednak Hindley-Milner może być również wykorzystywany do implementacji miękkiego pisania.

Oto ładniejsza description of the 0CFA algorithm.

Istotne papiery są 1991 praca doktorska sterowania przepływem Olin Dreszcze Analiza wyższego rzędu języków lub Taming Lambda i Flanagan & 1995 papier Set-Based Analiza Felleisen do pełnego schematu a jego stosowanie w miękkim Wpisując.