AUTOREP : Un programme autoréplicateur
Un petit exercice pour vous détendre , si vous aimez la programmation:
Je vous propose d'écrire un programme autoreproducteur :
Un tel programme est un programme source qui, lorsqu'on le compile puis l'exécute, produit sur la sortie standard un texte qui est précisément celui du programme source !
Un tel programme "autorep", si on l'écrit en C par exemple, va utiliser la fonction printf() pour produire ce texte. L'affaire est plus difficile qu'elle en a l'air : par exemple si votre programme commence par :
main() { printf("main() {\nprintf(...
On voit clairement que le serpent se mord la queue et que, avec cette approche, seul un programme infini pourrait se reproduire.
Afin de bien délimiter le champ du problème, j'impose donc les conditions suivantes :
- votre programme devra être fini
- il est interdit dans le corps du programme d'utiliser des fonctions de lecture de fichier (sinon, un programme tel que :
# autorep.c
main () { system("cat autorep.c"); }
serait un programme autoreproducteur ; ce n'est pas ce que je veux ! Il ne faut pas utiliser de fonctions d'entrée de données, et n'utiliser que "print" pour la fonction de sortie.
En C, le problème est donc non-trivial. Mais on pourrait inventer un langage spécialement conçu pour faire des autoreps : par exemple supposons qu'un tel langage dispose de la fonction "rep1()" qui prendrait une chaîne en argument et imprimerait la chaîne, suivie d'un caractère '(', encore une fois la chaïne, mais placée entre guillemets, puis un caractère ')' :
dans ce cas le minuscule programme :
rep1("rep1")
serait un autorep !
On voit dans ce programme que la chaîne "rep1" joue deux
rôles :
c'est le nom d'une fonction, mais c'est aussi l'argument de cette fonction.
C'est cette idée générale qu'il faut suivre pour faire
des autoreps.
Par exemple, voici un autorep écrit dans un langage un peu moins
ad-hoc, semblable à pascal mais disposant d'un certain nombre de
constantes chaînes prédéterminées :
(exemple adapté d'un exemple inventé par Douglas Hofstadter
et cité dans son merveilleux livre "Godel, Escher, Bach, les
brins d'une guirlande éternelle", publié chez interéditions)
Pour info, les américains appellent ces programmes des "Quine".
:
procedure rep2(gabarit)
imprimer gabarit,parenthese-gauche,
guillemet, gabarit, guillemet, parenthese-droite, point.
rep2 ("procedure rep2(gabarit)
imprimer(gabarit,parenthese-gauche,
guillemet, gabarit, guillemet, parenthese-droite, point.
rep2").
Cet autorep utilise la même idee que rep1 : la même chaîne sert à la fois de corps d'une fonction et d'argument de cette fonction. Cette fonction rep2 imprime la chaîne en argument, suivie d'elle même entre guillemets et suivie d'un point.
Par exemple , le programme:
rep2("coup-double").
imrimera : coup-double ("coup-double").
L'astuce est que la chaîne que l'on passe en argument à la fonction
rep2 est précisément le source de la fonction rep2 ! On obtient
donc un autorep.
Cette astuce est précisément celle utilisée par l'ADN en biologie, où le même groupe de trois bases est utilisé à la fois comme constituant physique de la molécule et comme codage pour un acide aminé...
Évidemment le langage utilisé dans le dernier autorep est encore un peu trituré pour les besoins de la cause : outre les constantes prédéterminées parenthese-gauche, parenthese-droite et point, on suppose que l'on termine les définitions de procédures par des points au lieu de les mettre entre crochets, et l'appel d'une fonction se fait simplement par le nom suivi des arguments, sans les parenthéser.
D'où la question : est-il possible de définir un autorep dans un "vrai" langage ? La réponse est oui !
J'en veux pour preuve le magnifique ;-) autorep suivant, écrit en java par moâ-même :
class Autorep {
static String guillemet = "\"";
static String backquote = "\\";
static String nl = "\n";
static String plus = "+";
static String virgule = ",";
static String pvirg = ";";
static String closep = ")";
static String closea = "}";
static String espace = " ";
static String nn = "n";
static String rep(String a, String b, String c, String d, String e, String f, String g, String h, String i, String j, String k, String l, String m, String n, String o) {
return (a+nl+b+guillemet+backquote+guillemet+guillemet+pvirg+nl+c+guillemet+backquote+backquote+guillemet+pvirg+nl+d+guillemet+backquote+nn+guillemet+pvirg+nl+e+guillemet+plus+guillemet+pvirg+nl+f+guillemet+virgule+guillemet+pvirg+nl+g+guillemet+pvirg+guillemet+pvirg+nl+h+guillemet+closep+guillemet+pvirg+nl+i+guillemet+closea+guillemet+pvirg+nl+j+guillemet+espace+guillemet+pvirg+nl+k+guillemet+nn+guillemet+pvirg+nl+l+nl+m+nl+espace+espace+closea+nl+n+nl+o+guillemet+a+guillemet+virgule+nl+guillemet+b+guillemet+virgule+nl+guillemet+c+guillemet+virgule+nl+guillemet+d+guillemet+virgule+nl+guillemet+e+guillemet+virgule+nl+guillemet+f+guillemet+virgule+nl+guillemet+g+guillemet+virgule+nl+guillemet+h+guillemet+virgule+nl+guillemet+i+guillemet+virgule+nl+guillemet+j+guillemet+virgule+nl+guillemet+k+guillemet+virgule+nl+guillemet+l+guillemet+virgule+nl+guillemet+m+guillemet+virgule+nl+guillemet+n+guillemet+virgule+nl+guillemet+o+guillemet+nl+closep+closep+pvirg+nl+closea+nl+closea);
}
public static void main(String argv []) {
System.out.println(rep("class Autorep {",
" static String guillemet = ",
" static String backquote = ",
" static String nl = ",
" static String plus = ",
" static String virgule = ",
" static String pvirg = ",
" static String closep = ",
" static String closea = ",
" static String espace = ",
" static String nn = ",
" static String rep(String a, String b, String c, String d, String e, String f, String g, String h, String i, String j, String k, String l, String m, String n, String o) {",
" return (a+nl+b+guillemet+backquote+guillemet+guillemet+pvirg+nl+c+guillemet+backquote+backquote+guillemet+pvirg+nl+d+guillemet+backquote+nn+guillemet+pvirg+nl+e+guillemet+plus+guillemet+pvirg+nl+f+guillemet+virgule+guillemet+pvirg+nl+g+guillemet+pvirg+guillemet+pvirg+nl+h+guillemet+closep+guillemet+pvirg+nl+i+guillemet+closea+guillemet+pvirg+nl+j+guillemet+espace+guillemet+pvirg+nl+k+guillemet+nn+guillemet+pvirg+nl+l+nl+m+nl+espace+espace+closea+nl+n+nl+o+guillemet+a+guillemet+virgule+nl+guillemet+b+guillemet+virgule+nl+guillemet+c+guillemet+virgule+nl+guillemet+d+guillemet+virgule+nl+guillemet+e+guillemet+virgule+nl+guillemet+f+guillemet+virgule+nl+guillemet+g+guillemet+virgule+nl+guillemet+h+guillemet+virgule+nl+guillemet+i+guillemet+virgule+nl+guillemet+j+guillemet+virgule+nl+guillemet+k+guillemet+virgule+nl+guillemet+l+guillemet+virgule+nl+guillemet+m+guillemet+virgule+nl+guillemet+n+guillemet+virgule+nl+guillemet+o+guillemet+nl+closep+closep+pvirg+nl+closea+nl+closea);",
" public static void main(String argv []) {",
" System.out.println(rep("
));
}
}
Une fois compilé par la commande
java Autorep.java
et exécuté par :
java Autorep
on obtient exactement le programme initial !
joli, non ?
Dans cet autorep bien réel, la fonction "rep" qui possède seize (!) arguments de type chaine, possède la propriété de pouvoir être définie sans utiliser aucun des caractères spéciaux de java, donc on peut mettre sa description dans une chaîne (en fait une liste de seize chaînes) qui précisément seront passées en argument à cette fonction par la méthode main()
C'est plus facile en java qu'en C, parce que java possède un vrai type String: si l'on voulait faire un autorep en C++, cet autorep devrait sans doute incorporer la description de la classe String...
Mais je dois dire que je trouve mon programme peu élégant. Il est surtout très long. Saurez-vous faire plus court en java ? Envoyez-moi vos solutions !ET VOICI MAINTENANT NOTRE JEU-CONCOURS :
Saurez-vous réaliser un autorep dans un autre langage ? (C, C++, ltr2, lisp, Ada, prolog..) ou encore simplifier celui que j'ai créé en java ?
Si oui, écrivez-moi !
Voici trois réponses :
Jean-Luc WIPPLER - Altran Technologie :
Bon, ben voila une version TeX.
\output{}\def\do#1{\catcode`#112}
\def~#1{\def~##1#1{##1#1##1#1\end}\dospecials\obeylines\tt~}~!
\output{}\def\do#1{\catcode`#112}
\def~#1{\def~##1#1{##1#1##1#1\end}\dospecials\obeylines\tt~}~!
Dominique Hollinger, du STNA : :
Voici une solution en CAML, utilisant la technique de ce brave DH (Hofstader, bien sur). En fait, c'est une transcription quasi directe de la fonction "eniuq" qu'il donne page 498 de l'edition VINTAGE.
fichier eniuq.ml
let eniuq temp =
let qm = make_string 1 (char_of_int 34) and
sc = make_string 1 (char_of_int 59) in
print_endline (temp ^ qm ^ temp ^ qm ^ sc ^ sc);
exit 0;;
eniuq"let eniuq temp =
let qm = make_string 1 (char_of_int 34) and
sc = make_string 1 (char_of_int 59) in
print_endline (temp ^ qm ^ temp ^ qm ^ sc ^ sc);
exit 0;;
eniuq";;
Compilation (genere du byte code comme JAVA ou Smalltalk):
camlc -o eniuq eniuq.ml
L'astuce est bien sur dans l'utilisation de la fonction char_of_int pour créer les caractères spéciaux de CAML... joli, non ?
Bernard Fishel propose une réponse en C le 11 janvier 2004 : intéressant, je n'aurais pas cru que c'était possible !
int main(){char*p="int main(){char*p=%c%s%c;printf(p,34,p,34,10); return 0;}%c;";
printf(p,34,p,34,10);return 0;}
Cet exemple est en fait tiré de la doc du compilateur gnu C. Le code
10 est le code de newline, le code 34 est le code de ". C'est fou ce qu'on
peut faire avec des pointeurs ! Je suis très admiratif devant ce petit
programme. Saurez vous faire encore mieux ?Eh bien il semble que Michel Verne ait trouvé, fin 2007, comment faire un autorep directement sous unix, avec le bourne shell (bsh) !
Voici sa solution :
a(){ echo $2 \\$1 $1 $2 $1 ;};a \' ' a(){ echo $2 \\$1 $1 $2 $1 ;};a '
C'est à la fois court et élégant. Bravo ! Qui fera la même chose avec bash ou csh ?
Voici une autre solution en java, par Charles:
public class Quine {
public static void main(String[] args) {
String s = "public class Quine {%3$c%4$cpublic static void main (String[] args) {%3$c%4$c%4$cString s = %2$c%1$s%2$c;%3$c%4$c%4$cSystem.out.printf(s, s, 34, 10, 9);%3$c%4$c}%3$c}";
System.out.printf(s, s, 34, 10, 9);
}
}
/* OUTPUT:
public class Quine {
public static void main (String[] args) {
String s = "public class Quine {%3$c%4$cpublic static void main (String[] args) {%3$c%4$c%4$cString s = %2$c%1$s%2$c;%3$c%4$c%4$cSystem.out.printf(s, s, 34, 10, 9);%3$c%4$c}%3$c}";
System.out.printf(s, s, 34, 10, 9);
}
}
*/
Elle est très courte, mais l'usage des codes ASCII me trouble un peu, ça manque d'élégance.Voici une solution en Perl, due à Gist:
#!/usr/bin/perl
my ($q, $n) = ("'", chr(10));
my $s = '#!/usr/bin/perl%smy ($q, $n) = ("%s", chr(10));%smy $s = %s%s%s;%sprintf $s, $n, $q, $n, $q, $s, $q, $n, $n;%s';
printf $s, $n, $q, $n, $q, $s, $q, $n, $n;
< page précédente : La fonction qui se commente elle même
Jeu de briques
Snake
Pacman
Bubble