16. Γλώσσες λογικού προγραμματισμού

ΑΡΧΕΣ ΓΛΩΣΣΩΝ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ (R.W.Sebesta) - Κεφάλαιο 16

• Λογικός προγραμματισμός
• Γλώσσες λογικού προγραμματισμού (Prolog)
• Κατηγορηματικός λογισμός
• Επισκόπηση της Prolog (αριθμητική, λίστες, αποσφαλμάτωση προγραμμάτων, τομείς εφαρμογών)

Η συμβολική λογική αποτελεί τη βάση για το λογικό προγραμματισμό και τις γλώσσες λογικού προγραμματισμού.

Στόχος του λογικού προγραμματισμού είναι ο προγραμματισμός να μην είναι διαδικαστικός, δηλαδή να μην απαιτείται η αναλυτική περιγραφή των ενεργειών που οδηγούν στη λύση του προβλήματος.

16.1 Εισαγωγή

Τα προγράμματα εκφράζονται σε μια μορφή συμβολικής λογικής και χρησιμοποιείται μια λογική διεργασία εξαγωγής συμπερασμάτων για την παραγωγή αποτελεσμάτων.

Τα λογικά προγράμματα είναι δηλωτικά και όχι διαδικαστικά, δηλαδή δεν περιγράφονται αναλυτικές διαδικασίες επίλυσης από τον προγραμματιστή. Αντίθετα, χρησιμοποιούνται δηλώσεις γεγονότων και κανόνων.

Τα προγράμματα σε γλώσσες λογικού προγραμματισμού είναι συλλογές δεδομένων και κανόνων. Ο χρήστης θέτει ερωτήματα, τα οποία απαντώνται χρησιμοποιώντας τα δεδομένα και τους κανόνες.

Το συντακτικό των λογικών γλωσσών είναι πολύ διαφορετικό από τις άλλες γλώσσες προγραμματισμού.

16.2 Μια σύντομη εισαγωγή στον κατηγορηματικό λογισμό

Η βάση του λογικού προγραμματισμού είναι η τυπική λογική που έχει στενή σχέση με τα μαθηματικά.

Μια πρόταση είναι μια λογική δήλωση που μπορεί να είναι αληθής ή όχι και αποτελείται από αντικείμενα και σχέσεις μεταξύ αντικειμένων.

Η συμβολική λογική μπορεί να χρησιμοποιηθεί για:

• Έκφραση προτάσεων
• Έκφραση σχέσεων μεταξύ προτάσεων
• Εξαγωγή νέων προτάσεων από αληθείς προτάσεις

Ο κατηγορηματικός λογισμός πρώτης τάξης είναι η μορφή συμβολικής λογικής που χρησιμοποιείται στο λογικό προγραμματισμό.

16.2.1 Προτάσεις (propositions)

• Οι απλοί όροι είναι οι σταθερές και οι μεταβλητές.
• Μια σταθερά είναι ένα σύμβολο που αναπαριστά ένα αντικείμενο.
• Μια μεταβλητή είναι ένα σύμβολο που μπορεί να αναπαριστά διαφορετικά αντικείμενα σε διαφορετικές χρονικές στιγμές.
• Ένας σύνθετος όρος αποτελείται από έναν συναρτητή (functor) και μια διατεταγμένη λίστα παραμέτρων.

Παραδείγματα σύνθετων όρων.

man(jake)
like(bob, steak)
man(fred)

που μπορεί να σημαίνουν ότι ο Jake είναι άνδρας, ότι στον bob αρέσει το steak, και ότι o fred είναι άνδρας.

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

16.2.2 Προτασιακή μορφή (clausal form)

Με τον κατηγορηματικό λογισμό υπάρχουν πολλοί τρόποι με τους οποίους μπορεί να διατυπωθεί το ίδιο νόημα. Για να μπορεί να χρησιμοποιηθεί σε ένα αυτόματο σύστημα χρησιμοποιείται μια τυποποιημένη μορφή που ονομάζεται προτασιακή μορφή και η οποία είναι σε θέση να εκφράσει όλες τις προτάσεις που εκφράζονται με τον κατηγορηματικό λογισμό.

Μια πρόταση σε προτασιακή μορφή έχει την ακόλουθη γενική μορφή

και σημαίνει ότι αν όλα τα Α είναι αληθή τότε τουλάχιστον ένα από τα Β θα είναι αληθές.

Ένα παράδειγμα:

που σημαίνει ότι αν ο Al είναι πατέρας του Bob και η Violet μητέρα του Bob και ο Louis παππούς του Bob τότε ο Louis είναι είτε πατέρας του Al είτε πατέρας της Violet.

16.3 Κατηγορηματικός Λογισμός και απόδειξη θεωρημάτων

Ανάλυση (Robinson 1965).

Προτάσεις Horn. Προτασιακή μορφή με επιπλέον περιορισμούς που καθιστά την ανάλυση υπολογιστικά αποδοτική.

16.4 Επισκόπηση του λογικού προγραμματισμού

Δηλωτική σημασιολογία: Υπάρχει ένας τρόπος προσδιορισμού του νοήματος κάθε πρότασης και δεν εξαρτάται από το πως μπορεί να χρησιμοποιηθεί η πρόταση για την επίλυση ενός προβλήματος (απλούστερη από τη σημασιολογία των προτάσεων των προστακτικών γλωσσών).

16.5 Η γέννηση της Prolog

Alen Coleraurer, Phillippe Roussel, Robert Kowalski (1972)

16.6 Τα βασικά στοιχεία της Prolog

Υπάρχουν πολλοί διάλεκτοι της Prolog. Η πλέον διαδεδομένη είναι η διάλεκτος του Εδιμβούργου.

16.6.1 Όροι

Ένας όρος στην Prolog είναι μια σταθερά, μια μεταβλητή ή μια δομή.

Οι μεταβλητές μπορούν να είναι bounded ή unbounded.

Τα γεγονότα ορίζονται μέσω των δομών.

Οι προτάσεις της Prolog είναι γεγονότα, κανόνες και τελικές καταστάσεις.

16.6.2 Προτάσεις γεγονότων

Δύο είδη προτάσεων:

• Ακέφαλες προτάσεις Horn (αντιστοιχούν σε γεγονότα)
• Προτάσεις Horn με κεφαλή (αντιστοιχούν σε κανόνες)

16.6.3 Προτάσεις κανόνων

Σε έναν κανόνα το δεξιό μέρος είναι το προηγούμενο (το if) και το αριστερό μέρος είναι το επόμενο (το then).

16.6.4 Προτάσεις τελικής κατάστασης

Οι προτάσεις τελικής κατάστασης, μένει να αποδειχθεί ότι ισχύουν ή ότι δεν ισχύουν, και είναι όμοιες εμφανισιακά με τις προτάσεις γεγονότα.

16.6.5 Η εξαγωγή συμπεράσματος στην Prolog

Η Prolog χρησιμοποιεί αντίστροφη αλυσίδωση (backward chaining), δηλαδή ξεκινά από το ζητούμενο (την τελική κατάσταση) και επιχειρεί να εντοπίσει μια σειρά αντιστοιχήσεων που οδηγεί σε υπάρχοντα γεγονότα. Η αντίστροφη αλυσίδωση λειτουργεί καλύτερα όταν αναμένεται ένα σχετικά μικρό σύνολο απαντήσεων.

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

Οπισθοδρόμηση (backtracking) είναι η επιστροφή σε κάποιο σημείο στο οποίο είχε ανατεθεί μια τιμή σε μια μεταβλητή και η δοκιμή μιας άλλης εναλλακτικής τιμής.

Πρόβλημα με την οπισθοδρόμηση

Η απάντηση για το ακόλουθο ερώτημα:

?- male(X), parent(X, shelley).

μπορεί να καθυστερεί περισσότερο από την απάντηση για το επόμενο ερώτημα:

?- parent(X, shelley), male(X).

16.6.6 Απλή αριθμητική

Οι αριθμητικές πράξεις εκτελούνται με τον τελεστή is.

?- B = 34, C=2, A is B/17 + C.
B = 34,
C = 2,
A = 4.

Ο τελεστής is έχει διαφορετική σημασιολογία από τον τελεστή εκχώρησης των προστακτικών γλωσσών.

Η πρόταση Sum is Sum + 1 δεν έχει νόημα στην Prolog.

?- Sum is Sum + 1.
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [10] _11678 is _11684+1
ERROR:    [9] <user>

Παράδειγμα με αριθμητικές πράξεις

speed(ford, 100).
speed(chevy, 105).
speed(dodge, 95).
speed(volvo, 80).
time(ford, 20).
time(chevy, 21).
time(dodge, 24).
time(volvo, 24).
distance(X, Y) :- speed(X, Speed),
    time(X, Time),
    Y is Speed * Time.

speed.pl

?- distance(chevy, Chevy_Distance).
Chevy_Distance = 2205.

16.6.7 Δομές λιστών

Οι λίστες είναι σειρές στοιχείων που μπορεί να είναι ατομικοί όροι, ατομικές προτάσεις ή λίστες.

Η κενή λίστα συμβολίζεται ως []

Ο συμβολισμός [Χ|Υ] υποδηλώνει μια λίστα με κεφαλή το στοιχείο X και ουρά τη λίστα Υ.

Μερικά βασικά κατηγορήματα για λίστες

• append/3
• reverse/2
• member/2

Μια υλοποίηση της append (η append υπάρχει υλοποιημένη στην Prolog)

my_append([], List, List).
my_append([Head | List_1], List_2, [Head | List_3]) :-
            my_append(List_1, List_2, List_3).

my_append.pl

Η δεύτερη από τις παραπάνω προτάσεις μπορεί να ερμηνευτεί ως εξής: Η επισύναψη της λίστας [Head | List_1] σε μια λίστα List_2 παράγει τη λίστα [Head | List_3] αν και μόνο αν η λίστα List_3 προκύπτει από την προσάρτηση της λίστας List_2 στη λίστα List_1.

?- trace.
[trace] ?- my_append([bob, jo], [jake, darcie], Family).
   Call: (10) my_append([bob, jo], [jake, darcie], _4546) ? creep
   Call: (11) my_append([jo], [jake, darcie], _4966) ? creep
   Call: (12) my_append([], [jake, darcie], _5016) ? creep
   Exit: (12) my_append([], [jake, darcie], [jake, darcie]) ? creep
   Exit: (11) my_append([jo], [jake, darcie], [jo, jake, darcie]) ? creep
   Exit: (10) my_append([bob, jo], [jake, darcie], [bob, jo, jake, darcie]) ? creep
Family = [bob, jo, jake, darcie].

Κατηγορήματα για λίστες που υποστηρίζει η SWI-PROLOG:

• member/2
• append/3
• append/2
• prefix/2
• select/3
• selectchk/3
• select/4
• selectchk/4
• nextto/3
• delete/3
• nth0/3
• nth1/3
• nth0/4
• nth1/4
• last/2
• proper_length/2
• same_length/2
• reverse/2
• permutation/2
• flatten/2
• clumped/2
• max_member/2
• min_member/2
• sum_list/2
• max_list/2
• min_list/2
• numlist/3
• is_set/1
• list_to_set/2
• intersection/3
• union/3
• subset/2
• subtract/3

SWI-PROLOG list of predicates

Μια υλοποίηση της member (η member υπάρχει υλοποιημένη στην Prolog)

my_member(Element, [Element|_]).
my_member(Element, [_|List]) :-  my_member(Element, List).

Ο χαρακτήρας _ υποδηλώνει μια ανώνυμη μεταβλητή.

?- 9 ?- trace.
[trace] 9 ?- my_member(a, [b,c,d]).
   Call: (10) my_member(a, [b, c, d]) ? creep
   Call: (11) my_member(a, [c, d]) ? creep
   Call: (12) my_member(a, [d]) ? creep
   Call: (13) my_member(a, []) ? creep
   Fail: (13) my_member(a, []) ? creep
   Fail: (12) my_member(a, [d]) ? creep
   Fail: (11) my_member(a, [c, d]) ? creep
   Fail: (10) my_member(a, [b, c, d]) ? creep
false.

16.7 Ελλείψεις της Prolog

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

16.7.1 Έλεγχος σειράς ανάλυσης

Για λόγους αποδοτικότητας και προκειμένου να αποφεύγονται οι ατέρμονοι βρόχοι, ο προγραμματιστής στην Prolog συχνά χρειάζεται να ενσωματώνει στα προγράμματα του πληροφορίες ροής ελέγχου που απομακρύνουν από τον καθαρό Λογικό Προγραμματισμό. Αυτό συμβαίνει διότι η Prolog έχει συγκεκριμένη σειρά με την οποία επιχειρεί τα ταιριάσματα (από πάνω προς τα κάτω στη βάση γνώσης).

Ο έλεγχος της οπισθοδρόμησης μπορεί να γίνει με τον τελεστή αποκοπής ! (cut). Ο τελεστής ! είναι στην πραγματικότητα μια τελική κατάσταση άμεσης επιτυχίας που αποτρέπει την ικανοποίηση εκ νέου μέσω οπισθοδρόμησης. Για παράδειγμα:

a,b,!,c,d.

αν τα a και b επιτύχουν αλλά το c αποτύχει τότε ολόκληρη η τελική κατάσταση αποτυγχάνει (μπορεί να είναι η επιθυμητή συμπεριφορά διότι ίσως να γνωρίζουμε ότι αν το c αποτυγχάνει τότε δεν έχει νόημα η εξέταση εναλλακτικών λύσεων για τα a και b).

16.7.2 Υπόθεση κλειστού κόσμου

Η Prolog είναι ένα σύστημα που μπορεί να αποδείξει ότι κάτι είναι αληθές αλλά όχι ότι είναι ψευδές. Εφόσον δεν μπορεί να αποδείξει με ότι περιέχεται στη βάση δεδομένων του ότι κάτι είναι αληθές υποθέτει ότι είναι ψευδές.

Έστω η ακόλουθη βάση γνώσης με το κατηγόρημα father(X,Y) που ερμηνεύεται ότι ο πατέρας του X είναι ο Y

father(aristea, sotiris).

Τα ακόλουθα ερωτήματα λόγω της υπόθεσης του κλειστού κόσμου θα δώσουν τις ακόλουθες απαντήσεις

?- father(aristea, Y).
Y = sotiris.

?- father(christos, Y).
false.

16.7.3 Το πρόβλημα της άρνησης

parent(bill, jake).
parent(bill, shelley).
sibling(X, Y) :- parent(M, X), parent(M, Y).

sibling.pl

Αν τεθεί το ακόλουθο ερώτημα, λαμβάνουμε την απάντηση ότι ο Jake είναι τέκνο των ίδιων γονέων με τον Jake, που δεν έχει νόημα ως απόκριση.

?- sibling(X,Y).
X = Y, Y = jake ;
X = jake,
Y = shelley ;
X = shelley,
Y = jake ;
X = Y, Y = shelley.

Με την ακόλουθη αλλαγή στον κώδικα που προσθέτει τον όρο not(X = Y) στο κατηγόρημα sibling/2.

parent(bill, jake).
parent(bill, shelley).
sibling(X, Y) :- parent(M, X), parent(M, Y), not(X = Y).

sibling2.pl

η απάντηση στο ίδιο ερώτημα, είναι πλέον η αναμενόμενη.

?- sibling(X,Y).
X = jake,
Y = shelley ;
X = shelley,
Y = jake ;
false

Ωστόσο, το not της Prolog δεν είναι ισοδύναμο τον λογικό τελεστή not των άλλων γλωσσών προγραμματισμού. Για παράδειγμα το

not(not(some_goal)).

δεν είναι ισοδύναμο με το

some_goal.

Αυτό φαίνεται στο ακόλουθο παράδειγμα

1 ?- member(X,[mary, fred, barb]).
X = mary ;
X = fred ;
X = barb.

2 ?- not(member(X,[mary, fred, barb])).
false.

3 ?- not(not(member(X,[mary, fred, barb]))).
true.

16.7.4 Εγγενείς περιορισμοί

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

PROLOG PROGRAMMING by ROMAN BARTÁK (sorting)

16.8 Εφαρμογές λογικού προγραμματισμού

Ο λογικός προγραμματισμός χρησιμοποιείται κυρίως σε Βάσεις Δεδομένων, έμπειρα συστήματα και στην επεξεργασία φυσικής γλώσσας.

16.8.1 Συστήματα διαχείρισης σχεσιακών βάσεων δεδομένων

Τα Συστήματα Διαχείρισης Σχεσιακών Βάσεων Δεδομένων (RDBMS=Relational Database Management Systems) αποθηκεύουν τα δεδομένα με μορφή πινάκων. Η γλώσσα SQL που χρησιμοποιείται για τα ερωτήματα προς τη βάση είναι δηλωτική όπως και ο λογικός προγραμματισμός (ο χρήστης δεν περιγράφει το πως θα ληφθούν τα αποτελέσματα αλλά μόνο τα χαρακτηριστικά των αποτελεσμάτων). Ο λογικός προγραμματισμός μπορεί να χρησιμοποιηθεί για την υλοποίηση ενός RDBMS ενώ επιπλέον παρέχει τη δυνατότητα λήψης επαγωγικών συμπερασμάτων (συμπεράσματα που προκύπτουν από το συνδυασμό γεγονότων και κανόνων που είναι αποθηκευμένα στη βάση). Ωστόσο, η υλοποίηση ενός RDBMS με λογικό προγραμματισμό υστερεί σε ταχύτητα εκτέλεσης σε σχέση με υλοποιήσεις σε προστακτικές γλώσσες προγραμματισμού.

16.8.2 Έμπειρα συστήματα

Τα έμπειρα συστήματα (expert systems) είναι συστήματα που επιδιώκουν την προσομοίωση ενός ανθρώπου ειδικού που διαθέτει εμπειρία και γνώση για μια γνωστική περιοχή (π.χ. γιατρού, μηχανικού αυτοκινήτων). Η Prolog χρησιμοποιείται συχνά στην κατασκευή έμπειρων συστημάτων.

16.8.3 Επεξεργασία φυσικής γλώσσας

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