jak napisać kłajna

To jest tekst o tym, jak napisać kłajn (https://en.wikipedia.org/wiki/Quine_%28computing%29), czyli program, który wypisuje swoje źródło bez korzystania z introspekcji. Zakładam, że czytelnik już kiedyś spotkał się z kłajnami, może nawet próbował napisać kłajna i czuje, dlaczego to jest trudne i ciekawe. Tekst składa się z dwu części: w pierwszej mówię, na jakiej zasadzie to będzie działać, w drugiej opisuję szczegółowo, jak napisać kłajna.

jak będzie działać kłajn

Teraz opowiem, jak dałoby się zrobić maszynę, która umie zbudować własną kopię. Oczywiście najprościej byłoby, żeby maszyna obejrzała samą siebie, zobaczyła, jak jest zbudowana, i zbudowała takie samo coś. Ale czy dałoby się zbudować maszynę, która umiałaby zbudować własną kopię bez introspekcji?

Najpierw zbudowałbym maszynę, która umie zbudować dowolną rzecz, jeśli tylko ma kartkę z jej planem. Mozna by powiedzieć, że taka maszyna to - dopóki nie włoży się w nią kartki z planem - żadna maszyna, bo jak ją włączyć, to nic nie zrobi, ale to nic. I tak jest fajna, bo wystarczy włożyć w nią kartkę z planem kajaka i będziemy mieli maszynę budującą kajak, wystarczy włożyć w nią kartkę z planem taczek i będziemy mieli maszynę budującą taczki itp. To może włożyć w nią kartkę z jej własnym planem i dostaniemy maszynę budującą własną kopię. Jest jeden problem: co będzie narysowane na tym planie w miejscu, gdzie jest narysowany zasobnik na plan? Czy ten zasobnik będzie pusty? Jeśli tak, to maszyna zbudowana według tego planu nie będzie umiała nic zbudować. A może na tym planie w miejscu, gdzie jest narysowany zasobnik na plan będzie narysowany dokładniutko plan tej maszyny? Już lepiej, tylko co powinno być narysowane na tym planie narysowanym na planie w miejscu, gdzie jest narysowany rysunek zasobnika na plan? Niestety, są dwie możliwości: albo na którymś z planów zasobnik będzie pusty - co oznacza, że maszyna nie zbuduje swojej idealnej kopii - albo nigdy nie skończymy rysować tego planu.

Zachęcam: zatrzymaj się tu na chwilę. Powyobrażaj sobie to wszystko, aż poczujesz się z tym swobodnie. Wyobraź sobie maszynę, która umie zrobić dowolną rzecz, jeśli tylko w jej zasobnik na plan jest włożony plan tej rzeczy. Wyobraź sobie, jak wkładamy w ten zasobnik plan biurka (samochodu, patelni, słuchawek, telefonu), wciskamy przycisk, a ona to robi. Teraz wyobraźmy sobie, że rysujemy plan tej maszyny, wkładamy ten plan w zasobnik na plan i uruchamiamy maszynę. Z maszyny-rodzica wyskakuje maszyna dziecko, uruchamiamy maszynę-dziecko - i co się wtedy stanie? A teraz kolejny eksperyment myślowy: rysujemy plan tej maszyny, ale tym razem na planie, na miejscu, gdzie jest narysowany zasobnik na plan, rysujemy plan biurka, po czym uruchamiamy maszynę, wyskakuje z niej maszyna-dziecko, uruchamiamy tę maszynę-dziecko - i co się teraz stanie? A teraz kolejny eksperyment myślowy: rysujemy plan tej maszyny, ale tym razem na planie, na miejscu, gdzie jest narysowany zasobnik na plan, rysujemy plan tej maszyny, z pustym zbiornikiem na plan. Po czym uruchamiamy maszynę, wyskakuje z niej maszyna-dziecko, uruchamiamy tę maszynę-dziecko... czy widzisz oczyma wyobraźni, co się dzieje?

A można przerobić tę maszynę, żeby działała trochę inaczej: żeby produkowała to, co jest narysowane na planie, a potem żeby kserowała kartkę z planej, na wyprodukowanej rzeczy znajdowała miejsce oznaczone napisem "tutaj" i w to miejsce włożyła tę kserówkę. A na kartce narysujemy dokładny plan tej maszyny, ale uwaga: z pustym zasobnikiem, na którym jest napisane "tutaj". I teraz patrz, co się stanie, kiedy włączymy maszynę: zbuduje swoją kopię ale niewyposażoną w żaden plan, skseruje plan i włoży go w zasobnik. I w ten sposób stworzyła swoją dokładną kopię.

Jeśli w tym momencie masz poczucie, że oszukuję, bo zrobienie kopii planu jest rodzajem introspekcji, jeśli masz do mnie żal, że nie powiedziałem dokładnie, jakie działania są niedozwoloną introspekcją, a jakie - na przykład kserowanie planu - nie, to odpędź od siebie te myśli. Ta cała opowieść o maszynie nie jest samodzielną zagadką. Ona nawet nie musi się idealnie trzymać kupy. Ona służy tylko temu, żebyś zaraz lepiej zrozumiał, dlaczego kłajn, który napiszę za chwilę, jest zbudowany tak, jak jest zbudowany, i jak to się dzieje, że on działa. Mi porównanie tego kłajna (tego, który za chwilę napiszę) do takiej maszyny dużo pomogło, dlatego i tobie o tej maszynie opowiadam.

Zwróćmy uwagę na jeden szczegół, który w przypadku maszyny jest mało istotny, ale będzie miał znaczenie, kiedy już naprawdę będę pisał kłajna. Ta maszyna po wyprodukowaniu maszyny nie może jej od razu oddać osobie, która nacisnęła przycisk - musi jeszcze przez chwilę ją potrzymać w rękach, żeby włożyć do niej kopię planu.

A teraz uwaga, podsumowanie, jak działa ta maszyna:

  1. ktoś wciska przycisk, maszyna rusza
  2. na podstawie planu produkuje maszynę umiejącą produkować dowolną rzecz na podstawie planu
  3. robi kopię planu
  4. wkłada tę kopię planu w zrobioną przez siebie maszynę
  5. oddaje zrobioną przez siebie maszynę wyposażoną w plan temu, kto wcisnął przycisk

Zachęcam: zatrzymaj się tu na chwilę. Powyobrażaj sobie to wszystko, aż poczujesz się z tym swobodnie. Wyobrażaj sobie dokładnie, po kolei, porządnie, wizualnie, jak ta maszyna działa, jak produkuje maszynę-dziecko, jak kseruje plan, jak wkłada kserówkę w maszynę dziecko, jak uruchamiamy maszynę-dziecko, co robi ta maszyna-dziecko, jak potem uruchamiamy maszynę-wnuczka... i tak dalej.

piszę kłajna

A teraz napiszę kłajna - czyli program wyświetlający sam siebie (bez korzystania z introspekcji). Najpierw napiszę go w Pythonie, żebyś pokazać, jak się pisze kłajna, a potem jeszcze napiszę w różnych innych językach, żeby pokazać, jakie mogą się pojawić problemy specyficzne dla danego języka i jak sobie z nimi poradzić

Najpierw zauważmy, że program wyświetlający sam siebie to szczególny przypadek programu, który wyświetla coś. Więc zacznę od napisania programu, który wyświetla coś. W Pythonie najprościej zrobić to tak:

print()

To jest program, który może wyświetlić cokolwiek - wystarczy to cokolwiek wstawić w nawiasy. Póki się tam niczego nie wstawi, ten program jest do niczego (jak maszyna bez planu), ale kiedy na przykład wstawię w te nawiasy słowo Polska, otrzymam program wyświetlający słowo Polska:

print('Polska')

Następnie zauważmy, że program wyświetlający sam siebie to program, który wyświetla program, który wyświetla sam siebie. A to z kolei jest szczególny przypadek programu, który wyświetla program, który wyświetla coś. Więc napiszmy program, który wyświetla program, który wyświetla coś. W Pythonie najprościej zrobić to tak:

print('print ()')

To jest program, który tworzy program, który może wyświetlić cokolwiek - wystarczy to cokolwiek wstawić w nawiasy. Jest on jak maszyna, która produkuje maszynę, która może wyprodukować cokolwiek, byle dać jej plan. Póki w te nawiasy się niczego nie wstawi, ten program jest do niczego (jak maszyna produkująca maszynę nie wyposażoną w plan), ale kiedy na przykład wstawię w te nawiasy słowo Polska, otrzymam program wyświetlający program wyświetlający słowo Polska:

print('print ("Polska")')

Jeszcze raz porównajmy to sobie z maszynami, o których pisałem w pierwszej części. Program print() jest jak maszyna, która może zrobić cokolwiek, byle dać jej plan tego cokolwiek. Napis 'print()' jest jak plan tej maszyny. Program print('print ()') jest jak maszyna umiejąca zrobić cokolwiek, jeśli dać jej plan, która w zasobniku na plan ma włożony plan maszyny, która zrobi cokolwiek, jeśli dać jej plan, która zasobnik na plan ma pusty. A program print('print ("Polska")') jest jak maszyna umiejąca zrobić cokolwiek, jeśli dać jej plan, która w zasobniku na plan ma włożony plan maszyny, która zrobi cokolwiek, jeśli dać jej plan, która w zasobniku na plan ma włożony plan słowa Polska. Zauważmy, że to nie jest program wypisujący swoje źródło - choć jest to program wypisujący źródło programu podobnego do siebie, więc jesteśmy całkiem blisko.

Teraz musimy zrobić manewr podobny, jak w pierwszej części robiliśmy z maszynami. Pamiętaz, jak w planie maszyny-dziecka na zasobniku na plan napisałem tutaj? No to teraz zrobię podobnie. Patrz:

print('print (tutaj)')

Czy pamiętasz, jak przerabiałem maszynę, żeby przed zwróceniem maszyny-dziecka w jej zasobnik wkładaliśmy kopię planu, na podstawie którego została zrobiona? To teraz zrobię podobnie: przerobię ten program, żeby po stworzeniu napisu ale przed wyświetleniem go w miejsce oznaczone słowem tutaj wkładała kopię tego napisu. Na razie niełatwo to zrobić, bo stworzenie napisu i wyświetlenie go jest w jednym poleceniu, więc nie ma kiedy zrobić tej podmianki. No to rozdzielę w tym programie stworzenie napisu od jego wyświetlenia:

napis='print (tutaj)'; print(napis)

Ale zaraz - skoro zmieniłem program, to powinienem zmienić też literał tego programu, żeby rodzic tworzył dziecko podobne do siebie:

napis='napis=tutaj; print (napis)'; print(napis)

Teraz dodaję do programu polecenie, które przed wyświetleniem napisu w miejsce słowa tutaj wstawia kopię tego napisu:

napis='napis=tutaj; print (napis)'; napis=napis.replace('tutaj', napis); print(napis)

Uruchamiam ten program i widzę:

napis=napis=tutaj; print (napis); print (napis)

Aha. Nie całkiem to, o co chodziło. Ten napis wstawiany za słowo tutaj ma być wzięty w cudzysłów. Jest w Pythonie do tego gotowa funkcja, która nazywa się repr. No to niech jej użyję: