Kiedy ma sens najpierw skompilować mój własny język do kodu C?

34

Kiedy projektując własny język programowania, warto napisać konwerter, który pobiera kod źródłowy i konwertuje go na kod C lub C ++, aby móc użyć istniejącego kompilatora, takiego jak gcc, aby uzyskać kod maszynowy? Czy istnieją projekty wykorzystujące to podejście?

danijar
źródło
4
Jeśli spojrzysz poza C, zobaczysz, że C # i Java również kompilują się do języków pośrednich. Jesteś oszczędzony przed ponowną pracą, którą wykonał ktoś inny, kierując się na język pośredni zamiast przechodzić bezpośrednio do asemblera.
Casey
1
@emodendroket Jednak C # i Java kompilują się do IL, która została zaprojektowana jako ogólnie IL, a konkretnie dla C # / Java, więc pod wieloma względami kod bajtowy CIL i JVM jest bardziej sensowny i wygodny, ponieważ IL może być kiedykolwiek. Nie chodzi o to, czy użyć żadnego języka pośredniego, ale o to, który język pośredni zastosować.
1
Spójrz na kilka implementacji wolnego oprogramowania generujących kod C. I mam nadzieję, że uczynisz swoją implementację językową darmowym oprogramowaniem.
Basile Starynkevitch
2
Oto zaktualizowany link z komentarza @ RobertHarvey: yosefk.com/blog/c-as-an-intermediate-language.html .
Christian Dean

Odpowiedzi:

52

Tłumaczenie kodu C jest bardzo dobrze ugruntowanym nawykiem. Oryginalne C z klasami (i wczesne implementacje C ++, zwane wtedy Cfront ) zrobiły to z powodzeniem. Robi to kilka implementacji Lisp lub Scheme, np. Chicken Scheme , Scheme48 , Bigloo . Niektórzy ludzie tłumaczone Prolog do C . Podobnie stało się z niektórymi wersjami Mozarta (i próbowano skompilować kod bajtowy Ocaml do C ). System CAIA sztucznej inteligencji J.Pitrat jest również ładowany i generuje cały swój kod C. Vala tłumaczy również na C dla kodu związanego z GTK. Książka Queinnec Lisp In Small Pieces mieć rozdział o tłumaczeniu na C.

Jednym z problemów przy tłumaczeniu na C są wywołania rekurencyjne . Standard C nie gwarantuje, że kompilator C przetłumaczy je poprawnie (na „skok z argumentami”, tj. Bez spożywania stosu wywołań), nawet jeśli w niektórych przypadkach najnowsze wersje GCC (lub Clang / LLVM) dokonują takiej optymalizacji .

Kolejnym problemem jest zbieranie śmieci . Kilka implementacji korzysta tylko z konserwatywnego śmieciarza Boehm (który jest przyjazny dla C ...). Jeśli chcesz wyrzucić śmieci (tak jak robi to kilka implementacji Lisp, np. SBCL), może to być koszmar (chciałbyś dlclosena Posix).

Jeszcze inna sprawa dotyczy pierwszorzędnych kontynuacji i call / cc . Ale możliwe są sprytne sztuczki (zajrzyj do Kurczaka). Dostęp do stosu wywołań może wymagać wielu trików (ale patrz śledzenie GNU itp.). Ortogonalna trwałość kontynuacji (tj. Stosów lub nici) byłaby trudna w C.

Obsługa wyjątków jest często kwestią emitowania sprytnych połączeń do longjmp itp.

Możesz wygenerować (w emitowanym kodzie C) odpowiednie #linedyrektywy. Jest to nudne i zajmuje dużo pracy (będziesz chciał, aby np. gdbStworzyć łatwiejszy do debugowania kod).

Mój język specyficzny dla domeny MELT lispy (w celu dostosowania lub rozszerzenia GCC ) jest przetłumaczony na język C (obecnie na słaby C ++). Ma swój własny generator kopiujący śmieci. (Być może zainteresuje Cię Qish lub Ravenbrook MPS ). W rzeczywistości generowanie GC jest łatwiejsze w generowanym maszynowo kodzie C niż w ręcznie napisanym kodzie C (ponieważ dostosujesz generator kodu C do bariery zapisu i maszyn GC).

Nie znam żadnej implementacji języka tłumaczącej na oryginalny kod C ++, tj. Używającej techniki „gromadzenia pamięci podczas kompilacji” do emitowania kodu C ++ przy użyciu wielu szablonów STL i szanujących idiom RAII . (proszę powiedzieć, jeśli znasz).

Dziwne jest dziś to, że (na obecnych komputerach z systemem Linux) kompilatory C mogą być wystarczająco szybkie, aby zaimplementować interaktywną pętlę read-eval-print- top przetłumaczoną na język C: będziesz emitować kod C (kilkaset linii) dla każdego użytkownika interakcji, będziesz forkkompilować go w obiekt współdzielony, który wtedy będziesz dlopen. (MELT robi to wszystko gotowe i zwykle jest wystarczająco szybkie). Wszystko to może zająć kilka dziesiątych sekundy i może być zaakceptowane przez użytkowników końcowych.

Jeśli to możliwe, polecam tłumaczenie na C, a nie na C ++, w szczególności dlatego, że kompilacja w C ++ jest powolna.

Jeśli implementujesz swój język, możesz również rozważyć (zamiast emitować kod C) niektóre biblioteki JIT, takie jak libjit , błyskawica GNU , asmjit , a nawet LLVM lub GCCJIT . Jeśli chcesz przetłumaczyć na C, możesz czasami użyć tinycc : kompiluje bardzo szybko wygenerowany kod C (nawet w pamięci), aby spowolnić kod maszynowy. Ale ogólnie chcesz skorzystać z optymalizacji przeprowadzonych przez prawdziwy kompilator C, taki jak GCC

Jeśli tłumaczysz na swój język C, pamiętaj, aby najpierw skompilować cały AST wygenerowanego kodu C w pamięci (ułatwia to również wygenerowanie najpierw wszystkich deklaracji, a następnie wszystkich definicji i kodu funkcji). W ten sposób można dokonać optymalizacji / normalizacji. Ponadto możesz być zainteresowany kilkoma rozszerzeniami GCC (np. Gotos komputerowy). Prawdopodobnie będziesz chciał uniknąć generowania ogromnych funkcji C - np. Ze stu tysięcy linii wygenerowanego C - (lepiej podzielisz je na mniejsze części), ponieważ optymalizacja kompilatorów C jest bardzo niezadowolona z bardzo dużych funkcji C (w praktyce i doświadczalnie,gcc -Oczas kompilacji dużych funkcji jest proporcjonalny do kwadratu wielkości kodu funkcji). Więc ogranicz rozmiar generowanych funkcji C do kilku tysięcy linii każda.

Zauważ, że zarówno kompilatory Clang (przez LLVM ), jak i GCC (przez libgccjit ) C & C ++ oferują jakiś sposób na emisję wewnętrznych reprezentacji odpowiednich dla tych kompilatorów, ale może to (lub nie) być trudniejsze niż emisja kodu C (lub C ++), i jest specyficzny dla każdego kompilatora.

Jeśli projektujesz język, który ma zostać przetłumaczony na C, prawdopodobnie potrzebujesz kilku sztuczek (lub konstrukcji), aby wygenerować mieszankę C z twoim językiem. Mój dokument DSL2011 MELT: przetłumaczony język specyficzny dla domeny osadzony w kompilatorze GCC powinien dać ci przydatne wskazówki.

Basile Starynkevitch
źródło
Masz na myśli „Schemat kurczaka”?
Robert Harvey
1
Tak, podałem adres URL.
Basile Starynkevitch
Czy względnie praktyczne jest stworzenie maszyny wirtualnej, takiej jak Java czy coś takiego, skompilowanie kodu bajtowego do C, a następnie użycie gcc do kompilacji JIT? A może powinny przejść od kodu bajtowego do zestawu?
Panzercrisis
1
@Panzercrisis Większość kompilatorów JIT wymaga zaplecza kodu maszynowego do obsługi takich funkcji, jak zamiana funkcji i łatanie istniejącego kodu drzwiami skokowymi / pułapkowymi. Poza tym gcc jest ... architektonicznie mniej odpowiedni do kompilacji JIT i innych przypadków użycia. Sprawdź jednak libgccjit: gcc.gnu.org/ml/gcc-patches/2013-10/msg00228.html i gcc.gnu.org/wiki/JIT
1
Świetny materiał orientacyjny. Dzięki!
capr
7

Ma to sens, gdy czas na wygenerowanie pełnego kodu maszynowego przeważa nad niedogodnością związaną z pośrednim etapem kompilowania „IL” w kodzie maszynowym przy użyciu kompilatora C.

Zazwyczaj języki specyficzne dla domeny są pisane w ten sposób, do zdefiniowania lub opisania procesu, który jest następnie kompilowany do pliku wykonywalnego lub biblioteki DLL, używany jest system bardzo wysokiego poziomu. Czas potrzebny na wytworzenie działającego / dobrego zestawu jest znacznie dłuższy niż wygenerowanie C, a C jest dość blisko kodu asemblera pod względem wydajności, więc rozsądne jest wygenerowanie C i ponowne wykorzystanie umiejętności pisarzy kompilatora C. Zauważ, że nie jest to tylko kompilacja, ale także optymalizacja - faceci, którzy piszą gcc lub llvm, spędzili dużo czasu na tworzeniu zoptymalizowanego kodu maszynowego, głupio byłoby spróbować odkryć na nowo całą ich ciężką pracę.

Bardziej akceptowalnym rozwiązaniem może być ponowne użycie zaplecza kompilatora LLVM, którego IIRC jest neutralny językowo, więc zamiast kodu C generujesz instrukcje LLVM.

gbjbaanb
źródło
Wydaje się, że biblioteki są dość istotnym powodem, aby to rozważyć.
Casey
Kiedy mówisz „twoja IL”, o czym mówisz? Abstrakcyjne drzewo składniowe?
Robert Harvey
@RobertHarvey nie, mam na myśli kod C. W przypadku PO jest to język pośredni w połowie drogi między jego własnym językiem wysokiego poziomu a kodem maszynowym. Podaję go w cudzysłowie, aby spróbować przekazać ten pomysł, że nie jest to IL używane przez wiele osób (np. Microsoft .NET IL na przykład)
gbjbaanb
2

Napisanie kompilatora do wygenerowania kodu maszynowego może nie być dużo trudniejsze niż napisanie kompilatora, który produkuje C (w niektórych przypadkach może być łatwiejsze), ale kompilator, który tworzy kod maszynowy, będzie w stanie wytwarzać uruchamialne programy tylko na konkretnej platformie, dla której to było napisane; kompilator, który wytwarza kod C, przeciwnie, może być w stanie wyprodukować program dla dowolnej platformy, która używa dialektu C, który generowany kod ma obsługiwać. Należy pamiętać, że w wielu przypadkach może być możliwe napisanie kodu C, który jest całkowicie przenośny i który będzie działał zgodnie z potrzebami bez użycia zachowań nie gwarantowanych przez standard C, ale kod, który opiera się na zachowaniach gwarantowanych przez platformę, może działać znacznie szybciej na platformach, które dają takie gwarancje, niż kod, który tego nie robi.

Załóżmy na przykład, że język obsługuje funkcję, która generuje UInt32z czterech kolejnych bajtów arbitralnie wyrównanego UInt8[], interpretowanego w sposób big-endian. W niektórych kompilatorach można napisać kod jako:

uint32_t dat = *(__packed uint32_t*)p;
return (dat >> 24) | (dat >> 8) | ((uint32_t)dat << 8) | ((uint32_t)dat << 24));

i niech kompilator wygeneruje operację ładowania słowa, a następnie instrukcję odwrotnego bajtu w słowie. Niektóre kompilatory nie obsługiwałyby modyfikatora __packed i pod jego nieobecność generowałyby kod, który nie działałby.

Alternatywnie można napisać kod jako:

return dat[3] | ((uint16_t)dat[2] << 8) | ((uint32_t)dat[1] << 16) | ((uint32_t)dat[0] << 24);

taki kod powinien działać na dowolnej platformie, nawet tam, gdzie CHAR_BITSnie ma 8 (zakładając, że każdy oktet danych źródłowych kończy się w odrębnym elemencie tablicy), ale taki kod może prawdopodobnie nie działać tak szybko, jak w przypadku nieprzenośnego wersja na platformy obsługujące te pierwsze.

Należy pamiętać, że przenośność często wymaga, aby kod był wyjątkowo liberalny w przypadku typecastów i podobnych konstrukcji. Na przykład kod, który chce pomnożyć dwie 32-bitowe liczby całkowite bez znaku i uzyskać niższe 32 bity wyniku, musi być zapisany jako przenośny:

uint32_t result = 1u*x*y;

Bez tego 1ukompilator w systemie, w którym INT_BITS zawierał się w przedziale od 33 do 64, mógł legalnie zrobić wszystko, co chciał, gdyby iloczyn xiy był większy niż 2 147 483 647, a niektóre kompilatory mają skłonność do korzystania z takich możliwości.

supercat
źródło
1

Powyżej masz doskonałe odpowiedzi, ale biorąc pod uwagę, że w komentarzu odpowiedziałeś na pytanie „Dlaczego przede wszystkim chcesz stworzyć własny język programowania?” Za pomocą „Byłoby to głównie do celów uczenia się”, „Ja” Mam zamiar odpowiedzieć pod innym kątem.

Sensowne jest napisanie konwertera, który pobiera kod źródłowy i konwertuje go na kod C lub C ++, dzięki czemu można użyć istniejącego kompilatora, takiego jak gcc, aby uzyskać kod maszynowy, jeśli jesteś bardziej zainteresowany nauczeniem się leksyki, składni i analiza semantyczna niż w nauce generowania i optymalizacji kodu!

Pisanie własnego generatora kodu maszynowego jest dość znaczącym dziełem, którego można uniknąć, kompilując do kodu C, jeśli nie jest to tym, czym jesteś zainteresowany!

Jeśli jednak interesuje Cię program asemblacyjny i fascynują Cię wyzwania związane z optymalizacją kodu na najniższym poziomie, to napewno napisz generator kodu do nauki!

Carson63000
źródło
-7

Zależy od używanego systemu operacyjnego, jeśli używasz systemu Windows, istnieje Microsoft IL (język pośredni), który konwertuje kod na język pośredni, dzięki czemu kompilacja w kod maszynowy nie zajmuje czasu. Lub Jeśli używasz Linuksa, istnieje do tego osobny kompilator

Wracając do pytania, kiedy projektując własny język, powinieneś mieć do tego osobny kompilator lub tłumacz, ponieważ maszyna nie zna języka wysokiego poziomu. Twój kod powinien zostać skompilowany w kod maszynowy, aby był użyteczny na komputerze

Tayyab Gulsher Vohra
źródło
2
Your code should be compiled into machine code to make it useful for machine- Jeśli twój kompilator wygenerował kod c jako wynik, możesz umieścić kod c w kompilatorze ac, aby wygenerować kod maszynowy, prawda?
Robert Harvey
tak. ponieważ maszyna nie obsługuje języka C
Tayyab Gulsher Vohra
2
Dobrze. Pytanie brzmiało więc: „Kiedy sensem jest emitować c i używać kompilatora ac, zamiast bezpośrednio emitować język maszynowy lub kod bajtowy?”
Robert Harvey
w rzeczywistości prosi o zaprojektowanie swojego języka programowania, w którym prosi: „konwertuje go na kod C lub C ++”. Wyjaśniam to, jeśli projektujesz własny język programowania, dlaczego powinieneś używać kompilatora c lub c ++. jeśli jesteś wystarczająco inteligentny, powinieneś zaprojektować swój własny
Tayyab Gulsher Vohra
8
Nie sądzę, że rozumiesz pytanie. Zobacz yosefk.com/blog/c-as-an-intermediate-language.html
Robert Harvey