Αποκοπή και Άρνηση

Όπως ήδη έχουμε τονίσει, σε κάθε ερώτηση ο μηχανισμός ελέγχου της Prolog ελέγχει αν αληθεύουν τα γεγονότα (της ερώτησης) από αριστερά προς τα δεξιά. Επίσης, όποτε αποτυγχάνει να ταυτοποιήσει ένα γεγονός οπισθοδρομεί προσπαθώντας να ικανοποιήσει με διαφορετικό τρόπο το αμέσως προηγούμενο γεγονός. Έτσι, ο μηχανισμός ελέγχου της Prolog προκειμένου ν' αποφανθεί αν ισχύει ή όχι ένα γεγονός, διασχίζει κατά βάθος το δένδρο υπολογισμού της ερώτησης για το γεγονός αυτό.

Πολλές φορές όμως μπορεί να μην είναι αναγκαίο ο μηχανισμός ελέγχου να ψάξει σε όλο το χώρο αναζήτησης (δηλαδή σε όλο το δένδρο υπολογισμού) για ν' αποφανθεί αν ένα γεγονός είναι αληθές ή όχι. Στη περίπτωση που γνωρίζουμε που μπορεί να βρίσκεται η λύση ή στην περίπτωση που μας αρκεί να βρούμε μία μόνο λύση, η Prolog μας δίνει την δυνατότητα ν' 'αποκόπτουμε' τις λοιπές λύσεις κάνοντας χρήση της δεσμευμένης λέξης "!" η οποία ονομάζετε αποκοπή (cut). Επίσης, υπάρχουν προβλήματα που είναι αναγκαία η επαναλαμβανόμενη διάσχιση ενός κλάδου μέχρι να ισχύσει μία συνθήκη. Στη περίπτωση αυτή, όπως θα δούμε παρακάτω, κάνοντας χρήση της οπισθοδρόμησης μέσω της δεσμευμένης λέξης fail και της αποκοπής μπορούμε να επαναλάβουμε παραπάνω από μία φορά ένα μέρος κώδικα.

Η αποκοπή (επίδραση αποκοπής στο δένδρο υπολογισμού)

Κάνοντας χρήση της αποκοπής "!" μπορούμε να μειώσουμε τον χώρο αναζήτησης στο δένδρο υπολογισμού μίας ερώτησης, ελέγχοντας τον τρόπο με τον οποίο η Prolog κάνει κατά βάθος αναζήτηση. Πιο συγκεκριμένα με την εντολή αυτή μπορούμε να αποκόψουμε κλάδους του δένδρου ή ακόμα και τμήματα αυτού, δηλώνοντας το πότε επιτρέπεται η οπισθοδρόμηση.

Για παράδειγμα, ας πάρουμε ως γνωστά τα ακόλουθα γεγονότα και κανόνες:

Όπως φαίνεται στο παρακάτω δένδρο υπολογισμού η Prolog δίνει οκτώ απαντήσεις στην ερώτηση ?- r(P,K).

Αν αντικαταστήσουμε τον κανόνα της γραμμής /*6*/ με τον κανόνα

r(X,Y):- b(X), a(X), a(Y),!.

τότε η Prolog θα μας δώσει μία μόνο λύση το ζεύγος {P=1, K=1}. Αυτό συμβαίνει διότι κατά την οπισθοδρόμηση ο μηχανισμός ελέγχου συναντά την αποκοπή και έτσι παραβλέπει όλους τους υπόλοιπους κλάδους του δένδρου. Στο επόμενο σχήμα γίνεται εμφανές το ποιοι κλάδοι παραλείπονται.

Αν αντικαταστήσουμε τον κανόνα της γραμμής /*6*/ με τον κανόνα

r(X,Y):- b(X), a(X),!, a(Y).

τότε η Prolog θα δώσει τρία διαφορετικά ζεύγη τιμών {P=1,K=1; P=1,K=2; P=1,K=5} (ικανοποιώντας τρεις φορές το a(Y)) και μετά θα σταματήσει την οπισθοδρόμηση λόγω της αποκοπής που συναντά. Στη γκρίζα περιοχή του επόμενου σχήματος εμφανίζονται οι κλάδοι που δεν λαμβάνονται υπόψη.

Τέλος, αν αντικαταστήσουμε τον κανόνα της γραμμής /*6*/ με τον κανόνα

r(X,Y):- !, b(X), a(X), a(Y).

τότε η Prolog οπισθοδρομώντας θα δώσει τα ζεύγη τιμών {P=1,K=1; P=1,K=2; P=1,K=5; P=5,K=1; P=5,K=2; P=5,K=5} αλλά όχι αυτά που προκύπτουν από τον κανόνα /*7*/. Στη συγκεκριμένη περίπτωση παραβλέπει τους κλάδους που σκιαγραφούνται στο παρακάτω σχήμα.

Η άρνηση ως αποτυχία

Όπως σε άλλες γλώσσες προγραμματισμού έτσι και στη Prolog είναι πολλές φορές επιθυμητό ένα κομμάτι κώδικα να το 'τρέχουμε' παραπάνω από μία φορά μέχρι να ισχύσει μία συνθήκη. Η χρήση της αποκοπής σε συνδυασμό με την άρνηση ως αποτυχία έχει ως αποτέλεσμα τη συνεχή εκτέλεση κώδικα μέχρι την επίτευξη κάποιου στόχου.

Η άρνηση ως αποτυχία (negation as failure) βασίζεται στην υπόθεση του κλειστού κόσμου, δηλαδή στο ότι αν κάτι δεν μπορεί ν' αποδειχθεί στο κόσμο του προβλήματός μας, τότε αυτό δεν ισχύει. Έτσι, αν ένα συγκεκριμένο γεγονός στο σώμα ενός κανόνα δεν μπορεί να ταυτοποιηθεί με ένα γεγονός ή κανόνα της βάσης δεδομένων, τότε η Prolog θεωρεί ότι δεν ισχύει (αποτυγχάνει) και έτσι οπισθοδρομεί μέχρι το αμέσως προηγούμενο γεγονός του ίδιου κανόνα το οποίο μπορεί να ταυτοποιηθεί με διαφορετικό τρόπο ή τον επόμενο κανόνα με την ίδια κεφαλή (αν δεν υπάρχει άλλο γεγονός στον ίδιο κανόνα).

Η αποτυχία στη Prolog μπορεί να επιτευχθεί είτε όταν ένα γεγονός δεν ισχύει είτε με τη δεσμευμένη λέξη fail.

Έτσι, η άρνηση στη Prolog ορίζεται με τον ακόλουθο τρόπο:

/*1*/ not(X):- X, !, fail.
/*2*/ not(_X).

Στη περίπτωση που το Χ αληθεύει τότε από την /*1*/ λόγω του fail θα αποτύχει και λόγω της αποκοπής δεν θα επιλέξει το γεγονός /*2*/. Έτσι, το not(X) θ' αποτύχει. Αντιθέτως, αν το Χ δεν αληθεύει τότε λόγω της οπισθοδρόμησης θα επιλέξει το /*2*/ οπότε το not(X) θα αληθεύσει.

Παράδειγμα άρνησης για να πετύχουμε οπισθοδρόμηση:

:- dynamic(temp/1).

box(1,200).
box(2,400).
box(3,300).
box(4,600).
box(5,350).

temp(box(0,0)).

heavier(_):-
  box(Id1,Hev1),
   temp(box(Id2,Hev2)),
   Hev1>Hev2,
   retract( temp(box(Id2,Hev2)) ),
   assert( temp(box(Id1,Hev1)) ),
  fail.

heavier(X):-temp(X).

Στο παραπάνω παράδειγμα, δεδομένου ενός συνόλου κιβωτίων το πρόγραμμα βρίσκει το κουτί με το μεγαλύτερο βάρος.