Partage

[Atelier] Prolog

Essayez un langage totalement différent !

1 2 3 >>

25 juillet 2010 à 2:37:05

Salut,

Vous avez envie de profiter de l'été en restant devant votre écran ? Voici un nouvel Atelier pour le forum Autres Langages. Le concept reste similaire aux ateliers précédents (dont Cod'Art, Compression, Brainfuck, Calculatrice(s) et P'tit Langage) : il s'agit de présenter son travail, de discuter, commenter et pourquoi pas retravailler/améliorer celui des autres.

Le sujet est par contre un peu différent. Plutôt qu'un problème donné à faire dans le langage de programmation de votre choix, il s'agit maintenant d'essayer, sous toutes ses coutures, un langage de programmation donné. Ça veut dire qu'il faut commencer par l'apprendre, essayer de comprendre ses spécificités, étudier ses points forts, ses applications privilégiées, et pourquoi pas essayer d'explorer un peu les coins plus sauvages.

Pour que ce soit amusant, j'ai essayé de choisir un langage radicalement différent de ce que vous connaissez déjà, qui demande une nouvelle façon de penser la programmation.

Le langage de cet atelier-ci est Prolog. Si ça marche, il y en aura d'autres, pour d'autres langages.

Qu'est-ce que Prolog ?

Prolog est un langage de programmation logique. De façon grossière, un programme Prolog est un ensemble de connaissances et de règle de déductions que le programmeur donne au langage. Le programmeur peut ensuite poser des questions, auxquels le programme essaiera de répondre en utilisant les informations fournies.

Plus exactement, on donne à Prolog des sortes de "règles de raisonnement", et on lui pose ensuite des questions. Il doit, en combinant les règles qu'on lui a donné, produire une réponse.

Voici un exemple d'informations que l'on pourrait vouloir fournir à Prolog (ce n'est pas du vrai code prolog, juste une description en français) :

Citation

Une personne X (les majuscules désignent des variables) est frère ou sœur de Y si X est différent de Y, et s'il existe une personne Z qui est parent à la fois de X et de Y.

X est parent de Y si X est père de Y, ou si X est mère de Y.

Tania est la mère de Sophie.
Thomas est le père de Sophie.
Thomas est le père d'Émilie.
Tania est la mère de Camille.
Michel est le père de Thomas.

On peut alors poser la question suivante :

Citation

Quels sont les frères et soeurs de Sophie ?

Et prolog fournira le bon résultat, à savoir tout ce qu'il peut déduire des informations qu'on lui a données :

Citation

Émilie et Camille.

Voici le code Prolog correspondant :

frère_ou_sœur(X,Y) :- parent(Z,X), parent(Z,Y), X \= Y.
parent(X,Y) :- père(X,Y).
parent(X,Y) :- mère(X,Y).
mère(tania, sophie).
père(thomas, sophie).
père(thomas, émilie).
mère(tania, camille).
père(michel, thomas).

Et pour interroger Prolog (la première ligne est la question, avec la réponse ensuite) :

?- frère_ou_sœur(sophie, X).
X = émilie ;
X = camille .

Suivant ce principe, on peut en fait écrire des programmes relativement élaborés. Historiquement, la programmation logique est appréciée dans tous les domaines où il faut "faire des déductions" : certaines bases de données, de systèmes d'intelligence artificielle, etc.

Que faire pour cet atelier ?

La meilleure chose à faire est de commencer par trouver un tutoriel pour apprendre le langage Prolog. Cela nécessitera certainement d'installer une implémentation du langage sur votre machine, pour pouvoir tester du code.

Un bon début peut être l'article wikipédia Prolog, qui donne une présentation un peu moins superficielle du langage, et des liens vers des cours de Prolog. Prolog étant un langage créé en France, il devrait être plutôt facile de trouver de la documentation francophone sur le sujet avec un peu de recherche.

Une fois que vous commencez à comprendre un peu le langage, vous devriez essayer de coder de petits exercices dans ce langage. S'ils vous paraissent intéressant, n'hésitez pas à les poster ici. Les questions sur le langage sont bienvenues si vous butez sur un point particulier, mais essayez quand même de faire des efforts de compréhension de votre côté.

Et surtout, rappelez-vous : le but de cet atelier est de présenter quelque chose de très, très différent de ce que nous connaissons. Si vous vous sentez perdu au départ, c'est normal, et même plutôt bon signe : ça veut dire que vous apprendrez de nombreuses choses avec cet atelier.

J'essaierai de mettre à jour ce premier post de temps en temps pour y mettre des informations utiles, des liens pertinents, et pourquoi pas des idées de choses à essayer en Prolog. Mais je vous rappelle que ceci est un atelier, et tout le monde est invité à participer, proposer des solutions ou commenter celles des autres. Nous sommes tous à la fois organisateurs, juges, conseillers et participants !

Liens utiles

- une longue série d'exercices avec corrections
- quelques cours en français sur Developpez.com

EMC1

25 juillet 2010 à 12:27:17

Une série d'exercices (avec correction), qui vont de basiques à élaborés pour ceux qui en chercheraient.

A propos de la ressource en Français, les quelques cours que j'ai lus étaient peu détaillés bien qu'intéressant.
Je vais sans doute m'y remettre à l'occasion de cet atelier, en cherchant en anglais cette fois.

gorgonite

25 juillet 2010 à 13:10:24

on avait tenté de faire une série de cours ici : http://prolog.developpez.com/cours/

bluestorm

25 juillet 2010 à 15:57:36

EMC1 > merci pour les exercices, j'essaierai de regarder !

J'ai fait quelques expérimentations avec Prolog ce matin : j'ai joué avec les listes.

Listes en prolog

En prolog, une liste est :

soit la liste vide, []
soit une liste constituée d'un élément de tête H, et du reste de la liste T. Cette liste est notée [H|T].

Cette notation est pratique quand on accède seulement à un élément de la liste, mais un peu indigeste quand on veut des listes à plusieurs éléments. Par exemple, la liste dont les éléments sont 1 et 2 est [1 | [2|[]] ]. Il existe donc les sucres syntaxiques [H1,H2,..] (par exemple [1,2,3] pour la liste de ces trois éléments) et [H1,H2,..|T] (la liste commençant par les H1, etc., et dont le reste est la liste T). Cette syntaxe a d'ailleurs été reprise par le langage Erlang.

Quelques exemples de fonctions sur les listes

Les fonctions présentées ici sont juste des essais. Il y a sans doute moyen de faire mieux ou différemment, et tous les commentaires sont bienvenus.

Vérification des listes

On peut écrire des choses qui ressemblent à des listes mais n'en sont pas. Par exemple [1|2] n'est pas une liste, car la queue, 2, n'est pas une liste; attention, il ne s'agit pas de la liste [1,2], qui est représentée par [1| [2|[]] ].

J'ai donc écrit une fonction list pour vérifier qu'une valeur est bien une liste :

la liste vide est bien une liste
[H|T] est une liste si T est bien une liste

list([]).
list([H|T]) :- list(T).

On peut l'interroger :

?- list([]).
true.

?- list([1,2,3]).
true.

?- list([1|2]).
false.

On peut aussi lui poser la question qui tue : "Quelles sont les listes X ?"

?- list(X).
X = [] ;
X = [_G266] ;
X = [_G266, _G269] ;
X = [_G266, _G269, _G272] ;
...

Prolog renvoie une suite de réponse, et à chaque fois le mode interactif me demande si je veux m'arrêter là, ou avoir la réponse suivante. Il commence par proposer la liste vide, puis la liste [_G266]. _G266 désigne en fait un nom de variable interne au mode interactif. Comme c'est une variable, cela veut dire que _G266 peut prendre n'importe quelle valeur : [1] est une liste, [[]] est une liste, etc. Il a donc désigné toutes les listes à un seul élément. Il continue ensuite à me proposer toutes les listes à deux éléments, à trois éléments, etc.

Appartenance à une liste

J'ai ensuite écrit la fonction qui teste si un élément appartient à une liste :

H appartient à [H|T] (comme la variable T peut prendre n'importe quelle valeur, ça désigne toutes les listes qui commencent par H)
sinon, X appartient à [H|T] si X appartient à T.

mem(H, [H|T]).
mem(X, [H|T]) :- mem(X, T).

Questions classiques :

?- mem(2, [1,2,3]).
true .

?- mem(5, [1,2,3]).
false.

Questions plus originales :

à quelles listes appartient 2 ?

?- mem(2, X).
  X = [2|_G269] ;
  X = [_G268, 2|_G272] ;
  X = [_G268, _G271, 2|_G275] ;
  X = [_G268, _G271, _G274, 2|_G278]...

(Il énumère toutes les listes qui contiennent 2 en première position, deuxième position..)

quels éléments appartiennent à [1,2,3] ?

?- mem(X, [1,2,3]).
  X = 1 ;
  X = 2 ;
  X = 3 .

Autres fonctions sur les listes

J'ai aussi écrit la fonction qui concatène deux listes (les met bout à bout). Pour laisser un peu de suspense, et que les autres puissent jouer aussi (c'est moins drôle quand on a déjà vu la solution), je ne la posterai pas ici. Je vous invite à essayer aussi, et à regarder ce qu'on peut obtenir en lui posant différentes questions. On peut par exemple la forcer à répondre aux questions suivantes :

la liste X est-elle préfixe de la liste Y ?
enlever la liste X du début de Y (par exemple enlever [1,2] à [1,2,3,4] pour obtenir [3,4])
enlever la liste X de la fin de Y

On peut aussi s'en servir pour coder une fonction qui, par exemple, trouve toutes les positions où l'élément X apparaît dans la liste Y.

Anonyme

25 juillet 2010 à 16:13:16

Tiens c'est marrant je me suis lancer ce matin et j'ai coder exactement la même chose que toi bluestorm :

find(X,[X|_]).
find(X,[_|L]) :- find(X,L).

Qui permet a la fois de savoir si un élément appartient à une liste ?- find(a,[a,b,c]).
Tt de lister tout les éléments d'une liste : ?- find(X,[a,b,c]).
(Voir de trouver les listes auquelles appartient un élément bien que ça semble moins intéressant.)
Mais par contre j'ai un warning que je ne comprend pas bien :

Citation

Clauses of find/2 are not together in the source-file

Juste un truc déroutant au début : pour tester un code il faut l'enregistrer dans un fichier et l'appeler avec par exemple

$ swipl -f fichier.pl

si l'on travaille avec SWI Prolog

ou bien

$ gprolog
| ?- ['fichier.pl']

Avec gprolog.

Je pensais au début pouvoir entrer les prédicats dans l'interpréteur directement à partir du shell mais on obtient ce genre d'erreur :
"uncaught exception: error(existence_error)"

Par contre j'ai plus de mal avec la fonction de concaténation. J'ai essayer quelque chose comme :

concat([H|T],L2,X) :- concat(T,L2,[H|X]).
concat([],L2,X) :- concat(L2,[],X).

Mais ça ne mène à rien.

spider-mario

25 juillet 2010 à 16:50:10

C'est possible, en les encadrant avec assert(...).

Note : consult('bla.pl'). permet aussi de les charger depuis un fichier.

rushia

25 juillet 2010 à 17:31:04

Pour la fonction de concaténation, j'ai fait ça :

concat([],L,L).
concat([H|T],L,[H|Tc]) :- concat(T,L,Tc).

Ça a l'air de marcher :

?- concat([1,2,3,4],[5,6,7,8,9],X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9].

Sinon, j'ai essayer de travailler un peu avec des arbres binaires :

max(X,Y,M) :-
   X=<Y,
   M=Y.
max(X,Y,M) :-
   X>Y,
   M=X.
hauteur(0,0).
hauteur(1,0).
hauteur(n(X,Y),L) :-
   hauteur(X,Lx),
   hauteur(Y,Ly),
   max(Lx,Ly,M), L is M+1.

Résultat sur l'arbre :

.    /   \
    /\   /\
   1 /\ 0  1
    /\ 0
   1  0

?- hauteur(n(n(1,n(n(1,0),0)),n(0,1)),L).
L = 4 .

Par contre, je me suis limité à un arbre ne pouvant "stocker" que des 0 et des 1 parce que je n'ai pas trouvé de moyen de donner une longueur 0 à un arbre n'étant en réalité qu'une feuille pour n'importe quel nombre.
Edit : Après réflexion, je vois la solution suivante, un peu lourde :
On désigne une feuille par f(x) ou x est ce que l'on veut.

max(X,Y,M) :-
   X=<Y,
   M=Y.
max(X,Y,M) :-
   X>Y,
   M=X.
hauteur(f(_),0).
hauteur(n(X,Y),L) :-
   hauteur(X,Lx),
   hauteur(Y,Ly),
   max(Lx,Ly,M), L is M+1.

?- hauteur(n(n(f(1),n(n(f(3.2),f(5)),f(4.1))),n(f(0.1),f(3))),L).
L = 4 .

Anonyme

25 juillet 2010 à 18:21:09

Oui ça marche mon erreur vient du fait qu'il faut réfléchir "à l'envers". On ne construit pas la liste, on doit en fait décrire ses propriétés.

Une chose amusante avec ce langage est qu'une fonction peut servir à plusieurs actions. Par exemple la fonction

remove_at(X,[X|R],1,R).
remove_at(X,[H|T],N,[H|R]) :- K is N - 1, remove_at(X,T,K,R).
?- remove_at(X,[a,b,c,d],2,R).
X = b,
R = [a, c, d] .

Permet d'insérer un élément dans une liste en changeant les paramètres :

remove_at(c,X,3,[a,b,d]).
X = [a, b, c, d] .

Et un peu de calcul avec une fonction factoriel :

fact(0,1).
fact(N,X) :- N > 0, K is N - 1, fact(K,X2), X is N*X2.

Abronsius

25 juillet 2010 à 19:41:36

Salut,

Je vais me mettre au Prolog pour cet atelier et j'ai trouver un cours vraiment très bien fait:
http://perso.crans.org/martin/Doc/Cour [...] %20PROLOG.pdf

gorgonite

25 juillet 2010 à 20:14:07

allez, je vais contribuer un peu...

Le solveur Prolog consiste à parcourir l'arbre des solutions en profondeur d'abord, et en sélectionnant les clauses de gauche à droite

Ainsi, reprenons l'exemple de Bluestorm

parent(X,Y) :- père(X,Y).
parent(X,Y) :- mère(X,Y).

Introduisons un peu de "récursivité" en cherchant des ancêtres

ancetre(X,Z) :- ancetre(Y,Z),parent(X,Y).
ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).

La première ligne va partir envoyer le solveur standard dans une boucle infinie puisqu'il va chercher à résoudre ancetre:-ancetre avant de s'intéresser à parent qui est en seconde position

Donc gardez à l'esprit que l'ordre des termes peut grandement influer sur la vitesse de l'analyse (surtout si des ! (cut) sont introduits)

mais ne despérez pas, on peut s'en sortir si le problème ne correspond pas à une recherche en profondeur d'abord, via la méta-interprétation (changer la stratégie de l'évaluation) ou via la mémoïzation (se souvenir des cas déjà étudiés)

EMC1

25 juillet 2010 à 21:11:46

Notons quand même qu'il n'y a pas de fonction en Prolog, on parle de prédicat, utilisés en essayant de prouver la véracité d'un but.

Par convention on donne l'usage d'un prédicat en écrivant ses termes + , - ou ? suivant qu'il doivent respectivement être donnés en entrée (une valeur), attendue en sortie (une variable libre) ou l'un des deux au choix.
Par exemple : between(+,+,?).

gnomnain

25 juillet 2010 à 23:46:00

Citation : nax

Oui ça marche mon erreur vient du fait qu'il faut réfléchir "à l'envers". On ne construit pas la liste, on doit en fait décrire ses propriétés.

Une chose amusante avec ce langage est qu'une fonction peut servir à plusieurs actions. Par exemple la fonction [...]

Oui, j'ai utilisé ça et c'est marrant :

prefix([X|XS],[X|YS]) :- prefix(XS,YS).
prefix(XS,[]).

length2([],0).
length2([X|Y],N) :- length(Y,M), N is M+1.

concat([],YS,YS).
concat([X|XS],YS,[X|ZS]) :- concat(XS,YS,ZS).

take(L,N,P) :- length2(P,N), prefix(L,P).
drop(L,N,S) :- length2(U,N), concat(U,S,L).

Je pourrais encore exprimer prefix avec concat, mais je l'ai pas fait (les prédicats take(L,N,P) et drop(L,N,S) veulent dire "P est la liste composée des N premiers éléments de N" et "S est ce qui reste quand on a enlevé N éléments". Par contre, je ne sais pas trop ce que ça fait niveau efficacité. J'imagine que comme je l'ai écrit, il crée un modèle pour la liste avec des trous partout (il connait son nombre d'éléménts), et ensuite il unifie avec le prédicat "prefix". Si c'est ça, ça fait du O(N) je crois.

Anonyme

25 juillet 2010 à 23:47:03

Petite remarque en passant : non seulement l'ordre des prédicats peut compter, mais également l'ordre de propositions séparées par une virgule. J'ai été confronté à ça en voulant extraire le maximum d'une liste.
Je m'explique :

mem(H, [H|_]).
mem(X, [_|T]) :- mem(X, T).

greater(_, []).
greater(X, [H|T]) :- X >= H, greater(X, T).

max(X, L) :- greater(X,L), mem(X, L).

Ce code refuse de fonctionner, on reçoit l'erreur :

?- max(X, [1,2,3]).
ERROR: >=/2: Arguments are not sufficiently instantiated

En revanche avec :

max(X, L) :- mem(X, L), greater(X,L).

tout fonctionne bien :

?- max(X, [1,2,3]).
X = 3 ;

Quelqu'un pourrait-il m'expliquer cela ?
D'ailleurs, même avec le deuxième code, on retombe toujours sur la même erreur avec certaines questions :

?- max(3, L).
L = [3] ;
ERROR: >=/2: Arguments are not sufficiently instantiated

bluestorm

25 juillet 2010 à 23:53:38

C'est un problème au niveau de l'opérateur >= qui n'est pas un opérateur logique. Il ne fonctionne que quand on lui donne deux valeurs, et pas des variables d'unification. Selon l'ordre dans lequel tu mets tes clauses et les arguments que tu donnes, si tu te retrouves au moment où tu testes >= à avoir déjà donné une valeur aux deux variables, tout va bien, par contre si ce n'est pas encore fait ça foire.

Les opérateurs arithmétiques primitifs sont aussi affectés par ce problème, ce qui les rend assez désagréables à utiliser. Je trouve plus amusant de recoder soit-même avec un encodage plus respectueux des aspects logique (mais moins performant).

D'ailleurs, si je me suis attaqué aux listes, c'est aussi parce que c'est une structure de donnée correspondant, d'une certaine manière, aux nombres en notation unaire. La fonction "somme" sur les nombres zero/succ est identique à la fonction "append" des listes.

Citation : gnomnain

Oui ça marche mon erreur vient du fait qu'il faut réfléchir "à l'envers". On ne construit pas la liste, on doit en fait décrire ses propriétés.

Une chose amusante avec ce langage est qu'une fonction peut servir à plusieurs actions.

Malheureusement, et c'est une des choses qui me déçoit avec prolog, ce n'est que très partiellement vrai. La programmation logique a une image de "programmation déclarative par excellence", on décrit les propriétés etc., mais en fait, des langages que je connais, c'est celui qui demande le plus d'avoir en tête les règles opérationnelles du langage. C'est un peu comme quand on essaie d'évaluer les performances d'un code Haskell, mais là ça joue sur la correction du code (si je m'en sers comme ça, est-ce qu'il va donner le résultat, ou boucler à l'infini ?).

Ceci dit, cette sensation est peut-être causée par mon manque d'habitude du paradigme.

Anonyme

26 juillet 2010 à 0:15:09

Citation : bluestorm

Je trouve plus amusant de recoder soit-même avec un encodage plus respectueux des aspects logique (mais moins performant).

Dans ce cas précis, tu recoderais ça comment ?

En attendant, j'ai tenté de recoder un tri par sélection, avant de passer à des tris plus compliqués... Je ne sais pas si ma solution est vraiment élégante, mais c'est celle qui m'est venue le plus naturellement.

less(_, []).
less(X, [H|T]) :- X =< H, less(X, T).
min(X, L) :- mem(X, L), less(X, L).

remove(X, [X|T], T).
remove(X, [H|T], [H|S]) :- remove(X, T, S).

selectionSort([], []).
selectionSort(L, [X|S]) :- min(X, L), remove(X, L, T), selectionSort(T, S).

Exemple :

selectionSort([3,1,2], L).
L = [1, 2, 3] .

?- selectionSort([3,1,2,17,2], L).
L = [1, 2, 2, 3, 17] .

EDIT : Désolé EMC1, ce n'était effectivement pas un tri à bulles comme je l'avais écrit à l'origine, mais je m'y attèle à l'heure actuelle

EMC1

26 juillet 2010 à 0:23:20

Je ne pense pas que ce soit recodable en pur Prolog, comme toute manipulation de nombres.

Cyprien_, ton tri s'apparente plus selon moi à un tri par sélection.

Je vois que tu m'as grillé...

Anonyme

26 juillet 2010 à 0:47:13

Apparemment c'est faisable :

bubble([X], [X]).
bubble([X ,Y | T], [Y|L]) :- X > Y, bubble([X | T], L).
bubble([X, Y | T], [X | L]) :- bubble([Y | T], L).

bubbleSort(L1, L) :- bubble(L1, L2), (L1 = L2, L2 = L ; bubbleSort(L2, L)), !.

Cette fois je ne crois pas me tromper en affirmant que c'est bien un tri à bulles

.

Exemple :

?- bubbleSort([1,3,2], L).
L = [1, 2, 3].

?- bubbleSort([4, 2, 5, 3, 1], L).
L = [1, 2, 3, 4, 5].

Orwell

26 juillet 2010 à 1:21:43

Pour ceux que ça intéresse, j'ai retrouvé l'énoncé d'un gros exercice en Prolog (tiré de mon cours de logique et IA à la fac :-°

)

Voici les questions:

On souhaite générer, en Prolog, la gamme d’assemblage d’un produit, constitué d’un ensemble de composants complexes. Chaque composant est modélisé comme une union de parallélépipèdes rectangles ayant les arrêtes parallèles aux axes (ces différentes parties de composants n'étant pas dissociables). Il s'agit donc de déterminer l'ordre (et les directions respectives) dans lequel on doit assembler chacun de ses composants complexes pour construire le produit complet.

L'ajout d'un composant complexe au produit à assembler se fait par translation latérale dans une des 6 directions de l'espace. (Note: En pratique, le robot manipulateur effectue une rotation du produit assemblé et présente toujours le nouveau composant dans la même direction). Il faut donc veiller à ne pas provoquer, au cours de la translation, de collision entre le composant à placer et les composants déjà assemblés.

La démarche adoptée pour générer la séquence d'assemblage est de partir du produit assemblé, et de déterminer l'ordre de désassemblage de chacun de ses composants. Il suffira ensuite d'inverser la séquence obtenue.

On demande:

1.A de définir des prédicats qui permettent de représenter un produit et ses composants complexes.
1.B de définir un prédicat audessus(A, B) qui détermine que le composant complexe B est au-dessus du composant complexe A (idem pour en-dessous, à gauche, à droite, devant, derrière).
1.C de définir un prédicat searchobstacles(X, L, dir) qui donne la liste des composants qui empêchent le retrait du composant X dans la direction dir. Et, de générer pour tous les composants, X, la base de données des faits de type obstacles(X, dir , liste).
1.D de générer un désassemblage possible.
1.E de générer tous les désassemblages possible.
1.F De choisir la meilleure gamme d’assemblage selon le critère de minimisation du nombre de changement de direction d’assemblage.

Et pour ceux qui ont besoin d'un coup de pouce, voici déjà des éléments de réponses aux 2 premières questions:

part(a, pa1, pointmin(pa1x1, pa1y1, pa1z1), pointmax(pa1x2, pa1y2, pa1z2)).
part(a, pa2, pointmin(pa2x1, pa2y1, pa2z1), pointmax(pa2x2, pa2y2, pa2z2)).
part(b, pb1, pointmin(pb1x1, pb1y1, pb1z1), pointmax(pb1x2, pb1y2, pb1z2)).

assemblage([a, b]).

existe(X) :- assemblage(L), membre(X, L).

auDessus(A, B) :- 
  part(A, PA, pointmin(Axmin, Aymin, Azmin), pointmax(Axmax, Aymax, Azmax)),
  part(B, PB, pointmin(Bxmin, Bymin, Bzmin), pointmax(Bxmax, Bymax, Bzmax)),
  A\=B, existe(A), existe(B),
  Axmin < Bxmax,
  Bxmin < Axmax,
  Aymin < Bymax,
  Bymin < Aymax,
  Bzmax =< Azmin.

Et un assemblage cadeau pour jouer avec et tenter de le désassembler:

part(a,pa1,pointmin(0,0,0),pointmax(1,1,1)).
part(a,pa2,pointmin(0,0,1),pointmax(1,1,2)).
part(b,pb1,pointmin(1,1,0),pointmax(2,2,1)).
part(c,pc1,pointmin(1,0,0),pointmax(2,1,1)).
part(d,pd1,pointmin(3,1,0),pointmax(4,2,1)).
part(d,pd2,pointmin(4,1,0),pointmax(5,2,1)).
part(e,pe1,pointmin(5,1,0),pointmax(6,2,1)).
part(e,pe2,pointmin(5,0,0),pointmax(6,1,1)).
part(e,pe3,pointmin(5,0,1),pointmax(6,1,2)).
part(f,pf1,pointmin(0,2,0),pointmax(1,3,1)).
part(f,pf2,pointmin(1,2,0),pointmax(2,3,1)).
part(f,pf3,pointmin(2,2,0),pointmax(3,3,1)).

assemblage([a,b,c,d,e,f]).

Amusez-vous bien

bluestorm

26 juillet 2010 à 8:24:40

Citation : Cyprien_

Citation : bluestorm

Je trouve plus amusant de recoder soit-même avec un encodage plus respectueux des aspects logique (mais moins performant).

Dans ce cas précis, tu recoderais ça comment ?

Il s'agit d'utiliser des entiers logiques plutôt que des entiers machines. Tout encodage sous forme d'une structure de donnée supportant l'unification conviendrait, j'en utilise un particulièrement simple, et qui fera plaisir au prépiste qui sommeille en toi :

isnat(z).
isnat(s(N)) :- isnat(N).

less(z, N).
less(s(M), s(N)) :- less(M, N).

Ensuite c'est facile :

mem(H, [H|_]).
mem(X, [_|T]) :- mem(X, T).

greater(_, []).
greater(X, [H|T]) :- less(H, X), greater(X, T).

J'ai trois versions de "max". Elles fonctionnent toutes dans le sens max(X, [z, s(z), s(s(z))]), mais leur comportement sur max(s(s(z)), L) est intéressant.

max1(X, L) :- greater(X,L), mem(X, L).

?- max1(s(s(z)), L).
Action (h for help) ? abort
% Execution Aborted

(Boucle à l'infini)

max2(X, L) :- mem(X, L), greater(X,L).

?- max2(s(s(z)), L).
L = [s(s(z))] ;
L = [s(s(z)), z] ;
L = [s(s(z)), z, z] ;
L = [s(s(z)), z, z, z] ;
L = [s(s(z)), z, z, z, z] ...

greater2(_, []).
greater2(X, [H|T]) :- greater2(X, T), less(H, X).
max3(X, L) :- mem(X, L), greater2(X,L).

?- max3(s(s(z)), L).
L = [s(s(z))] ;
L = [s(s(z)), z] ;
L = [s(s(z)), s(z)] ;
L = [s(s(z)), s(s(z))] ;
L = [s(s(z)), z, z] ;
L = [s(s(z)), s(z), z] ;
L = [s(s(z)), s(s(z)), z] ;
L = [s(s(z)), z, s(z)] ;
L = [s(s(z)), s(z), s(z)] ;
L = [s(s(z)), s(s(z)), s(z)] ...

Je n'ai pas encore vraiment réfléchi à pourquoi ces fonctions se comportent comme cela; il faudrait dessiner l'arbre de résolution, mais je n'ai pas beaucoup de temps en ce moment.

Einstein++

26 juillet 2010 à 8:42:57

Le langage est très intéressant, merci pour cet atelier.
Voici mon tri insertion :

insert(X, [], [X|[]]).
insert(X, [H|T], [X|[H|T]]) :- X =< H.
insert(X, [H|T], [H|Z]) :- insert(X, T, Z).

isort([], []).
isort([H|T], L) :- isort(T, Y), insert(H, Y, L).

exemple :

?- isort([5], L).
L = [5] .

?- isort([5, 4, 2, 3, 1, 5, 0], L).
L = [0, 1, 2, 3, 4, 5, 5] .

Cygal

26 juillet 2010 à 9:31:35

Citation : nax

Mais par contre j'ai un warning que je ne comprend pas bien :
Citation

Clauses of find/2 are not together in the source-file

Ça veut dire que deux clauses d'une même fonction ne se suivent pas, par exemple si tu as laissé un "find" d'arité 2 traîner ailleurs dans ton fichier.

Anonyme

26 juillet 2010 à 10:17:55

J'ai dessiné la trace lors de l'appel de ta première fonction de maximum, bluestorm, et en fait, tout simplement, Prolog va d'abord tester toutes les possibilités avec des listes ne contenant que zéro, parce que zéro est inférieur à s(s(s(z))).
Tu peux le mettre en évidence par :

?- greater(s(s(s(z))), L).
L = [] ;
L = [z] ;
L = [z, z] ;
L = [z, z, z] ;
...

EDIT : à noter que selon ce qu'on veut faire, certaines versions sont meilleures :

max1, ou bien max4 obtenu en inversant les prédicats mem et greater dans max3, bouclent à l'infini après la première solution.
Et max>4 est le "meilleur" si on veut obtenir toutes les listes dont N est le maximum : avec max3 on n'obtient pas toutes les permutations (ou plutôt on les obtiendra quand on aura fait toutes les listes commençant par N, donc jamais

).

EDIT² : je me suis un peu intéressé à la possibilité de faire des AST, déjà simplement pour des expressions numériques.
Le code que je montre s'appuie sur les entiers naturels redéfinis par bluestorm (et n'a que 2 opérations), mais avec des entiers naturels ça marche aussi bien, le seul souci étant de différencier une valeur numérique d'un arbre...

isNat(z).
isNat(s(N)) :- isNat(N).

op(+).
op(*).

add(N, z, N).
add(N, s(X), s(Y)) :- add(N, X, Y).

mul(_, z, z).
mul(N, s(X), Y) :- add(N, Z, Y), mul(N, X, Z), !.

eval_op(A, +, B, X) :- add(A, B, X).
eval_op(A, *, B, X) :- mul(A, B, X).

ast(N) :- isNat(N).
ast((A, OP, B)) :- ast(A), ast(B), op(OP).

eval(N, N) :- isNat(N).
eval((A, OP, B), X) :-
    ast((A, OP, B)),
    eval(A, N),
    eval(B, M),
    eval_op(N, OP, M, X).

Exemple :

?-  eval(((s(z), +, s(s(z))), *, s(s(z))), N).
N = s(s(s(s(s(s(z)))))) ;
false.

Pour le fun, j'ai essayé de demander ceci à Prolog :

?- eval(A, s(s(z))).
A = s(s(z)) ;
A = (z, (+), s(s(z))) ;
(boucle infinie...)

Dommage que ça ne marche pas, quelqu'un saurait coder tout ça de meilleure manière, pour que Prolog arrive à répondre ?

EDIT³: pour plus de commodité lors de l'entrée :

toNat(0, z).
toNat(X, s(N)) :- X > 0, Y is X-1, toNat(Y, N).

L'opération inverse ne marche pas par contre (ie. revenir à des valeurs numériques) :

toNat(1, U), toNat(2, D), toNat(3, T), eval(((U,+,D),*,T), X).
U = s(z),
D = s(s(z)),
T = s(s(s(z))),
X = s(s(s(s(s(s(s(s(s(z)))))))))

EMC1

26 juillet 2010 à 12:23:18

bluestorm :

Tu peux utiliser le très utile prédicat trace pour suivre la résolution :

2 ?- 
|    trace.
Unknown message: query(yes)
[trace] 2 ?- max3(s(s(z)), L).
   Call: (7) max3(s(s(z)), _G3167) ? creep
   Call: (8) mem(s(s(z)), _G3167) ? creep
   Exit: (8) mem(s(s(z)), [s(s(z))|_G3236]) ? creep
   Call: (8) greater2(s(s(z)), [s(s(z))|_G3236]) ? creep
   Call: (9) greater2(s(s(z)), _G3236) ? creep
   Exit: (9) greater2(s(s(z)), []) ? creep
   Call: (9) less(s(s(z)), s(s(z))) ? creep
   Call: (10) less(s(z), s(z)) ? creep
   Call: (11) less(z, z) ? creep
   Exit: (11) less(z, z) ? creep
   Exit: (10) less(s(z), s(z)) ? creep
   Exit: (9) less(s(s(z)), s(s(z))) ? creep
   Exit: (8) greater2(s(s(z)), [s(s(z))]) ? creep
   Exit: (7) max3(s(s(z)), [s(s(z))]) ? creep
L = [s(s(z))]

Cyprien_ :

Pour revenir à des valeurs numériques :

natTo(0,z).
natTo(X,s(L)):- natTo(Y,L), X is Y+1.

Orwell

26 juillet 2010 à 13:42:21

Je ne comprends pas trop ce que vous essayez de faire avec des requêtes comme celles-ci:

Citation : bluestorm

J'ai trois versions de "max". Elles fonctionnent toutes dans le sens max(X, [z, s(z), s(s(z))]), mais leur comportement sur max(s(s(z)), L) est intéressant.
max1(X, L) :- greater(X,L), mem(X, L).

?- max1(s(s(z)), L).
Action (h for help) ? abort
% Execution Aborted
(Boucle à l'infini)

Citation : Cyprien_

Pour le fun, j'ai essayé de demander ceci à Prolog :
?- eval(A, s(s(z))).
A = s(s(z)) ;
A = (z, (+), s(s(z))) ;
(boucle infinie...)
Dommage que ça ne marche pas, quelqu'un saurait coder tout ça de meilleure manière, pour que Prolog arrive à répondre ?

Dans le premier cas, la question posée à Prolog est "donne-moi toutes les listes possibles dont s(s(z)) est le maximum", et dans le second: "donne-moi tous les arbres possibles ayant s(s(z) comme évaluation". C'était juste pour voir que oui, Prolog donne une infinité de résultats, ou vous vous attendiez à autre chose? :euh:

Anonyme

26 juillet 2010 à 13:45:37

Non, l'intérêt aurait été que Prolog arrive effectivement à donner des résultats. Dans les deux exemples que tu as cités, "boucle infinie" signifie que Prolog tourne indéfiniment, sans donner de nouveaux résultats.

Dans le cas de max, en utilisant max4 (voir mon post précédent), Prolog arrive au contraire à générer une infinité de listes qui conviennent (et à chaque fois qu'on demande un résultat de plus, Prolog arrive à en donner un).
Et je me demandais s'il serait possible de faire pareil pour les arbres syntaxiques : programmer de tel sorte que Prolog puisse générer à volonté des arbres qui conviennent.

neo2500

26 juillet 2010 à 14:10:24

Bonjour,

Je commance à faire moi aussi mes tests, mais je vois que vous étes plus rapide que moi...
Je vais essayer un résolveur de sudoku (cf le lien du début de topic).

Orwell

26 juillet 2010 à 14:12:23

OK, je comprends mieux

A priori oui, c'est possible, mais ça dépend de l'ordre de définition des clauses et des prédicats qui les composent; Prolog va soit construire d'abord les solutions les plus complexes (-> boucle infinie), soit les plus simples (longue liste de solutions de complexité croissante).

bluestorm

26 juillet 2010 à 22:23:44

Citation : Cyprien_

EDIT² : je me suis un peu intéressé à la possibilité de faire des AST, déjà simplement pour des expressions numériques.
Le code que je montre s'appuie sur les entiers naturels redéfinis par bluestorm (et n'a que 2 opérations), mais avec des entiers naturels ça marche aussi bien, le seul souci étant de différencier une valeur numérique d'un arbre...
isNat(z).
isNat(s(N)) :- isNat(N).

op(+).
op(*).

add(N, z, N).
add(N, s(X), s(Y)) :- add(N, X, Y).

mul(_, z, z).
mul(N, s(X), Y) :- add(N, Z, Y), mul(N, X, Z), !.

eval_op(A, +, B, X) :- add(A, B, X).
eval_op(A, *, B, X) :- mul(A, B, X).

ast(N) :- isNat(N).
ast((A, OP, B)) :- ast(A), ast(B), op(OP).

Je n'aime pas la manière dont tu fais. Tu utilises le fait qu'il est possible de différencier les cas en inspectant les valeurs. En pratique, la vérification isNat étant linéaire, tu as des coûts de performance.

Comme pour un langage fonctionnel, la bonne solution me semble ici de faire une somme disjointe. On peut utiliser pour cela des symboles "nat" et "op" par exemple.

is_nat(z).
is_nat(s(N)) :- is_nat(N).

is_op(+).
is_op(*).

add(N, z, N).
add(N, s(X), s(Y)) :- add(N, X, Y).

mul(_, z, z).
mul(N, s(X), Y) :- add(N, Z, Y), mul(N, X, Z), !.

eval_op(A, +, B, X) :- add(A, B, X).
eval_op(A, *, B, X) :- mul(A, B, X).

is_ast(nat(N)) :- is_nat(N).
is_ast(op(A, OP, B)) :- ast(A), ast(B), is_op(OP).

eval(nat(N), N).
eval(op(A, OP, B), X) :-
    eval(A, M),
    eval(B, N),
    eval_op(M, OP, N, X).

PS : si vous vous sentez de vous lancer dans un sous-projet un peu consistant pour l'atelier (non parce que là, hier soir je faisais gentiment des listes, aujourd'hui on fait des ASTs, demain on code un évaluateur lisp et après-demain un compilateur Haskell98 ?), n'hésitez pas à ouvrir un topic à part en mettant le tag [Atelier Prolog] dans le titre, et postant ici un petit message pour donner le lien.

Anonyme

26 juillet 2010 à 22:33:27

Non seulement ton code est effectivement plus propre, mais en plus il répond à ma question précédente : cette fois, Prolog arrive sans soucis à générer des arbres dont le résultat est celui demandé :

?- eval(A, s(s(z))).
A = nat(s(s(z))) ;
A = op(nat(s(s(z))), +, nat(z)) ;
A = op(nat(s(z)), +, nat(s(z))) ;
A = op(nat(z), +, nat(s(s(z)))) ;
A = op(nat(s(s(z))), *, nat(s(z))) ;
A = op(nat(s(s(z))), +, op(nat(z), +, nat(z))) ;
...

Il n'y avait donc pas que des problèmes de performance, mais aussi de conception visiblement.

bluestorm

26 juillet 2010 à 23:29:02

int_to_nat(0, z).
int_to_nat(X, s(N)) :- X > 0, Y is X-1, int_to_nat(Y, N).

nat_to_int(z, 0).
nat_to_int(s(N), X):- nat_to_int(N, Y), X is Y+1.

En ayant envie de faire la conversion nat<->int en profondeur dans les arbres, je me suis rendu compte qu'on voulait une fonction 'map' et que je ne savais pas faire d'ordre supérieur en Prolog.

map_ast(F, nat(N), R) :- apply(F, [nat(N), R]).
map_ast(F, op(A, OP, B), R) :-
        map_ast(F, A, A2),
        map_ast(F, B, B2),
        apply(F, [op(A2, OP, B2), R]).

on_leaf(F, nat(N), nat(R)) :- apply(F, [N, R]).
on_leaf(F, op(A, OP, B), op(A, OP, B)).

Exemples :

?- T = op(nat(2), +, nat(3)), map_ast(on_leaf(int_to_nat), T, T2), eval(T2, T3), nat_to_int(T3, R).
T = op(nat(2), +, nat(3)),
T2 = op(nat(s(s(z))), +, nat(s(s(s(z))))),
T3 = s(s(s(s(s(z))))),
R = 5 .

?- N = 4, int_to_nat(N, N2), eval(T, N2), map_ast(on_leaf(nat_to_int), T, R).
N = 4,
N2 = s(s(s(s(z)))),
T = nat(s(s(s(s(z))))),
R = nat(4) ;
N = 4,
N2 = s(s(s(s(z)))),
T = op(nat(s(s(s(s(z))))), +, nat(z)),
R = op(nat(4), +, nat(0)) ;
N = 4,
N2 = s(s(s(s(z)))),
T = op(nat(s(s(s(z)))), +, nat(s(z))),
R = op(nat(3), +, nat(1)) ;
N = 4,
N2 = s(s(s(s(z)))),
T = op(nat(s(s(z))), +, nat(s(s(z)))),
R = op(nat(2), +, nat(2)) ...

PS : dans ces exemples, j'ai une tripotée de variables intermédiaires (T2, T3, N2..) dans les tests. Comment ne pas afficher leur valeur ?

1 2 3 >>

[Atelier] Prolog

Essayez un langage totalement différent !

Qu'est-ce que Prolog ?

Que faire pour cet atelier ?

Liens utiles

Listes en prolog

Quelques exemples de fonctions sur les listes

Supprimer

Modérer

Signaler le message aux modérateurs