Κατηγορήματα στην 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, τον όρο. Οι όροι ορίζονται αναδρομικά. Ένας όρος μπορεί να είναι:

σταθερά, δηλαδή άτομο ή αριθμός
μεταβλητή
άτομο(όρος1, ... όρος_ν)

Παραδείγματα όρων:

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

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

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

sum(A, B) (άθροισμα)
diff(A, B) (διαφορά)
prod(A, B) (γινόμενο)
quot(A, B) (πηλίκο)
pow(A, B) (ύψωση σε δύναμη)
τη μεταβλητή X
καθώς και ακεραίους.

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

Αντιγράφετε τα αρχεία c:\apps\arity\bin\dos\ari σε έναν δικό σας κατάλογο (κάτω από το home σας).
Τρέχετε την εντολή api.
Στο ?- που εμφανίζεται μπορείτε να πληκτρολογήσετε ερωτήσεις.
Για να πληκτρολογήσετε κανόνες πατάτε Switch (ALT-S) και γράφετε τους κανόνες που θέλετε στο διορθωτή που εμφανίζεται.
Πριν βγείτε από το διορθωτή βεβαιωθείτε πως η εντολή Buffers - Reconsult on exit είναι ενεργοποιημένη (ALT-B ALT-C).
Για να βγείτε από το διορθωτή επιλέγετε πάλι Switch (ALT-S).
Το αρχείο κειμένου arity.hlp περιέχει στοιχεία για όλα τα ορισμένα από την Arity Prolog κατηγορήματα.

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

Μ. Κατζουράκη, Μ. Γεργατσούλης και Σ. Κόκκοτος PROγραμματίζοντας στη LOGική. Εκδόσεις Νέων Τεχνολογιών, 1991.

Christopher John Hogger. Introduction to Logic Programming. Academic Press, 1984.
Robert Kowalski. Predicate logic as programming language. In Jack L. Rosenfeld, editor, Information Processing 74, Proceedings of IFIP congress 74, pages 569–574, Stockholm, Sweden, August 1974. International Federation of Information Processing, North-Holland.
Robert Kowalski. Logic as a computer language. In Keith L. Clark and Sten-Åke Tärnlund, editors, Logic Programming, pages 3–16. Academic Press, 1982.
Francis G. McCabe. Logic and Objects. Prentice Hall, 1992.
Richard A. O'Keefe. The Craft of Prolog. MIT Press, 1990.
Uday S. Reddy. On the relationship between logic and functional languages. In Doug DeGroot and Gary Lindstrom, editors, Logic Programming, Functions, Relations and Equations, pages 3–36. Prentice Hall, Englewood Cliffs, NJ, USA, 1986.
J. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23–41, January 1965.
Peter H. Salus, editor. Handbook of Programming Languages, volume III: Functional and Logic Programming Languages. Macmillan Technical Publishing, 1998.
Leon Sterling and Ehud Shapiro. The Art of Prolog. MIT Press, 1986.
David H. D. Warren. An abstract Prolog instruction set. Technical Note 309, SRI International, Artificial Intelligence Center, Computer Science and Technology Division, 333 Ravenswood Ave., Menlo Park, CA, USA, October 1983.

Ασκήσεις

Άσκηση 10

Ορίστε σε 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.

Περιεχόμενα