OK, there is something that sometimes haunts me:

"Is it possible to write a piece of source-code, that once compiled, is able to produce some source code file, which on its turn onced compiled, produces the same algorithmic?"

State of mind

I will not try to find any heuristic or algorithmic that tries to find a solution to that problem. I am more interested in the possible approaches and fields that this question may arise or resort to.

Let's admit that I do not always live with that piece of thought in mind. I have to confess that I never took the time in order to handle this question.

Obviously, the way the question is expressed, needs to be refined and clarified a bit, because it has been introduced in a rough manner. What is this question about, and cannot it be expressed in a more articulated way?

Formalism?

I'd just like to whether this is possible to write a piece of code (let's say in Java, for instance, since this is a modern object-oriented language, with the introspection moreover), that - provided it has been properly compiled - produces some files. We assume that the generated file contain code instrusctions for which a grammar already exists (or even, that has been generated by the program on-the-fly). A compiler is supposed t exist for the grammar that is associated with the language (we discard the case when the program has also geneated the compiler code, because this code will need on its turn to be compiled by an already existing compiler, which only postpone the problem). This means that this code can be compiled. If we run the resulting executable, is is possible that it does the same thing as the original program (i.e. generate the source code)?

OK, the concept of grammar needs to be precisely addressed, the concept of compilation and compiler all the same.

The question has the benefit to ask new questions. And while trying to enlight the original question, other questions ill raise at the same time.

Different languages

Even if the question is not defined clearly enough, I feel that the answer may depend on the languages that we consider:

• there are interpreted languages (source-code that gets read and converted to the microprocessor basic instructions on-the-fly) like Prolog,
• there are compiled languages (source-code that gets formerly transformed only once in instructions for a specific microprocessor) like C++,
• and there are semi-interpreded languages (that are first transformed only once in lower-level instructions, independtly of the target microprocessor, and those instructions converted on-the-fly into the actual microprocessor instructions at runtime) like Java.

Those languages do not offer the same features, and this means that depending on the languages involved, their may be classes of languages for which the answer to the question is definitevely no.

Two approaches

As already said, in order to answer to the question, there are two main approaches (which should be considerded, by the way, only once the question has been enough formalised in order to removed any obscur understanding):

1. either I try to think on how I would do to write such a program,
2. or you feel more interested on what it sounds by you.

The latter is the approach I am interested in. And I prefer to try thinking on the consequences that it brings whether the assertion is right or wrong. There are chances that there are configurations (depending on the class of languages involved, like the three classes we have already mentionned) when the answer is always yes, and configurations when the answer is always true. At least, there must be configurations where the answer is sometimes yes, sometimes no, but you cannot get an automatic answer.

If this is false

In that case, I'd love to have a demonstration that this is not possible under certain circumstances. I'm confident that this has something in relation with the information theory.

If this is true

If, under certain circumstances, the answer to the question is yes, it means that we can create kind of a fractalistic movement, that starts from some source code, that generates some source code (can it be exactly the same?), which on its turns runs exactly the same way as the original program. When I say "run", I mean has exactly the same behavior as the initial one.

Je ne sais si ce sont mes récentes lectures du numéro spécial de "Pour la science" dédié à Alan Turing, ou bien parce que cela trottait dans ma tête depuis un petit moment, mais je voulais partager cette pensée : "un programme, c'est comme une démonstration mathématique".

Evidemment, en tant qu'informaticien que je suis, ce raccourci est un peu facile. Je vais tout de même m'en expliquer.

Les langages informatiques pour créer des programmes

Tous les programmes informatiques actuels sont construits à partir d'instructions écrite dans un langage de programmation. Vous avez certainement déja entendu parlé de Java, de C++, de C#, de Python, de PERL : il s'agit de langages qui sont faits de jeux d'instructions, permettant d'exprimer une algorithmique. Un terme un peu pompeux pour désigner une série d'actions. L'intégralité d'un logiciel est contenu dans des fichiers textuels qui contiennent ces instructions, et constituent le code source. Ce code source est soit compilé, c'est-à-dire transformé (par ce que l'on appelle un compilateur) en instructions de très bas niveau qui sont les seuls comprises par un microprocesseur (on parle de langage compilé), soit interprété au moment de l'exécution pour être traduit au démarrage de l'application en ces mêmes instructions élémentaires (on parle de langage interprété). Bon, je m'égare, je ne vais pas écrire un cours d'informatique. Retenez juste que pour un écrire un logiciel, il faut écrire du code source qui contient les instructions du programme.

Les fonctionnalités du logiciel capturées

Dans un monde où tout va pour le mieux, lorsqu'un utilisateur a besoin d'un nouveau logiciel, ou de bénéficier de nouvelles fonctionnalités sur un logiciel existant, il exprime de manière non programmatique ce qu'il attend. C'est le travail du développeur (oui, c'est comme cela que l'on appelle le boutonneux à lunette qui pisse des lignes de code à la petite semaine) de transcrire les fonctionnalités en code. Il utilise pour cela un langage de programmation.

Si l'on considère maintenant que les besoins de l'utilisateur sont suffisamment précis pour que l'on puisse préciser les résultats attendus (jouer un morceau de musique précis, par exemple) par le logiciel attendu en fonction des entrées - dans ce cas d'exemple, l'utilisateur a saisi le nom de l'artiste dans une boîte de dialogue, ainsi que le titre du morceau - il est possible de dire si le logiciel fonctionne bien - en tout cas, pour ce cas d'utilisation. J'ai pris volontairement un cas d'utilisation simple, mais nous allons nous y attarder.

Il n'est pas de chemin unique

Nous avons donc décrit un cas d'utilisation simplissime où l'on sait avec précision quelles sont les entrées du programmes et quelles sont les sorties. Et bien, figurez-vous (mais ça vous l'aviez deviné) qu'il existe une multitude de manière d'écrire le code de ce programme. Vous voyez où je veux en venir ?

C'est comme pour les mathématiques, lorsque l'on veut démontrer un théorème : on sait où l'on veut arriver et l'on dispose d'hypothèses. Et il existe le plus souvent une multitude de manières de prouver un théorème, en invoquant tel ou tel raisonnement. D'ailleurs, s'il n'existait qu'un seul chemin, les maths ce serait drôlement plus simple.

Le programmeur comme un mathématicien ?

Oui, on appelle également programmeur (ou développeur) celui qui écrit les lignes de codes (attention, tout programmeur est informaticien, mais pas l'inverse). Pour moi, l'informaticien se retrouve dans la même problématique que le mathématicien : il doit démontrer un théorème, à savoir écrire un programme. Le mathématicien utilise les hypothèses, les instruments de la logique (la déduction, l'induction) pour arriver à démontrer une assertion. De son côté, l'informaticien utilise les besoins les cas d'utilisation qui lui ont été fournis, le langage informatique (sa grammaire, sa syntaxe) afin de produire un logiciel fidèle aux attentes de l'utilisateur.

Et comme en mathématiques, il peut se trouver en face d'un programme à réaliser qui n'est pas démontrable (pire, pour lequel on peut démontrer qu'il n'est pas possible à réaliser), et donc impossible à réaliser. Si la proposition qu'on lui demande de démontrer n'est pas vrai, il y a fort à parier qu'il ne pourra écrire le programme correspondant.

Et comme en mathématiques, il existe des démonstrations plus ou moins élégantes. En informatique, il existe des programmes plus ou moins élégamment écrits : cela se révèle en général lorsqu'il faut faire évoluer le logiciel. Plus le programme est écrit de manière inélégante, plus il sera difficile de le faire évoluer. Sachez que les programmeurs ont également des considérations esthétiques lorsqu'ils sont intéressés par leur travail, et c'est ce qui fait qu'ils peuvent passer pas mal de temps à discuter sur la manière de faire, que l'on rencontre des puristes à chaque coin de code, et qu'ils ont entre eux des discussions obscures de mathématiciens.

Des mathématiciens qui s'ignorent

Je ne sais si j'ai été suffisamment clair, mais j'espère vous avoir fait partager mon point de vue. Personnellement, je trouve cette note un peu baclée, je ne suis pas content, et donc j'y reviendrai plus tard.

Sachez que comme Monsieur Jourdain, le programmeur écrit des démonstrations sans le savoir !