Discussion :

[prologO]

bonjour à tout et à tous
je cherche comment programmer cette fonction en prolog ?
La fonction d'Ackermann est définie récursivement comme suit :



Merci.

[Eusebius]

Peut-être que tu pourrais nous montrer ce que tu as déjà fait, et où tu bloques ?

[pcaboche]

Je dirais de faire un truc comme ça (traduction litérale):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ackermann(0, N, A) :-
  !,
  A is N+1.
 
 
ackermann(M, 0, A) :-
  M>0,
  !,
  M1 is M-1,
  ackermann(M1, 1, A).
 
 
ackermann(M, N, A) :-
  M>0,
  N>0,
  !,
  M1 is M-1,
  N1 is N-1,
  ackermann(M, N1, T),
  ackermann(M1, T, A).

[Eusebius]

Sinon, je dirais de faire un truc comme ça (traduction litérale):

Ya pas besoin de cut.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
ackermann(0, N, A) :-
	A is N+1.
ackermann(M, 0, A) :-
	M > 0,
	M2 is M-1,
	ackermann(M2, 1, A).
ackermann(M, N, A) :-
	M > 0, N > 0,
	M2 is M-1,
	N2 is N-1,
	ackermann(M, N2, A1),
	ackermann(M2, A1, A).

Je voulais pas cracher la solution...

[pcaboche]

Ya pas besoin de cut.

Je sais, c'est juste pour éviter d'avoir à évaluer des clauses qui seront fausses de toutes façons (ça optimise un peu). Et puis, ça facilite un peu la lecture (avant le cut -> les tests conditionnels, après le cut -> les calculs).

Je voulais pas cracher la solution...

Oui, je sais, mais quand quelqu'un bute sur quelque chose d'aussi simple, plusieurs possibilités:

1. il ne comprend pas le principe alors on donne un exemple propre pour aider, mais la lecture de l'exemple l'obligera à lire les tutos disponibles
2. c'est un paresseux qui veut qu'on fasse ses devoirs à sa place et dans ce cas là, on sévit assez rapidement en cas de récidive

S'il se trouve dans le premier cas, pas de problème, on donne un petit coup de pouce. S'il se trouve dans le deuxième cas, le jour où il se retrouvera avec un problème épineux à résoudre, on lui dira bien gentiment qu'on n'est pas là pour faire son boulot, qu'il n'a qu'à lire les tutos et on le laissera avec son problème.

[Eusebius]

Je sais, c'est juste pour éviter d'avoir à évaluer des clauses qui seront fausses de toutes façons (ça optimise un peu). Et puis, ça facilite un peu la lecture (avant le cut -> les tests conditionnels, après le cut -> les calculs).

Mauvaise idée de faire mettre des cut partout à un débutant, on perd en lisibilité, et on risque de perdre en complétude un jour ou l'autre. Je pense que c'est une meilleure méthode d'apprendre à partitionner tous les cas, quand on peut.

Oui, je sais, mais quand quelqu'un bute sur quelque chose d'aussi simple, plusieurs possibilités:

1. il ne comprend pas le principe alors on donne un exemple propre pour aider, mais la lecture de l'exemple l'obligera à lire les tutos disponibles
2. c'est un paresseux qui veut qu'on fasse ses devoirs à sa place et dans ce cas là, on sévit assez rapidement en cas de récidive

S'il se trouve dans le premier cas, pas de problème, on donne un petit coup de pouce. S'il se trouve dans le deuxième cas, le jour où il se retrouvera avec un problème épineux à résoudre, on lui dira bien gentiment qu'on n'est pas là pour faire son boulot, qu'il n'a qu'à lire les tutos et on le laissera avec son problème.

On n'a pas les mêmes méthodes, chacun son truc

[Eusebius]

Je sais, c'est juste pour éviter d'avoir à évaluer des clauses qui seront fausses de toutes façons (ça optimise un peu). Et puis, ça facilite un peu la lecture (avant le cut -> les tests conditionnels, après le cut -> les calculs).

PS que tu optimises ou pas, la fonction d'ackermann, elle partira vite dans les choux...

[pcaboche]

Mauvaise idée de faire mettre des cut partout à un débutant, on perd en lisibilité, et on risque de perdre en complétude un jour ou l'autre.

Si on lit mes tutos et qu'on applique les patterns de programmation, on se retrouve avec les règles:

1. "si un prédicat retourne au maximum une solution, alors mettre des cut dans chaque clause"
2. "si un prédicat peut retourner plusieurs solutions, ne pas mettre de cut du tout" (enfin, en théorie...)

Ca dépend des méthodes d'apprentissage.

Le mieux selon moi est de montrer plusieurs points de vue différents, de les comparer, de montrer l'intérêt de chacun, etc.

PS que tu optimises ou pas, la fonction d'ackermann, elle partira vite dans les choux...

C'est clair... Je n'avais pas du tout regardé ce qu'elle faisait en fait, j'ai juste traduit "bêtement" l'énoncé (parce que c'est ce qui était demandé).

[Eusebius]

Ca dépend des méthodes d'apprentissage.

Oui, je suis d'accord, et je respecte la tienne. La mienne c'est de partir de la logique pour faire de la programmation logique, pour ensuite expliquer la SLD-résolution et l'arbre d'interprétation. Et comme la coupure n'a pas de sens en logique et brise la SLD-résolution, ma philosophie est qu'il faut la réserver aux cas exceptionnels et réfléchis, et ne pas en faire une utilisation systématique.

Ceci dit j'ai lu attentivement, avec bénéfice et intérêt ton article sur les patterns. Mais je ne l'utilise pas en enseignement.

[prologO]

bonjour à tout et à tous
mercie pour tous le monde pour l'algorithme

[Eusebius]

bonjour à tout et à tous
mercie pour tous le monde pour l'algorithme

N'oublie pas de cliquer sur "résolu"

[pcaboche]

La mienne c'est de partir de la logique pour faire de la programmation logique, pour ensuite expliquer la SLD-résolution et l'arbre d'interprétation.

C'est tout à fait cohérent et je respecte cette méthode d'aprentissage.

Ce qui pourrait être intéressant, ce serait d'avoir plusieurs cours d'introduction à Prolog, avec différentes méthodes et points de vues (logique, patterns, algèbre relationnelle, TP pas à pas...) et de faire une sorte de "sommaire" expliquant les différentes méthodes avec des liens sur les documents correspondant.

Par extension, on peut avoir une sorte de "guide de lecture" qui permettrait au débutant de savoir quel document lire et dans quel ordre (avec en plus une sorte de graphique).

[Boubou Balrog]

J'ai jeté un oeil à votre débat et j'ai une ou deux p'tites questions... je peux ?

- ça signifie quoi 'perdre en complétude' ?
- les cut sont-ils parfois nécessaires quand même ? Genre, si tu les mets pas, le code ne fonctionnera pas.
- Si on écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Ackermann(0,M,A) :-
               ....

C'est équivant à ça ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Ackermann(N,M,A) :-
               N==0,...

[pcaboche]

je peux ?

Je sais pas... non je rigole, tu peux.

- ça signifie quoi 'perdre en complétude' ?

Si tu utilises des cut, tu n'examines pas toutes les clauses, donc tu "perds en complétude".

- les cut sont-ils parfois nécessaires quand même ?

Certains fanatiques de Prolog te diront que les cut c'est pas bien, c'est le mal absolu, qu'il ne faut surtout pas les utiliser, etc. C'est un point de vue.

Dans la pratique, les cut permettent de supprimer certains points de choix, donc d'éviter les retours sur traces. Si on n'a pas besoin d'effectuer de retour sur trace, cela veut dire que l'on n'a pas besoin de sauvegarder l'état du programme avant retour sur trace, donc cela économise de la mémoire, donc cela évite les dépassements de capacité de la pile (synonyme de plantage).

Genre, si tu les mets pas, le code ne fonctionnera pas.

Ben euh... si tu enlèves les cut d'un programme qui en a besoin, c'est sûr que ça marchera tout de suite moins bien...

Si on écrit :
(...)
C'est équivant à ça ?

Non, c'est équivalent à ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
ackermann(N,M,A) :-
               N = 0,...

La différence entre '=' et '==' ? '==' fait un test d'égalité alors que '=' essaye d'unifier. Le comportement sera différent si l'une des deux opérandes est libre (non unifiée),

Pour plus d'infos ->

[pcaboche]

Dans la pratique, les cut permettent de supprimer certains points de choix, donc d'éviter les retours sur traces. Si on n'a pas besoin d'effectuer de retour sur trace, cela veut dire que l'on n'a pas besoin de sauvegarder l'état du programme avant retour sur trace, donc cela économise de la mémoire, donc cela évite les dépassements de capacité de la pile (synonyme de plantage).

Typiquement, dans le problème qui nous préoccupe (Ackermann), on sait que l'on aura au maximum 1 solution, donc il n'est pas nécessaire de garder des points de choix pour faire des retours sur trace. C'est pour cela qu'on utilise des cut (cela n'enlève rien à la complexité de l'algo mais ça évite de surcharger la pile).