Ogólne zasady pisania kompilatora X w Z w Y

9

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.

python compiler

— jaimechen
źródło

Nie bezpośrednio związane, ale nieco podobna koncepcja: en.wikipedia.org/wiki/Supercompilation

— SK-logic

1

Nie jestem pewien, czy to pytanie naprawdę pasuje do Przepełnienia stosu, zwłaszcza, że jest w nim tak wiele pytań, ale nadal podziwiam myśl, która się w to pojawiła.

4

Pomimo tego, czego mogłeś się nauczyć, AST nie jest wymagany - jest to po prostu strategia stosowana przez niektóre kompilatory.

1

Prawdopodobnie należy to do cstheory.stackexchange.com

— 9000

3

Implementacja Pythona w PyPy, podobnie jak większość „interpreterów”, jest tak naprawdę kompilatorem bajtekodowym i interpretatorem tego formatu bajtowego w jednym.

4

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?

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.

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?

Czy istnieje kompilator py2rpy? Teoretycznie tak. Turing gwarantuje kompletność .

Jedną z metod konstruowania py2rpyjest 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:

// suppose that /pypy/source/ contains the source code for pypy (i.e. Python -> Nothing RPython)
cp /pypy/source/ /tmp/py2rpy/pypy/

// suppose $inputfile contains an arbitrary Python source code
cp $inputfile /tmp/py2rpy/prog.py

// generate the main.rpy
echo "import pypy; pypy.execfile('prog.py')" > /tmp/py2rpy/main.rpy

cp /tmp/py2rpy/ $outputdir

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ąc rpython 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ę)

q3. Czy dostępne są jakieś ogólne zasady lub teoria?

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”

q4. ...

Tu nie ma pytania.

— Lie Ryan
źródło

Twój kompilator py2rpy jest naprawdę sprytny. To prowadzi mnie do innego pomysłu. 1. Czy pypy musi być napisane w RPython w kompilatorze? Wszystko czego potrzebujesz to coś, co może interpretować pliki Pythona, prawda? 2. os.system ('python $ inputfile') może również działać, jeśli jest obsługiwany w RPython. Nie jestem pewien, czy nadal można go nazwać kompilatorem, a przynajmniej nie dosłownie.

Czy pypy nadal używa maszyny wirtualnej Python? Teraz jest jasne. pypy_the_compiler = Pythonie -> PythonVMCode RPython, pypy_the_interpreter = PythonVMCode -> Nic RPython, cpython_the_compiler = Pythonie -> PythonVMCode C cpython_the_interpreter = PythonVMCode -> Nic C

@jaimechen: 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.

— Lie Ryan

@jaimechen: bardziej praktyczny kompilator mógłby przeanalizować plik wejściowy pod kątem sekwencji kodu, które wie, jak je skompilować i skompilować osobno, a także sposób na przeskakiwanie między Pythonem „rekompilowanym do RPython” a „interpreter- wspomagany „Python. Może także wykorzystywać techniki powszechnie stosowane w kompilacji JIT, aby wykryć, czy dane dane wejściowe mogą generować różne dane wyjściowe z powodu różnic w semantyce RPython i Python oraz powrotu do interpretacji w tych przypadkach. Wszystkie te są wyrafinowaniem, które można zobaczyć w bardziej praktycznym Python -> RPythonkompilatorze.

— Lie Ryan

Być może należy dodać tutaj ograniczenie: przekształć maszynę stanu X w maszynę stanu Z, bez pomocy istniejącej 3. maszyny. Dzieje się tak, gdy X jest całkowicie nowy, jak dotąd nie istniał żaden kompilator ani interpreter.

— jaimechen

2

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.

— użytkownik207421
źródło

Tak, to jest to, dzięki. pl.wikipedia.org/wiki/Tombstone_diagram

— jaimechen

1

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.

— John R. Strohm
źródło

1

Dzięki. Kompilator „kompiluje”, podczas gdy interpreter „wykonuje”, czy może być lepszy wgląd w dwa rodzaje programów, tak jakby ich typy były różne?

— jaimechen

1

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ć

function Square(i: Integer)
begin
    Square := i * i
end

do

int Square(int i)
{
    return i * i;
}

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:

int i = 0;
while (i < 1)
{
    i++
}
return i;

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.

— Alex ten Brink
źródło