Les quines : des programmes informatiques auto-réplicateurs

Les cellules de notre organisme sont capables de se répliquer à l’identique, et ça nous parait bien naturel. Et pourtant, la question de l’auto-réplication est loin d’être évidente.

Pour s’en rendre compte, essayez-vous au petit défi suivant : écrire un programme informatique qui produise en sortie son propre code source. Ça paraît simple, non ?

Vous allez voir que ça n’est pas le cas, et que l’écriture d’un tel programme nécessite de se creuser un peu les méninges.

Un essai naïf

A première vue, le défi parait facile. Il suffit d’utiliser la fonction print, ou son équivalent dans le langage de programmation considéré. Alors allons-y, on commence à écrire son programme par une ligne d’introduction du genre

begin mon_programme

Puis on poursuit par une ligne de code qui permet d’imprimer la ligne précédente

print("begin mon_programme")

Ensuite il nous faut une ligne qui imprime celle qu’on vient d’écrire

print("print("begin mon_programme")")

et la suite

print("print("print("begin mon_programme")")")

Bon, pas besoin de continuer plus loin : vous voyez que ça ne marche pas ! Bien sûr, il existe une solution qui est d’ouvrir le propre fichier source du programme, de le lire et de l’imprimer. Mais cette solution est considérée comme de la triche : le défi suppose qu’on ne fournisse aucune donnée d’entrée à notre programme.

Après un peu de réflexion et quelques essais infructueux, j’ai pensé que le défi était impossible. Mais rassurez-vous, c’est possible ! Dans son livre Gödel, Escher et Bach, Douglas Hofstadter a baptisé ce genre de programmes un quine, en référence au logicien Willard van Orman Quine, qui a beaucoup étudié les paradoxes de ce genre. Alors comment écrire un quine ?

Un quine en français

Pour comprendre le principe générique de l’écriture d’un quine dans un langage de programmation, on peut commencer par en trouver un en français. Voici une solution possible:

Ecrivez, puis écrivez entre guillemets « Ecrivez, puis écrivez entre guillemets »

Si vous appliquez à la lettre cette instruction en français, vous allez la reproduire ! Si un quine est possible en français, il doit être possible dans un langage de programmation.

Si on décortique un peu ce quine en français, on peut voir qu’il est composé de deux parties : la première partie est la partie active, il s’agit de l’instruction proprement dite. La seconde partie, celle qui est entre guillemets, peut être appelée les données. Il s’agit d’une chaîne de texte, mais dont la signification est de permettre de construire la partie active. On peut examiner l’analogie biologique de cette construction.

Je vous ai dit que les cellules de notre organisme sont un bon système auto-réplicateur. Il se trouve que nos cellules fonctionnent un peu comme notre quine en français. La cellule elle-même peut être vue comme la partie active, car c’est elle la machine qui va effectuer des opérations. L’ADN lui est vu comme les données, c’est de l’information, et cette information contient le plan de montage de la partie active.

La beauté de l’histoire, c’est que quand la cellule se divise, elle réplique à la fois sa partie active et son plan de montage. L’instruction Ecrivez, puis écrivez entre guillemets « Ecrivez, puis écrivez entre guillemets » est finalement très analogue à ce que fait la cellule qui applique une instruction du genre « Duplique-toi et duplique aussi ton ADN ».

Un vrai quine informatique

Écrire un quine dans un langage de programmation, c’est donc possible, mais ça n’est pas non plus super trivial. La page wikipedia référence des quines écrits dans différents langages. Pour vous donner une idée, en voici un en C

#include<stdio.h>
char*i="\\#include<stdio.h>",n='\n',q='"',*p=
"%s%cchar*i=%c%c%s%c,n='%cn',q='%c',*p=%c%c%s%c,*m=%c%c%s%c%c;%s%c",*m=
"int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}"
;int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}

Pas très lisible, hein ? La bonne nouvelle, c’est qu’on peut démontrer que tout langage de programmation possède un quine, et même une infinité (PS pour les matheux : c’est une conséquence d’un théorème de type « point fixe ».)

Souvent dans un quine, il est possible d’insérer des morceaux qui ne changent en rien l’exécution du programme, tout en conservant sa propriété de quine. Un peu comme si on insérait des commentaires, par exemple

[Ceci est un commentaire] Ecrivez, puis écrivez entre guillemets « [Ceci est un commentaire] Ecrivez, puis écrivez entre guillemets »

Ces morceaux de code qui ne modifient pas la propriété d’autoréplication, et qui semblent ne servir à rien, sont appelés des introns. Là aussi c’est une analogie biologique, car le terme d’intron désigne normalement le nom de ces morceaux d’ADN qui font partie de notre code génétique mais qui ne sont pas interprétés.

Dans les quines, les introns permettent de faire des choses très bizarres : des multiquines. Par exemple un multiquine C-Java, c’est un code C qui une fois exécuté fournit en sortie un code Java, qui lui même exécuté fournit le code C d’origine. Tordu, hein ? Et pas facile à écrire, et encore moins à lire ! Et on est pas obligés de se limiter à 2 langages. On peut le faire avec 3, 4, 5…il y a même un grand malade qui a fait un multiquine pour 11 langages de programmation consécutifs (je ne connais même pas de nom la moitié de ces langages).

Vers des machines auto-réplicatrices

Au delà de ces performances qui peuvent vous laisser indifférents, les quines permettent de se poser des tas de questions sur l’auto-réplication. Et l’auto-réplication « physique » est loin d’être un problème simple. De nombreux chercheurs essayent de mettre au point une machine auto-réplicatrice, c’est-à-dire qui puisse construire une copie d’elle-même à partir des ressources disponibles dans son environnement. Eh bien ça n’est pas facile !

Il existe à ce jour quelques tentatives intéressantes, mais semble-t-il aucune qui soit totalement convaincante. Par exemple celle-ci, fruit de travaux menés à l’Université de Cornell

[youtube=http://www.youtube.com/watch?v=K_EWzxRn8Xo]

Cette vidéo est assez bluffante, mais on est pas dans l’autoréplication pure, puisque le robot n’utilise pas vraiment son environnement brut, mais exploite des cubes qui lui sont fournis. Ca n’est donc pas encore considéré comme une preuve pure qu’une machine auto-réplicatrice soit possible. D’un autre côté c’est rassurant, ça nous met pour l’instant à l’abri d’une invasion de la Terre par des robots auto-réplicateurs !

Une très bonne source sur les quines, sur le site de David Madore

Le même furieux qui a fait le multiquine à 11 langage a récemment posté une vidéo d’un quine avec microcontrolleur Arduino et des LEDs !