Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Program koji lista samog sebe

[es] :: Art of Programming :: Program koji lista samog sebe

Strane: 1 2

[ Pregleda: 7023 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Program koji lista samog sebe15.05.2007. u 07:57 - pre 205 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
195.252.119.*

Sajt: www.vast.com


+2 Profil

icon Re: Program koji lista samog sebe16.05.2007. u 16:37 - pre 205 meseci
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
His majesty Grand Duke of Shumadija and Western Pomoravlje
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Program koji lista samog sebe16.05.2007. u 17:09 - pre 205 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

GxRxN

Član broj: 118184
Poruke: 25
*.eunet.yu.



Profil

icon Re: Program koji lista samog sebe17.05.2007. u 00:12 - pre 205 meseci
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.
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: Program koji lista samog sebe17.05.2007. u 02:07 - pre 205 meseci
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
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Program koji lista samog sebe17.05.2007. u 09:25 - pre 205 meseci
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().
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: Program koji lista samog sebe17.05.2007. u 10:44 - pre 205 meseci
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?
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Program koji lista samog sebe17.05.2007. u 12:27 - pre 205 meseci
Pa, sad, na nekim sistemima može. Ali, nije na svim sistemima 13=='\n'. Znači, opet nije po standardima.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: Program koji lista samog sebe18.05.2007. u 08:10 - pre 205 meseci
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]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: Program koji lista samog sebe18.05.2007. u 08:26 - pre 205 meseci
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]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
Prikačeni fajlovi
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
*.cmu.carnet.hr.

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: Program koji lista samog sebe19.05.2007. u 12:15 - pre 205 meseci
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!
 
Odgovor na temu

formeye
Ivan Čukić
KDE developer, Free Software Network
Serbia
BGD

Član broj: 5188
Poruke: 388
*.dynamic.sbb.co.yu.

Sajt: ivan.fomentgroup.org


Profil

icon Re: Program koji lista samog sebe19.05.2007. u 16:51 - pre 205 meseci
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 :)
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
 
Odgovor na temu

dusans
Stojanov Dušan
Pančevo

Član broj: 9551
Poruke: 1343
195.252.78.*



+311 Profil

icon Re: Program koji lista samog sebe20.05.2007. u 12:39 - pre 205 meseci
Evo jednog za C64 Basic (a da nije prazan :))) ):

Code:

10 LIST


Pozdrav!
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Program koji lista samog sebe21.05.2007. u 18:37 - pre 205 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
193.198.17.*

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: Program koji lista samog sebe21.05.2007. u 20:32 - pre 205 meseci
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.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Program koji lista samog sebe22.05.2007. u 22:16 - pre 205 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
*.cc.fer.hr.

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: Program koji lista samog sebe23.05.2007. u 09:54 - pre 205 meseci
http://en.wikipedia.org/wiki/Constructive_proof
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
77.46.236.*



+2789 Profil

icon Re: Program koji lista samog sebe25.05.2007. u 19:39 - pre 205 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
*.cmu.carnet.hr.

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: Program koji lista samog sebe25.05.2007. u 22:55 - pre 205 meseci
No, hoćeš li konstruirati eval za C++? Poželjno neku prenosivu verziju koja ne radi ispod haube sa internalijama kompilatora :)
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Program koji lista samog sebe26.05.2007. u 10:07 - pre 205 meseci
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š.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Art of Programming :: Program koji lista samog sebe

Strane: 1 2

[ Pregleda: 7023 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.