Prolog Language
Monotonicité

Raisonnement sur les prédicats monotones

Les prédicats monotones peuvent être débogués en appliquant un raisonnement déclaratif .

En pur Prolog, une erreur de programmation peut entraîner l'un ou l'autre des phénomènes suivants:

1. le prédicat réussit incorrectement dans un cas où il devrait échouer
2. le prédicat échoue incorrectement dans un cas où il devrait réussir
3. le prédicat boucle inopinément là où il ne devrait produire qu'un ensemble fini de réponses.

À titre d'exemple, considérons comment nous pouvons déboguer la casse (2) par un raisonnement déclaratif: nous pouvons systématiquement supprimer les objectifs des clauses du prédicat et voir si la requête échoue toujours . En code monotone, la suppression des objectifs peut tout au plus rendre le programme résultant plus général . Par conséquent, nous pouvons identifier les erreurs en voyant lequel des objectifs conduit à l'échec inattendu.

Exemples de prédicats monotones

Voici des exemples de prédicats monotones :

• unification avec (=)/2 ou unify_with_occurs_check/2
• dif/2 , exprimant le déséquilibre des termes
• Les contraintes CLP (FD) aiment (#=)/2 et (#>)/2 , en utilisant un mode d’exécution monotone.

Les prédicats Prolog qui utilisent uniquement des objectifs monotones sont eux-mêmes monotones.

Les prédicats monotoniques permettent un raisonnement déclaratif:

1. L'ajout d'une contrainte (c.-à-d. Un objectif) à une requête peut tout au plus réduire , jamais étendre, l'ensemble des solutions.
2. La suppression d'un objectif de tels prédicats peut au maximum prolonger , jamais réduire, l'ensemble des solutions.

Prédicats non monotones

Voici des exemples de prédicats qui ne sont pas monotones:

• des prédicats méta-logiques tels que var/1 , integer/1 etc.
• les prédicats de comparaison de termes comme (@<)/2 et (@>=)/2
• les prédicats qui utilisent !/0 , (\+)/1 et d'autres constructions qui rompent la monotonie
• prédicats tout-solutions comme findall/3 et setof/3 .

Si ces prédicats sont utilisés, l’ ajout d’ objectifs peut conduire à plus de solutions, ce qui va à l’encontre de l’importante propriété déclarative connue de la logique selon laquelle l’ajout de contraintes peut tout au plus réduire , jamais étendre, l’ensemble des solutions.

Par conséquent, d'autres propriétés sur lesquelles nous nous appuyons pour le débogage déclaratif et d'autres raisonnements sont également rompues. Par exemple, les prédicats non monotones brisent la notion fondamentale de commutativité de la conjonction connue de la logique du premier ordre. L'exemple suivant illustre ceci:

?- var(X), X = a.
X = a.

?- X = a, var(X).
false.

Toutes les solutions-prédicats comme findall/3 briserai monotonicité: Ajout des clauses peut conduire à l'échec des objectifs qui avaient eu lieu auparavant. Cela va également à l'encontre de la montonicité telle qu'elle est connue par la logique du premier ordre, où l' ajout de faits peut tout au plus augmenter , sans jamais réduire l'ensemble des conséquences.

Alternatives monotones pour les constructions non monotones

Voici des exemples d'utilisation de prédicats monotones au lieu de constructions impures et non monotones dans vos programmes:

• dif/2 est destiné à être utilisé à la place de constructions non monotones comme (\=)/2
• les contraintes arithmétiques (CLP (FD), CLP (Q) et autres) sont destinées à être utilisées à la place des prédicats arithmétiques modulés
• !/0 conduit presque toujours à des programmes non monotones et devrait être complètement évité .
• Les erreurs d'instanciation peuvent être commises dans des situations où vous ne pouvez pas prendre une décision éclairée à ce stade.

Combiner la monotonie à l'efficacité

On prétend parfois que, pour des raisons d'efficacité, nous devons accepter l'utilisation de constructions non monotones dans les programmes Prolog du monde réel.

Il n'y a aucune preuve à ce sujet. Des recherches récentes indiquent que le sous-ensemble purement monotone de Prolog peut non seulement suffire à exprimer la plupart des programmes du monde réel, mais aussi à être efficace dans la pratique. Une construction récemment découverte et encourageant cette vue est if_/3 : elle combine la monotonie avec une réduction des points de choix. Voir Indexation dif / 2 .

Par exemple, code du formulaire:

pred(L, Ls) :-
    condition(L),
    then(Ls).
pred(L, Ls) :-
    \+ condition(L),
    else(Ls).

Peut être écrit avec if_/3 comme:

pred(L, Ls) :-
    if_(condition(L),
        then(Ls),
        else(Ls)).

et combine la monotonie avec le déterminisme.