Jak zaimplementowano generyczne w nowoczesnym kompilatorze?

Chodzi mi o to, w jaki sposób przechodzimy od szablonu T add(T a, T b) ...do wygenerowanego kodu? Zastanawiałem się nad kilkoma sposobami osiągnięcia tego celu, przechowujemy funkcję ogólną w AST, Function_Nodea następnie za każdym razem, gdy jej używamy, przechowujemy w oryginalnym węźle funkcji jej kopię ze wszystkimi typami Tpodstawionymi typami, które są jest używany. Na przykład add<int>(5, 6)zapisze kopię funkcji ogólnej addi zastąpi wszystkie typy T w kopii przez int.

Więc wyglądałoby to tak:

struct Function_Node {
    std::string name; // etc.
    Type return_type;
    std::vector<std::pair<Type, std::string>> arguments;
    std::vector<Function_Node> copies;
};

Następnie możesz wygenerować dla nich kod, a kiedy odwiedzisz Function_Nodelistę kopii copies.size() > 0, wywołujesz visitFunctionwszystkie kopie.

visitFunction(Function_Node& node) {
    if (node.copies.size() > 0) {
        for (auto& node : nodes.copies) {
            visitFunction(node);
        }
        // it's a generic function so we don't want
        // to emit code for this.
        return;
    }
}

Czy to zadziała dobrze? Jak nowoczesne kompilatory podchodzą do tego problemu? Myślę, że być może innym sposobem byłoby wstrzyknięcie kopii do AST, tak aby przebiegała ona przez wszystkie fazy semantyczne. Pomyślałem też, że być może uda ci się wygenerować je w natychmiastowej formie, na przykład MIR Rdza lub SIL Swift.

Mój kod jest napisany w Javie, przykładami są tutaj C ++, ponieważ dla przykładów jest to nieco mniej szczegółowe - ale zasada jest w zasadzie taka sama. Chociaż może być kilka błędów, ponieważ jest to po prostu ręcznie napisane w polu zapytania.

Zauważ, że mam na myśli nowoczesny kompilator, ponieważ to najlepszy sposób na rozwiązanie tego problemu. A kiedy mówię ogólne, nie mam na myśli takich, jak ogólne Java, w których używają usuwania tekstu.

Jak zaimplementowano generyczne w nowoczesnym kompilatorze?

Zapraszam do zapoznania się z kodem źródłowym nowoczesnego kompilatora, jeśli chcesz wiedzieć, jak działa nowoczesny kompilator. Zacznę od projektu Roslyn, który implementuje kompilatory C # i Visual Basic.

W szczególności zwracam uwagę na kod w kompilatorze C #, który implementuje symbole typu:

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Symbols

i możesz także zajrzeć do kodu reguł konwertowalności. Jest wiele rzeczy, które dotyczą algebraicznej manipulacji typami rodzajowymi.

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Binder/Semantics/Conversions

Starałem się, aby ten ostatni był czytelny.

Zastanawiałem się nad kilkoma sposobami osiągnięcia tego celu, przechowujemy funkcję ogólną w AST jako Function_Node, a następnie za każdym razem, gdy jej używamy, przechowujemy w oryginalnym węźle funkcji jej kopię ze wszystkimi typami T podstawionymi na typy które są używane.

Opisujesz szablony , a nie ogólne . C # i Visual Basic mają w swoich systemach typów rzeczywiste generyczne.

Krótko mówiąc, działają w ten sposób.

• Zaczynamy od ustalenia reguł, które formalnie stanowią typ w czasie kompilacji. Na przykład: intjest typem, parametr typu Tjest typem, dla dowolnego typu typ Xtablicy X[]jest również typem i tak dalej.

• Reguły dotyczące leków generycznych obejmują podstawienie. Na przykład class C with one type parameternie jest typem. To wzór do tworzenia typów. class C with one type parameter called T, under substitution with int for T jest typem.

• Reguły opisujące relacje między typami - zgodność po przypisaniu, sposób określania typu wyrażenia itp. - są projektowane i implementowane w kompilatorze.

• Język kodu bajtowego obsługujący typy ogólne w jego systemie metadanych został zaprojektowany i zaimplementowany.

• W czasie wykonywania kompilator JIT zamienia kod bajtowy na kod maszynowy; odpowiada za skonstruowanie odpowiedniego kodu maszynowego ze względu na ogólną specjalizację.

Na przykład w C #, kiedy mówisz

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>(); 
c.X(123);

następnie kompilator sprawdza C<int>, czy argument intjest poprawnym podstawieniem Ti odpowiednio generuje metadane i kod bajtowy. W czasie wykonywania jitter wykrywa, że ​​a C<int>jest tworzone po raz pierwszy i dynamicznie generuje odpowiedni kod maszynowy.

Większość implementacji generycznych (a raczej: parametrycznego polimorfizmu) używa usuwania typu. To znacznie upraszcza problem kompilowania kodu ogólnego, ale działa tylko dla typów pudełkowych: ponieważ każdy argument jest faktycznie nieprzezroczystym wskaźnikiem, potrzebujemy VTable lub podobnego mechanizmu wysyłania, aby wykonywać operacje na argumentach. W Javie:

<T extends Addable> T add(T a, T b) { … }

można skompilować, sprawdzić typ i wywołać w taki sam sposób jak

Addable add(Addable a, Addable b) { … }

z wyjątkiem tego, że generycy dostarczają kontrolerowi typu znacznie więcej informacji na stronie połączenia. Ta dodatkowa informacja może być obsługiwana przez zmienne typu , szczególnie gdy wnioskuje się o typach ogólnych. Podczas sprawdzania typu każdy typ ogólny można zastąpić zmienną, nazwijmy to $T1:

$T1 add($T1 a, $T1 b)

Zmienna typu jest następnie aktualizowana o więcej faktów, gdy stają się znane, aż można ją zastąpić konkretnym typem. Algorytm sprawdzania typu musi być napisany w sposób uwzględniający te zmienne typu, nawet jeśli nie są one jeszcze rozpoznane jako kompletny typ. W samej Javie można to zwykle zrobić łatwo, ponieważ typ argumentów jest często znany, zanim trzeba będzie poznać typ wywołania funkcji. Godnym uwagi wyjątkiem jest wyrażenie lambda jako argument funkcji, które wymaga użycia takich zmiennych typu.

Znacznie później optymalizator może wygenerować wyspecjalizowany kod dla określonego zestawu argumentów, co byłoby efektywnym rodzajem wstawiania.

Tabeli VT dla argumentów typu ogólnego można uniknąć, jeśli funkcja ogólna nie wykonuje żadnych operacji na typie, a jedynie przekazuje je do innej funkcji. Np. Funkcja Haskell call :: (a -> b) -> a -> b; call f x = f xnie musiałaby wstawiać xargumentu. Wymaga to jednak konwencji wywoływania, która może przekazywać wartości bez znajomości ich rozmiaru, co zasadniczo ogranicza je do wskaźników.

Pod tym względem C ++ bardzo różni się od większości języków. Klasa lub funkcja szablonowa (tutaj omówię tylko funkcje szablonowe) sama w sobie nie jest możliwa do wywołania. Zamiast tego szablony należy rozumieć jako meta-funkcję w czasie kompilacji, która zwraca rzeczywistą funkcję. Ignorując przez chwilę wnioskowanie o szablonie, ogólne podejście sprowadza się do następujących kroków:

1. Zastosuj szablon do podanych argumentów szablonu. Np nazywając template<class T> T add(T a, T b) { … }jak add<int>(1, 2)dałoby nam rzeczywistą funkcję int __add__T_int(int a, int b)(lub cokolwiek jest używana nazwa-maglowania podejście).

2. Jeśli kod dla tej funkcji został już wygenerowany w bieżącej jednostce kompilacji, kontynuuj. W przeciwnym razie wygeneruj kod tak, jakby funkcja int __add__T_int(int a, int b) { … }została zapisana w kodzie źródłowym. Wymaga to zastąpienia wszystkich wystąpień argumentu szablonu jego wartościami. Prawdopodobnie jest to transformacja AST → AST. Następnie sprawdź typ wygenerowanego AST.

3. Skompiluj wywołanie, jakby był kod źródłowy __add__T_int(1, 2).

Zauważ, że szablony C ++ mają złożoną interakcję z mechanizmem rozwiązywania problemu przeciążenia, którego nie chcę tutaj opisywać. Zauważ również, że to generowanie kodu uniemożliwia stworzenie metody opartej na szablonie, która jest również wirtualna - podejście oparte na usuwaniu typów nie cierpi z powodu tego znacznego ograniczenia.

Co to oznacza dla twojego kompilatora i / lub języka? Musisz dokładnie przemyśleć rodzaj leków generycznych, które chcesz zaoferować. Usuwanie typu w przypadku braku wnioskowania o typach jest najprostszym możliwym podejściem, jeśli obsługiwane są typy pudełkowe. Specjalizacja szablonów wydaje się dość prosta, ale zwykle wiąże się ze zniekształcaniem nazw i (w przypadku wielu jednostek kompilacji) znacznego powielania danych wyjściowych, ponieważ szablony są tworzone w miejscu wywołania, a nie w miejscu definicji.

Podejście, które pokazałeś, jest zasadniczo oparte na C ++. Przechowujesz jednak szablony specjalistyczne / tworzone jako „wersje” szablonu głównego. Jest to mylące: nie są one takie same koncepcyjnie, a różne instancje funkcji mogą mieć bardzo różne typy. To skomplikuje sytuację na dłuższą metę, jeśli pozwolisz również na przeciążenie funkcji. Zamiast tego potrzebujesz pojęcia zestawu przeciążenia, który zawiera wszystkie możliwe funkcje i szablony o wspólnej nazwie. Oprócz rozwiązania problemu przeciążenia można rozważyć różne szablony, które są całkowicie od siebie oddzielone.