Quel est l'arbre SLD pour cette requête?
considérons le programme Prolog suivant (de "L'Art de Prolog"):
natural_number(0).
natural_number(s(X)) :- natural_number(X).
plus(X, 0, X) :- natural_number(X).
plus(X, s(Y), s(Z)) :- plus(X, Y, Z).
et la requête:
?- plus(s(s(s(0))), s(0), Z).
SICStus et SWI produisent la réponse attendue Z = s(s(s(s(0)))) , mais interrogent l'utilisateur pour la réponse suivante (une réponse correcte no / false ). Cependant, je ne peux pas comprendre pourquoi il y a une branche ouverte dans l'arbre SLD après que le seul but soit trouvé. J'ai essayé de déboguer à la fois sous SICStus et sous SWI, mais je Je ne suis pas encore vraiment capable d'interpréter le résultat. Je peux seulement dire que, pour autant que j'ai pu comprendre, les deux Retour à plus(s(s(s(0))), 0, _Z2) . Quelqu'un peut m'aider à comprendre ce comportement?
3 réponses
le problème n'est pas directement lié aux arbres SLD, puisque Prolog les systèmes ne construisent pas d'arbres SLD de manière prospective vous le décrire. Mais quelques optimisations trouvées dans certains Prolog les systèmes ont essentiellement cet effet et de changer la brute aveugle correspondance tête de force. À savoir l'indexation et l'élimination du point de choix.
il y a maintenant une limitation connue de SWI-Prolog. Bien qu'il ne
multi-argument d'indexation, il ne fait pas point de choix élimination
pour les index de non-premier argument indexation en cascade. Moyen
il sélectionne uniquement un argument, mais alors pas plus loin. Il y a quelques
Les systèmes Prolog qui font l'indexation multi-arguments et l'indexation en cascade.
Par exemple dans Jekejeke Prolog nous n'avons pas de faux:
Bye
P. S.: La nouvelle version de Jekejeke Prolog ne littéralement cascade, comme il détecte que le premier indice d'argument n'a pas de sensibilité. Par conséquent, bien qu'il construise l'indice pour le premier argument en raison du motif d'appel réel, il saute le premier indice d'argument et ne l'utilise pas, et utilise uniquement le deuxième argument. Sauter donne un peu de vitesse. :- )
le saut est vu via la commande dump/1
environnement de développement version:
?- dump(plus/3).
-------- plus/3 ---------
length=2
arg=0
=length=2
arg=1
0=length=1
s=length=1
Yes
donc il n'a pas arg=0 et construit un arg=1
index ici, mais construit en parallèle un arg=0 et
un index arg=1 . On pourrait encore appeler cette heuristique en cascade
puisque les requêtes individuelles conduisent à des index multiples, mais ils
n'ont pas vraiment la forme d'une cascade.
de nombreux systèmes Prolog ne sont pas aussi intelligents que nous le pensons. Cela s'explique par plusieurs raisons, notamment par le choix de l'exécuteur. Ce qui semble important pour certains pourrait ne pas l'être pour d'autres.
en conséquence ces points de choix restants peuvent s'accumuler dans le temps et empêcher de libérer des données auxiliaires. Par exemple, lorsque vous souhaitez lire dans une longue liste de texte. Une liste qui est si longue qu'elle ne rentre pas dans la mémoire à la fois, mais peut encore être traitée efficacement avec library(pio) .
si vous attendez exactement une réponse, vous pouvez utiliser call_semidet/1 pour la rendre déterminée.
Voir cette réponse pour sa définition et un cas d'utilisation.
?- plus(s(s(s(0))), s(0), Z). Z = s(s(s(s(0)))) ; false. ?- call_semidet(plus(s(s(s(0))), s(0), Z)). Z = s(s(s(s(0)))).
mais vous pouvez le voir aussi d'un côté plus optimiste: toplevels modernes (comme celui en SWI) ne vous montrer quand il ya des points de choix restants. Vous pouvez donc envisager des contre-mesures comme call_semidet/1 .
voici quelques réponses connexes:
Pour nous, il est évident que les deux clauses sont plus 'isolés'. Nous pouvons dire cela parce que nous savons que 0 \= s(Y) . Mais (je pense) une telle analyse est en général prohibitive, et Prolog considère alors qu'une telle branche doit encore être prouvée: ici une trace montrant que l'appel (7) est encore "ouvert" pour des alternatives après que la première solution ait été trouvée.
