Betrakta Python-koden nedan.
s = 's = %r\nprint(s%%s) #Hello'
print(s%s) #HelloDu kan prova köra den härifrån. Vad händer?
Ett program som skriver ut sin egen källkod utan att fuska kallas för en ’quine’. (Som ’fusk’ räknas direkt uppläsning av programfilen och annat liknande.) Exemplet ovan består av tre delar:
- Kod som data. Strängen *’s = %r\nprint(s%%*s) #Hello’ innehåller kopian av programmet i text form.
- Kod som processerar datan. Notera att all processerande kod befinner sig i någon form i den användbara datan.
- Övrig data. Kommentarerna #Hello samt mellanslagen är fullständigt övriga och kan tas bort utan större problem.
Du kanske tänker att quiner är unika för Python-språket, men i själva verket kan man bevisa följande sats:
För alla vettiga programmeringsspråk L existerar det åtminstone ett program P∈ L som skriver ut innehållet av P.
Beviset kan läsas här för dem som är intresserade. I ett nötskal listas alla giltiga program P_(i) upp, vartefter det bevisas att för varje beräkningsbar funktion h kan man hitta en fixpunkt k så att P_(k) och P_(h(k)) är identiska. Genom att välja funktionen h så att P_(h(t)) skriver ut innehållet av P_(t) kan man hitta k så att programmet P_(k) skriver ut innehållet av sig själv.
Utifrån detta presenterar jag Waffes ouroborosprogram teorem (WOooP teoremet):
Givet vettiga programmeringsspråk L₁, L₂, … L_(n) existerar det ett en serie av program P₁∈ L₁, P₂ ∈ L₂, … P_(n)∈ L_(n) där P_(n) skriver ut P₁, och P_(i) skriver ut P_(i+1).
Programmen P₁, P₂, … P_(n) kallas då för ouroborosprogram, namngett efter den mytologiska ormen som äter sin egen svans. Börjandes från P_(i) får man efter minst n körningar tillbaka det ursprungliga programmet P_(i). En quine kan då tänkas vara ett ouroborosprogram på bara ett språk.
För att bevisa WOooP räcker det med att definiera L_(C) som språkens L₁, L₂, … L_(n) sammansättning. Man kan sedan använda första satsen för att bevisa att det måste finnas en quine för L_(C), vilket är ouroborosprogrammet vi söker efter.
Som ett test på mitt teorem skrev jag ett hackigt ouroborosprogram från Python till Clojure till R. Ta gärna och testa för er själva! Koden finns i min git här: code.py.
Alla tre språken har online terminaler, så inget behöver installeras för att testa koden.
P.S. Här är ett lite längre ouroborosprogram på 128 språk.