תכנות לוגי

ראינו ב OCaml עקרונות של תכנות פונקציונלי שהוא מופע של פרדיגמת declarative programming שמבוסס הצהרות וגם את while שהיא שפת התכנות הפרוצדורלית תחת פרדיגמת imperative programming הבסיסית ביותר.

ישנם מופעים נוספים תחת הפרדיגמות השונות ואחד מהם הוא התכנות הלוגי תחת פרדיגמת ה declarative programming

Prolog

פרולוג היא שפת תכנות לוגית שפותחה במקור לכתיבת יישומי בינה מלאכותית. השפה היא שלמה טיורינג, כלומר ניתן לממש באמצעותה כל מה שאפשר לממש בשפות התכנות הנפוצות. שמה נגזר מצירוף המילים PROgramming LOGic.

ביטויים

1. מספרים
2. אטומים - ביטויים המתחילים באות תחילית lower case או בגרשיים elephant, xYZ, a_123, ’Another pint please . (נקראים גם atomic term)
3. משתנים- מתחילים באות גדולה
4. ביטויי קריאה (compound term) - מורכב מאטום ומספר ביטויים למשל f(t1,t2...) .
   • אטומים וביטויי קריאה נקראים predicates
   • ביטויי קריאה בלי משתנים נקראים ground terms
5. functors - זוג סגור של שמכיל $\text{<autom, num of variables>}$ למשל <a,5> זה אטום שמכיל 5 ארגומנטים. נוכל להשתמש בkeyword השמור בשפה functor כדי לבדוק האם ביטויי קריאה שהגדרנו מקיים את ״תנאי״ הפנקטור למשל :

functor(a(x,y,z,w,v),a,5) -> will return true

6. רשימות (נתמקד בהמשך)

דגשים:

• כל פקודה נגמרת בנקודה.
• בפרולוג מגדירים פרדיקטים כעובדות
• שאילתא בודקת האם היחס המבוקש נמצא בפרדיקט שהגדרנו

פסוקיות

פסוקית ב prolog היא אחת מהצורות הבאות

1. עובדות
   
2. חוקים- נכתבים בסינתקס cute(x):-cat(x) המשמעות של :- זה if או is implied by.

סינתקס:

rule_name(object1, object2, ...) :- fact/rule(object1,
 object2, ...)
Suppose a clause is like :
P :- Q;R.
This can also be written as
P :- Q.
P :- R.

If one clause is like :
P :- Q,R;S,T,U.

Is understood as
P :- (Q,R);(S,T,U).
Or can also be written as:
P :- Q,R.
P :- S,T,U.

התו ״,״ מייצג את הפסוק and .

לדוגמה:
happy(lili) :- dances(lili).
hungry(tom) :- search_for_food(tom).
friends(jack, bili) :- lovesCricket(jack), lovesCricket(bili).
goToPlay(ryan) :- isClosed(school), free(ryan).

3. פרדיקטים- יהי f/n פנקטור. הפרדיקט שלו הוא אוסף הפסוקיות ש f מופיע בראשון.

תוכנית- בפרולוג, תוכנית היא רצף של פסוקיות. נסתכל על תוכנית שמגדירה עובדות על ה״עולם״ וחוקים

parent(pam,bob)
parent(tom,bob)
parent(tom,liz)
parent(bob,ann)
parent(bob,pat)
parent(pat,jim)


*if X is parent of Z then he is ancestor of Z*
ancestor(X,Z) :- parent(X,Z) 

*if X is parent of Y and Y is ancestor of Z then X is ancestor of Z*
ancestor(X,Z) :- parent(X,Y), ancestor (Y,Z)

כעת נראה מה קורה כשננסה לבדוק האם חוקים מתקיימים למשל נקבל ש parent(pam,bob) יחזיר true ו ancestor(pam,ann) יהיה query של החוק הראשון שהוא נתקל בו בקוד (הסדר משנה) ולכן הוא ״מופע״ של החוק הראשון וצריך לשאול האם parent(pam,ann) מתקיים, מאחר והתשובה היא לא הוא ילך לחוק השני וינסה למצוא התאמה עבור השאילתה הזו. המקרים היחידים שצריך לבדוק הם parent(pam,bob) כי רק במקרה הזה X מתקים לערך השאילתה ובמקרה הזה מתקיים גם ש ancestor(bob,ann) הוא true כי parent(bob,ann) מתקיים.

נגדיר את מה שעשינו בצורה פורמלית-

הגדרה:
מופע של פסוקית c הוא פסוקית $c^{\prime }$ המתקבלת מ c על ידי החלפת המשתנים בביטויים כלשהם.

הגדרה: G (השאלה) נכונה ב P (תוכנית) אם יש C (חוק) ב P ומופע שלה I (שאילתה) כך ש
1) הראש של I זהה ל G
2) הגוף של I נכון ב P
עבור: a :- b1,...,bn מתקיים ש a הוא הראש והשאר זה הגוף.

הסינתקס לשאילתה הוא מהצורה- $?-bigger(elephant,monkey).$ נוכל להחליף את אחד הערכים במשתנה ולקבל אילו ערכים נוכל לשים עבור המשתנה הזה מהעולם כדי שהשאילתה תהיה נכונה

אם אין יותר פתרונות יוחזר NO.

שיוויון אריתמטי ו שיוויון סינתקסטי
== - מייצג שיוויון סינתקסטי
=:= - מייצג שיוויון אריתמטי

למשל - 3+4 =:= 2+5 יחזיר true אבל אם נשים == נקבל false.

ניתן לבדוק שיווין unifiable עם האופרטור = . למשל $3+4=3+X$ יחזיר X=4 שכן אם נחליף X ב 4 נקבל ביטויים שווים ברמת הסינתקס.

assert

כדי להוסיף עובדות ל prolog ניתן להשתמש גם ב assert שזו מילת מפתח שמגדירה predicates. למשל assert(parent(pam,bob)) מגדירה פרדיקת parent שיש לו ״עובדה״ ש pam,bob יחזיר עבור הפרדיקט true.

באדום הגדרנו את העובדות , לאחר מכן הפעלנו שאילתות.

הכנסת עובדות לבסיס הנתונים
בנוסף לפקודה assert ניתן להכניס עובדות מתוך קובץ pl. ולאחר מכן טוענים את העובדות בעזרת הפונקציה consult(file name). בסיס הנתונים שבו שמורות כל העובדות נקרא logicbase.

פרדיקטים

פרדיקט מוגדר על ידי השם ומספר הארגומנטים שלו:

שני פרדיקטים בעלי אותו שם אך בעלי מספר שונה של ארגומנטים נחשבים שני פרדיקטים שונים.

פרדיקט יכול להיות גם עם ארגומנט אחד או בלי ארגומנטים בכלל (על ידי המילה השמורה .pred).

כפי שכבר ציינו ארגומנט יכול להיות מהצורה הבאה

1. מספר
2. אטום - קבוע טקסט המתחיל באות קטנה או שמתחיל ומסתיים ב '-'.
3. משתנה - מתחיל באות גדולה או הסימן _ (משתנה אנונימי)
4. מבנה

פרדיקטים ופונקציות משמשות אותנו לייצוג עובדות , מבני נתונים וביצוע חישובים כמו בכל שפה.

פרדיקט עם משתנים
ניתן לבצע שאילתות עם פרמטרים כדי לקבל מידע למשל:

זה שאילתה שמחזירה את כל מי שיש לו יחס parent עם liz. זה יחזיר בהתחלה רק את הראשון ואם נרצה על ידי לחיצה על ; נקבל עוד תשובות.

ניתן גם לבצע שאילתות עם מספר משתנים

ניתן להרגיש גם פרדיקט על משתנה, משמעותו שכל ארגומנט שיתקבל בפרדיקט מקיים את הפרדיקט.

or , and:
שאילתות and נבצע עם ','

שאילתת or נבצע עם ';'

• הערות בprolog נעשות עם % או עם /*
• פרדיקט מיוחד בפרולוג הוא write שמאפשר כתיבה למסך ומחזיר תמיד true.
• פרדיקט חשוב נוסף הוא halt שעוצר את התוכנית.

מבנה

ניתן להשתמש בפונקציות כייצוג של מבנה המחבר מספר פרמטרים ביחד.

מזכיר מאוד SQL שהיא גם שפת תכנות לוגית.

נשים לב שניתן לשים פרמטרים היכן שרוצים לגלות מי מקיים את הפרדיקט עבור מי שאינו משתנה. ״תחזיר לי את כל ה X שהם בני 28 בבר אילן״.

נתבונן בדוגמה הבאה:

?- consult(door)
true.

?- location(apple, kitchen)
true.

?- location(kitchen, apple)
false.

• הגדרנו 3 חדרים.
• יחס של דלתות בין חדרים.
• מיקומים של חפצים בחדרים השונים.

ניתן לבצע binding ולראות את כל החדרים שיש לנו

נשים לב לתופעה מעניינת- הפרדיקט אינו דו כיווני, כלומר הגדרנו שיש door(office, hall) ומן הסתם ששאילתה כזו תחזיר אמת אבל היינו מצפים שגם הפוך יעבוד אם נרצה ובמקרה הזה נקבל על השאילתה door(hall, office) את התוצאה false.

כיצד נוכל להפוך את זה לסימטרי בלי פשוט להגדיר עוד ״עובדה״. לשם כך משתמשים בחוקים.

חוקים

עובדות נתנו לנו את הדרך לתאר יחסים ועובדות. ניתן גם להגדיר חוקים שנותנים לנו את האפשרות להגדיר ״משפטים״ למשל - if _ then _ also באמצעות התחביר הבא

• head :- body.
  • המשמעות היא if body then head

כעת כדי לטפל בבעיה שהדלת דו צדדים נוכל להוסיף את שני החוקים הבאים

בעצם אמרנו שאם door(X,Y) אז connect(X,Y) וגם היחס ההפוך door(Y,X) נמצא בconnect.

כעת באמצעות שימוש בשאילתה על connect היינו מקבלים את הדרוש.

היינו יכולים גם ליצור חוק על door על ידי
door(X,Y) :- door(Y,X)

סמנטיקה:
בהינתן P:-Q,R ניתן לומר:

1. P הוא אמת רק אם Q וגם R הוא אמת.
2. מ Q ומ R נובע P.
3. כדי לפתור את בעיה P, יש לפתור ראשית את תת הבעיה Q ולאחר מכן את תת הבעיה R.
4. כדי לספר את P, יש לספק ראשית את Q ולאחר מכן לספק את R.

אריתמטיקה

הוסיפו לפרולוג אפשרות לפרש ביטויים אריתמטיים אבל מכיוון שהשפה עובדת בשיטת התאמת מחרוזות (pattern matching) צריך לכתוב במפורש שאנחנו רוצים לפרש את הביטוי עם האופרטור is:

• פרולוג גם תומכת בפעולות השוואה אריתמטיות
  

'=' רגיל משווה בין מחרוזות. למשל אם נרשום A+1 = 2+B אז פרולוג ישלים לנו את A = 2 ו B=1 בגלל שזה מה שהם צריכים להיות כדי שהמחרוזות יהיו שוות.

GCD
נרצה למצוא מי GCD כלומר המחלק המשותף הגדול ביותר. למשל gcd(160,80,D) יתן D=80.

כדי לפתור את זה נצטרך להגדיר מספר חוקים:

gcd(X,X,X).
gcd(X,Y,D) :- 
	X < Y,
	Y1 is Y - X,
	gcd(X, Y1, D).

gcd(X,Y,D) :-
	X > Y,
	gcd(Y, X, D)

בעצם אמרנו

1. אם שני המספרים ב gcd הם אותו דבר אז המחלק הגדול ביותר הוא המספר עצמו.
2. אם $X<Y$ וגם קיים $Y_1=Y-X$ שמקיים ש $gcd(X,Y_1,D)=TRUE$ אז גם $gcd(X,Y,D)$ הוא true.
3. אם $X>Y$ אז פשוט נבדוק את ההופכי ונחזור למקרה 2.

לולאות

נדגים בנייה של לולאה באמצעות הגדרות רקרוסיביות:

sumto(1,1)
sumto(N,S) :- N>1 , M is N-1, sumto (M,R), S is R+N

S הוא הסכום של כל המספרים מ 1 עד N . הגדרנו חוק בסיס שה sum(1,1) כלומר הסכום של 1 הוא 1.
לאחר מכן הגדרנו חוק על כל מקרה אחר שמחייב ש N>1 וגם עבור משתנה זמני M=N-1 יתקיים שהסכום של כל המספרים מ1 עד ל M יהיה R ולבסוף צריך שיתקיים S=R+N . בעצם הגדרנו כאן לולאה באמצעות כללי רקורסיה.

למשל עבור sum(4,10) נקבל true וכפי שאמרנו נוכל לקבל את הערך עצמו אם נשאיר את S כנעלם למשל sum(4,S) ״יחזיר״ S=10.

רשימות

דבר ראשון מגדירים $\text{member(X,[X|L])}$ כלומר תמיד יתקיים הכלל ש X הוא חבר ברשימה שהוא האיבר הראשון שלה. נגדיר גם את כלל $\text{member(X,[Y|L]) :- member(X,L)}$ כלומר X הוא חבר ברשימה ש Y הוא האיבר הראשון שלה אם הוא חבר בתת הרשימה L.

נקבל למשל ש $\text{member(1,[1,2,3,4])}$ יחזיר true ואבל $\text{member(5,[1,2,3,4,])}$ יחזיר false.

נראה כעת קוד דוגמה שממיין מערך בסדר הפוך:

simplsort(X,Y) :- permut(X,Y), sorted(Y).

sorted([]).
sorted([_]).
sorted([A,B | X]) :- A =< B, sorted([B | X]).

permut([], []).
permut(X, [A | Y]) :- concat(X1, [A | X2], X), concat(X1, X2, X3), permut(X3, Y).

concat([], Y , Y).
concat([A|X],Y, [A|Z]) :- concat(X,Y,Z)

הכלל simplesort מבקש ש sorted(Y) וגם permut(X,Y) יתקיימו.

sorted מוגדר כ true על רשימה ריקה ואחרת מוגדר ממויין אם כל איבר A שבא לפני B במערך יקיים ש $A\le B$ .
permut מוגדר כ true על שני מערכים ריקים אחרת הוא רוצה לבדוק האם מערך X הוא פרמוטציה של $[A|Y]$ על ידי כך שהוא מחייב ש A נמצא איפשהו ב X והוא בודק את זה על ידי הכלל concat שבודק האם שרשור של שני מערכים נותן את המערך השלישי.

סינטקס

• ניתן לכתוב רשימות באופן הבא
  • 
  • וגם
  • H מייצג איבר ברשימה ו T את המשך הרשימה (כמו ב OCaml).
  • $[]$ זאת הרשימה הריקה.

דוגמה 1
נכתוב פונקציה שמחזירה את אורך הרשימה:

size([],0).
size([H|T], N) :- size(T, N1), N is N1 + 1.

דוגמה 2
נכתוב פרדיקט שמקבל רשימה ומשתנה ומחזיר האם משתנה נמצא ברשימה

isin(X,[X|_]).
isin(X,[_|T]):- intin(X,T).

• אם המערך במקום האפס הוא האיבר שאנחנו מחפשים נחזיר true אם הם שקולים (הכלל הראשון)
• אחרת, (בגלל שזה אחרת היא כי פרולוג בודק את העובדות לפי הסדר אז קודם כל הוא יבדוק את הכלל הראשון ואז את הכלל השני). תבדוק האם היא בתת הרשימה T. אם T הוא הרשימה הריקה זה יעצור אוטומטי.

דוגמה 3
נכתוב פרדיקט שמקבל שני רשימות ומשתנה נוסף ומחזיר במשתנה הנוסף את השרשור של שתי הרשימות.

concat([],L,L).
concat([X|L1], L2, [X|L3]) :- concat(L1,L2,L3)

במילים: אם L3 הוא שרשור של L1 ושל L2, אזי אם נוסיף איבר X להתחלה, נוכל להגיד כי $[X|L_1]$ ו L2 זהים יחד ל $[X|L_3]$ .

צורת חשיבה שלא מזכירה תכנות אימפרטיבי כמו שאנחנו רגילים, החשיבה ה״לוגית״ היא שונה מהחשיבה הסדרתית של התכנות האימפרטיבית והיא מכריחה אותנו לכמת את הבעיה לפרדיקטים , משימה שלא תמיד תהיה פשוטה.

דוגמה 4
נכתוב פרדיקט שמקבל רשימה של מספרים ומשתנה נוסף ומחזיר במשתנה סכום הרשימה

sumlis([],0).
sumlis([H|T], N) :- sumlis([T],N1), N is N1 + H

1. אם הרשימה ריקה הסכום הוא 0
2. אם יש רשימה מהסגנון של השרשור $[H|T]$ אז הסכום יהיה N אם הסכום של שאר הרשימה T הוא N1 וגם $N=N_1+H$ .

על פניו נראה נכון מבחינה לוגית, אבל אפילו על קלט קצר נקבל

הסיבה שזה עובד ככה היא בגלל השיטה שבה prolog עובד כדי להבין בגלל מיהו ה N . השיטה נקראת backtracking וזאת שיטה שיכולה להיות בזבזנית כפי שנראה בהמשך.

Backtracking

איך prolog מוצאת תשובות לשאילתות? השאלה הזאת תעזור לנו גם להבין איך להגדיר את השאילתות שלנו בצורה יותר יעילה כפי שראינו בדוגמה הקודמת.

נסתכל על הדוגמה הבאה

alert(X, normal) :- X<3
alert(X, alert1) :- X>3, X<6.
alert(X, alert2) :- X>6.

ניתן לראות שהוא מחזיר לי ערכי Y לפי המספר שהבאנו. נשים לב שאם אין לו עוד תשובה להחזיר לשאילתה הוא מחזיר false.

נשים לב שכאשר אנחנו מבקשים עוד פתרונות עם ; הוא ירוץ על השאילתות הנוספות ברשימה לפי הסדר.

באמצעות הפקודה trace נוכל לראות את מהלך הקריאות של prolog כאשר הוא מחפש תשובה לשאילתה.

נפעיל trace על השאילתה alert(2,Y) , Y = alert1 שאמורה להחזיר false בגלל ש X<3 .

בעצם prolog בונה מעין עץ החלטות לפי האפשרויות ש Y יכול לקבל.

ניתן לראות שהוא מנסה להציב כל אחד מהאפשרויות עבור Y ואז לראות האם ההצבה הזאת מקיימת את תנאי השאילתה. אם הוא נכשל הוא עובר לאפשרות הבאה עד שהוא מוצא אפשרות או עד שהוא פסל את כל האפשרויות ואז יחזיר false.

נשים לב שכל פעם מנסה לספק את השאלתה השמאלית ולאחר מכן לספק את הימנית. יש שאילתות כמו במקרה הזה שאם נצליח לספק את התנאי הראשון אין מה להמשיך לבדוק את שאר ההחלטות המקבילות בעץ כי אין חפיפה בין המקרים. למשל אם 2<3 אין מה לבדוק את המקרים האחרים במקרה הזה כי אנחנו יודעים ש Y צריך להיות normal בהכרח ולא יכול להיות מקרים אחרים.

כדי לקטוע את פרולוג מלבצע בדיקות מיותרות בעץ ההחלטות נשתמש באופרטור '!' . אופרטור זה תמיד מחזיר true. באופן פורמלי:

אומר שאם $B_1,\dots B_m$ מתקיים אז יתבצע החיתוך של העץ וכל הפתרונות שלא מקיימים את הנ״ל לא יבדקו בחיפוש.

כדי לתקן את הדוגמה הקודמת נעשה

alert(X, normal) :- X<3 !.
alert(X, alert1) :- X>3, X<6 !.
alert(X, alert2) :- X>6 !.