Program koji lista samog sebe

Program koji lista samog sebe 15.05.2007. u 08:57 · pre 237 meseci #1

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 16.05.2007. u 17:37 · pre 237 meseci #2

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

Potpis

His majesty Grand Duke of Shumadija and Western Pomoravlje

Re: Program koji lista samog sebe 16.05.2007. u 18:09 · pre 237 meseci #3

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 17.05.2007. u 01:12 · pre 237 meseci #4

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.

Re: Program koji lista samog sebe 17.05.2007. u 03:07 · pre 237 meseci #5

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

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

1

Re: Program koji lista samog sebe 17.05.2007. u 10:25 · pre 237 meseci #6

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().

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 17.05.2007. u 11:44 · pre 237 meseci #7

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?

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Program koji lista samog sebe 17.05.2007. u 13:27 · pre 237 meseci #8

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

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 18.05.2007. u 09:10 · pre 237 meseci #9

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...}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Program koji lista samog sebe 18.05.2007. u 09:26 · pre 237 meseci #10

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...}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

quines.zip0.43k

Re: Program koji lista samog sebe 19.05.2007. u 13:15 · pre 236 meseci #11

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!

Potpis

Put the funk in funktion.

Re: Program koji lista samog sebe 19.05.2007. u 17:51 · pre 236 meseci #12

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 :)

Potpis

While you were hanging yourself on someone else's words
Dying to believe in what you heard
I was staring straight into the shining sun

Re: Program koji lista samog sebe 20.05.2007. u 13:39 · pre 236 meseci #13

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

Code:

10 LIST

Pozdrav!

Re: Program koji lista samog sebe 21.05.2007. u 19:37 · pre 236 meseci #14

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 21.05.2007. u 21:32 · pre 236 meseci #15

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.

Potpis

Put the funk in funktion.

Re: Program koji lista samog sebe 22.05.2007. u 23:16 · pre 236 meseci #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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 23.05.2007. u 10:54 · pre 236 meseci #17

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

Potpis

Put the funk in funktion.

Re: Program koji lista samog sebe 25.05.2007. u 20:39 · pre 236 meseci #18

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.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Program koji lista samog sebe 25.05.2007. u 23:55 · pre 236 meseci #19

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

Potpis

Put the funk in funktion.

Re: Program koji lista samog sebe 26.05.2007. u 11:07 · pre 236 meseci #20

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š.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Forum kao aplikacija na telefonu

Srodne teme