Program koji lista samog sebe

[ Nedeljko @ 15.05.2007. 07:57 ] @

Da li ste pokušali da napišete program koji izlistava samog sebe, naravno, bez upotrebe naredbi koje se odnose na datoteke? Ja dajem svoj doprinos na jeziku C++, a voleo bih da vidim što više ideja.

Code:
const char procenat[] = "%", navodnik[] = "\"", obrnuta_kosa_crta[] = "\\";
#include <iostream>
using namespace std;
const char red[][100] = {
"const char procenat[] = %",
"%, navodnik[] = %",
"%%, obrnuta_kosa_crta[] = %",
"%;",
"#include <iostream>",
"using namespace std;",
"const char red[][100] = {",
"%%",
"};",
"void ispisi_red(int red_num, bool kraj_reda = true)",
"{",
"     int i;",
"     for (i=0; red[red_num][i]!=0; i++)",
"         cout << (red[red_num][i]==procenat[0] ? navodnik[0] : red[red_num][i]);",
"     if (kraj_reda)",
"        cout << endl;",
"}",
"int i;",
"int main()",
"{",
"    ispisi_red(0, false);",
"    cout << procenat;",
"    ispisi_red(1, false);",
"    cout << obrnuta_kosa_crta;",
"    ispisi_red(2, false);",
"    cout << obrnuta_kosa_crta << obrnuta_kosa_crta;",
"    for (i=3; i<7; i++)",
"        ispisi_red(i);",
"    for (i=0; red[i][0]!=0; i++)",
"        cout << navodnik << red[i] << navodnik << %,% << endl;",
"    for (i=7; red[i][0]!=0; i++)",
"        ispisi_red(i);",
"}",
""
};
void ispisi_red(int red_num, bool kraj_reda = true)
{
     int i;
     for (i=0; red[red_num][i]!=0; i++)
         cout << (red[red_num][i]==procenat[0] ? navodnik[0] : red[red_num][i]);
     if (kraj_reda)
        cout << endl;
}
int i;
int main()
{
    ispisi_red(0, false);
    cout << procenat;
    ispisi_red(1, false);
    cout << obrnuta_kosa_crta;
    ispisi_red(2, false);
    cout << obrnuta_kosa_crta << obrnuta_kosa_crta;
    for (i=3; i<7; i++)
        ispisi_red(i);
    for (i=0; red[i][0]!=0; i++)
        cout << navodnik << red[i] << navodnik << "," << endl;
    for (i=7; red[i][0]!=0; i++)
        ispisi_red(i);
}

Napominjem da je prazan red na kraju programa bitan da bi izlaz (ako ga preusmerimo u neku datoteku) bio identičan originalnom izvornom kodu.

[ masetrt @ 16.05.2007. 16:37 ] @

Pa za c/c++ to je manje vise jedina fora. Mada koliko se secam nekad davno je u nekom casopisu Dejan Ristanovic postavio isti zadatak samo je trebao da se resi u bejziku. Kolko se secam resenje je bilo nesto mnogo ludo, ali ga ja tada nisam razumeo (imao sam ala 12 godina). Pa ako neko zna to resenje bilo bi lepo da ga postuje. Casopis je mislim bio galaksija ili racunari. Evo ga inace link za resenje tog problema "malo elegantnije" (ali ako nizemo mak na konac):

http://www.iwebthereforeiam.com/programming/selfWrite4.asp

[ Nedeljko @ 16.05.2007. 17:09 ] @

Može i preko C++ programa koji sadrži funklciju za interpretiranje proizvoljnog C++ programa. To je ideja koja se koristi u dokazu opštije teoreme. Videti drugu Klinijevu teoremu rekurzije.

http://en.wikipedia.org/wiki/Kleene's_recursion_theorem

Samolistajući programi su samo poseban slučaj fiksne tačke pri jednoj određenoj totalnoj izračunljivoj funkciji.

[ GxRxN @ 17.05.2007. 00:12 ] @

Ovo je verzija je u javi:

Code:

public class Main{
public static void main(String[] args){
int b[]={112,117,98,108,105,99,32,99,108,97,115,115,32,77,97,105,110,123,10,112,117,98,108,105,99,32,115,116,97,116,105,99,32,118,111,105,100,32,109,97,105,110,40,83,116,114,105,110,103,91,93,32,97,114,103,115,41,123,10,105,110,116,32,98,91,93,61,123,125,59,10,112,40,98,44,48,44,54,55,41,59,10,118,40,98,44,48,44,98,46,108,101,110,103,116,104,45,49,41,59,10,112,40,98,44,54,56,44,98,46,108,101,110,103,116,104,45,49,41,59,10,125,10,10,115,116,97,116,105,99,32,118,111,105,100,32,112,40,105,110,116,91,93,32,110,105,122,44,32,105,110,116,32,115,116,97,114,116,44,32,105,110,116,32,115,116,111,112,41,123,10,102,111,114,32,40,105,110,116,32,105,61,115,116,97,114,116,59,32,105,60,61,115,116,111,112,59,32,105,43,43,41,10,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,40,99,104,97,114,41,110,105,122,91,105,93,41,59,10,125,10,10,115,116,97,116,105,99,32,118,111,105,100,32,118,40,105,110,116,91,93,32,110,105,122,44,32,105,110,116,32,115,116,97,114,116,44,32,105,110,116,32,115,116,111,112,41,123,10,102,111,114,32,40,105,110,116,32,105,61,115,116,97,114,116,59,32,105,60,61,115,116,111,112,59,32,105,43,43,41,123,10,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,110,105,122,91,105,93,41,59,10,105,102,40,105,33,61,115,116,111,112,41,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,40,99,104,97,114,41,52,52,41,59,10,125,10,125,10,10,125};
p(b,0,67);
v(b,0,b.length-1);
p(b,68,b.length-1);
}

static void p(int[] niz, int start, int stop){
for (int i=start; i<=stop; i++)
System.out.print((char)niz[i]);
}

static void v(int[] niz, int start, int stop){
for (int i=start; i<=stop; i++){
System.out.print(niz[i]);
if(i!=stop)System.out.print((char)44);
}
}

}

Sintaksa programa se sastoji iz 3 spojena stringa: A+B+C. String A je text koji predstavlja sintaksu programa do definisanja niza b (zakljucno sa "...b[]={"). String C je text koji predstavlja sintaksu programa nakon definisanja niza b ("};..."). String B predstavlja string A+C u numerickoj varijanti, ukljucujuci i zareze("112,117,98,108,105,..."). Na primer, "ABC" bi postao "65,66,67".

Funkcija p stampa deo niza b u znakovnom obliku, a funkcija v u numerickom, uz odvajanje elemenata zarezom.

Glavni deo:
1) p(b,0,67);//stampanje stringa A u znakovnom obliku
2) v(b,0,b.length-1);//stampanje stringa B u numerickom obliku
3) p(b,68,b.length-1);//stampanje stringa C u znakovnom obliku

Izostavljanjem 2) dela, na izlazu bi se dobio nedefinisan niz b ("...b[]={}..."), dok se njegovim ukljucivanjem dobija funkcionalan program. Da bi se dobio string B, potrebno je napraviti pomocni program, ciji se izlaz zatim hard-koduje (ugradi) u finalnu verziju...

U matematiku se slabo razumem, nadam se da sve ovo ima nekog smisla :) Program sam napisao pre jedno godinu dana, valjda podstaknut nekim clanakom u javasvet-u.

[ uranium @ 17.05.2007. 02:07 ] @

Prvi put sam čuo za taj problem pre nekih 10 godina.
Rešio sam ga u Pascal-u a rešenje mi je otvorilo put da napišem i program koji ispisuje samog sebe unazad.

Evo da napišem svoje rešenje u C-u i Perl-u:

Code:

main(){char*x="main(){char*x=%c%s%c;printf(x,34,x,34);}";printf(x,34,x,34);}

Code:

$x = '$x = %c%s%c; printf ($x, 39, $x, 39);'; printf ($x, 39, $x, 39);

Kasnije sam saznao da sam sve vreme izmišljao toplu vodu

http://www.nyx.net/~gthompso/quine.htm

[ Nedeljko @ 17.05.2007. 09:25 ] @

Poštovani Uraniume,

Tvoje rešenje, mada radi na većini C prevodilaca, ipak nije ispravno po C standardima. Standardi yahtevaju da uključiš zaglavle stdio.h ako koristiš funkciju printf().

[ uranium @ 17.05.2007. 10:44 ] @

Ha, ha, ha

Očekivao sam sličan komentar

Code:

#include <stdio.h>
int main(){char*x="#include <stdio.h>%cint main(){char*x=%c%s%c;printf(x,13,34,x,34);return 0;}";printf(x,13,34,x,34);return 0;}

Može li tako?

[ Nedeljko @ 17.05.2007. 12:27 ] @

Pa, sad, na nekim sistemima može. Ali, nije na svim sistemima 13=='\n'. Znači, opet nije po standardima.

[ uranium @ 18.05.2007. 08:10 ] @

Opet si potpuno u pravu (nažalost

)

Nadam se da neće biti zamerki na sledeći kod:

Code:

#define nl '??/n'
#include <stdio.h>
int main(){char *x="#define nl '??%c%c'%c#include <stdio.h>%cint main(){char *x=%c%s%c;printf(x,47,110,nl,nl,34,x,34,92,'%cn');return 0;}%c";printf(x,47,110,nl,nl,34,x,34,92,'\n');return 0;}

Naravno, da bi koristio trigraph-e moraš da kompajliraš sa tom opcijom (npr. nešto kao -trigraphs).
Ukoliko bude potrebe za objašnjenjem koda - tu sam

_{Edit: dodat newline karakter na kraju source fajla...}

_{[Ovu poruku je menjao uranium dana 18.05.2007. u 10:45 GMT+1]}

[ uranium @ 18.05.2007. 08:26 ] @

Evo sad videh da može i bez trigraph-a.

Code:

#include <stdio.h>
int main(){char *x="#include <stdio.h>%cint main(){char *x=%c%s%c;printf(x,'%cn',34,x,34,92,92,'%cn');return 0;}%c";printf(x,'\n',34,x,34,92,92,'\n');return 0;}

_{Edit: dodat newline karakter na kraju source fajla...}

_{[Ovu poruku je menjao uranium dana 18.05.2007. u 10:46 GMT+1]}

[ cynique @ 19.05.2007. 12:15 ] @

Citat:

Nedeljko: Može i preko C++ programa koji sadrži funklciju za interpretiranje proizvoljnog C++ programa.

Nešto tipa eval? ;) Nema toga za C++...

Citat:

To je ideja koja se koristi u dokazu opštije teoreme. Videti drugu Klinijevu teoremu rekurzije.

http://en.wikipedia.org/wiki/Kleene's_recursion_theorem

Samolistajući programi su samo poseban slučaj fiksne tačke pri jednoj određenoj totalnoj izračunljivoj funkciji.

U biti se argument postojanja pozivanjem na Kleenejev teorem svodi na to da za svaki (izračunljiv) program (tj. funkciju) p koji ispisuje sadržaj nekog drugog (proizvoljnog) programa postoji program k takav da k i p(k) rade istu stvar - ispisuju kod od k. I eto quinea k.

U nekim, tzv. homoikoničkim jezicima je pisanje quineova mnooogo lakše od algoloidnih izbljuvaka, jer ne postoji semantička disonanca između reprezentacije koda i podataka. Npr. u Schemeu (a i za ostale Lisp dijalekte):

Code:

((lambda (x)
        (list x (list (quote quote) x)))
    (quote
        (lambda (x)
            (list x (list (quote quote) x)))))

U nekim je drugim još i kraće!

[ formeye @ 19.05.2007. 16:51 ] @

Najkraci je u perlu:

self.pl

Code:

LOL (replikuje u potpunosti sam sebe - ne ispisuje nista jer je i program prazan)

P.S. Nemojte da me shvatate ozbiljno... nesto sam veseo trenutno :)

[ dusans @ 20.05.2007. 12:39 ] @

Evo jednog za C64 Basic (a da nije prazan :))) ):

Code:

10 LIST

Pozdrav!

[ Nedeljko @ 21.05.2007. 18:37 ] @

Citat:

cynique: U biti se argument postojanja pozivanjem na Kleenejev teorem svodi na to da za svaki (izračunljiv) program (tj. funkciju) p koji ispisuje sadržaj nekog drugog (proizvoljnog) programa postoji program k takav da k i p(k) rade istu stvar - ispisuju kod od k. I eto quinea k.

Tačno. Međutim, to je samo dokaz postojanja takvog programa pozivanjem na drugu Klinijevu teoremu rekurzije koja garantuje postojanje "fiksne tačke". Međutim, time "fiksna tačka" nije konstruisana. Konstrukcija je data u dokazu Klinijeve teoreme. Dokaz se oslanja na s-m-n teoremu i na teoremu o postojanju univerzalne funkcije.

Ti nemaš funkciju nalik na eval u C++ jeziku kao standardnu bibliotečku funkciju, ali se ona može isporogramirati. Kako li bi se inače pravili interpreteri i kompajleri za programske jezike.

[ cynique @ 21.05.2007. 20:32 ] @

Pa da, zato sam i napisao postojanja.

Interpreteri/kompilatori su zasebni izvršni programi, ne implicitni konstrukti samog jezika/standardnih biblioteka koji se mogu po potrebi invocirati. Evaluator npr. (S/M)-izraza valja razlikovati od translatora (jezičnog procesora) koji jedan jezik prevodi u drugi, dok ta razlika iščezava u jeziku u kojem je sve izraz (sem nekolicine "specijalnih formi" za posebnom redukcijskom strategijom), i tad se evaluator može poistovjetiti sa prevoditeljem ukoliko je dostupan za compile-time. Tako se evaluator za takav jezik da ostvariti i u jeziku koji se evaluira (homoikoničnost je dakako zahtjev i ovdje), pa dobiješ metacirkularni evaluator.

Pod .NET-om se npr. može in-memory napisati C# program kao string i iz njega izgenerirati izvodivi strojni kod, no svejedno takvo nešto nije ugrađeno u sam jezik kao first-class konstrukt i više spada u dirty hacks domenu nego u nešto uobičajeni uzorak korištenja jezika. Eval teško da uopće ima smisla za statički tipizirane jezike, a kamoli za one koje su usto i nakaradne budževine poput C++a.

[ Nedeljko @ 22.05.2007. 22:16 ] @

U svakom programskom jeziku možeš napisati funkciju koja prohvata program na tom jeziku kao string i interpretira ga. To i jeste poenta teoreme o postojanju univerzalne funkcije. s-m-n funkcija u nekom smislu postiže suprotan efekat: Za dati program sa m>=n ulaza i n ulaza izračunava program sa m-n ulaza koji postiže isti efekat, pri čemu je onih n ulaza u s-m-n funkciju fiksirano za rezultujući program.

[ cynique @ 23.05.2007. 09:54 ] @

http://en.wikipedia.org/wiki/Constructive_proof

[ Nedeljko @ 25.05.2007. 19:39 ] @

Pa, Klinijev dokaz i jeste kontruktivan, do na konstruktivnost univerzalne funkcije i s-m-n funkcije, čija se egzistencija i inače uobičajeno dokazuje konstruktivno. Dakle, te dve funkcije se koriste u konstrukciji, pa tvoja primedba

Citat:

cynique: Nešto tipa eval? ;) Nema toga za C++...

nije na mestu.

[ cynique @ 25.05.2007. 22:55 ] @

No, hoćeš li konstruirati eval za C++? Poželjno neku prenosivu verziju koja ne radi ispod haube sa internalijama kompilatora :)

[ Nedeljko @ 26.05.2007. 10:07 ] @

Naravno da je to veliki posao i da nemam vremena time da se bakćem da bih nekome nešto dokazao. No, ako se prihvati da je ANSI/ISO C++ Tjuring potpun, onda se na njemu može napisati prevodilac sa ANSI/ISO C++ jezika na bajt kod za neku zamišljenu mašinu, kao i emulator za tu mašinu (interpreter bajt koda). Ne misliš valjda ozviljno da je to neostvarivo? Do sada si pokazivao odlično teorijsko znanje. Nemoj da me razočaravaš.

[ cynique @ 27.05.2007. 15:33 ] @

U teoriji je moguće, ali u praksi bi to bilo jako teško, i neuporabljivo u praktičnim programima. Sad sam pogledao .NET System.CodeDom.Compiler implementacije - postoje sučelja za VB.NET (VBCodeProvider), C# (CSharpCodeProvider) i JScript (JScriptCodeProvider). Microsoft.VisualC assembly, s druge strane, ne sadrži nešto tipa VisualCCodeProvider, pitam se zašto ;)

[ Nedeljko @ 28.05.2007. 10:53 ] @

Ja lično mislim da Majkrosoft namerno gura C++ u provaliju, ne bi li ga u potpunosti zamenio novijim i boljim jezicima. Naravno, C++ je još uvek nezamenljiv u nekim oblastima, pa ga Majkrosoft postepeno potiskuje smanjivanjem broja tih oblasti putem poboljšavanja drugih rešenja. Ni J# Majkrosoft nešto ne favorizuje. U knjizi "Mastering Java 2 J2SE 1.4" autor Džon Zukovski (John Zukowski) tvrdi da se Java ne uklapa u Majkrosoftovo gledište, tako da čak i čitaocima kojima se svideo Visual J++ i žele tesnu saradnju sa Windowsom preporučuje prelazak na C#.

Štaviše, u Visual C++ 6 klasa CLabel nije imala metode SetTextColor i SetBkColor, koje u Visual Basic-u 6 postoje, pa autor knjige Visual C++ 6 Biblija kao rešenje navodi pravljenje izvedene klasu iz klase CLabel koja je te stvari omogućavala koristeći neke fore sa refleksijom događaja.

Citat:

cynique: U teoriji je moguće, ali u praksi bi to bilo jako teško, i neuporabljivo u praktičnim programima.

Bilo bi približno onoliko teško koliko i napraviti C++ prevodilac, a u ovoj temi o praktičnim programima ne govorimo. Ja sam rekao da opšti Klinijev dokaz postojanja takvog programa pretpostavlja postojanje univerzalne funkcije i s-m-n funkcije. Ako se govori o rešenju na određenom programskom jeziku, onda se mogu naći prečice. No, C++ rešenje bazirano na Klinijevom dokazu bi bilo jako dugo i nezgrapno, ali bi bilo ostvarivo.

[ ristanovic @ 02.06.2007. 01:48 ] @

>> Mada koliko se secam nekad davno je u nekom casopisu Dejan Ristanovic
>> postavio isti zadatak samo je trebao da se resi u bejziku. Kolko se secam
>> resenje je bilo nesto mnogo ludo

Ludo... kako se uzme. Dakle:

Varijanta 1:

1 A$="1 A$=:PRINT LEFT$(A$,5)+CHR$(34)+A$+CHR$(34)+MID$(A$,6)":PRINT LEFT$(A$,5)+CHR$(34)+A$+CHR$(34)+MID$(A$,6)

Varijanta 2:

1 READ A$:PRINT A$CHR$(34)A$:DATA"1 READ A$:PRINT A$CHR$(34)A$:DATA

Varijanta 1 se meni lično više sviđa, mada je varijanta 2 nešto kraća.

Dejan

[ masetrt @ 04.06.2007. 14:27 ] @

Hvala Dejanu na odgovoru. Ovaj kod mi je nekada mnogo ludje i misticnije izgledao :D