Post

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

Commentaires

apres voir lu ton post, je me dis 42 fois de suite que j'ai bien fait de ne pas faire d'informatique dans ma vie, ca me fout un de ces mal de tete !! ;-)

JLR @ septembre 26, 2003 11:09 PM

Ben... Il manque qqch derrière ton #include, dans le programme C. A mon avis c'est

H_I @ septembre 27, 2003 12:35 AM

Argh! Je me suis fait avoir aussi ;)
Essayons de rattraper la manoeuvre: ça devrait être <include>.

Prolog ça semble un peu magique, quand on n'a pas fait de logique (et dieu sait que ça n'est pas naturel, la logique).
Enfin... si dieu ne le sait pas, moi je trouve.

H_I @ septembre 27, 2003 12:37 AM

Oups, je suis fatigué. C'est <stdio.h>. Vais aller m'coucher moi.

H_I @ septembre 27, 2003 12:38 AM

Tu aurais pu attaquer directement par la présentation du prolog, car j'ai peur que les non-informaticiens aient lachés à mi-chemin ;-)

Sinon prolog c'était aussi le nom d'un Système d'Exploitation multitache (et français!) dans les années 80. Il parait qu'on s'en sert encore dans les milieux industriels.

tehu @ septembre 27, 2003 12:52 AM

Merci pour stdio, j'avais oublié de les passer en entités html. Prolog a un côté 'magique' certes, mais ses mécanismes internes sont d'une logique (ahah) très compréhensible - tout repose sur la notion de vérité. On a des axiomes, qui par définition sont vrais, et des règles qui permettent de reformuler d'autres vérités. Au final, en jouant simplement sur la *syntaxe* on arrive à avoir des possibilités *sémantiques* impressionnantes. Lire _Gödel, Escher, Bach_ de Douglas Hofstadter pour saisir de quoi il retourne en profondeur.

Iok @ septembre 27, 2003 12:59 AM

ça permet de comprendre sommairement la comparaison entre un programme style C et un style Prolog.
:) (faut bien que quelqu'un réponde à la question, non ?)

mouche @ septembre 27, 2003 02:59 PM

ça permet de comprendre sommairement la comparaison entre un programme style C et un style Prolog.
:) (faut bien que quelqu'un réponde à la question, non ?)

mouche @ septembre 27, 2003 03:02 PM

Ajouter un commentaire :

Cookie ?