Annexe C Quelques exemples de programmes Prolog II+. PrologIA HERITAGE II+

PDF Herunterladen

Dokument

A!ociation

Prolog

HERITAGE

Annexe C

Quelques exemples de programmes Prolog II+

C.1. Les grammaires

C.2. Dérivation formelle

C.3. Les mutants

C.4. Interrogation par évaluation d'une formule logique

C.5. Un casse-tête

C.6. Construction d'un chemin

C.7. Les arbres infinis

C.1.

Les grammaires

Description du problème

La grammaire d'un langage est un ensemble de règles qui permet de déterminer si oui ou non une suite de mots construits sur un certain alphabet appartient au langage. Si oui, on peut alors mettre en évidence la structure sous-jacente de la phrase analysée.

Les langage hors-contexte forment une classe importante : voici par exemple la grammaire définissant l'ensemble de toutes les expressions arithmétiques que l'on peut construire sur les nombres entiers, les opérateurs +, -, * avec leurs priorités habituelles :

(0) <expression> ::= <somme>

(1) <somme> ::= <produit> <reste de somme>

(2) <produit> ::= <primaire> <reste de produit>

(3)

(4)

::= <nombre>

::= ( <expression> )

(5)

(6)

::= <op add> <produit> <reste de somme>

::= <vide>

©PrologIA

C - 2

Annexe C

(7)

(8)

::= <op mul> <primaire> <reste de produit>

::= <vide>

(9) <op mul> ::= *

(10)

(11)

::= +

::= -

(12)

(13)

(21)

::= 0

::= 1

...

::= 9

(22) <vide> ::=

Par exemple, la décomposition de l'expression : 2 * 3 + 6 est donnée dans la figure

C.1 (les noms des symboles non-terminaux ont été abrégés).

C . 1 . 1 .

Représentation de la grammaire en Prolog

Examinons comment écrire cet analyseur en Prolog. Pour cela, considérons la chaîne d'entrée comme un graphe : le premier sommet du graphe est placé au début de la phrase, et on ajoute un sommet après chaque mot de la phrase. Chacun des mots va alors étiqueter l'arc qui joint les deux sommets qui l'encadrent. Avec notre exemple nous obtenons :

2 * 3 + 6

• -----> • -----> • -----> • -----> • -----> • a b c d e f

A!ociation

Prolog

HERITAGE

<expr>

<somme>

__/ \__

___/ \__

/ \

/ \ / | \

| / | \ | / \ |

<nb> <op-m> <prim> <r-d-p> | <prim> <r-d-p> |

| | | | | | | |

| | <nb> <vide> | <nb> <vide> <vide>

| | | | |

2 * 3 + 6

©PrologIA

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 3

Figure C.1

Les règles de la grammaire peuvent alors être vues comme des instructions permettant de compléter ce graphe. C'est ainsi qu'une règle comme (21) sera interprétée par : s'il y a un arc étiqueté par "9" entre le noeud x et le noeud y du graphe, rajouter entre x et y un arc étiqueté "nombre".

Une règle comme (1) donnera : s'il y a un arc étiqueté produit entre les noeuds x et y et un arc étiqueté reste de somme entre les noeuds y et z, rajouter un arc étiqueté

expression entre x et z. Avec ces conventions, analyser une phrase revient à chercher un arc étiqueté expression entre le premier et le dernier sommet du graphe associé. Si on y parvient, la phrase sera acceptée, sinon elle sera rejetée.

Ecrivons maintenant le programme en Prolog : à chaque symbole non -terminal N de la grammaire, nous associerons un prédicat du même nom N(<x, y>) qui sera interprété par : il existe un arc étiqueté N entre les noeuds x et y du graphe.

Pour la règle (1) ceci donne la clause :

somme(<x, y>) -> produit(<x, z>) reste_de_somme(<z, y>);

Revenons un peu sur le graphe, celui-ci peut être simplement représenté par la liste des mots constituant la phrase d'entrée :

• sommet a

/ \

2 •

/ \

* •

/ \

3 •

/ \ sommet b sommet c sommet d

+ •

/ \ sommet e

6 nil sommet f

Chacun des sommets du graphe correspond à un sous-arbre de l'arbre précédent.

Avec cette façon de faire, dans N(<x, y>), x représente la chaîne d'entrée avant d'effacer N et y représente la chaîne restant à analyser après avoir effacé N. De plus, cette représentation permet de traduire les règles terminales comme (12), (13), etc… par :

nombre(<x, y>) -> mot(n, <x, y>) integer(n) ;

qui utilise la règle standard :

mot(a, <a.x, x>) -> ;

et la règle prédéfinie integer. Enfin, reconnaître si une phrase appartient au langage défini par notre grammaire revient à effacer :

expression(<p, nil>)

où p représente la phrase d'entrée sous forme de liste.

©PrologIA

C - 4

Annexe C

C . 1 . 2 .

Mise en évidence de la structure profonde

Nous sommes donc rendus au point où nous savons traduire une grammaire en un ensemble de clauses qui diront si oui ou non une phrase appartient au langage.

Nous pouvons faire mieux en complétant nos relations pour faire ressortir l'arbre construit par l'analyse de la phrase : pour l'exemple précédent.

add

/ \

mul 6

/ \

2 3

Pour cela, nous n'aurons besoin que d'ajouter un argument aux prédicats associés aux non-terminaux de la grammaire. Celui-ci ne fera qu'exprimer comment une phrase est construite à partir des sous-phrases qui la composent. Nous obtenons donc :

nombre(n, <x, y>) -> mot(n, <x, y>) ; primaire(n, <x, y>) -> nombre (n, <x, y>) ;

Finalement, notre règle de départ deviendra :

somme(e, <x, y>) ->

produit(p, <x, z>) reste_de_somme(p, e, <z, y>);

où e représentera l'arbre associé à l'expression analysée. Voici le programme définitif :

"grammaire des expressions" expression(e,<x,y>) -> somme(e,<x,y>); somme(e,<x,y>) ->

produit(p,<x,z>)

reste_de_somme(p,e,<z,y>); produit(p,<x,y>) ->

primaire(f,<x,z>)

reste_de_produit(f,p,<z,y>); primaire(n,<x,y>) -> mot(n,<x,y>) integer(n); primaire(e,<x,y>) ->

mot("(",<x,z>)

expression(e,<z,t>)

mot(")",<t,y>); reste_de_somme(p,e,<x,y>) ->

mot(o,<x,z>)

op_add(o,o_a)

produit(p',<z,t>)

reste_de_somme(<o_a,p,p'>,e,<t,y>); reste_de_somme(e,e,<x,x>) ->; reste_de_produit(f,p,<x,y>) ->

mot(o,<x,z>)

op_mul(o,o_m)

primaire(f',<z,t>)

reste_de_produit(<o_m,f,f'>,p,<t,y>);

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 5

reste_de_produit(f,f,<x,x>) ->; mot(a,<a.x,x>) ->; op_add("+",add) ->; op_add("-",sub) ->; op_mul("*",mul) ->;

"lecture" read(l) -> in_sentence(s,l);

"lancement" run ->

outm("l'expression ")

lire(p)

analyse(p,e)

val(e,f)

outm("vaut")

outl(f); analyse(p,e) -> expression(e,<p,".".nil>) !; analyse(p,e) -> outm("... est incorrecte") fail;

On utilise le prédicat read qui lit une phrase terminée par "." et la transforme en une liste de mots. Par exemple :

> read(p);

12+(23-4)*5+210-34-43.

{p=12."+"."(".23."-".4.")"."*".5."+".210."-".34."-

".43.".".nil}

Le prédicat expression construit l'arbre syntaxique associé à la phrase lue (si elle appartient au langage). On peut ensuite communiquer cet arbre au prédicat évaluable

val qui calcule et imprime sa valeur. Tout ceci est fait par l'appel de la règle run.

C.2.

Dérivation formelle

En analyse mathématique, la dérivation est une opération qui, à une expression algébrique associe une autre expression algébrique appelée dérivée. Les expressions sont construites sur les nombres, les opérateurs +, -, *, des symboles fonctionnels comme sin, cos… et un certain nombre d'inconnues. La dérivation se fait par rapport à l'une de ces inconnues. Dans notre exemple, les nombres seront toujours entiers. Nous n'aurons qu'une inconnue : x, et les seuls symboles fonctionnels unaires seront sin et cos. La première partie du programme est la grammaire d'analyse de ces expressions : c'est celle de l'exemple précédent qui a été complétée. La voici :

"grammaire des expressions" expression(e,<x,y>) -> somme(e,<x,y>); somme(e,<x,y>) ->

©PrologIA

C - 6

Annexe C

produit(p,<x,z>)

reste_de_somme(p,e,<z,y>); produit(p,<x,y>) ->

facteur(f,<x,z>)

reste_de_produit(f,p,<z,y>); facteur(f,<x,y>) ->

primaire(p,<x,z>)

reste_de_facteur(p,f,<z,y>); primaire(n,<x,y>) -> mot(n,<x,y>) integer(n); primaire("x",<x,y>) -> mot("x",<x,y>); primaire(<o_u,p>,<x,y>) ->

mot(o,<x,z>)

op_un(o,o_u)

primaire(p,<z,y>); primaire(e,<x,y>) ->

mot("(",<x,z>)

expression(e,<z,t>)

mot(")",<t,y>); reste_de_somme(p,e,<x,y>) ->

mot(o,<x,z>)

op_add(o,o_a)

produit(p',<z,t>)

reste_de_somme(<o_a,p,p'>,e,<t,y>); reste_de_somme(e,e,<x,x>) ->; reste_de_produit(f,p,<x,y>) ->

mot(o,<x,z>)

op_mul(o,o_m)

facteur(f',<z,t>)

reste_de_produit(<o_m,f,f'>,p,<t,y>); reste_de_produit(f,f,<x,x>) ->; reste_de_facteur(p,f,<x,y>) ->

mot(o,<x,z>)

op_exp(o,o_e)

primaire(p',<z,t>)

reste_de_facteur(<o_e,p,p'>,f,<t,y>); reste_de_facteur(f,f,<x,x>) ->; mot(a,<a.x,x>) ->; op_add("+",plus) ->; op_add("-",minus) ->; op_mul("*",mult) ->; op_exp("^",exp) ->; op_un("-",minus) ->; op_un(sin,sin) ->; op_un(cos,cos) ->;

"règles de dérivation" derivee(x,x,1) ->; derivee(n,x,0) -> integer(n); derivee(plus(u,v),x,plus(u',v')) ->

©PrologIA

A!ociation

Prolog

HERITAGE

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 7

derivee(u,x,u')

derivee(v,x,v'); derivee(minus(u,v),x,minus(u',v')) ->

derivee(u,x,u')

derivee(v,x,v'); derivee(mult(u,v),x,plus(mult(u,v'),mult(v,u'))) ->

derivee(u,x,u')

derivee(v,x,v'); derivee(exp(u,n),x,mult(n,mult(u',exp(u,minus(n,1))))) ->

derivee(u,x,u'); derivee(minus(u),x,minus(u')) -> derivee(u,x,u'); derivee(sin(u),x,mult(u',cos(u))) -> derivee(u,x,u'); derivee(cos(u),x,minus(mult(u',sin(u)))) -> derivee(u,x,u');

"règles de simplification" simplifier(<o_b,x,y>,u) ->

simplifier(x,x')

simplifier(y,y')

simp(o_b,x',y',u); simplifier(<o_u,x>,u) -> simplifier(x,x') simp(o_u,x',u); simplifier(x,x) ->; simp(plus,0,x,x) ->; simp(plus,x,0,x) ->; simp(minus,x,0,x) ->; simp(minus,0,x,y) -> simp(minus,x,y); simp(mult,0,x,0) ->; simp(mult,x,0,0) ->; simp(mult,1,x,x) ->; simp(mult,x,1,x) ->; simp(exp,x,0,1) ->; simp(mult,minus(x),y,u) ->

simp(mult,x,y,v)

simp(minus,v,u); simp(mult,x,minus(y),u) ->

simp(mult,x,y,v)

simp(minus,v,u); simp(exp,x,1,x) ->; simp(exp,0,x,0) ->; simp(exp,1,x,1) ->; simp(o_b,x,y,u) ->

dif(o_b,exp)

integer(x)

integer(y)

evalCst(<o_b,x,y>,u); simp(o_b,x,<o_b,u,v>,t) -> simp(o_b,x,u,z) simp(o_b,z,v,t); simp(o_b,x,y,<o_b,x,y>) ->; simp(minus,0,0) ->; simp(minus,minus(x),x) ->; simp(sin,0,0) ->; simp(cos,0,1) ->; simp(o_u,x,<o_u,x>) ->; evalCst(plus(x,y),u) -> val(x+y,u); evalCst(minus(x,y),u) -> val(x-y,u); evalCst(mult(x,y),u) -> val(x*y,u);

"lecture"

©PrologIA

C - 8

Annexe C read(nil) -> next_char'(".") ! in_char'("."); read(a.b) -> in_ident(a) ! read(b); read("+".b) -> next_char'("+") ! in_char'("+") read(b); read("-".b) -> next_char'("-") ! in_char'("-") read(b); read(a.b) -> in_integer(a) ! read(b); read(a.b) -> in_char'(a) read(b);

"écriture" ecrire(<o_b,x,y>) ->

op_bin(o,o_b)

outm("(")

ecrire(x)

outm(o)

ecrire(y)

outm(")"); ecrire(minus(x)) -> ! outm("-") ecrire(x); ecrire(<o_u,x>) -> ! op_un(o,o_u) out(o) ecrire(x); ecrire(x) -> string(x) ! outm(x); ecrire(x) -> out(x); op_bin(o,o_b) -> op_add(o,o_b); op_bin(o,o_b) -> op_mul(o,o_b); op_bin(o,o_b) -> op_exp(o,o_b);

"lancement" run ->

outm("l'expression ")

read(p)

analyse(p,e)

derivee(e,"x",e')

simplifier(e',f)

outm("a pour derivee")

ecrire(f)

line

!; analyse(p,e) -> expression(e,<p,nil>) !; analyse(p,e) -> outm("... est incorrecte") fail;

Voici par exemple le résultat de l'analyse d'une expression:

$ prolog

> insert("deriv.p2");

{}

> read(p) expression(e, <p, nil>);

3*x^2+6*x+5.

{p=3."*"."x"."^".2."+".6."*"."x"."+".5.".".nil, e=plus(plus(mult(3,exp("x",2)),mult(6,"x")),5)}

Nous avons ensuite défini la relation de dérivation : derivee(f, x, f') signifie : f' est la dérivée de f par rapport à x. Cette relation comporte une règle par opérateur ou symbole fonctionnel et s'exprime de manière très naturelle. Par exemple, la dérivée de l'expression précédente est donnée par :

> read(p) expression(e, <p, nil>) derivee(e, "x", e');

3*x2^+6*x+5.

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 9

..., e'=plus(plus(plus(mult(3,mult(2,mult(1,exp("x",minus(2,1)))))

, mult(exp("x",2),0)),plus(mult(6,1),mult("x",0))),0)}

Comme on le voit, le résultat est loin d'être simplifié ! Nous avons donc adjoint un programme de simplification (très incomplet) qui permet d'obtenir une écriture plus condensée. Tout cela est résumé par le prédicat run dont voici un exemple d'utilisation :

> run; l'expression 3*x^2+6*x+5. a pour derivee ((6*x)+6)

> run; l'expression cos(-3*x^2+2). a pour derivee ((6*x)*sin(-(3*(x^2))+2))

C.3.

Les mutants

Il s'agit de produire des mutants issus d'animaux différents. Pour cela les animaux sont connus par leur nom sous forme de chaîne de caractères. Deux animaux donnent naissance à un mutant si la fin du nom du premier animal est identique au début du nom du second. L'aspect intéressant de ce programme est qu'on utilise une même relation, conc, de deux façons différentes : d'une part pour réunir deux listes, d'autre part pour décomposer une liste en deux sous-listes.

Voici les résultats produits en partant de l'ensemble d'animaux : alligator, tortue, caribou, ours, cheval, vache, lapin, pintade, hibou, bouquetin et chèvre.

> joli_mutant; alligatortue caribours caribouquetin chevalligator chevalapin vacheval vachevre lapintade hibours hibouquetin

> et voici le programme (avec l'option -f vU):

"MUTANTS" mutant(_z) ->

animal(_x)

animal(_y)

conc(_a,_b,_x)

dif(_b,nil)

conc(_b,_c,_y)

dif(_c,nil)

conc(_x,_c,_z); conc(nil,_y,_y) ->;

©PrologIA

C - 10

Annexe C

conc(_e._x,_y,_e._z) -> conc(_x,_y,_z); joli_mutant -> mutant(_z) expl(_z) line fail; expl(nil) ->; expl(_a._l) -> out(_a) expl(_l); animal(a.l.l.i.g.a.t.o.r.nil) ->; animal(t.o.r.t.u.e.nil) ->; animal(c.a.r.i.b.o.u.nil) ->; animal(o.u.r.s.nil) ->; animal(c.h.e.v.a.l.nil) ->; animal(v.a.c.h.e.nil) ->; animal(l.a.p.i.n.nil) ->; animal(p.i.n.t.a.d.e.nil) ->; animal(h.i.b.o.u.nil) ->; animal(b.o.u.q.u.e.t.i.n.nil) ->; animal(c.h.e.v.r.e.nil) ->;

C.4.

logique

Interrogation par évaluation d'une formule

Dans cet exemple on a constitué une banque de données portant sur des individus dont on connaît le nom, l'âge, la ville d'origine et le fait qu'ils portent ou non des lunettes. Tous ces renseignements sont résumés par une assertion telle que :

individu(candide, 20, constantinople, non) -> ;

qui indique que l'individu nommé candide est âgé de 20 ans, qu'il est né à

constantinople et ne porte pas de lunettes. On dispose également de relations

élémentaires (les formules atomiques) portant sur ces données.

Le programme consiste à évaluer une formule logique construite à partir des formule atomiques, des connecteurs "et" et "ou" et des quantificateurs existentiel et universel portant sur des variables typées, c'est à dire dont le domaine des valeurs est précisé. Ainsi, la question type que l'on peut poser est du genre :

« quels sont les valeurs de x appartenant au domaine D pour lesquelles la propriété P est vraie ? »

ce qui est traduit par la formule :

element(x, ens(x, D, P)).

Par exemple, la question : (1) dans quelle ville habite mimosa ? se traduit par la formule.

element(x, ens(x, ville, habite_a(mimosa, x)))

de même : (2) olive porte-t-elle des lunettes ? se traduit par :

element(x, ens(x, booleen, lunette(olive, x)))

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 11 et enfin : (3) quelles sont les villes ayant au moins un habitant age de moins de 20

ans et portant des lunettes ? correspondant à :

element(x, ens(x, ville, existe(y, nom, et(habite_a(y, x),

et(est_age_de(y, a),

et(inferieur(a, 20),

lunette(y, oui)))))))

Ces trois questions ont été pré-enregistrées et sont activées par reponse-a-tout qui

écrit la question en clair suivie des réponses. Voici ce que cela donne (les réponses de la machine sont précédées de "-->") :

> reponse_a_tout; dans quelle ville habite mimosa ?

--> aspres_sur_buech olive porte-t-elle des lunettes ?

--> non quelles sont les villes ayant au moins un habitant age de moins de 20 ans et portant des lunettes ?

--> severac_le_chateau

--> aspres_sur_buech

Voici le programme complet :

"(1) banque de donnees" individu(candide,20,constantinople,non) ->; individu(cunegonde,20,constantinople,oui) ->; individu(gontran,94,aspres_sur_buech,non) ->; individu(casimir,2,severac_le_chateau,oui) ->; individu(clementine,1,cucugnan,non) ->; individu(popeye,99,aspres_sur_buech,oui) ->; individu(olive,99,aspres_sur_buech,non) ->; individu(mimosa,1,aspres_sur_buech,oui) ->; individu(bip,15,pampelune,non) ->; individu(ignace,114,loyola,oui) ->; individu(balthazar,87,jerusalem,non) ->; individu(gaspard,96,smyrne,oui) ->; individu(melchior,34,kartoum,non) ->;

"(2) definition des types" type(x,nom) -> nom(x); type(x,age) -> age(x); type(x,ville) -> ville(x); type(x,booleen) -> booleen(x); nom(candide) ->; nom(cunegonde) ->; nom(gontran) ->; nom(casimir) ->; nom(clementine) ->; nom(popeye) ->; nom(olive) ->; nom(mimosa) ->; nom(bip) ->; nom(ignace) ->; nom(balthazar) ->; nom(gaspard) ->;

©PrologIA

C - 12

Annexe C

nom(melchior) ->; age(20) ->; age(94) ->; age(2) ->; age(1) ->; age(99) ->; age(15) ->; age(114) ->; age(87) ->; age(96) ->; age(34) ->; ville(constantinople) ->; ville(aspres_sur_buech) ->; ville(severac_le_chateau) ->; ville(cucugnan) ->; ville(pampelune) ->; ville(loyola) ->; ville(jerusalem) ->; ville(smyrne) ->; ville(kartoum) ->; booleen(oui) ->; booleen(non) ->;

"(3) listes des formules atomiques" atomique(habite_a(x,y)) ->; atomique(est_age_de(x,y)) ->; atomique(lunette(x,y)) ->; atomique(plus_age(x,y)) ->; atomique(inferieur(x,y)) ->; atomique(different(x,y)) ->;

"(4) evaluation des formules atomiques" habite_a(x,y) -> individu(x,a,y,b); est_age_de(x,y) -> individu(x,y,v,b); plus_age(x,y) ->

individu(x,a,v,b)

individu(y,a',v',b')

val(inf(a',a),1); lunette(x,y) -> individu(x,a,v,y); inferieur(x,y) -> val(inf(x,y),1); different(x,y) -> dif(x,y);

"(5) evaluation des formules" vrai(p) -> atomique(p) p; vrai(non(p)) -> non(vrai(p)); vrai(et(p,q)) -> vrai(p) vrai(q); vrai(ou(p,q)) -> vrai(p); vrai(ou(p,q)) -> vrai(q); vrai(existe(x,t,p)) -> type(x,t) vrai(p); vrai(tout(x,t,p)) -> non(vrai(existe(x,t,non(p))));

©PrologIA

A!ociation

Prolog

HERITAGE

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 13

"(6) definitions utiles" non(p) -> p ! fail; non(p) ->;

"(7) calcul des reponses" reponse_a_tout ->

question(i,q)

element(y,q)

line

outm("-->")

out(y)

line; element(x,ens(x,t,p)) ->

type(x,t)

vrai(p);

"(8) listes des questions" question(1,ens(x,ville,habite_a(mimosa,x))) ->

outm("(1) dans quelle ville habite mimosa ?"); question(2,ens(x,booleen,lunette(olive,x))) ->

outm("(2) olive porte-t-elle des lunettes ?"); question(3,ens(x,ville,existe(y,nom,et(habite_a(y,x),

et(est_age_de(y,a),et(inferieur(a,20),lunette(y,oui)))))))

outm("(3) quelles sont les villes ayant au moins un habitant")

outm("age de moins de 20 ans et portant des lunettes ?");

C.5.

Un casse-tête

Dans cet exemple, il s'agit de résoudre le célèbre problème de crypto-arithmétique dans lequel en remplaçant chaque occurrence des lettres s, e, n, d, m, o, r, y par un même chiffre, on ait :

SEND

+MORE

-----

MONEY

Une programmation conventionnelle oblige à prendre en compte deux problèmes simultanément : celui de l'addition proprement dite et le fait que deux lettres différentes sont remplacées par deux chiffres différents. Au contraire, avec le dif retardé, ces deux problèmes sont bien séparés : le prédicat differents met en place toutes les inéquations à l'avance. On n'a plus ensuite qu'à exprimer l'addition et les

dif se débloquent progressivement au fur et à mesure que l'on avance dans la résolution du problème. Le programme est rendu plus clair, mais aussi plus efficace. Voici la solution :

> jolie_solution;

9567

+1085

-----

©PrologIA

C - 14

Annexe C

10652

{}

Voici le programme :

"resolution de SEND+MORE=MONEY" solution(s.e.n.d.m.o.r.y) ->

different(s.e.n.d.m.o.r.y.nil)

somme(r1,0,0,m,0)

somme(r2,s,m,o,r1)

somme(r3,e,o,n,r2)

somme(r4,n,r,e,r3)

somme(0,d,e,y,r4); somme(r,0,0,r,0) -> ! retenue(r); somme(r,x,y,z,r') ->

retenue(r)

chiffre(x)

chiffre(y)

val(add(r,add(x,y)),t)

val(div(t,10),r')

val(mod(t,10),z); chiffre(0) ->; chiffre(1) ->; chiffre(2) ->; chiffre(3) ->; chiffre(4) ->; chiffre(5) ->; chiffre(6) ->; chiffre(7) ->; chiffre(8) ->; chiffre(9) ->; retenue(1) ->; retenue(0) ->; different(nil) ->; different(x.l) -> hors_de(x,l) different(l); hors_de(x,nil) ->; hors_de(x,a.l) -> dif(x,a) hors_de(x,l); jolie_solution -> solution(s) jolie_sortie(s); jolie_sortie(s.e.n.d.m.o.r.y) ->

outm(" ") out(s) out(e) out(n) out(d) line

outm("+") out(m) out(o) out(r) out(e) line

outm("----") line

out(m) out(o) out(n) out(e) out(y) line;

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 15

C.6.

Construction d'un chemin

Ce programme énumère des chemins sans boucle par utilisation de la règle freeze.

Rappelons que freeze retarde l'effacement du littéral sur lequel il porte tant qu'une certaine variable n'est pas affectée. Il est utilisé ici pour construire un bon chemin qui est un chemin qui ne passe pas deux fois par la même étape.

Pour cela, on calcule un chemin possible par la règle chemin que l'on valide au fur et

à mesure par la règle bonne-liste, ce qui permet de rejeter automatiquement le chemin en cours de construction dès qu'on tente de lui adjoindre une étape qui y figure déjà. Voici la liste des chemins sans boucle passant par Marseille, Londres, et Los Angeles suivie du programme :

> bon_chemin(l);

{l=Marseille.nil}

{l=London.nil}

{l=LosAngeles.nil}

{l=Marseille.London.nil}

{l=Marseille.London.LosAngeles.nil}

}l=Marseille.LosAngeles.nil}

{l=Marseille.LosAngeles.London.nil}

{l=London.Marseille.nil}

{l=London.Marseille.LosAngeles.nil}

{l=London.LosAngeles.nil}

{l=London.LosAngeles.Marseille.nil}

{l=LosAngeles.Marseille.nil}

{l=LosAngeles.Marseille.London.nil}

{l=LosAngeles.London.nil}

{l=LosAngeles.London.Marseille.nil}

Et voici le programme :

"chemins sans boucles" bon_chemin(l) -> bonne_liste(l) chemin(l); chemin(x.nil) -> etape(x); chemin(x.x'.l) -> route(x,x') chemin(x'.l); route(x,x') -> etape(x) etape(x'); etape(Marseille) ->; etape(London) ->; etape(LosAngeles) ->;

©PrologIA

C - 16

Annexe C

"liste sans repetition" bonne_liste(l) -> freeze(l,bonne_liste'(l)); bonne_liste'(nil) ->; bonne_liste'(x.l) -> hors_de(x,l) bonne_liste(l); hors_de(x,l) -> freeze(l,hors_de'(x,l)); hors_de'(x,nil) ->; hors_de'(x,x'.l) -> dif(x,x') hors_de(x,l);

C.7.

Les arbres infinis

Les automates d'états finis sont un bon exemple d'objets qui peuvent être représentés par des arbres infinis (rationnels). Le programme présenté ici calcule un automate minimal qui accepte certaines chaînes et en refuse d'autres. Toutes ces chaînes sont faites à partir de a et b. La règle prédéfinie draw-equ(x) est utilisée à la fois pour dessiner l'automate et pour minimiser sa taille, c'est à dire le nombre de ses

états. Son utilisation suppose que le module de dessin soit chargé.

> infinite;

> accepte(s, "a"."b".nil) accepte(s, "b"."a".nil)

refuse(s, "a".nil) refuse(s, "b".nil)

refuse(s, "a"."a".nil) refuse(s, "b"."b".nil)

refuse(s, "a"."a"."b".nil) refuse(s, "b"."b"."a".nil)

entier_de_Peano(n)

automate_de_taille(s, n)

draw_equ(s)

fail;

x x = final

/ \

aa bb

| |

y z y = non_final

/ \

aa bb

| |

z x z = non_final

/ \

aa bb

| |

x y

Le terme fail force le backtracking pour éviter l'impression finale. Voici le programme complet permettant de produire tout cela. Il faut noter que les buts

accepte(s,x) et refuse(s,x) sont effacés de façon complétement déterministe. Pour cette raison, afin d'obtenir l'automate minimal, il n'est pas nécessaire de placer

entier_de_Peano(n) comme premier but de la suite des buts précédents (à effacer).

A!ociation

Prolog

HERITAGE

©PrologIA

A!ociation

Prolog

HERITAGE

Quelques exemples de programmes Prolog II+

C - 17

"Automate d'etat fini" accepte(s,nil) -> etat_final(s); accepte(s,e.x) -> fleche(s,e,s') accepte(s',x); refuse(s,nil) -> non_etat_final(s); refuse(s,e.x) -> fleche(s,e,s') refuse(s',x); etat_final(<final,aa(s1),bb(s2)>) ->; non_etat_final(<non_final,aa(s1),bb(s2)>) ->; fleche(<f,aa(s1),bb(s2)>,"a",s1) ->; fleche(<f,aa(s1),bb(s2)>,"b",s2) ->;

"Calcul d'un automate de taille donnee" automate_de_taille(s,n) -> automate_de_taille(s.nil,n,nil); automate_de_taille(nil,0,l) ->; automate_de_taille(s.l,n,l') ->

element_de(s,l')

automate_de_taille(l,n,l'); automate_de_taille(s.l,suc(n),l') ->

non_element_de(s,l')

fleche(s,"a",s1)

fleche(s,"b",s2)

automate_de_taille(s1.s2.l,n,s.l'); element_de(s,s.l) ->; element_de(s,s'.l) -> dif(s,s') element_de(s,l); non_element_de(s,nil) ->; non_element_de(s,s'.l) -> dif(s,s') non_element_de(s,l);

"Enumeration des entiers de Peano" entier_de_Peano(0) ->; entier_de_Peano(suc(n)) -> entier_de_Peano(n);

©PrologIA

C - 18

Annexe C

A!ociation

Prolog

HERITAGE