Załóżmy, że X jest językiem wejściowym, Z jest językiem wyjściowym, a następnie f jest kompilatorem napisanym w języku Y.
f = X -> Z
Ponieważ f jest tylko programem, myślę, że Y może być dowolnym językiem, prawda? Możemy więc mieć kompilatory f1, f2, każdy napisany w Y1, Y2.
f1 = f Y1
f2 = f Y2
g = Z -> M
h = g . f # We get a compiler X -> M
Weźmy na przykład kompilator cpython, X to Python, Z to kod VM Python, Y to C.
cpython = Python -> PythonVMCode C
interpreter = PythonVMCode -> Nothing
interpreter2 = PythonVMCode -> MachineCode
Źródła Pythona są kompilowane do kodu VM języka Python, plików .pyc, a następnie interpretowane przez interpretera. Wygląda na to, że możliwe jest istnienie kompilatora, który może bezpośrednio wykonywać Pythona -> MachineCode, choć jest to bardzo trudne do wdrożenia:
hardpython = interpreter2 . cpython
Możemy też napisać inny kompilator do pracy w Pythonie -> PythonVMCode, w innym języku, powiedzmy sam Python.
mypython = Python -> PythonVMCode Python
mypython2 = Python -> PythonVMCode Ruby
Oto skomplikowany przykład PyPy. Jestem tylko nowicjuszem PyPy, popraw mnie, jeśli się mylę:
PyPy doc http://doc.pypy.org/en/latest/architecture.html#pypy-the-translation-framework
Naszym celem jest zapewnienie możliwego rozwiązania problemu implementatorów języków: pisanie l * o * p tłumaczy dla l dynamicznych języków i platform p z ważnymi decyzjami projektowymi.
Możemy myśleć, że l to X, p to Y. Istnieje program, który tłumaczy wszystkie programy RPython na C:
rpython_compiler = RPython -> C Python
pypy = Python -> Nothing RPython
translate = compile the program pypy written in RPython using rpython_compiler
py2rpy = Python -> RPython Python
py2c = Python -> C Python
py2c = rpython_compiler . py2rpy
Programy RPython są jak instrukcje VM, rpython_compiler to VM.
q1. pypy to interpreter, program RPython, który potrafi interpretować kod Pythona, nie ma języka wyjściowego, więc nie możemy traktować go jako kompilatora, prawda?
Dodany:
- Właśnie odkryłem, że nawet jeśli po tłumaczeniu pypy nadal jest tłumaczem, tylko tym razem napisane w C.
- Jeśli spojrzymy głęboko w pypy tłumacza, uważam, że musi istnieć jakiś kompilator, który kompiluje źródła Pythona do niektórych AST, a następnie uruchom
lubię to:
compiler_inside_pypy = Python -> AST_or_so
q2. Czy istnieje kompilator py2rpy, który przekształca wszystkie programy Pythona w RPython? W jakim języku jest napisany, nie ma znaczenia. Jeśli tak, otrzymujemy kolejny kompilator py2c. Jaka jest różnica między pypy a py2rpy w naturze? Czy py2rpy jest dużo trudniejszy do napisania niż pypy?
q3. Czy dostępne są jakieś ogólne zasady lub teoria?
Więcej kompilatorów:
gcc_c = C -> asm? C # not sure, gimple or rtl?
g++ = C++ -> asm? C
clang = C -> LLVM_IR C++
jython = Python -> JVMCode java
ironpython = Python -> CLI C#
q4. Biorąc pod uwagę f = X -> Z, program P napisany w X. Co chcemy zrobić, gdy chcemy przyspieszyć P? Możliwości:
przepisz P w bardziej wydajnym algorytmie
przepisz f, aby wygenerować lepsze Z
jeśli Z jest interpretowane, napisz lepszy interpreter Z (PyPy jest tutaj?)
przyspieszyć programy napisane w Z rekurencyjnie
zdobądź lepszą maszynę
ps. To pytanie nie dotyczy technicznych sposobów pisania kompilatora, ale wykonalności i złożoności pisania pewnego rodzaju kompilatora.
Odpowiedzi:
PyPy jest podobny do CPython, oba mają kompilator + interpreter. CPython ma kompilator napisany w C, który kompiluje Python do kodu bajtowego Python VM, a następnie wykonuje kod bajtowy w interpreterie napisanym w C. PyPy ma kompilator napisany w RPython, który kompiluje Python do kodu bajtowego Python VM, a następnie uruchamia go w PyPy Interpreter napisanym w RPython.
Czy istnieje kompilator py2rpy? Teoretycznie tak. Turing gwarantuje kompletność .
Jedną z metod konstruowania
py2rpy
jest po prostu włączenie kodu źródłowego interpretera Pythona napisanego w RPython do wygenerowanego kodu źródłowego. Przykład kompilatora py2rpy napisanego w języku Bash:teraz za każdym razem, gdy trzeba przetłumaczyć kod Pythona na kod RPython, wywołujesz ten skrypt, który tworzy - w $ outputdir - RPython
main.rpy
, kod źródłowy interpretera Pythona RPython oraz binarny obiekt blob prog.py. Następnie możesz wykonać wygenerowany skrypt RPython, dzwoniącrpython main.rpy
.(uwaga: ponieważ nie znam projektu rpython, składnia wywoływania interpretera rpython, możliwość importowania pypy i wykonania pypy.execfile, a rozszerzenie .rpy jest całkowicie wymyślone, ale myślę, że masz rację)
Tak, każdy język Turing Complete można teoretycznie przetłumaczyć na dowolny język Turing Complete. Niektóre języki mogą być trudniejsze do przetłumaczenia niż inne, ale jeśli pytanie brzmi „czy to możliwe?”, Odpowiedź brzmi „tak”
Tu nie ma pytania.
źródło
Does pypy have to be written in RPython in your compiler?
Nie, nie musi być napisany w RPython, ale RPython musi być w stanie powiedzieć „interpreterowi pomocniczemu” / „środowisku wykonawczemu”, aby wykonał kod Pythona. Tak, to prawda, że nie jest to „kompilator” w sensie praktycznym, ale jest konstruktywnym dowodem na to, że można pisaćPython -> RPython
.Is pypy still using the Python VM?
Wierzę, że pypy w ogóle nie używa CPython (mogę się mylić), zamiast tego PyPy ma własną implementację „Python VM”, która jest napisana w RPython.Python -> RPython
kompilatorze.Aby odpowiedzieć tylko na q2, istnieje książka kompilatora Williama McKeemana, w której teoria kompilatorów dla języka X napisana w języku Y produkującym język wyjściowy Z jest badana za pomocą systemu T-diagramów. Opublikowane w latach siedemdziesiątych, tytuł nie pod ręką, przepraszam.
źródło
q1. Zasadniczo interpreter nie jest kompilatorem. Kluczowa różnica między kompilatorem a tłumaczem polega na tym, że tłumacz zawsze zaczyna się od nowa, z kodem źródłowym w języku źródłowym. Jeśli zamiast tego Twoim pypy był pyAST lub kod pyP, a wtedy miałeś interpreter kodu AST lub P, możesz nazwać pyAST kompilatorem. Tak działał stary kompilator UCSD PASCAL (a także kilka innych): skompilowano do jakiegoś kodu P, który został zinterpretowany podczas uruchamiania programu. (Nawet .NET zapewnia coś takiego, gdy zwartość generowanego kodu obiektowego jest znacznie ważniejsza niż szybkość.)
q2. Tak oczywiście. Zobacz UCSD PASCAL (i kilka innych).
q3. Przeszukuj klasyczne teksty w informatyce. Przeczytaj na Concurrent PASCAL, autor: Per Brinch-Hansen (jeśli pamięć mi służy). Wiele napisano o kompilatorach i generowaniu kodu. Generowanie pseudokodu niezależnego od maszyny jest zwykle o wiele łatwiejsze niż generowanie kodu maszynowego: pseudokod jest zwykle wolny od dziwactw, które niezmiennie zawierają prawdziwe maszyny.
q4. Jeśli chcesz, aby wygenerowany obiekt działał szybciej, sprawisz, że kompilator będzie mądrzejszy, aby lepiej zoptymalizować. Jeśli twój obiekt jest interpretowany, rozważ spychanie bardziej złożonych operacji w prymitywne pseudoinstrukcje (CISC vs. RISC to analogia), a następnie staraj się zoptymalizować frack z twojego interpretera.
Jeśli chcesz, aby Twój kompilator działał szybciej, musisz spojrzeć na WSZYSTKO, co robi, w tym na przemyślenie kodu źródłowego. Po załadowaniu samego kompilatora najbardziej czasochłonną częścią kompilacji jest ZAWSZE wczytywanie kodu źródłowego do kompilatora. (Weźmy na przykład C ++. Wszystkie inne rzeczy są względnie równe, kompilator, który musi przeskrobać 9 000 (a może 50 000) linii plików #include w celu skompilowania prostego programu „Hello, World” nigdy nie będzie tak szybki jak jeden które muszą tylko odczytać cztery lub pięć wierszy).
Nie pamiętam, gdzie go przeczytałem, ale oryginalny kompilator Oberona w ETH-Zurich miał bardzo wyrafinowany mechanizm tablic symboli, dość elegancki. Punktem odniesienia dla wydajności kompilatora Wirtha był czas kompilacji kompilatora. Pewnego ranka wszedł do środka, wyciągnął wspaniałą, wielokrotnie połączoną tablicę symboli ultra-drzew i zastąpił ją prostą tablicą liniową i prostymi liniowymi wyszukiwaniami. Doktoranci w jego grupie byli wstrząśnięci. Po zmianie kompilator był szybszy, ponieważ moduły, które kompilował, były zawsze na tyle małe, że elegancki potwór narzucił więcej całkowitych kosztów ogólnych niż tablica liniowa i wyszukiwanie liniowe.
źródło
Twoje pytania, jak już powiedziano, doprowadziły mnie do przekonania, że tak naprawdę chcesz / potrzebujesz wyjaśnienia, czym jest kompilator, czym jest tłumacz i różnic między nimi.
Kompilator odwzorowuje program napisany w języku X na funkcjonalnie równoważny program napisany w języku Y. Na przykład kompilator od Pascal do C może się skompilować
do
Większość kompilatorów kompiluje „w dół”, więc kompilują języki programowania wyższego poziomu na języki niższego poziomu, a ostatecznym językiem niższego poziomu jest kod maszynowy.
Większość kompilatorów kompiluje się bezpośrednio do kodu maszynowego, ale niektóre (zwłaszcza Java i .NET) kompilują się do „kodu bajtowego” ( kod bajtowy Java i CIL ). Pomyśl o kodzie bajtowym jako kodzie maszynowym hipotetycznego komputera. Ten kod bajtowy jest następnie interpretowany lub JIT podczas uruchamiania (więcej na ten temat później).
Tłumacz wykonuje program napisany w jakimś języku Z. Tłumacz interpretuje program krok po kroku, wykonując go w miarę upływu czasu. Na przykład:
Wyobraź sobie, że interpreter patrzy na linię programu dla linii, bada linię, wykonuje to, co robi, patrzy na następną linię i tak dalej.
Najlepszym przykładem tłumacza jest procesor komputera. Interpretuje kod maszynowy i wykonuje go. Sposób działania procesora zależy od jego fizycznej budowy. Sposób działania programu tłumacza zależy od wyglądu jego kodu. CPU interpretuje i wykonuje zatem program interpretera, który z kolei interpretuje i wykonuje dane wejściowe. W ten sposób możesz połączyć tłumaczy.
JITter to kompilator Just-In-Time. JITter to kompilator. Jedyną różnicą jest czas, w którym jest wykonywany: większość programów jest pisana, kompilowana, wysyłana do użytkowników, a następnie wykonywana, ale kod bajtowy Java i CIL są najpierw wysyłane do użytkowników, a następnie tuż przed ich uruchomieniem są kompilowane na maszynę kod ich użytkowników.
C # -> (kompilacja) -> CIL -> wysłane do klienta -> (kompilacja tuż przed wykonaniem) -> kod maszynowy -> (wykonanie)
Ostatnią rzeczą, o której chcesz wiedzieć, jest kompletność Turinga ( link ). Językiem programowania jest Turing Complete, jeśli potrafi obliczyć wszystko, co potrafi „ maszyna Turinga ”, tzn. Jest co najmniej tak „potężna” jak maszyna Turinga. The Church-Turinga teza stanowi, że maszyna Turinga jest co najmniej tak mocny jak każdej maszynie możemy kiedykolwiek zbudować. Wynika z tego, że każdy kompletny język Turinga jest tak samo potężny jak maszyna Turinga, a zatem wszystkie kompletne języki Turinga są równie potężne.
Innymi słowy, dopóki Twój język programowania jest kompletny (prawie wszystkie z nich są), nie ma znaczenia, który język wybierzesz, ponieważ wszystkie mogą obliczyć te same rzeczy. Oznacza to również, że nie ma znaczenia, który język programowania wybierzesz do napisania kompilatora lub tłumacza. Wreszcie, oznacza to, że zawsze możesz napisać kompilator z języka X na Y, jeśli X i Y są kompletne w Turingu.
Pamiętaj, że ukończenie Turinga nie mówi nic o tym, czy Twój język jest wydajny, ani o wszystkich szczegółach implementacji twojego procesora i innego sprzętu, ani o jakości kompilatora, którego używasz dla tego języka. Również twój system operacyjny może zdecydować, że twój program nie ma uprawnień do otwierania pliku, ale to nie utrudnia twojej zdolności do obliczania czegokolwiek - celowo nie zdefiniowałem obliczeń, ponieważ zajęłoby to kolejną ścianę tekstu.
źródło