IokanaaN - Blog

Petit topo sur la programmation

Pour répondre à MediaTic à propos de GNU Prolog: si vous ne savez pas ce que c'est, c'est que vous n'en avez probablement pas besoin ;-) Prolog est un langage de programmation. Plus précisement, il s'agit d'une famille de langages. Il existe différentes implémentations d'interprétes/compilateurs Prolog, i.e. de logiciels permettant de traduire un programme de ce langage (qui n'est à la base que du texte) pour obtenir quelque chose d'exécutable par l'ordinateur. GNU Prolog en est une de ces implémentations.

Quand JLR dit Il manque le "what is" sur le site GNU Prolog et tout serait si simple, ce n'est pas tout à fait exact : il y a une section what is GNU Prolog qui commence le site, où il est dit GNU Prolog is a free Prolog compiler with constraint solving over finite domains. Forcément, ça ne fait avancer le shmilblick que d'un tout petit pas quand on n'a pas entendu parler de Prolog aupravant. Prolog est l'abbréviation de Programmation Logique. À la différence de langage comme le C où il s'agit de donner les instructions dans l'ordre où elle doivent être exécutées (plus ou moins bien structurées avec des boucles et des fonctions) comme par exemple :

#include <stdio.h>

/* fonction factorielle */
/* fact(n) n'est définie que sur N+ */
int fact(unsigned int n) {
   if(n<2) {
      return 1;
   }
   else {
      return n*fact(n-1);
   }
}

int main(int ac, char **av) {
   printf("Factoriel(42)=%d\n",fact(42));
   exit 0;
}

Dans cet exemple, même si les instructions ne sont pas exécutées dans l'ordre dans lequel elles apparaissent dans le code source du programme, on connait la séquence linéaire qui va se produire :

1. fonction main (point d'entrée du programme)
2. calcul de l'argument de printf d'où appel de fact(42)
3. code de la fonction fact avec argument 42:
1. (n>=2) donc calcul de 42*fact((42-1))
2. code de la fonction fact avec argument 41:
1. (n>=2) donc calcul de 41*fact(41-1)
2. code de la fonction fact avec argument 40:
• […]
• code de la fonction fact avec argument 1:
1. (n<2) donc retourne le résultat 1
• […]
3. retourne 40*…*1
3. retourne 41*40*…*1
4. retourne le résultat 42*41*40*…*1
5. fonction printf avec le texte "Factoriel(42)=%d\n"
   dont %d est remplacé par l'argument !42
   et \n est un retour à la ligne pour faire joli.

En revanche, en Prolog, on ne détermine pas des instructions à exécuter. On donne des axiomes et des clauses. Il s'agit purement de la formulation logique du problème qu'on doit résoudre. Un axiome est une vérité : Bob est humain peut-être représenté de la manière suivante Humain(Bob). et pour dire que Bob est mortel, on peut écrire Mortel(Bob). mais on peut aussi dire que tous les humaines sont mortels, Mortel(X):-Humain(X). ce qui veut dire si X rends vrai Humain(X) alors X rends vrai Mortel(X) Un programme Prolog pourra exprimer des choses comme cela :

pere(bob,pb).
mere(bob,mbob).
pere(pbob,ppbob).
grandperepaternel(X,Z):-Pere(X,Y),Pere(Y,Z).
grandperepaternel(bob,JEVEUXSAVOIRQUI)?

Dans ce cas, le programme va trouver JEVEUXSAVOIRQUI="ppbob" et il va le trouver sans qu'on ait besoin de spécifier comment, car la réponse est contenue dans l'énoncé. Les rouages d'un interprète Prolog consiste à faire l'unification des clauses de Horn du programme et d'afficher le ou les résultats de cette unification. En bon français, cela signifie que le logiciel cherche ce qui est compatible pour transformer ce qu'il ne connait pas (X,Y,JEVEUXSAVOIRQUI) en des choses qu'il connait (bob,pbob,ppbob), et au final si c'est possible donner la solution. Poursuite de l'exemple :

parent(X,Y):-pere(X,Y).
parent(X,Y):-mere(X,Y).
grandpere(X,Z):-parent(X,Y),pere(Y,Z).
pere(bob,pbob).
mere(bob,mbob).
pere(pbob,ppbob).
pere(mbob,pmbob).
grandpere(bob,QUI)?

On aura alors QUI="ppbob" en première réponse. Si on demande d'avoir d'autres réponses, on aura QUI="pmbob". Ou bien pmbob aura été trouvé en premier et ppbob en second : on ne contrôle pas l'ordre d'exécution mais seulement les données de l'exécution. D'ailleurs, on pourra aussi bien demander grandpere(QUI,ppbob)? et obtenir la liste des petits-enfants de ppbob…

Comme je le disais dans le billet d'aujourd'hui, l'informatique, ce n'est pas la bureautique. Pour aller plus loin, la programmation en informatique, ce n'est pas seulement la programmation linéaire (Assembleur, Basic, C, Cobol…), il existe de nombreuses familles de langages : Programmation Objet (Java, SmallEiffel), Prog. fonctionnelle (Lisp, Caml), Prog. Logique (Prolog), etc. On peut quasiment tout programmer* en tout, mais certains langages sont mieux adaptés à certains types de problèmes.

Si vous êtes sages, un jour, je vous expliquerai comment traduire automatiquement un langage objet en code binaire pour processeur 68K… Ou pas.

Nota bene :

• Je n'ai testé aucun des exemples, il serait donc étonnant qu'ils fonctionnent sans que je me soit fourvoyé 42 fois…
• on peut aussi écrire int fact(int n){return n?n*fact(n-1):1;}
• Est-ce que ce que j'ai expliqué est très confus pour tous les non-informaticiens, ou bien est-ce que ça permet de comprendre sommairement la comparaison entre un programme style C et un style Prolog ?
• Si vous êtes informaticien, corrigez-moi là où c'est nécessaire (dans l'optique de restez néophytique, quitte à approximer veugra…
• * : on peut tout programmer, je parle de choses "programmables", hein, pas de problèmes indécidables, 'spèces de pinailleurs :-p