Κατηγορήματα στην Prolog

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Εισαγωγή

Η προστακτικές γλώσσες προγραμματισμού όπως η Fortran, η Pascal και η C έχουν κατασκευαστεί και να διευκολύνουν τον προγραμματισμό υπολογιστών αρχιτεκτονικής von Neumann (επεξεργαστής που εκτελεί κώδικα και επεξεργάζεται δεδομένα από τη μνήμη). Ιστορικά, ο στόχος για το σχεδιασμό των γλωσσών αυτών είναι να γίνει ο προγραμματισμός του υπολογιστή προσιτός στον άνθρωπο. Έτσι, η διαδικασία της λύσης ενός προβλήματος με υπολογιστή εμφανίζεται διχοτομημένη ανάμεσα στην ανάλυση του προβλήματος και, στη συνέχεια, την κωδικοποίησή του σε υπολογιστή.

Η εξέλιξη της ισχύος των υπολογιστών και του αντίστοιχου θεωρητικού υπόβαθρου μας έχει επιτρέψει να εξετάζουμε διαφορετικές προσεγγίσεις επίλυσης προβλημάτων με υπολογιστή που να βασίζονται όχι στο να κάνουν την αρχιτεκτονική του υπολογιστή προσιτή στον άνθρωπο, αλλά στο να κάνουν τη διατύπωση των προβλημάτων από τον άνθρωπο προσιτή στον υπολογιστή. Έτσι, τόσο ο συναρτησιακός όσο και ο λογικός προγραμματισμός επιτρέπουν τη διατύπωση του προβλήματος που πρέπει να επιλυθεί με βάση έναν συμβολισμό και αφήνουν στον υπολογιστή να λύσει το πρόβλημα με βάση τη διατύπωσή του. Η βάση του λογικού προγραμματισμού μπορεί να διατυπωθεί ως εξής:

ή τη σύνοψή της από τον Bob Kowalski: Η ιστορία του λογικού προγραμματισμού και της Prolog μπορεί να συνοψιστεί από τους παρακάτω σταθμούς:
J. Robinson (1965)
Διατύπωση του αλγόριθμου της ταυτοποίησης (unification). Ο αλγόριθμος αυτός βρίσκει ένα σύνολο από στοιχειώδεις αντικαταστάσεις σε μεταβλητές για να καταστήσει δύο όρους ταυτόσημους.
R. Kowalski (1974)
Διαδικασιακή ερμηνεία προτάσεων Horn. Προτάσεις της μορφής Α αν Β1 και Β2 και ... Βν μπορούν να ερμηνευτούν διαδικασιακά ως: για να ισχύει το Α, πρέπει να ισχύει το Β1 και το Β2 και ... το Βν.
A. Colmerauer (1973)
Υλοποίηση διερμηνευτή της Prolog σε Fortran.
D. Warren (1977)
Υλοποίηση μεταγλωττιστή της Prolog (σε ενδιάμεση γλώσσα την Warren Abstract Machine).
Ιαπωνία (1981)
Πρόγραμμα υπολογιστών πέμπτης γενιάς. Έδωσε ώθηση στην Prolog υιοθετώντας το λογικό προγραμματισμό ως βασική τεχνολογία του προγράμματος.

Σχέσεις

Η βάση της Prolog είναι τα γεγονότα (facts), οι κανόνες (rules) και οι ερωτήσεις (queries). Υπάρχει μόνο μια δομή δεδομένων, ο όρος (term). Τα γεγονότα ορίζουν μια αληθή σχέση ανάμεσα σε αντικείμενα.

Παράδειγμα 1 (ορισμός σχέσεων ανάμεσα σε ακέραιούς):

sum(0, 0, 0).
sum(0, 1, 1).
sum(1, 0, 1).
sum(1, 1, 2).

Παράδειγμα 2 (ορισμός σχέσεων ανάμεσα σε ανθρώπους):

father(anthi, giannis). father(petros, giannis). father(thanasis, giannis). father(iro, giannis). father(nikos, thanasis). father(giorgos, thanasis). mother(anthi, maria). Οι λέξεις nikos, petros, anthi, στο παραπάνω παράδειγμα είναι σταθερές της γλώσσας (όπως και οι ακέραιοι στο προηγούμενο). Ονομάζονται άτομα (atoms) και γράφονται με αρχικό μικρό γράμμα.

Με βάση τα παραπάνω γεγονότα μπορούμε να εκτελέσουμε ερωτήσεις για να μάθουμε αν μια σχέση είναι αληθής ή ψευδής. Όταν η Arity Prolog βρει μια αληθή λύση στην ερώτησή μας μας εμφανίζει το σύμβολο ->. Στο σημείο εκείνο μπορούμε να πατήσουμε Enter για να δηλώσουμε πως μας ικανοποιεί η λύση, ή ; για να δηλώσουμε πως θέλουμε να δούμε και άλλες λύσεις. Παράδειγμα:

?- sum(0, 0, 0).
 ->

yes
?- sum(1, 1, 2).
 ->

yes
?- sum(1, 1, 0).

no
?- sum(5, 3, 9).

no

Λογικές μεταβλητές

Ερωτήσεις με μεταβλητές

Οι λογικές μεταβλητές στην Prolog (γράφονται με αρχικό κεφαλαίο γράμμα) μπορούν να χρησιμοποιηθούν για να τεθούν ερωτήσεις για να μάθουμε κάποιο στοιχείο από τα γεγονότα που έχουμε ορίσει. Παράδειγμα:
?- sum(1, 1, X).

X = 2
yes
?- sum(X, 1, X).

no
?- sum(X, X, 2).

X = 1
yes
?- father(iro, X).

X = giannis
yes
?- father(X, Y).

X = anthi
Y = giannis ->;

X = petros
Y = giannis ->;

X = thanasis
Y = giannis ->;

X = iro
Y = giannis ->;

X = nikos
Y = thanasis ->
yes

Γεγονότα με μεταβλητές

Με βάση τις μεταβλητές μπορούμε ακόμα να ορίσουμε και γενικευμένα γεγονότα (universal facts). Για παράδειγμα για να ορίσουμε πως όλοι αγαπούν τη Μαίρη γράφουμε:

loves(X, mairi).

Όροι

Με βάση τα παραπάνω μπορούμε να ορίσουμε τη δομή δεδομένων της Prolog, τον όρο. Οι όροι ορίζονται αναδρομικά. Ένας όρος μπορεί να είναι:

Παραδείγματα όρων:
sum(0, 0, 1)
car(color(red), engine(1600), abs, speed(172), doors(2,2,1))
loves(X, Y)

Σύζευξη

Μπορούμε να ενώσουμε ερωτήσεις μεταξύ τους με το κόμμα (,) για να απαιτήσουμε να είναι και οι δύο αληθείς:
?- sum(0, 1, 1), sum(1, 1, 2).

yes
?- sum(0, 1, 1), sum(1, 1, 3).

no
Μπορούμε να ορίσουμε ακόμα κανόνες με βάση ένα γεγονός και κάποιες σχετικές ερωτήσεις με την παρακάτω σύνταξη:
a :-
        b1,
        b2,
        bn.
Ο κανόνας διαβάζεται ως εξής: ισχύει το a αν ισχύει το b1 και το b2 και το bn. Αν ορίσουμε παραπάνω από έναν κανόνα για το ίδιο γεγονός τότε οι κανόνες ισχύουν διαζευκτικά (αρκεί να ισχύει ένας).

Παράδειγμα:


parent(X, Y) :-
        father(X, Y).
parent(X, Y) :-
        mother(X, Y).
?- parent(anthi, X).

X = giannis ->;

X = maria
yes
?- parent(X, giannis).

X = anthi ->;

X = petros ->;

X = thanasis ->;

X = iro ->;

no

Παράδειγμα:

grandfather(X, Y) :-
        parent(X, Z),
        father(Z, Y).
?- grandfather(X, Y).

X = giannis
Y = nikos ->;

X = giannis
Y = giorgos ->;

no

Αριθμητική με αναδρομή

Με βάση τον αναδρομικό ορισμό των φυσικών αριθμών μπορούμε να τους ορίσουμε αξιωματικά και στην Prolog. Ορίζουμε τον όρο s(X) να παριστάνει τον επόμενο φυσικό αριθμό από το X. Έτσι, ορίζοντας το 0 το 1 είναι s(0), το 2 είναι s(s(0)), κ.λπ. Ο κανόνας nat ορίζει τους φυσικούς αριθμούς. Μπορούμε με επαγωγή να αποδείξουμε πως όλοι οι φυσικοί παράγονται και αναγνωρίζονται από τον nat.
nat(0).
nat(s(X)) :-
	nat(X).
?- nat(0).

yes
?- nat(s(0)).

yes
?- nat(s(s(s(s(0))))).

yes
?- nat(X).

X = 0 ->;

X = s(0) ->;

X = s(s(0)) ->;

X = s(s(s(0))) ->;

X = s(s(s(s(0)))) ->

X = s(s(s(s(s(0))))) ->;

X = s(s(s(s(s(s(0)))))) ->;

X = s(s(s(s(s(s(s(0))))))) ->;

X = s(s(s(s(s(s(s(s(0)))))))) ->;

X = s(s(s(s(s(s(s(s(s(0))))))))) ->;

X = s(s(s(s(s(s(s(s(s(s(0)))))))))) ->
...
Με βάση τον ορισμό αυτό μπορούμε να ορίσουμε μια σχέση διάταξης:
less(0, X) :-
	nat(X).

less(s(X), s(Y)) :-
	less(X, Y).

?- less(s(0), 0).

no
?- less(s(0), s(s(0))).

yes
?- less(X, s(s(s(s(0))))).

 X = 0 ->;

 X = s(0) ->;

 X = s(s(0)) ->;

 X = s(s(s(0))) ->;

 X = s(s(s(s(0)))) ->;

no
Με παρόμοιο τρόπο μπορούμε να ορίσουμε και την πρόσθεση:
plus(0, X, X) :-
        nat(X).

plus(s(X), Y, s(Z)) :-
        plus(X, Y, Z).
Είναι αξιοσημείωτο πως το κατηγόρημα της πρόσθεσης με τη μορφή που έχει οριστεί μπορεί να υπολογίσει άθροισμα, διαφορά, όρους που δημιουργούν ένα άθροισμα, ή να ελέγξει αν ένα άθροισμα είναι αληθές:
?- plus(s(0), s(0), X).

X = s(s(0))
yes
?- plus(s(0), X, s(s(s(0)))).

X = s(s(0))
yes
?- plus(X, Y, s(s(0))).

X = 0
Y = s(s(0)) ->;

X = s(0)
Y = s(0) ->;

X = s(s(0))
Y = 0 ->;

no
?- plus(s(0), 0, 0).

no
Με τη χρήση του αθροίσματος μπορούμε να ορίσουμε και το γινόμενο:
times(0, X, 0)

times(s(X), Y, Z) :-
        times(X, Y, W),
        plus(W, Y, Z).
Το κατηγόρημα για το γινόμενο που έχει οριστεί με τον τρόπο αυτό έχει και αυτό παρόμοια ευελιξία:
?- times(s(s(0)), s(s(s(0))), X).

X = s(s(s(s(s(s(0))))))
yes
?- times(X, s(s(0)), s(s(s(s(0))))).

X = s(s(0)) ->.

yes
?- times(X, Y, s(s(s(s(0))))).

X = s(0)
Y = s(s(s(s(0)))) ->;

X = s(s(0))
Y = s(s(0)) ->;

?- times(s(0), s(0), s(0)).

yes

Υπολογισμοί στην Prolog

Αν και ο παραπάνω ορισμός των ακεραίων είναι αξιοθαύμαστος για τη λιτότητα και την πληρότητά του, οι υλοποιήσεις της Prolog για υπολογισμούς αριθμών χρησιμοποιούν το κατηγόρημα is(X, Y) και την υλοποίηση των αριθμών από τον επεξεργαστή του υπολογιστή. Αυτό υπολογίζει το αποτέλεσμα της αριθμητικής έκφρασης στο Y και την ταυτοποιεί με το X. Το κατηγόρημα αυτό είναι μεν αποδοτικό, δε συμπεριφέρεται όμως με την ευελιξία που δείξαμε στα παραπάνω παραδείγματα. Παράδειγμα:
?- is(X, 1 + 2).

X = 3

?- is(2, 1 + 1).

yes
?- is(Y, 3 * 8 + 4 / 5).

Y = 24.8
yes
?- is(2, X + X).

no

Λίστες

Οι λίστες στην Prolog ορίζονται με τη σύνταξη [Head | Tail] όπου Head είναι το στοιχείο που αποτελεί την κεφαλή της λίστας και Tail τα υπόλοιπα στοιχεία. Η σύνταξη αυτή αποτελεί απλώς συντομογραφία για όρους των οποίων το όνομα είναι η τελεία (.). Με βάση τον ορισμό των λιστών μπορούμε πολύ εύκολα να ορίσουμε σύνθετους αλγόριθμους όπως την ταξινόμηση quick sort:
quicksort([X|Xs], Ys) :-
        partition(Xs, X, L, B),
        quicksort(L, Ls),
        quicksort(B, Bs),
        append(Ls, [X | Bs], Ys).

quicksort([], []).

partition([X|Xs], Y, [X|Ls], Bs) :-
        X =< Y,
        partition(Xs, Y, Ls, Bs).

partition([X|Xs], Y, Ls, [X|Bs]) :-
        X > Y,
        partition(Xs, Y, Ls, Bs).

partition([], Y, [], []).

append([], X, X).

append([H | T], X, [H | Z]) :-
        append(T, X, Z).

?- quicksort([4,2,8,12,1,7], X).

X = [1,2,4,7,8,12] ->.

yes

Συμβολική επεξεργασία

Με βάση μεταβλητές και όρους μπορούμε να γράψουμε ένα πρόγραμμα που να αναγνωρίζει πολυώνυμα ορισμένα με τον παρακάτω τρόπο:
polynomial(X, X).

polynomial(N, X) :-
        number(N).

polynomial(sum(A, B), X) :-
        polynomial(A, X),
        polynomial(B, X).

polynomial(diff(A, B), X) :-
        polynomial(A, X),
        polynomial(B, X).

polynomial(prod(A, B), X) :-
        polynomial(A, X),
        polynomial(B, X).

polynomial(quot(A, B), X) :-
        polynomial(A, X),
        number(B).

polynomial(pow(A, B), X) :-
        polynomial(A, X),
        integer(B).
Ερωτήσεις:
?- p(sum(x, 1), x).
 ->.

yes
?- p(sum(x, 1), y).

no
?- polynomial(sum(prod(5,pow(x, 2)), prod(2, x)), x).
 ->.

yes
?- polynomial(sum(prod(5,pow(x, 2)), pow(y, 3)), x).

no
?- polynomial(sum(prod(5,pow(x, 2.1)), prod(2, x)), x).

no

Σύντομες οδηγίες για τη χρήση της Arity Prolog

Βιβλιογραφία

Ασκήσεις

Άσκηση 10

  1. Ορίστε σε Prolog το κατηγόρημα
    polynomial_value(P, X, V).
    
    όπου:
    • Pείναι ένα πολυώνυμο ορισμένο με βάση τους όρους:
      • sum(A, B) (άθροισμα)
      • diff(A, B) (διαφορά)
      • prod(A, B) (γινόμενο)
      • pow(A, B) (ύψωση σε δύναμη)
      • τη μεταβλητή x (προσοχή, μικρό γράμμα)
      • καθώς και ακεραίους.
    • X η τιμή της μεταβλητής x
    • V η τιμή του πολυωνύμου.

Παράδειγμα:

?- polynomial_value(prod(5, pow(x, 3)), 3, X).

X = 135 ->

yes
?- polynomial_value(sum(prod(5, pow(x, 3)), prod(x, 5)), 4, X).

X = 340 ->.

yes
Την ύψωση ενός αριθμού σε δύναμη μπορείτε να την ορίσετε ως εξής:
raise(X, 0, 1).
raise(X, N, Y) :-
        N2 is N - 1,
        raise(X, N2, K),
        Y is K * X.