Az Escher-quine

(in English)

Ez kicsit bonyolult lesz, emberek.
  A cím két úr nevéből van, akik közül a másodikat közszóként használjuk, kezdjük ővele. Willard Van Orman Quine (1908–2000), a huszadik század egyik legnagyobb hatású filozófusa, matematikai logikus, nyelvfilozófus, számos jelentős gondolat megfogalmazója, mint például a Quine-paradoxon. Ezzel a paradoxonnal magam is találkozom, amikor nyelvet tanulok.

Mondjuk látok egy képet, amin mindenféle dolgok vannak. (Ez itt az Ablak–Zsiráfból való, 11. kiadás, 1971.) Ez magyar anyanyelvű gyerekeknek készült, akik olvasni is tudnak, a szöveget életkorukhoz és tudásszintjükhöz tervezték, de képzeljük el, hogy én most nyelvtanulás céljából tanulmányozom. (Tényleg használok olyan könyveket, amiket lett anyanyelvű kisiskolás gyerekeknek írtak.) Középen a fehér ruhás emberhez az van írva, hogy PÉK, és valamit berak valahová egy lapáttal. Vagy kivesz. Nem tudok magyarul, nem ismerem ezt a szót, és nem ismerem föl, hogy mi történik a képen. Lehet, hogy amúgy gyerek vagyok, és tényleg nem láttam még péket munkában. Vajon rájövök, hogy azok ott maizék, amiket a krāsnsba rak bele, és ez az ember egy maiznieks? És ez egy egyszerű eset, mert a valóságban, amikor az anyanyelvét tanuló kisgyerek valaminek a nevét hallja, akkor legtöbbször ambivalens a szituáció: anya rámutat egy tárgyra, de abban az irányban egy csomó tárgy van, és ha a gyerek azonosítja is a helyeset, netán anya a kezébe veszi, akkor is: az a szó vajon annak az adott konkrét tárgynak a neve, vagy absztrahálnia kell tárgyak egy kategóriájára, és ha igen, melyikre, avagy a tárgy valamely tulajdonságára, vagy valamilyen vele kapcsolatos cselekvésre? Láttam egy filmet valakiről, aki ezer darab tárgynak a nevét ismeri, mindegyik név egy-egy adott konkrét tárgy neve, de egyikről sem tud absztrahálni valamilyen tárgycsoportra, -kategóriára, tárgyak valamilyen tulajdonságára, semmilyen absztrakcióra nem képes. Noha felnőtt – viszont kutya. A kisgyerektől elvárjuk, hogy a labda szót hallva rövid időn belül ne az adott individuális tárgyra asszociáljon, hanem a szót absztrahálja mindazon tárgyakra, amik gömb alakú, eldobva gurulni, repülni, pattogni tudó játékok, ugyanakkor ha ő egy magyar gyerek, akkor azt is elvárjuk tőle, hogy a (szintén korosztályának szókincsébe tartozó) golyó szótól, illetve tárgykategóriától is meg tudja különböztetni, ami egy cseppet sem egyszerű egy magyarul tanuló felnőttnek, akinek angol az anyanyelve, és neki mind a kettő ball.

Hát ilyesmikkel is foglalkozott Quine professzor, és ez adta az indíttatást Douglas Hofstadternek, hogy az ő nevét használja a rekurzió egy sajátos formájára. 1979-ben megjelent Gödel, Escher, Bach: az örök aranyfonat című könyvében (a magyar cím tőlem) quine-oknak nevezi el azokat a számítógépprogramokat, amik elindítva kiírják saját forráskódjukat. Így például az alábbi ZX Spectrumra írt program:
  10 PRINT "Ez itt egy szöveg"
  20 PRINT "(kétsoros)"
  elindítás után ezt fogja kiírni:
  Ez itt egy szöveg
  (kétsoros)
  Ez tehát nem quine. Ahhoz, hogy quine lehessen, a föntebb zölddel írt szöveget kellene kiírnia. No de azt csak akkor fogja kiírni, ha így írjuk:
  10 PRINT "10 PRINT ""Ez itt egy szöveg"""
  20 PRINT "20 PRINT ""(kétsoros)"""
  (az idézőjelben dupla idézőjelet kell írni, ha idézőjelet szeretnénk kiíratni). Csakhogy azzal, hogy a szöveget átírtuk erre a pirossal írt változatra, az lett az elvárás, hogy a piros szöveget írja ki, ne a zöldet. Csak akkor lenne quine. (Ezek a példák egy képzeletbeli Spectrumról vannak, amelyik tud ékezetes betűket is; könnyen meg lehet tanítani neki őket.)
  Azt hiszem, elég nyilvánvaló, hogy quine-t írni nem egyszerű. Ennek ellenére vannak egysoros quine-ok is, mint például ez a Python nyelven írt programocska:

print((lambda s:s%s)('print((lambda s:s%%s)(%r))'))

ami, ha lefuttatjuk egy Pythonul tudó gépen, természetesen azt fogja kiírni, hogy

print((lambda s:s%s)('print((lambda s:s%%s)(%r))'))

Ennélfogva egy quine-t megírni érdekes agytorna, de lefuttatni az unalom netovábbja, pontosan tudjuk, hogy mi fog történni. Meg fog jelenni ugyanaz a szöveg, amit addig is láttunk.
  A programozók azonban imádnak játszani, ezért létrejöttek mindenféle egyéb quine-ok.

Csaló quine-ok. Egy quine-nak elő kell állítania a saját forráskódját még egyszer, nem pedig megnéznie a memóriát vagy a lemezt és elolvasnia a forráskódot. A csaló quine-ok igenis ezt teszik. Természetesen bármely BASIC nyelven értő házi számítógépen egy olyan program, aminek teljes tartalma

1 LIST

azt fogja kiírni, hogy

1 LIST

– tehát quine, de csal, nem készíti el azt a szöveget még egyszer, hogy 1 (szóköz) L I S T, csak kiolvassa a memóriából a programot és kilistázza.
  Uroboroszok. Az ógörögöknél, akiknek az életben gyakran előforduló dolgok mindegyikére volt szavuk, uroborosz saját farkába harapó kígyót jelentett. Azt nem tudom, hogy a kígyók mikor csinálnak effélét, de az uroboroszprogramok megteszik. Adott nyelven (például C++-ban) írunk egy programot, ami elindítva egy másik nyelven (például Javában) írt program forráskódját produkálja; ha ez utóbbi programot elindítjuk, akkor kiírja az eredeti C++ nyelvű program forráskódját. De ez egyszerű eset. Endó Juszke írt egy Ruby nyelvű programot, ami produkál egy Rust nyelvű programot, ami egy Scala nyelvűt, ami egy Scheme nyelvűt, és így tovább, ábécérendben Zsh-ig, aztán jön az A+, Ada, AFNIX és így tovább az ábécén végig, egészen a Ruby nyelvig, összesen százhuszonnyolc programnyelvet mozgat meg avégett, hogy aztán visszakapja ugyanazt a Ruby nyelvű forráskódot, amivel kezdte.
  Multiquine-ok. Több különböző nyelven írt program csoportja, amelyek mindegyike képes arra, hogy a csoport bármelyik tagjának a forráskódját kiírja (ideértve a sajátját is), s egy adott paraméter segítségével választhatunk, hogy melyiket kérjük.
  Sugárzásbiztos quine-ok. Olyan quine-ok, amikből ha bármely (egy darab) karaktert elveszünk, akkor is képesek kiírni a forráskódjukat, éspedig a törölt karakter helyreállításával.
  Nyilván ki lehet még ilyeneket találni. Most éppen kitaláltam a mutálódó quine-t, a sugárzásbiztos ihletésére: kiírja a forráskódját, de elképzelhető, hogy egy karakter hiányozni fog belőle, vagy eggyel több lesz, vagy valamelyik helyett egy másik áll, viszont ettől még továbbra is quine és ki tudja írni a forráskódját, csak megvan az esély ugyanezekre a változásokra, és így tovább, tehát ha az eredeti quine-t lefuttatjuk százszor, akkor kapunk száz quine-gyereket, amik csak egy ponton különböznek az eredetitől, és ha ezeket is lefuttatjuk száz-száz alkalommal, akkor kapunk tízezer quine-unokát, amik már két ponton különböznek, és így tovább, és így tovább. Halvány fogalmam sincs, hogy lehet-e ilyet írni csakugyan. Az én programozói tudásommal az egész kérdéskörhöz hozzá se szagolok.
  Viszont mindazok a programtípusok, amikről eddig szólt a cikk, egyvalamiben megegyeznek. Amikor elindítjuk őket, egy szöveget kapunk. Ami ugyebár a saját forráskódjuk vagy egy másik programé, mindenesetre egy szöveg. Amit be lehet tölteni szövegszerkesztőbe, olvasni lehet, ki lehet nyomtatni. Ezt a cikket egy olyan program kedvéért írtam, aminek a kimenete nem szöveg, hanem cselekvés. Ennek ellenére ez is quine. Ez az Escher-quine.

A kis videón az látható, hogy Nagy Dániel A. egy programot gépel be ZX Spectrumon. A Sinclair-gépeken ezt így csinálják, a képernyő alsó részén van a szerkesztőablak, egyetlen sornyi, és ha az megtelik, akkor fölfelé növekszik; amikor kész (megnyomtuk az Entert), akkor fölugrik a felső képernyőrészbe. A gépelés elég sajátosan történik a Spectrum tarkabarka billentyűzetén: a kurzor nem vonalka és nem kocka, hanem egy villogó betű, K E L C G közül valamelyik, és a betűtől függ, hogy a lenyomott billentyű milyen jelet vagy szót ad. Például az N billentyű L módban kis n betűt ad, C módban Nagyot, K módban a NEXT utasításszót, E módban az INKEY$ függvénynevet, de ismeri még az OVER szót és a , vesszőt is. Ez az egy gomb. Ez a Sinclair-gépek egyedi sajátossága, a nyolcvanas évek elején ez egy úttörő kezdeményezés volt, és mellesleg a Spectrum-rajongók mindmáig imádják. Én legalábbis. Szóval ezért váltakozik ott folyton a K és az L, és ezért jelennek meg a BASIC-szavak egyben, nem pedig betűnként, mert az egy-egy billentyűlenyomás. Direkt rajta van a billentyűzeten a Spectrum BASIC teljes szókincse.
  
  Nos, most, hogy tisztáztuk, mi történik a videón, elmondom, hogy nem ez történik a videón. A videó nem azt mutatja, ahogy Dániel begépeli a programot, hanem a program futása látható rajta. Ez egy quine, hiszen kiírja a saját forráskódját, de nem szövegként, hanem eljátssza, hogy begépeli. Az utánzás szinte tökéletes. Hogy mégis utánzás, azt onnan lehet tudni, hogy az olyan szavak, mint RESTORE, READ, DATA, FLASH, LEN, STR$ és CHR$, úgy jelennek meg, hogy a kurzor előzőleg nem vált E-re, pedig egy valódi Spectrumon (vagy akár egy emulátoron) ezeket a szavakat nem lehet elérni anélkül, hogy előzőleg (a Caps Shift és a Symbol Shift billentyűk együttes lenyomásával) E-re változtatnánk a kurzort, s ezután még ugye rá kell tennünk az ujjunkat a megfelelő kulcsszó billentyűjére, ami időbe telik, ezalatt az E-nek egy rövid időre látszania kellene, ha Dániel maga gépelne. De hát kit zavar ez? A világegyetem mint egész önmagánál egyszerűbb modellel nem írható le. A Spectrum is egy kicsi világegyetem.

Azt a nevet, hogy Escher-quine, én adtam neki. A címbeli másik úrnak, M. C. Eschernek van ez az ismert rajza:
  
  A címe Drawing Hands (Tekenen), és 1948-ban jelent meg. Természetesen erre a rajzra már hivatkozott Hofstadter is az említett könyvben, Escher neve benne is van a címében. De így, hogy Escher-quine (angolul kötőjel nélkül, külön írva), nem találtam meg a neten, így van esély, hogy ezt én találtam ki.
  Definícióm szerint Escher-quine az a quine, ami nem saját forráskódját (önmaga kész állapotát) reprodukálja, hanem saját forráskódjának elkészítését. (© Láng Attila D., 2019.)
  Az eljárás nem egészen ismeretlen a számítástechnika történelmében. Sok filmben láthatók feliratok, amik úgy jelennek meg, mintha azokat egy ember gépelné be egy számítógépbe; ilyen például az 1979-es A fekete lyuk. A számítástechnikai szakirodalomban valaha külön kategóriát képviseltek azok a magazinok, amiket programként írtak meg és terjesztettek, és ezek egy részében az oldalak nem egyszerűen csak megjelentek, hanem a betűket sorban egymás után írta ki a gép, mintha egy ember gépelné be őket éppen akkor. Magam is írtam ilyet. No de ezt quine-nal kombinálni, olyan quine-t írni, ami a saját begépelését imitálja – ez világcsúcs.

Mivel az olvasó böngészője nem Spectrum, meglehetős vesződségembe került egy önmagánál egyszerűbb modellel leírni a Spectrumot és olyan listát készíteni, ami olyan, mint egy igazi Spectrumon. Legalábbis az enyémben olyan. Szürke háttéren jelenik meg fekete betűkkel, igazi Spectrum-betűtípussal. Remélem, az olvasónál is. Úgy az igazi.

Nézzünk meg egy-két apró részletet. Van benne egy olyan (70. sor), hogy PRINT #1;AT 1,0;l$; FLASH 1;c$;: PAUSE 10+20*RND stb. Ez írja ki a sor addig érvényes állapotát (l$) és a kurzort (c$), méghozzá utóbbit villogva (FLASH 1), éspedig az egészet a szerkesztőablakba (PRINT #1). Életszerű körülmények között ez így nem működne, mert a valóságban a kurzor ide-oda mozoghat a szerkesztés alatt álló sorban, de hát itt soha nem javítunk, ezért megfelel. A PAUSE utasítás pedig vár egy kicsit, mielőtt továbbmenne, ez a szünet két virtuális gombnyomás között.
  Tipikusan spectrumos, ahogy a kurzorbetűt tartalmazó c$ értéket kap: LET c$="LK"(1+(a$(i)=":" OR a$(i)=" THEN ")), vagyis „legyen az LK szöveg első karaktere plusz még egyedik (vagyis a második), ha a$-ban az i-edik karakter egy kettőspont vagy a THEN kulcsszó” (Spectrumon az is egyetlen karakter). Alighanem ezt a részt kellene úgy átírni, hogy LET c$="LKE"(1+(a$(i)=":" OR a$(i)=" THEN ")+(a$(i+1)=" RESTORE " OR a$(i+1)=" DATA " OR a$(i+1)=" READ " OR a$(i+1)="CHR$ " OR a$(i+1)="STR$ " OR a$(i+1)="LEN " OR a$(i+1)=" FLASH ")), és akkor megjelenne az E kurzor is, de ezt nem merem biztosan állítani anélkül, hogy beírnám egy emulátorba.
  A főprogram a 20–50. sorokban levő ciklus, ami végigolvassa a DATA sorokban még egyszer leírt saját szövegét, és elkezd bűvészkedni vele. Karakterenként kiírja előbb a programsor számát és DATA részét (i$), aztán a lényeget (a$), ezt a részt a 60. sorbeli rutin csinálja, és a 70. sorban a már látott PRINT végzi a kiírást a villogó kurzorral és a várakozással. Minden sor után töröljük a képernyőt és a képernyő tetejére kiírjuk az addig elkészült programszöveget (p$), mint egy valódi Spectrum. Az o változó feladata arról gondoskodni, hogy amikor már nem fér ki az egész a képernyőre, akkor csak az utolsó néhány sort írjuk ki. (Itt találtam egy szépséghibát: a 120., 130. és a 140. sor gépelése közben a legfelül kiírt sor száma eggyel balra csúszik, a 150. sor gépelésekor pedig egy csonka sor látható fent, de ezek o megfelelő értékének csökkentésével orvosolhatók.)

A quine-ok ezzel a tökéletesség újabb fokára emelkedtek: eddig csak passzívan reprodukálták magukat, de Dániel quine-ja már aktívan elkészíti magát újra. (Nem, de jól hangzik.) A következő fokozatot csak úgy lehet elérni, ha olyan quine-t írunk, ami a quine-t megíró berendezést is virtuálisan elkészíti. Letölti és installálja a szoftverkörnyezetet, amiben ő maga fut. Esetleg rajzol és animál egy robotot, aki legépel egy billentyűzeten egy scriptet, amely megrajzolja és animálja őt magát.
  De az igazi quine, a quine-ok quine-ja az, amely elkészíti önmaga alkotóját, amint megalkotja a quine-t. Ezt a feladatot azonban Isaac Asimov már elvégezte.

A cikket persze elküldtem Dánielnek, aki nagyon kedvesen elmesélte a quine írásának történetét, át is adom neki a szót. Igaza van, tényleg egy csomó minden „csalást” nem vettem észre.

Először is, ez egy „bűvészmutatvány”, abban az értelemben, hogy nem az történik, amit a (figyelmetlen) néző látni vél, de abban az értelemben nem, hogy amit látni vél, az nem csoda, tehát elvileg megvalósítható lenne. Az a mondat szerintem teljesen nem helyénvaló a cikkben, hogy „A világegyetem mint egész önmagánál egyszerűbb modellel nem írható le.” A világegyetemre sem biztos, hogy igaz, de a Spectrumra biztos, hogy nem. Lehetett volna olyan Escher quine-t írni Spectrum BASIC-ben, ami tökéletesen úgy néz ki, mintha valaki begépelné a forráskódját. Az én programom rengeteget „csal”, nem az E kurzor hiánya az egyetlen dolog, amin „lebukik”, hogy nem tényleges programbegépelésről van szó. Példának okáért a legutoljára beírt sor száma után egy > jelnek kéne lenni (sorkurzor), amit én lespóroltam. A K kurzorral beírható kulcsszavak idézőjelen belül nem úgy íródnak be, ahogy nálam, hiszen magától a kurzor nem vált át idézőjelen belül K-ra attól, hogy mi pl. egy PRINT kulcsszót akarunk beírni. Még kettőspont után sem vált át. Az idézőjelen belüli K előállításának kanonikus (a gépkönyvben leírt) módja, hogy beírjuk a THEN kulcsszót, majd miután beírtuk a kívánt utasítást, visszamegyünk és letöröljük. További „lebukás”, hogy amikor már a DATA sorokat pötyögi a program, akkor az idézőjelek rögtön duplán íródnak be, nem két leütéssel. És még van jópár hasonló „csalás”, amik azonban általában olyasmik, amikről a képernyőn történő „hihető” folyamat elvonja a néző figyelmét.
  Miért pont ott húztam meg a határt, ahol? Miért nem implementáltam még egy pár dolgot a fentiekből, amikor pontosan tudatában vagyok annak, hogy hiányoznak és pontosan tudom, hogy hogyan kéne megcsinálni? Ennek oka abban van, ahogy a program készült.
  Nyilván nem úgy készült, ahogy a futtatás mutatja: nem leültem a gép elé és rögtön bepötyögtem a kész programot. A program egy kihívásra készült (van egy Spectrum BASIC csoport a Facebookon, ahol ilyenekkel szórakoztatjuk egymást), ahol az volt a feladat, hogy írjunk programot, ami úgy csinál, mintha egy programot valaki beírna és végrehajtaná. A feladat kiírója persze arra gondolt, hogy valami kis egyszerű programocskát fog „bepötyögni és végrehajtani” a feladat megoldása, de nekem rögtön az jutott eszembe, hogy mekkorát szólna, ha ugyanezt egy quine csinálná (tényleg nagyot szólt). Az ötlet úgy megihletett, hogy éjféltől hajnali háromig dolgoztam rajta, amíg elégedett nem lettem az eredménnyel. A program írásának folyamata magyarázza, hogy miért pont ott álltam meg, ahol, illetve egészen pontosan miért pont odáig vágtam vissza (pl. a > kiírása egy ponton benne volt a programban, de kiszedtem).
  Nyilván azzal kezdtem, hogy írtam egy olyan quine-t, ami soronként írja ki magát. Ez egy egyszerű kétmenetű ciklus, ami DATA sorokból kiolvas valamit, és azt az első menetben simán kiírja sorszámokkal, a második menetben pedig köré tesz idézőjeleket, és elé írja, hogy DATA. Ezzel kb. 10 perc után megvoltam. Utána szépen végigmentem a programon és minden sorát beraktam egy DATA sorba. Ez volt még egy pár perc. Utána elkezdtem cizellálni. Első körben a sort kiíró PRINT utasítást kicseréltem egy GO SUB-ra és a PRINT utasítást kitettem egy szubrutinba. Majd lecseréltem egy ciklusra, ami betűnként írja ki a sort (és ha már itt tartunk, a második ciklusmenetben duplázza az idézőjeleket). És egyszercsak eljött az a pillanat, amikor a program már nem fért ki egy képernyőre és az automatikus listázás egy scroll? kérdéssel megakadt (magában a ROM-ban ez úgy van megoldva, hogy az automatikus listázás egy külön üzemmód, amit egy flag bit jelöl egy rendszerváltozóban és olyankor scroll? prompt helyett továbbmegy, és állít azon, hogy honnan kezdje a következő automatikus listázást). Ez tehát azt jelentette, hogy annál a sornál, ahol ez előfordult, az automatikus listázást nem a program elejétől, hanem egy későbbi sortól kell csinálni. Mivel ez csak a második menetben fordult elő, módosult a READ a$ sor READ o,a$: IF n THEN LET p$=p$(o TO )-ra. Most már nagyjából egy órája dolgoztam a programon.
  Itt a munka hatékonysága erősen leesett. A számokat kézzel írtam be, a megfelelő sorok hosszát 5-tel megnövelve, összeadva és hozzáadva egyet (sorszám 4 byte-ja + a sorvégi enter, + 1-től számolunk a stringekben).
  Minden változtatás után újra kellett őket számolni. És nagyon fontos, hogy a program (a DATA sorok nélkül) kiférjen egy képernyőre, különben már mindkét ciklusmenetben szórakozni kéne azzal, hogy nem az elejétől írom ki a programot és ráadásul a két menetben más-más offszeteket kéne használni. Tehát vagy írnom kellett volna egy külön programot az offszetek kiszámolásához, vagy kétszer annyi offszettel kellett volna kézzel bajlódni. Mindkét esetben igen erősen megnövekedett volna az elvégzendő munka, úgyhogy inkább vettem egy nagy levegőt és meghúztam a határt, hogy mi az, ami feltétlenül szükséges a hihetőséghez, és mi az, amit úgysem vesz észre senki. A lényeg, hogy a program egy képernyőre kiférjen, mert ha nem, akkor utána rengeteg meló következik.
  Ezzel ment el a háromórás munkából majdnem kettő. Az eredmény szerintem tök jó lett. Hajnali háromkor befejeztem, beküldtem az eredményt a csoportba és lefeküdtem aludni. Másnap kialvatlanul mentem munkába. :)
  Azt nyilván nem várom tőled, hogy az egész munkafolyamatot megírd, csak azt, hogy a „A világegyetem mint egész önmagánál egyszerűbb modellel nem írható le.” mondat helyett az igazi okot jelöld meg a kompromisszumos pontatlanság okaként: pontosabb programot írni indokolatlanul sokkal több munka lett volna, a programozó legfőbb erénye pedig a lustaság. :)

»»»»»»