W gazecie refleksje o zaufaniu, Ken Thompson, jeden z twórców Uniksa, pisze fascynujący (i czytelny) przegląd tego, jak kompiluje się kompilator C. Podobne pojęcia można zastosować do CoffeeScript lub dowolnego innego języka.

Idea kompilatora, który kompiluje własny kod, jest niejasno podobna do quine : kodu źródłowego, który po wykonaniu tworzy jako wyjście oryginalny kod źródłowy. Oto jeden przykład kawowego quine ' a. Thompson podał ten przykład C quine:

char s[] = {
    '\t',
    '0',
    '\n',
    '}',
    ';',
    '\n',
    '\n',
    '/',
    '*',
    '\n',
    … 213 lines omitted …
    0
};

/*
 * The string s is a representation of the body
 * of this program from '0'
 * to the end.
 */

main()
{
    int i;

    printf("char\ts[] = {\n");
    for(i = 0; s[i]; i++)
        printf("\t%d,\n", s[i]);
    printf("%s", s);
}

Następnie możesz się zastanawiać, jak kompilator jest nauczany, że sekwencja escape, taka jak '\n' reprezentuje kod ASCII 10. Odpowiedź jest taka, że gdzieś w kompilatorze C, istnieje procedura, która interpretuje literały znaków, zawierające pewne warunki, takie jak ten, aby rozpoznać sekwencje ukośnika wstecznego:

…
c = next();
if (c != '\\') return c;        /* A normal character */
c = next();
if (c == '\\') return '\\';     /* Two backslashes in the code means one backslash */
if (c == 'r')  return '\r';     /* '\r' is a carriage return */
…

Możemy więc dodać jeden warunek do powyższego kodu ...

if (c == 'n')  return 10;       /* '\n' is a newline */

... aby stworzyć kompilator, który wie, że '\n' reprezentuje ASCII 10. Co ciekawe, ten kompilator, i wszystkie kolejne Kompilatory skompilowane przez niego , "wiedzą", że mapowanie, więc w następnej generacji kodu źródłowego można zmienić tę ostatnią linię na

if (c == 'n')  return '\n';

... i zrobi to, co trzeba! 10 pochodzi od kompilatora i nie musi być już jawnie definiowany w kodzie źródłowym kompilatora.¹

Jest to jeden z przykładów funkcji języka C zaimplementowanej w kodzie C. Teraz, powtórz proces ten dla każdej funkcji języka i masz kompilator "self-hosting": kompilator C, który jest napisany w języku C.

¹ fabuła opisana w artykule jest taka, że skoro kompilator może być" nauczony " takich faktów, to może być również źle nauczony generowania plików wykonywalnych w sposób trudny do wykrycia, a taki akt sabotażu może utrzymywać się we wszystkich kompilatorach produkowanych przez skażony kompilator.

Otrzymałeś już bardzo dobrą odpowiedź, jednak chcę zaoferować Ci inną perspektywę, która, miejmy nadzieję, będzie dla Ciebie pouczająca. Najpierw ustalmy dwa fakty, co do których oboje możemy się zgodzić:

1. kompilator CoffeeScript jest programem, który może kompilować programy napisane w CoffeeScript.
2. kompilator CoffeeScript jest programem napisanym w CoffeeScript.

Jestem pewien, że możesz się zgodzić, że zarówno #1, jak i #2 są prawdziwe. Spójrz na te dwa oświadczenia. Czy ty widzisz teraz, że kompilator CoffeeScript jest całkowicie normalny, aby móc skompilować kompilator coffeescript?

Kompilator nie obchodzi co kompiluje. Tak długo, jak jest to program napisany w CoffeeScript, może go skompilować. A sam kompilator CoffeeScript to taki program. Kompilator CoffeeScript nie obchodzi, że jest to kompilator CoffeeScript, który kompiluje. Widzi tylko Kod CoffeeScript. Kropka.

Jak można kompilator kompiluje się sam, czyli co oznacza to stwierdzenie?

Tak, to dokładnie to, co to stwierdzenie znaczy, i mam nadzieję, że teraz widzisz, jak to stwierdzenie jest prawdziwe.

Jak kompilator może się skompilować lub co oznacza to stwierdzenie?

To właśnie oznacza. Po pierwsze, kilka rzeczy do rozważenia. Istnieją cztery obiekty, na które musimy spojrzeć:

• kod źródłowy dowolnego programu CoffeScript
• (wygenerowany) zbiór dowolnego programu CoffeScript
• kod źródłowy kompilatora CoffeScript
• The (generated) assembly Of The CoffeScript kompilator

Teraz powinno być oczywiste, że możesz użyć wygenerowanego zestawu - pliku wykonywalnego-kompilatora CoffeScript, aby skompilować dowolny dowolny program CoffeScript i wygenerować zestaw dla tego programu.

Teraz kompilator CoffeScript sam w sobie jest tylko dowolnym programem CoffeScript, a więc może być kompilowany przez kompilator CoffeScript.

Wydaje się, że Twoje zamieszanie wynika z faktu, że kiedy tworzysz swój własny nowy język, nie mieć kompilator jeszcze można użyć do kompilacji kompilatora. To na pewno wygląda na problem z jajkiem i kurczakiem, prawda?

Wprowadzić proces zwany bootstrapping.

1. piszesz kompilator w już istniejącym języku (w przypadku CoffeScript oryginalny kompilator został napisany w Rubim), który może skompilować podzbiór nowego języka
2. piszesz kompilator, który może skompilować podzbiór nowego języka w nowym sam język. Możesz używać tylko funkcji językowych, które kompilator z powyższego kroku może skompilować.
3. używasz kompilatora z kroku 1, Aby skompilować kompilator z kroku 2. To pozostawia Ci zbiór, który został pierwotnie napisany w podzbiorze nowego języka i który jest w stanie skompilować podzbiór nowego języka.

Teraz musisz dodać nowe funkcje. Powiedzmy, że zaimplementowałeś tylko while - pętle, ale chcesz również for - pętle. To nie jest problem, ponieważ można przepisać każda for - pętla w taki sposób, że jest while - pętla. Oznacza to, że możesz używać tylko while-pętli w kodzie źródłowym kompilatora, ponieważ zestaw, który masz pod ręką, może tylko je skompilować. Ale można tworzyć funkcje wewnątrz kompilatora, które mogą pasować i kompilować for - pętle z nim. Następnie używasz już posiadanego zestawu i kompilujesz nową wersję kompilatora. A teraz masz zestaw kompilatora, który może również parsować i kompilować for - loops! Możesz teraz wrócić do pliku źródłowego i przepisać dowolne while - pętle, których nie chcesz mieć w for-pętle.

Płukać i powtarzać, aż wszystkie funkcje języka, które są pożądane, mogą być skompilowane za pomocą kompilatora.

while i for oczywiście były to tylko przykłady, ale to działa dla każdej nowej funkcji językowej, którą chcesz. I wtedy znajdujesz się w sytuacji, w której znajduje się CoffeScript: kompilator kompiluje się sam.

Jest tam dużo literatury. refleksje o zaufaniu zaufanie jest klasycznym każdy zainteresowany tym tematem powinien przeczytać co najmniej raz.

Małe, ale ważne wyjaśnienie

Tutaj termin kompilator mówi o tym, że istnieją dwa pliki . Jednym z nich jest plik wykonywalny, który pobiera jako pliki wejściowe napisane w CoffeScript i tworzy jako plik wyjściowy inny plik wykonywalny, łączony plik obiektowy lub współdzieloną bibliotekę. Drugi to plik źródłowy CoffeeScript, który tak się składa, że opisuje procedurę kompilacji coffeescript.

Zastosujesz pierwszy plik do drugiego, tworząc trzeci, który jest w stanie wykonać ten sam akt kompilacji co pierwszy (ewentualnie więcej, jeśli drugi plik definiuje funkcje nie zaimplementowane przez pierwszy), a więc może zastąpić pierwszy, jeśli chcesz.

1. kompilator CoffeeScript został napisany w Rubim.
2. kompilator CoffeeScript został następnie napisany ponownie w CoffeeScript.

Ponieważ wersja Ruby kompilatora CoffeeScript już istniała, została użyta do stworzenia wersji coffeescript kompilatora coffeescript.

Jest to znany jako kompilator self-hosting .

Tu nie chodzi o Kompilatory, ale o ekspresję języka, ponieważ kompilator jest tylko programem napisanym w jakimś języku.

Kiedy mówimy, że "język jest napisany/zaimplementowany", mamy na myśli, że kompilator lub interpreter dla tego języka jest zaimplementowany. Istnieją języki programowania, w których można pisać programy, które implementują ten język (są kompilatorami/interpretatorami dla tego samego języka). Języki te nazywane są uniwersalnymi języki .

Aby to zrozumieć, pomyśl o metalowej tokarce. Jest to narzędzie służące do kształtowania metalu. Za pomocą tego narzędzia można stworzyć kolejne, identyczne narzędzie, tworząc jego części. Tak więc narzędzie to jest maszyną uniwersalną. Oczywiście pierwszy z nich powstał przy użyciu innych środków (innych narzędzi) i prawdopodobnie był niższej jakości. Ale pierwszy z nich został użyty do budowy nowych z większą precyzją.

Drukarka 3D to niemal uniwersalna maszyna. Ty można wydrukować całą drukarkę 3D za pomocą drukarki 3D (nie można zbudować końcówki, która topi plastik).

Dowód przez indukcję

Krok indukcyjny

N + 1 wersja kompilatora jest napisana w X.

W ten sposób może być skompilowany przez N-tą wersję kompilatora (również napisaną w X).

Base case

Ale pierwsza wersja kompilatora napisana w X musi być skompilowana przez kompilator X, który jest napisany w języku innym niż X. Ten krok nazywa się bootstrapping kompilatora.

Kompilatory przyjmują specyfikację wysokiego poziomu i przekształcają ją w implementację niskiego poziomu, taką jak może być wykonywana na sprzęcie. Dlatego nie ma związku między formatem specyfikacji a rzeczywistym wykonaniem poza semantyką języka, który jest adresowany.

Kompilatory krzyżowe przenoszą się z jednego systemu do innego systemu, Kompilatory krzyżowe kompilują specyfikację jednego języka do innej specyfikacji języka.

W zasadzie kompilowanie jest tylko tłumaczenie, a poziom jest zwykle wyższy-poziom języka do niższego-poziom języka, ale istnieje wiele wariantów.

Kompilatory Bootstrapujące są oczywiście najbardziej mylące, ponieważ kompilują język, w którym są napisane. Nie zapomnij o początkowym etapie bootstrapowania, który wymaga co najmniej minimalnej istniejącej wersji wykonywalnej. Wiele bootstrappowanych kompilatorów pracuje najpierw nad minimalnymi funkcjami języka programowania i dodaje dodatkowe złożone funkcje języka idąc do przodu, o ile nowa funkcja może być wyrażona przy użyciu poprzednich funkcji. Gdyby tak nie było, wymagałoby to wcześniejszego opracowania tej części "kompilatora" w innym języku.