:: Home » Numeri » #56 » COMPUTER » Codice autogenerante
1999
25
Set

Codice autogenerante

media 5 dopo 1 voti
Commenti () - Page hits: 6250
Codice autogenerante

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!


Thomas Serafini

1
Prima della soluzione alcune note:
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%cchar b[]={%c~,10,34);fprintf(f,~%s~,b); \
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%cchar b[]={%c",10,34);fprintf(f,"%s",b); \
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%cchar b[]={%c%s%c}; \
%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%cchar b[]={%c%s%c};%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);}

 
:: Vota
Vota questo articolo: 1 - 2 - 3 - 4 - 5 (1 = scarso - 5 = ottimo)
 
:: Thomas Serafini

Thomas Serafini, nato il 12/3/1977, è iscritto all'ultimo anno della facoltà di Matematica a Modena. Lavora come sviluppatore software ed è un musicista dilettante. Su KULT Underground si occupa della parte musicale e cura articoli divulgativi a carattere matematico/scientifico.


MAIL: thomas@kultunderground.it
 
:: Automatic tags
 
:: Articoli recenti
 
KULT Virtual Press e KULT Underground sono iniziative amatoriali no-profit - per gli e-book e per gli articoli fare riferimento alla sezione Copyright
Webmaster: Marco Giorgini - e-mail: marco @ kultunderground.org - Per segnalazioni o commenti inviare una e-mail a: info @ kultunderground.org
Questo sito è ospitato su server ONE.COM

pagina generata in 165 millisecondi