Jakie wyzwania wiążą się z pisaniem kompilatora dla języka pisanego dynamicznie?

W tym wykładzie Guido van Rossum mówi (27:30) o próbach napisania kompilatora dla kodu Python, komentując go mówiąc:

okazuje się, że nie jest tak łatwo napisać kompilator, który zachowuje wszystkie fajne właściwości dynamicznego pisania, a także zachowuje poprawność semantyczną programu, dzięki czemu robi to samo bez względu na to, jak dziwnie robisz gdzieś pod przykryciem i faktycznie działa szybciej

Jakie (możliwe) wyzwania wiążą się z pisaniem podczas pisania kompilatora dla dynamicznie pisanego języka, takiego jak Python?

Uproszczono oświadczenie Guido w sformułowaniu pytania. Problemem nie jest pisanie kompilatora dla języka dynamicznego. Problem polega na napisaniu takiego, który jest (kryterium 1) zawsze poprawny, (kryterium 2) utrzymuje dynamiczne pisanie, a (kryterium 3) jest zauważalnie szybsze dla znacznej ilości kodu.

Łatwo jest zaimplementować 90% (niespełniających kryteriów 1) języka Python i konsekwentnie szybko na nim działać. Podobnie łatwo jest stworzyć szybszy wariant Pythona ze statycznym pisaniem (niespełniające kryterium 2). Wdrożenie 100% jest również łatwe (o ile implementacja języka jest skomplikowana), ale jak dotąd każdy łatwy sposób wdrożenia okazuje się stosunkowo wolny (niespełniające kryterium 3).

Wdrożenie poprawnego interpretera i JIT , implementacja całego języka i szybsze, ponieważ niektóre kody okazują się wykonalne, choć znacznie trudniejsze (por. PyPy) i tylko wtedy, gdy zautomatyzujesz tworzenie kompilatora JIT (Psyco zrobił to bez niego , ale był bardzo ograniczony w tym, jaki kod może przyspieszyć). Pamiętaj jednak, że jest to wyraźnie poza zakresem, ponieważ mówimy o statyce(inaczej kompilatory z wyprzedzeniem). Wspominam tylko o tym, aby wyjaśnić, dlaczego jego podejście nie działa w przypadku kompilatorów statycznych (lub przynajmniej nie istnieje kontrprzykład): Najpierw musi zinterpretować i obserwować program, a następnie wygenerować kod dla określonej iteracji pętli (lub innego kodu liniowego ścieżka), a następnie zoptymalizuj to na podstawie założeń, które są prawdziwe tylko dla tej konkretnej iteracji (a przynajmniej nie dla wszystkich możliwych iteracji). Oczekuje się, że wiele późniejszych wykonań tego kodu będzie również pasowało do oczekiwań, a tym samym skorzysta z optymalizacji. Niektóre (stosunkowo tanie) kontrole są dodawane w celu zapewnienia poprawności. Aby to wszystko zrobić, musisz wiedzieć, na co się specjalizować, oraz powolną, ale ogólną implementację, do której należy się wycofać. Kompilatory AOT nie mają. Nie mogą specjalizować się w ogólew oparciu o kod, którego nie widzą (np. kod ładowany dynamicznie), a specjalizacja niedbale oznacza generowanie większej ilości kodu, który ma wiele problemów (wykorzystanie icache, rozmiar binarny, czas kompilacji, dodatkowe gałęzie).

Wdrożenie kompilatora AOT, który poprawnie implementuje cały język jest również stosunkowo łatwe: Wygeneruj kod, który wywołuje w środowisku wykonawczym, aby zrobić to, co zrobiłby interpreter, gdy był zasilany tym kodem. Nuitka (głównie) to robi. Jednak nie przynosi to znacznej poprawy wydajności (niespełnianie kryteriów 3), ponieważ nadal musisz wykonywać tyle samo niepotrzebnej pracy, co interpreter, z wyjątkiem wysłania kodu bajtowego do bloku kodu C, który wykonuje to, co skompilowałeś. Ale to tylko niewielki koszt - na tyle znaczny, że warto go zoptymalizować w istniejącym tłumaczu, ale nie na tyle znaczący, aby uzasadnić zupełnie nową implementację własnymi problemami.

Co byłoby potrzebne, aby spełnić wszystkie trzy kryteria? Nie mamy pojęcia Istnieje kilka schematów analizy statycznej, które mogą wyodrębnić niektóre informacje na temat konkretnych typów, przepływu sterowania itp. Z programów w języku Python. Te, które dają dokładne dane wykraczające poza zakres pojedynczego bloku podstawowego, są bardzo powolne i muszą zobaczyć cały program, a przynajmniej większość. Mimo to niewiele możesz zrobić z tymi informacjami, poza optymalizacją kilku operacji na wbudowanych typach.

Dlaczego tak jest Mówiąc wprost, kompilator albo usuwa możliwość wykonywania kodu Pythona załadowanego w czasie wykonywania (niespełniające kryteriów 1), albo nie przyjmuje żadnych założeń, które mogłyby zostać unieważnione przez dowolny kod Pythona. Niestety, obejmuje to prawie wszystko przydatne do optymalizacji programów: globale łącznie z funkcjami mogą być odbijane, klasy mogą być mutowane lub całkowicie zastępowane, moduły mogą być również dowolnie modyfikowane, importowanie może być przejęte na kilka sposobów, itp. Pojedynczy ciąg przekazywany do eval, exec, __import__lub wiele innych funkcji, może wykonać dowolną z tych czynności. W efekcie oznacza to, że nie można zastosować prawie żadnych dużych optymalizacji, przynosząc niewielkie korzyści w zakresie wydajności (niespełnianie kryteriów 3). Powrót do powyższego akapitu.

Najtrudniejszym problemem jest ustalenie, jaki typ ma wszystko w danym momencie.

W języku statycznym, takim jak C lub Java, po obejrzeniu deklaracji typu wiesz, czym jest ten obiekt i co może zrobić. Jeśli deklarowana jest zmienna int, jest to liczba całkowita. Nie jest to na przykład odwołanie do funkcji, którą można wywołać.

W Pythonie może być. To okropny Python, ale legalny:

i = 2
x = 3 + i

def prn(s):
    print(s)

i = prn
i(x)

Ten przykład jest dość głupi, ale ilustruje ogólną ideę.

Bardziej realistycznie, możesz zastąpić funkcję wbudowaną funkcją zdefiniowaną przez użytkownika, która robi coś nieco innego (jak wersja, która rejestruje swoje argumenty podczas wywoływania).

PyPy korzysta z kompilacji Just-In-Time po obejrzeniu tego, co faktycznie robi kod, co pozwala PyPy'emu znacznie przyspieszyć. PyPy może oglądać pętlę i sprawdzać, czy przy każdym uruchomieniu pętli zmienna foojest zawsze liczbą całkowitą; wtedy PyPy może zoptymalizować kod, który wyszukuje typ fooprzy każdym przejściu przez pętlę, i często może nawet pozbyć się obiektu Python reprezentującego liczbę całkowitą i foomoże po prostu stać się liczbą umieszczoną w rejestrze na procesorze. W ten sposób PyPy może być szybszy niż CPython; CPython dokonuje wyszukiwania typu tak szybko, jak to możliwe, ale nawet samo wyszukiwanie nie jest jeszcze szybsze.

Nie znam szczegółów, ale pamiętam, że był projekt o nazwie Unladen Swallow, który próbował zastosować technologię kompilatora statycznego w celu przyspieszenia Pythona (przy użyciu LLVM). Możesz wyszukać w Google „Unladen Swallow” i sprawdzić, czy możesz znaleźć dyskusję, dlaczego nie udało się to, jak się spodziewali.

Jak mówi druga odpowiedź, kluczowym problemem jest ustalenie informacji o typie. W zakresie, w jakim możesz to zrobić statycznie, możesz bezpośrednio wygenerować dobry kod.

Ale nawet jeśli nie możesz tego zrobić statycznie, nadal możesz wygenerować rozsądny kod, tylko w czasie wykonywania, gdy otrzymasz rzeczywiste informacje o typie. Informacje te często okazują się stabilne lub mają co najwyżej kilka różnych wartości dla dowolnej konkretnej jednostki w danym punkcie kodowym. Język programowania SELF jest pionierem wielu pomysłów dotyczących agresywnego zbierania typów środowiska uruchomieniowego i generowania kodu środowiska wykonawczego. Jego pomysły są szeroko stosowane w nowoczesnych kompilatorach opartych na JIT, takich jak Java i C #.