Un programme qui s'écrit lui-même : les quines

Un quine est un programme dont la sortie à l'exécution est, caractère pour caractère, son propre code source. La contrainte qui rend l'exercice intéressant : interdiction de lire son propre fichier. Un programme qui ferait cat de lui-même ne prouve rien. Interdiction, aussi, de prendre la moindre entrée. Le programme doit donc contenir sa propre description et savoir la réimprimer.

C'est un classique de l'informatique théorique — on y croise le théorème de récursion de Kleene — mais c'est surtout la graine d'une idée beaucoup plus concrète : un code qui sait se reproduire. Le projet Dr Quine de Sigabort42 déroule cette idée en trois marches, de la curiosité pure au programme qui se recompile et se relance lui-même. Cet article les parcourt.

La solution triviale, et pourquoi elle est bannie

Dans la plupart des langages, un fichier source vide produit une sortie vide. La sortie est donc identique à la source : techniquement, c'est un quine. C'est aussi une pirouette qui n'apprend rien, et elle est écartée d'office. Tout l'exercice consiste à écrire un quine non trivial, qui produit réellement quelque chose.

Le cœur du problème : un texte qui se décrit lui-même

Si tu essaies naïvement, tu tombes vite sur un serpent qui se mord la queue :

Pour afficher le programme, il faut afficher la chaîne…
…mais la chaîne doit contenir l'instruction qui l'affiche…
…qui contient la chaîne… qui contient l'instruction…

La sortie est de contempler le code sous deux angles à la fois : une partie données (une chaîne de caractères) et une partie code (les instructions). L'astuce du quine, c'est d'écrire une chaîne qui contient tout le programme sauf elle-même, puis de l'imprimer deux fois : une fois comme du code, une fois comme de la donnée entre guillemets.

Voici un quine C minimal, pour isoler le mécanisme :

char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);}

• s contient le texte du programme, avec un trou : %s à l'endroit où s devrait se citer lui-même.
• printf(s, 34, s, 34) imprime s… en réinjectant s dans le %s, encadré de deux guillemets (le caractère 34 en ASCII, ").

Le %c à 34 est la clé : on ne peut pas écrire " directement à l'intérieur de la chaîne sans la fermer, donc on l'imprime par son code. Les projets de Sigabort42 poussent cette même idée avec des %c pour les sauts de ligne (10), les tabulations (9) et les délimiteurs de commentaires (47 42 pour /*), afin que la sortie respecte le formatage exact attendu.

Marche 1 — Colleen : le quine qui s'affiche

Colleen est le quine « canonique » du projet : il imprime son propre source sur la sortie standard, en respectant une mise en forme imposée (indentation, commentaires dedans et dehors d'une fonction). On le vérifie d'une ligne :

./Colleen | diff - Colleen.c   # aucune différence → c'est un quine valide

Toute la difficulté est dans la table des %c : chaque espace significatif, chaque tabulation et chaque guillemet du source est reconstruit par son code ASCII, dans le bon ordre. Le projet demande la même chose en C, en assembleur, en Python et en Ruby — le principe est identique, seule la façon de citer une chaîne change d'un langage à l'autre.

Marche 2 — Grace : le quine qui se recopie sur le disque

Grace ne se contente plus d'afficher : il écrit son propre code dans un nouveau fichier, Grace_kid.c. Au lieu d'un printf vers la sortie standard, c'est un dprintf vers un descripteur obtenu par open("./Grace_kid.c", O_RDWR | O_CREAT, …).

Le saut conceptuel est important. Un quine qui s'affiche est une curiosité. Un quine qui produit un fichier source identique à lui-même vient de franchir la frontière : il ne se décrit plus, il se réplique. Grace_kid.c, compilé, est à son tour un Grace.

Marche 3 — Sully : la réplication qui se compile et se relance

Sully est la marche qui donne tout son sens au nom du projet. Il part d'un compteur — disons 5 — et, à chaque exécution :

1. il écrit son propre source dans Sully_N.c, avec le compteur décrémenté à l'intérieur ;
2. il compile ce fichier avec gcc ;
3. il lance le binaire produit, via system().

  Sully (i=5)
    └─ écrit Sully_4.c, le compile, l'exécute
         └─ Sully_4 écrit Sully_3.c, le compile, l'exécute
              └─ Sully_3 → Sully_2 → Sully_1 → Sully_0
                                                  └─ i a atteint 0 : la chaîne s'arrête

Chaque génération fabrique la suivante et lui passe la main, jusqu'à ce que le compteur tombe à zéro. Le programme ne se contente plus d'exister : il se propage, en laissant derrière lui une lignée de descendants compilés.

Le lien avec la sécurité

Retire le compteur qui arrête la chaîne, et remplace « écrire mon source à côté » par « écrire mon code dans un autre programme » : tu as décrit le mécanisme central d'un virus informatique. L'auto-réplication — un code capable de produire une copie fonctionnelle de lui-même — est exactement ce que Sully met en scène dans un cadre inoffensif et borné.

C'est pour ça que Dr Quine est intéressant en sécurité : avant de comprendre comment un malware se propage ou comment un antivirus le reconnaît, il faut avoir tenu dans ses mains la plus petite brique du problème. Un programme qui se décrit lui-même n'est pas qu'un jeu : c'est la version épurée, lisible, d'une idée qu'on retrouve ensuite dans du code bien moins amical.

Le code

Les trois étapes, en C, assembleur, Python et Ruby, sont sur le dépôt : github.com/Sigabort42/dr_quine. Le plus instructif est de lancer ./Colleen | diff - Colleen.c et de constater, de ses propres yeux, qu'il n'y a aucune différence.