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

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 !

5 réflexions sur “Les quines : des programmes informatiques auto-réplicateurs

  1. Ben ça c’est drôle, parce que j’ai fait mon dernier td de calculabilité sur ce sujet. On peut d’ailleurs faire mieux qu’un quine, on peut faire un point fixe. C’est à dire un programme qui calcule automatiquement le point fixe d’un autre. Si par exemple je lui donne alors un programme qui à partir de son entrée donne le programme qui affiche cette entrée, alors par le point fixe, j’obtiens automatiquement un quine.

    En OCaml, ça fait 15 lignes de code, mais bien sur, j’appelle le compilateur. Pour avoir un point fixe indépendant, il faut y intégrer tout un compilateur, c’est plus compliqué.

    Dommage que les étudiants aient trouvé ça trop dur, mais une fois le point fixe fait, on peut faire des choses amusantes, en particulier un programme qui calcule le md5 de son source et l’affiche (sans relire son fichier source bien sur). On peut donc techniquement faire des programmes qui vérifient s’ils ont été patchés (‘cracké’ ?)…

  2. ton lien « Une très bonne source sur les quines, sur le site de David Madore » est foireux (quand tu oublies le http://, WordPress génère un lien à partir de la page courante…) le bon est donc http://www.madore.org/~david/computers/quine.html

    J’étais très content de voir que Python, mon langage préféré, permet d’écrire une des plus courtes quines de la page wikipedia. A part HQ9+, il n’y a que Ruby qui fait mieux, et comme je ne comprenais pas le programme j’ai cherché et documenté son fonctionnement ici : http://fr.wikipedia.org/wiki/Quine_(informatique)#Ruby

    J’ai un peu ramé pour pour comprendre ton exemple en français, qui me parait plus compliqué que dans n’importe quel langage de programmation ;-). En fait je ne comprenais pas le sens du premier « Ecrivez », je ne voyais pas la distinction avec une simple autoréférence comme « écrivez la présente phrase ».

    Puis j’ai trouvé sur la page wikipédia une version de la quine en français qui me semble plus explicite http://fr.wikipedia.org/wiki/Quine_(informatique)#Fran.C3.A7ais:

    Recopier puis recopier entre guillemets la phrase « Recopier puis recopier entre guillemets la phrase »

    Pour accentuer la distinction avec une simple autoréférence en ajoutant un peu plus de traitement, je propose:

    Recopier à l’envers, puis recopier entre guillemets les lettres «serttel sel stemelliug ertne reipocer siup ,srevne’l à reipoceR»

    • Merci pour la correction du lien, c’est modifié !

      Je t’avoue que quand j’ai commencé à écrire ce billet, je suis aller taper « quine » dans le moteur de recherche de drgoulu.com, je me disais que tu avais forcément déjà publié un(e?) quine en python 🙂

  3. Pour qu’un robot s’auto-réplique, il faudrait qu’il crée de la matière première à partir de rien, donc ça paraît un peu compromis.

    Concernant la programmation, je me suis souvent demandé si les vers fonctionnaient sur ce principe. Mais j’imagine que le concept est apparu surtout pour la question d’une vie artificielle capable d’évoluer et de se reproduire, non ?

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s