Κατηγορήματα στην 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) :-
        father(Z, X),
        father(Y, Z).
?- 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.

Ασκήσεις

Άσκηση (προαιρετική)

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.

• Περιεχόμενα

 Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:26 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».