Ο μηχανισμός ελέγχου της Prolog
Για να εκτελεστεί ένα πρόγραμμα Prolog πρέπει πρώτα να γίνει consult και μετά ο χρήστης να εισάγει τουλάχιστον μία ερώτηση (πρόταση) στο διερμηνέα της Prolog. Για ν' αποφασίσει η Prolog αν η πρόταση που ρωτάμε ισχύει, ο μηχανισμός ελέγχου της Prolog προσπαθεί να ενοποιήσει (στη βιβλιογραφία υπάρχει και ο όρος ταύτιση ή ταυτοποίηση) κάθε γεγονός της πρότασης με τουλάχιστον ένα γεγονός της βάσης δεδομένων ή με τουλάχιστον έναν κανόνα.
Η ενοποίηση αυτή πραγματοποιείται με σειριακό τρόπο εξετάζοντας όλα τα γεγονότα και τους κανόνες από πάνω προς τα κάτω. Για το λόγω αυτό η σειρά με την οποία εισάγουμε τα γεγονότα και τους κανόνες στη βάση δεδομένων έχει σημασία διότι καθορίζει τη σειρά με την οποία θα γίνουν οι ενοποιήσεις και άρα και τα αποτελέσματα που θα πάρουμε.
Ο μηχανισμός ενοποίησης
Δύο σύνθετοι όροι ή ατομικοί τύποι ταυτίζονται μεταξύ τους όταν:
- τα ονόματα των δύο σύνθετων όρων είναι τα ίδια,
- οι δύο σύνθετοι όροι είναι της ίδιας τάξης και τέλος
- αν ο κάθε ένας όρος του ενός σύνθετου όρου μπορεί να ενοποιηθεί με τον αντίστοιχο όρο του άλλου εφαρμόζοντας τους κανόνες του παρακάτω πίνακα.
| Όρος1 \ Όρος2 | Σταθερά c1 (άτομο ή αριθμός) |
Μεταβλητή V1 | Σύνθετος όρος s1(t11,t12,...,t1n) |
| Σταθερά c2 (άτομο ή αριθμός) |
ταυτίζεται μόνο όταν η c1 είναι ίδια με τη c2 | η μεταβλητή V1 παίρνει την τιμή c2 | δεν ενοποιείται |
| Μεταβλητή V2 | η μεταβλητή V2 παίρνει την τιμή c1 | η μεταβλητή V1 ενοποιείται με τη V2 | η μεταβλητή V2 ενοποιείται με τον σύνθετο όρο s1(t11,t12,...,t1n) |
| Σύνθετος όρος s2(t21,t22,...,t2m) | δεν ενοποιείται | η μεταβλητή V2 ενοποιείται με τον σύνθετο όρο s2(t21,t22,...,t2m) | επιτυγχάνει μόνο αν ισχύουν τα τρία βήματα του αλγόριθμου ταύτισης για τους όρους s1 και s2 |
Σημαντικό:
(α) οι ενοποιήσεις των όρων ενός ατομικού τύπου ή σύνθετου όρου γίνονται πάντοτε από αριστερά προς τα δεξιά.
(β) Η ενοποίηση δύο μεταβλητών έχει ως αποτέλεσμα να μοιράζονται την ίδια διεύθυνση μνήμης.
(γ) Στην περίπτωση που μία μεταβλητή εμφανίζεται παραπάνω από μία φορά σε έναν ατομικό τύπο ή σύνθετο όρο ή κανόνα τότε λόγω του ότι όλες οι μεταβλητές αυτές μοιράζονται την ίδια διεύθυνση μνήμης, η ενοποίηση μίας εκ των μεταβλητών αυτών με έναν όρο ενός άλλου ατομικού τύπου ή σύνθετου όρου ή κανόνα έχει ως αποτέλεσμα την μετάδοση (propagation) της τιμή της μεταβλητής αυτής και στις υπόλοιπες μεταβλητές του ατομικού τύπου (ή σύνθετου όρου ή κανόνα). Έτσι σε κάθε χρονική στιγμή, σε έναν ατομικό τύπο (ή σύνθετο όρο ή κανόνα) όλες οι μεταβλητές που έχουν το ίδιο όνομα είτε έχουν κάποια τιμή είτε είναι ελεύθερες.
(δ) Όταν μία μεταβλητή ταυτοποιείται με ένα σύνθετο όρο τότε ο όρος αυτός πρέπει να ελεγχθεί ότι δεν περιλαμβάνει μεταξύ των όρων του τη μεταβλητή αυτή (από κάποια προηγούμενη ενωποίηση). Αλλιώς δημιουργείται ατέρμονας βρόγχος και ο μηχανισμός ταυτοποίησης αποτυχαίνει βγάζοντας μύνημα λάθους.
Παραδείγματα
Έστω ότι έχουμε εισάγει τα παρακάτω γεγονότα στη βάση δεδομένων της Prolog:
/*1*/ on(cube(_), table).
/*2*/ on(ball(1), cube(1)).
/*3*/ on(ball(3), cube(2)).
/*4*/ on(ball(2), cube(3)).
/*5*/ is_clear(cube(4)).
/*6*/ is_clear(cube(5)).
/*7*/
can_move(cube(X), cube(Y)):-
is_clear(cube(X)),
is_clear(cube(Y)),
on(cube(Y), table).
Στις ακόλουθες ερωτήσεις γίνονται οι παρακάτω ενοποιήσεις (δεξιά στήλη):
?- on(ball(1), cube(1)). |
Επιτυχής ταύτιση με το γεγονός 2. |
?- on(ball(2), cube(X)). |
Επιτυχής ταύτιση με το γεγονός 4. Ενοποιήσεις μεταβλητών: X=3 |
?- on(ball(_)). |
Δεν ταυτίζεται διότι η τάξη του είναι 1, ενώ όλα τα γνωστά γεγονότα του ίδιου κατηγορήματος έχουν τάξη 2. |
?- on(cube(1), table). |
Επιτυχής ταύτιση με το γεγονός 1. Ενοποιήσεις μεταβλητών: ο ατομικός τύπος cube(1) ενοποιείται με τη μεταβλητή _ του γεγονότος 1. |
?- can_move(cube(4),cube(5)). |
Επιτυχής ταύτιση με τη κεφαλή του κανόνα 7. Ενοποιήσεις μεταβλητών: η μεταβλητή X ενοποιείται με τον ατομικό τύπο cube(4) της ερώτησης και η τιμή αυτή της μεταβλητής μεταδίδεται και στις υπόλοιπες μεταβλητές με το ίδιο όνομα στο σώμα του κανόνα. Το ίδιο γίνεται και για τον ατομικό τύπο cube(4). Η ερώτηση αληθεύει γιατί κάθε σύνθετος όρος του σώματος του κανόνα ταυτίζεται με τουλάχιστον ένα γεγονός της βάσης. |
Η εκτέλεση ενός προγράμματος Prolog
Όπως τονίσαμε παραπάνω κάθε πρόγραμμα Prolog εκτελείται εισάγοντας μία ερώτηση στο διερμηνέα της Prolog. Η ερώτηση αυτή έχει την ακόλουθη μορφή:
?- q1, q2, ..., qn.
Η Prolog μέσω του μηχανισμού ελέγχου, προσπαθεί να ταυτίσει τα γεγονότα αυτά με αυτά που έχει στη βάση δεδομένων αρχίζοντας πάντα από αριστερά προς τα δεξιά (πρώτα το q1 μετά το q2 κοκ.). Για κάθε γεγονός qκ το οποίο ισχύει (δηλαδή ενοποιείται με κάποιο γεγονός ή κανόνα της βάσης δεδομένων), μεταδίδει τη τιμή κάθε ενοποιημένης μεταβλητής που πιθανών να περιέχει στα υπόλοιπα γεγονότα της ερώτησης και μετά ελέγχει αν αληθεύει το επόμενο γεγονός qκ+1 .
Στη περίπτωση που αποτύχει να ταυτίσει το γεγονός qκ με κάποια πρόταση (γεγονός ή κανόνα), τότε ο μηχανισμός ελέγχου οπισθοδρομεί τη σειρά εκτέλεσης (ελέγχου) των γεγονότων της ερώτησης, δηλαδή κάνει backtracking κατά ένα γεγονός. Πιο συγκεκριμένα, για το αμέσως προηγούμενο γεγονός της ερώτησης qκ-1 αναζητά την επόμενη πρόταση που μπορεί να ταυτιστεί. Αυτό μπορεί να έχει ως αποτέλεσμα τη μεταδώσει νέων τιμών στις μεταβλητές των γεγονότων τις ερώτησης και άρα ν' αλλάξει τον τρόπο με τον οποίο αναζητά το αληθές των γεγονότων της ερώτησης.
Έστω τώρα ότι το γεγονός qκ ταυτίζεται με τη κεφαλή του ακόλουθου κανόνα r.
r:- f1, f2, ..., fm.
Τότε ο μηχανισμός ελέγχου της Prolog αφού πρώτα μεταδώσει στο σώμα του κανόνα οποιαδήποτε ενοποίηση έχει γίνει μεταξύ των όρων των qκ και r, ελέγχει σειριακά αν ικανοποιούνται τα γεγονότα του σώματος του κανόνα εφαρμόζοντας πάλι των μηχανισμό ελέγχου, αλλά αυτή τη φορά για το σώμα του κανόνα.
Έτσι, δεδομένου μίας προότασης (όπως η παραπάνω ερώτηση ή το σώμα ενός κανόνα) ο μηχανισμός ελέγχου της Prolog ελέγχει από αριστερά προς τα δεξιά αν ικανοποιούνται όλα τα γεγονότα της πρότασης, ενώ για κάθε έναν από αυτούς τους ελέγχους ψάχνει από πάνω προς τα κάτω τη βάση δεδομένων για γεγονότα και κανόνες που μπορούν να ταυτιστούν με το γεγονός της ερώτησης (βλ. παρακάτω σχήμα).
Το ψάξιμο όμως της Prolog δε σταματάει μετά τον επιτυχή έλεγχο και του τελευταίου γεγονότος της πρότασης. Η Prolog δίνει τη δυνατότητα στο χρήστη να ζητήσει τη συνέχιση του ψαξίματος στη βάση δεδομένων και για άλλες λύσεις πατώντας το πλήκτρο ";". Σ' αυτή τη περίπτωση ο μηχανισμός ελέγχου κάνει backtracking προσπαθώντας να βρει εναλλακτικές ενοποιήσεις για κάθε ένα γεγονός της πρότασης αρχίζοντας όμως από το τέλος προς την αρχή.
Παράδειγμα
Έστω το παρακάτω πρόγραμμα Prolog:
a(1).
a(2).
a(3).
b(1).
b(5).
b(3).
r(X,Y):- b(X), a(X), a(Y).
r(1,Y):- b(Y).
Στην ερώτηση
?- r(X,Y).
Ο μηχανισμός ελέγχου της Prolog κάνοντας χρήση του κανόνα r(X,Y) ελέγχει πρώτα αν ικανοποιείται το γεγονός b(X) μετά το a(X) και τέλος το a(Y), δίνοντας ως πρώτη απάντηση το ζεύγος τιμών:
X = 1
Y = 1
αν πατήσουμε το πλήκτρο ";" τότε η Prolog θα κάνει backtracking προσπαθώντας να ικανοποιήσει και πάλι το τελευταίο γεγονός a(Y) του κανόνα r(X,Y). Έτσι παίρνουμε τις τιμές:
X = 1
Y = 2
Πατώντας και πάλι το πλήκτρο ";" παίρνουμε την τελευταία εναλλακτική επιλογή που ικανοποιεί το a(Y) και κατ'επέκταση την ερώτηση r(X,Y):
X = 1
Y = 3
Συνεχίζοντας να ζητάμε εναλλακτικές λύσεις για την ερώτηση ο μηχανισμός ελέγχου θα συνεχίσει να κάνει backtracking ελέγχοντας αυτή τη φορά για εναλλακτικές επιλογές το γεγονός a(X) του κανόνα. Λόγω του ότι όμως η μεταβλητή Χ του γεγονότος αυτού είναι ενοποιημένη με τη μεταβλητή Χ του b(X) που ήδη έχει πάρει μία τιμή, τη θεωρούμε ως σταθερή. Οπότε η μεταβλητή Χ του a(Χ) δεν μπορεί να πάρει άλλη τιμή πέρα από αυτή που ήδη έχει. Έτσι ο μηχανισμός ελέγχου οπισθοδρομεί στο αμέσως επόμενο γεγονός b(X).
Η επόμενη τιμή του Χ που ικανοποιεί το b(X) είναι το 5. Η τιμή αυτή μεταδίδεται στο a(X) όπου όμως δεν ταυτίζεται με κάποιο γεγονός της βάσης επομένως ο μηχανισμός ελέγχου οπισθοδρομεί προσπαθώντας να βρει μία άλλη τιμή για το b(X). Εξαντλώντας τις εναλλακτικές επιλογές για το γεγονός b(X) και μετά για το γεγονός a(Y) παίρνουμε τις ακόλουθες απαντήσεις:
X = 3
Y = 1 ;
X = 3
Y = 2 ;
X = 3
Y = 3 ;
Τέλος, εξαντλώντας όλες τις δυνατές περιπτώσεις, ο μηχανισμός ελέγχου προσπαθεί να ικανοποιήσει πάλι το γεγονός r(X,Y) επιλέγοντας τον επόμενο κανόνα με κεφαλή r(1,Y). Έτσι παίρνουμε και τις παρακάτω απαντήσεις:
X = 1
Y = 1 ;
X = 1
Y = 5 ;
X = 1
Y = 3 ;
No
| Τελευταία ενημέρωση σελίδας: 27/10/2008 |