J'essaie de comprendre pourquoi les implémentations de prologs ne se comportent pas selon le modèle d'exécution dans les manuels de manuels - par exemple, celui du livre par Sterling et Shapiro's "The Art of Prolog" (Chapitre 6, "Pure Prolog", Section 6.1, "Le modèle d'exécution de Prolog").
Le modèle d'exécution à laquelle je me réfère est celui-ci (page 93 de Sterling & Shapiro):
Entrée: Un objectif G et un programme P
sortie: une instance de G qui est une conséquence logique de P, ou non sinon
algorithme: En outre (Page 120 du même livre), Prolog choisit les objectifs ( Le programme ci-dessous a une définition de si j'essaie de prouver résolvant: correspondance d'unification résolvant: Unification correspond à nouveau résolvant: correspondance d'unification résolvant: et " alors puis-je supposer que le modèle d'exécution dans les manuels de manuels n'est pas précisément ce que Prolog utilise? Choisissez l'objectif A ) dans l'ordre de gauche à droite et recherchées des clauses ( Choisissez la clause renommée. .. ) Dans la commande qu'ils apparaissent dans le programme. non (appelé n le programme) et un seul fait. n (n (f (x))) , il réussit (selon à deux manuels et également sur Swi Prolog, Gnu Prolog et Yap). Mais n'est-ce pas un peu étrange? Selon ce modèle d'exécution, que plusieurs livres exposent, c'est ce à quoi je m'attendrais d'arriver (sauter le renommage des variables pour garder les choses simples, car il n'y aurait pas de conflit de toute façon):
n (n (f (z)))
x en première clause avec n (f (z)) et remplace l'objectif avec la queue de cette clause.
n (f (z)) ,!, échouez .
x dans la première clause avec f (z) et remplace le premier objectif dans le résolvant avec la queue de la clause
f (z),!, échouez,!, échouez .
f (z) -> succès! Maintenant, cela est éliminé du résolvant.
!, Échec,!, échec .
!, échouer ,!, échouer " devrait pas réussir! Après la coupe, il y a un échec. Fin de l'histoire. (Et en effet, entrant !, échouer,!, Échoue comme une requête échouera dans tous les systèmes Prolog que j'ai accès à). N (X): - Appelez (x) ,! / code > Ne fait aucune différence dans tous les prologiques que j'ai essayés.
6 Réponses :
Vous avez un niveau supplémentaire de nidification dans votre objectif de test: au lieu de: et en effet, si nous essayons Cela fonctionne comme prévu: Donc, votre compréhension de Prolog est correcte, votre cas de test n'était pas! Mise à jour montrant les effets des négations de négations:
Je comprends que si j'appelle des objectifs de tout ce qui fonctionne, tout fonctionne, mais le modèle d'exécution présenté dans des livres ne fonctionne pas de manière récursive. C'est itératif (et n'utilise pas de piles). Les nouveaux objectifs sont simplement annexés au résolvant et si je suis ce modèle, la requête doit être échouée (elle ne le fait pas).
Je ne sais pas ce que tu veux dire sur la récursion vs itération. La résolution est un algorithme récursif. La raison pour laquelle vous n'obtenez pas la réponse que vous attendez est parce que vous négociez la négation à chaque fois que vous ajoutez un N () supplémentaire terme. J'ai mis à jour ma réponse pour montrer ce problème.
Je veux dire que "appel (x)" est un appel récursif au moteur Prolog. Sinon, alors il suffirait d'ajouter X au résolvant - puis n (n (f (a))) échouerait.
Votre programme n'est pas un programme PURE PRAGolog, car il contient un! / 0 en N / 1. Vous pouvez vous poser la question plus simple: avec vos définitions, pourquoi la requête ? - n (f (x))). échoue bien qu'il y ait une faite n (x ) Dans votre programme, ce qui signifie que n (x) est vrai pour chaque x et devrait donc tenir notamment pour f (x) aussi? En effet, les clauses du programme ne peuvent plus être considérées comme isolées en raison de l'utilisation de l'utilisation! / 0, et le modèle d'exécution pour Pure Prolog ne peut pas être utilisé. Une alternative plus moderne et pure pour de tels prédicats impuraux est souvent des contraintes, par exemple DIF / 2, avec laquelle vous pouvez contraindre une variable à être distincte d'un terme.
tandis que le tapis est juste en ce que votre programme n'est pas pur PRAGolog (et cela est pertinent car le titre du chapitre est pur PRAGolog), non seulement depuis que vous utilisez une coupe, mais aussi depuis que vous écrivez des prédicats qui gèrent d'autres prédicats (pure PRAGolog est un sous-ensemble de la logique de premier ordre) Ce n'est pas le problème principal; Vous êtes simplement manquant de retour en arrière
Pendant que vous avez effectivement une coupure, cela ne sera pas atteint avant que le but n (f (x)) réussisse. Cependant, comme vous le savez, cela échouera et par conséquent, Prolog sera en arrière et correspondra à la deuxième clause.
Je ne vois pas comment cela contredirait avec le modèle décrit dans 6,1 (et aurait du mal à croire que d'autres livres décriraient un modèle dans lequel l'exécution continuerait après avoir échoué et permettrait ainsi la coupe de tailler les autres solutions ). En tout état de cause, je constate que je constate que la conclusion selon laquelle "les implémentations de PROLO ne se comportent pas conformément au modèle d'exécution dans les manuels" est assez similaire à "Il existe un bogue au compilateur", d'autant plus que le "contre-exemple" se comporte comme il ne devrait (pas (non (vrai)) devrait être vrai)
Je ne veux certainement pas dire que les implémentations ne se comportent pas correctement. J'essaie effectivement de comprendre pourquoi les livres ne décrivaient pas le modèle d'exécution plus précisément. Je sais aussi, intuarité, que N (f (a)) échouera et que Prolog sera en arrière. Toutefois, cela ne correspond pas au modèle d'exécution, à Chich "appel (x)" n'est pas un appel récursif à l'interprète. Je suppose que cela "appeler (x)" n'est pas pure prologique, et c'est pourquoi N (N (F (a)))) réussit.
Lorsque vous atteignez la dernière étape:
Le Vous ne pouvez pas bien placer une coupe puis-je supposer que le modèle d'exécution dans les manuels de manuels n'est pas précisément ce que Prolog utilise?
Oui Bien sûr, les vrais prologs ont Coupe ! ici signifie "Effacer tout". Donc, le résolvant devient vide. (Ceci semble bien sûr, mais il est assez proche). Les coupes n'ont aucune signification du tout ici, le premier échoue indique de retourner la décision et 2e échoue pour le retourner. Maintenant, résolvant est vide - la décision était "oui" et reste donc, à deux reprises. (Ceci est aussi le simuler ... Le "retournement" n'a aucun sens en présence de backtracking).
! sur la liste des objectifs dans le résolvant, car ce n'est pas un seul des objectifs à remplir. Il a un sens sensationnel , dit normalement "Arrêtez d'essayer d'autres choix", mais cet interprète conserve no piste aucun choix (it "comme si "Faites tous les choix à la fois). échoue n'est pas qu'un objectif de remplir aussi, il est écrit "où vous avez réussi à dire que vous n'avez pas , et vice versa ".
couper et échec contrairement à l'interprète abstrait que vous avez mentionné. Cet interprète n'a pas de backtracking explicite et a plutôt plusieurs succès de Magic (son choix est intrinsèquement non déterministe comme si tous les choix sont fabriqués à Une fois, en parallèle - des prologs réels uniquement émulent que par exécution séquentielle avec une arrière-marche explicite, à quel le coupé se réfère - il n'a tout simplement aucun sens autrement).
Merci d'avoir répondu. Je pensais que ! seulement signifiait "s'engager dans les liaisons déjà dans la substitution actuelle et ne pas revenir en arrière" ... Je ne comprends pas pourquoi le résolveur deviendrait vide.
Par exemple, la coupe ici ne rend pas le résolvant vide: a (x): - écrire ('one'),!, Écrire ('deux'). ------ B (x): - A (x), écrire ('trois'). Cela imprimera en fait "Onetwothree" ("Three" a été imprimé parce que "écriture (" trois ")" n'a pas été retiré du résolvant lorsque la coupe a été trouvée. Je suis toujours un peu confus.
Prenez remarque ce que cet interprète implique. Lorsque vous parlez de "Choisir", il dit "quiconque qui correspond peut être choisi" mais alors, parle de "Et si un autre choix a été fait". Cela signifie qu'une "course" de cet interprète explique un résultat; Mais il est implicié que tous les choix possibles sont fabriqués, et donc tous les résultats possibles sont arrivés à. "Coupe" consiste à réduire le nombre de résultats trouvés. Il dit: "Ne cherchez pas plus de résultats, ce que j'ai pour le moment suffit". Vous ne le mettez pas dans le résolvant, c'est pas un objectif logique à remplir. C'est une commande opérationnelle 2intrptr.
Dans votre exemple avec "Ecrire", vous avez une autre "écriture" après la coupe, vous devez donc l'exécuter aussi. Quand j'ai dit "la coupe ici signifie ..." Ce n'était pas un bon libellé peut-être. La "coupe" et "échec" n'étaient pas là-bas dans la première place à l'intérieur du résolvant, ils étaient comme si des notes attachées à côté de cela. Vous ne pouvez tout simplement pas exécuter ce code de votre part avec cet interprète, il n'a aucun concept de commandes opérationnelles, uniquement d'objectifs logiques. La coupe n'a que la signification lorsque les choix sont explicites, séquentielles. Ici, ils sont implicites, tous faits à la fois, non déterminisciquement, comme en parallèle.
La légende ci-dessous vous dit ce que cet algorithme particulier est sur:
Figure 4.2 B> Un interprète abstrait pour les programmes logiques blockQuote>En outre, sa description se lit comme suit: P>
sortie: b> une instance de g i> une conséquence logique de p i> ou non sinon. BlockQuote>C'est-à-dire que l'algorithme de 4.2 vous montre uniquement comment calculer une conséquence logique pour les programmes logiques. Cela vous donne seulement une idée de la façon dont Prolog fonctionne réellement. Et en particulier ne peut pas expliquer le
! Code>. En outre, l'algorithme de 4.2 ne peut expliquer que sur la manière dont une solution («conséquence») est trouvée, mais Prolog essaie de les trouver de manière systématique appelée backtracking chronologique. La coupe interfère avec l'arrière-marche chronologique de manière très particulière qui ne peut pas être expliquée au niveau de cet algorithme. P>Vous avez écrit: P>
De plus (page 120 du même livre), Prolog choisit des objectifs(Choisissez l'objectif A) code> dans l'ordre de gauche à droite et des clauses(choisissez la clause renommée ...) code > Dans l'ordre dans lequel ils se présentent dans le programme. blockQuote>qui manque un point important que vous pouvez lire à la page 120: p>
Le mécanisme d'exécution de Prolog est obtenu à partir de l'interprète abstraite en choisissant l'objectif le plus à gauche ... et en remplaçant le choix non déterministe d'une clause par recherche séquentielle d'une clause injectable et de retour en arrière b>. blockQuote>Donc c'est ce petit ajout "et en arrière" qui rend les choses plus complexes. Vous ne pouvez pas voir cela dans l'algorithme abstrait. P>
Voici un exemple minuscule pour montrer que la rampe de retour n'est pas explicitement traitée dans l'algorithme. P>
p :- q(X), r(X). q(1). q(2). r(2).
Je pense que vous l'avez presque raison. Le problème est ici:
RESOLVENT: n(_)