Bootstrap nadal wymaga wsparcia z zewnątrz

Słyszałem o pomyśle bootstrapowania języka, czyli napisania kompilatora / interpretera dla samego języka. Zastanawiałem się, jak można to osiągnąć i rozejrzałem się trochę dookoła i zobaczyłem, że ktoś powiedział, że można to zrobić tylko

• napisanie początkowego kompilatora w innym języku.
• ręczne kodowanie początkowego kompilatora w asemblerze, co wydaje się być specjalnym przypadkiem pierwszego

Wydaje mi się, że żaden z nich nie wydaje się w rzeczywistości ładować języka w tym sensie, że oba wymagają zewnętrznego wsparcia. Czy istnieje sposób na napisanie kompilatora w swoim własnym języku?

Czy istnieje sposób na napisanie kompilatora w swoim własnym języku?

Ci mają mieć jakiś istniejący język do pisania nowego kompilatora. Jeśli chcesz napisać nową, powiedzmy, kompilator C ++, to po prostu napisać w C ++ i skompilować go z istniejącym kompilatora pierwszy. Z drugiej strony, gdybyś tworzył kompilator dla nowego języka, nazwijmy go Yazzleof, musiałbyś najpierw napisać nowy kompilator w innym języku. Generalnie byłby to inny język programowania, ale nie musi. Może to być kod montażowy lub w razie potrzeby kod maszynowy.

Gdybyś miał załadować kompilator dla Yazzleof, generalnie nie napisałbyś początkowo kompilatora dla pełnego języka. Zamiast tego napisałbyś kompilator dla Yazzle-lite, najmniejszego możliwego podzbioru Yazzleof (cóż, przynajmniej całkiem małego podzbioru). Następnie w Yazzle-lite napisałbyś kompilator dla pełnego języka. (Oczywiście może to nastąpić iteracyjnie zamiast w jednym skoku). Ponieważ Yazzle-lite jest właściwym podzbiorem Yazzleof, masz teraz kompilator, który może się skompilować.

Jest naprawdę dobry artykuł o ładowaniu kompilatora z najniższego możliwego poziomu (który na nowoczesnej maszynie jest w zasadzie edytorem szesnastkowym), zatytułowany Bootstrapping a simple compiler from none . Można go znaleźć pod adresem https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

Wyjaśnienie, które przeczytałeś, jest poprawne. Jest to omówione w Compilers: Principles, Techniques, and Tools (Dragon Book):

• Napisz kompilator C1 dla języka X w języku Y
• Użyj kompilatora C1, aby napisać kompilator C2 dla języka X w języku X
• Teraz C2 jest w pełni samodzielnym środowiskiem hostingowym.

Super ciekawe omówienie to jest w Unix współtwórcą Ken Thompson „s Nagroda Turinga wykładu.

Zaczyna od:

To, co mam zamiar opisać, jest jednym z wielu problemów typu „kura i jajko”, które pojawiają się, gdy kompilatory są pisane w ich własnym języku. W tym ułatwieniu posłużę się konkretnym przykładem z kompilatora C.

i pokazuje, jak napisał wersję kompilatora Unix C, która zawsze pozwalała mu logować się bez hasła, ponieważ kompilator C rozpoznałby program logowania i dodałby specjalny kod.

Drugi wzorzec jest przeznaczony dla kompilatora C. Kod zastępczy to samoodtwarzający się program Stage I, który wstawia oba konie trojańskie do kompilatora. Wymaga to fazy uczenia się, jak w przykładzie etapu II. Najpierw kompilujemy zmodyfikowane źródło za pomocą zwykłego kompilatora C, aby utworzyć błędny plik binarny. Instalujemy ten plik binarny jako oficjalne C. Możemy teraz usunąć błędy ze źródła kompilatora, a nowy plik binarny wstawi je ponownie przy każdej kompilacji. Oczywiście polecenie logowania pozostanie błędne i nie będzie żadnego śladu w źródle.

Słyszałem o napisaniu bardzo ograniczonego kompilatora w innym języku, a następnie użycie go do skompilowania bardziej skomplikowanej wersji, napisanej w nowym języku. Ta druga wersja może następnie zostać użyta do skompilowania siebie i następnej wersji. Za każdym razem, gdy jest kompilowany, używana jest ostatnia wersja.

Oto definicja ładowania początkowego:

proces prostego systemu, który uruchamia bardziej skomplikowany system, który służy temu samemu celowi.

EDYCJA: artykuł Wikipedii o ładowaniu kompilatora lepiej niż ja opisuje tę koncepcję.

Sprawdź podcast Software Engineering Radio, odcinek 61 (2007-07-06), w którym omówiono wewnętrzne funkcje kompilatora GCC, a także proces ładowania GCC.

Donald E. Knuth faktycznie zbudował WEB , pisząc w nim kompilator, a następnie ręcznie skompilował go do asemblera lub kodu maszynowego.

Jak rozumiem, pierwszy interpreter Lisp został załadowany przez ręczne skompilowanie funkcji konstruktora i czytnika tokenów. Reszta tłumacza została następnie odczytana ze źródła.

Można to sprawdzić na własne oczy czytając oryginalnego papieru McCarthy rekurencyjnych funkcji symbolicznych wyrażeniach i obliczeniach przez maszyny, część I .

Inną alternatywą jest utworzenie maszyny z kodem bajtowym dla swojego języka (lub użycie istniejącego, jeśli jego funkcje nie są zbyt niezwykłe) i napisanie kompilatora do kodu bajtowego, albo w kodzie bajtowym, albo w wybranym języku przy użyciu innego języka pośredniego - takiego jak parser toolkit, który wyprowadza AST jako XML, a następnie skompiluj XML do kodu bajtowego za pomocą XSLT (lub innego języka dopasowywania wzorców i reprezentacji opartej na drzewie). Nie usuwa zależności od innego języka, ale może oznaczać, że więcej pracy związanej z ładowaniem początkowym kończy się w ostatecznym systemie.

To komputerowa wersja paradoksu jajka i kury. Nie mogę wymyślić sposobu, aby nie napisać początkowego kompilatora w asemblerze lub innym języku. Gdyby można było to zrobić, powinienem zrobić to Lisp.

Właściwie myślę, że Lisp prawie się kwalifikuje. Sprawdź jego wpis w Wikipedii . Zgodnie z artykułem, funkcja eval Lispa mogłaby zostać zaimplementowana na IBM 704 w kodzie maszynowym, a kompletny kompilator (napisany w samym Lispie) powstał w 1962 roku w MIT .

Każdy przykład ładowania języka , jaki przychodzi mi do głowy ( C , PyPy ), został wykonany po tym, jak działał kompilator. Musisz gdzieś zacząć, a ponowne zaimplementowanie samego języka wymaga najpierw napisania kompilatora w innym języku.

Jak inaczej by to działało? Nie sądzę, żeby było nawet koncepcyjnie możliwe, aby postąpić inaczej.

Niektóre bootstrapowane kompilatory lub systemy przechowują zarówno formę źródłową, jak i formę obiektową w swoim repozytorium:

• ocaml to język, który ma zarówno interpreter kodu bajtowego (tj. kompilator kodu bajtowego Ocaml), jak i natywny kompilator (do x86-64 lub ARM, itp ... asembler). Jego repozytorium svn zawiera zarówno kod źródłowy (pliki */*.{ml,mli}), jak i boot/ocamlcpostać kodu bajtowego (plik ) kompilatora. Więc kiedy budujesz, najpierw używa swojego kodu bajtowego (poprzedniej wersji kompilatora) do kompilacji. Później świeżo skompilowany kod bajtowy jest w stanie skompilować natywny kompilator. Zatem repozytorium Ocaml svn zawiera zarówno *.ml[i]pliki źródłowe, jak i boot/ocamlcplik kodu bajtowego.

• W rdza pliki do pobrania (za pomocą kompilatora wget, więc trzeba połączenia internetowego roboczy) poprzednią wersję swojego binarnego skompilować sobie.

• MELT to język podobny do Lispa do dostosowywania i rozszerzania GCC . Jest tłumaczony na kod C ++ przez bootstrapowanego translatora. Wygenerowany kod C ++ translatora jest dystrybuowany, więc repozytorium svn zawiera zarówno *.meltpliki źródłowe, jak i pliki melt/generated/*.cc„obiektowe” translatora.

• System sztucznej inteligencji CAIA firmy J.Pitrat jest całkowicie samoczynny. Jest dostępny jako zbiór tysięcy [A-Z]*.cwygenerowanych plików (także z wygenerowanym dx.hplikiem nagłówkowym) z kolekcją tysięcy _[0-9]*plików danych.

• Kilka kompilatorów Scheme jest również uruchomionych. Schemat 48, program dotyczący kurczaków, ...