Qualche giorno fa mi e’ stato proposto un interessante problema, che ho trovato molto divertente risolverlo. Si tratta di un classico rompicapo informatico a cui però non avevo mai pensato seriamente. Il problema e’ il seguente: scrivere un programma (con un qualunque linguaggio ad alto livello) che una volta compilato ed eseguito crei come output un file contenente il codice sorgente. Ovviamente l’applicazione non può leggere il file sorgente, altrimenti ne farebbe una copia ed il gioco sarebbe già finito. L’eseguibile non può essere manipolato, altrimenti si potrebbe aggiungere in coda all’eseguibile il sorgenti del programma. Se invece si pensa di aggiungere il sorgente alle risorse dell’eseguibile, allora il programma dovrà creare non solo il sorgente dell’applicazione, ma anche il sorgente dato in input al compilatore di risorse: per farla breve, niente trucchetti strani, ma soltanto un vero algoritmo che rigeneri se stesso.
Ci sono due tipi di difficoltà nel risolvere questo tipo di problema. La prima e’ di carattere logico e ben si comprende con un semplice esempio scritto in un metalinguaggio; un codice autogenerante deve sicuramente contenere un istruzione di stampa:
stampa(…)
Questa istruzione stampa in un file quello che c’e’ tra parentesi. Ora cominciamo a costruire un codice autogenerante:
stampa()
Questo non e’ ancora un codice autogenerante perché il suo output e’ nullo: bisogna che il comando stampa() contenga tra le parentesi il nostro sorgente:
stampa(stampa())
Ma apportando questa modifica il sorgente e’ variato, quindi dobbiamo mettere di nuovo tra parentesi il nuovo codice modificato:
stampa(stampa(stampa()))
Si capisce ben presto che questo tipo di soluzione porta ad una successione non finita di modifiche che mai ci porta ala soluzione del problema.
Il secondo tipo di problema e’ relativo al tipo di linguaggio utilizzato e nasce a causa delle regole sintattiche del linguaggio. Ad esempio Se in C vogliamo stampare una stringa, ci sono dei problemi quando la stringa contiene il carattere delle virgolette o del %.
Pensateci un po’ su e poi confrontate le vostre idee con la mia soluzione1.
Se questo genere di rompicapo vi appassiona particolarmente, consiglio una visitina al sito http://www.ioccc.org; qui vengono organizzate gare in cui vince il codice C più oscuro ed astruso!
1
1) Il codice e’ scritto in C, vista la diffusione ormai universale di questo linguaggio;
2) Il sorgente contiene righe di codice lunghe circa 200 caratteri perche’ in un codice autogenerante anche la presenza di un carrige return puo’ cambiare la struttura del codice. Per questioni tipografiche e’ impossibile stampare su un’unica rica queste lunghe linee, per cui verranno interrotte mesiante il segno
Ad esempio: la riga
int main(void){FILE *fp;fp=fopen("s.txt");fclose(fp);}
puo’ essere spezzata come
int main(void){FILE *fp;
fp=fopen("s.txt");fclose(fp);}
ma nel file sorgente DEVE essere scritta tutta su un’unica linea.
Ed ora la prima soluzione!
#include
char b[]={"int main(){FILE*f;int i;f=fopen(~s.txt~,~w~);
fprintf(f,~#include
for(i=0;b[i];i++)if(b[i]==126)b[i]=34;fprintf(f,~%c};%c~,34,10);
fprintf(f,~%s~,b);fclose(f);}"};
int main(){FILE*f;int i;f=fopen("s.txt","w");
fprintf(f,"#include
for(i=0;b[i];i++)if(b[i]==126)b[i]=34;
fprintf(f,"%c};%c",34,10);fprintf(f,"%s",b);fclose(f);}
Infine un breve commento. Non potendo scrivere direttamente tra virgolette il sorgente completo (per i problemi di ricorsione precedentemente illustrati), l’idea e’ quella di avere il codice sorgente in una stringa e di stamparlo nell output due volte, una per ricreare l’inizializzazione della stringa ed una per scrivere il codice vero e proprio.
Il maggiore inconveniente tecnico, nasce nella rappresentazione in C delle virgolette in una stringa. Per questo motivo, nell’inizializzazione della stringa le virgolette sono rappresentate dal carattere ~ il quale viene poi sostituito dal codice col carattere delle virgolette.
Ho presentato la mia soluzione ad un amico, Claudio Silenzi, il quale ha fatto un po’ di ordine nei sorgenti e mi ha restituito una soluzione piu’ pulita e semplice della mia. La logica e’ la stessa, ma ha tolto ridondanze e brutture presenti nel mio codice.
Ecco quindi la sua proposta:
#include
char b[]={"int main(){FILE*f;int i;f=fopen(~s.txt~,~w~);
fprintf(f,~#include
%c~,10,34,b,34,10);for(i=0;b[i];i++)if(b[i]==126)b[i]=34;
fprintf(f,~%s~,b);fclose(f);}"};
int main(){FILE*f;int i;f=fopen("s.txt","w");
fprintf(f,"#include
10,34,b,34,10);for(i=0;b[i];i++)if(b[i]==126)b[i]=34;
fprintf(f,"%s",b);fclose(f);}
