|
פרולוג היא שפה הצהרתית, דקלרטיבית. כשאנו חושבים על תכנית בפרולוג, אנחנו חושבים מה להגיד, ולא מתעכבים יותר מדי על איך. בפרק זה ראינו לראשונה כי גם אם האספקטים הפרוצדורליים אינם בראש מעיניו של המתכנת בפרולוג, יש בהחלט לתת עליהם את הדעת.
ההגדרה התמימה למראה wizard :- wizard סיבכה אותנו בלולאה אינסופית, וכעת נראה דוגמאות נוספות של מלכודות פרוצדורליות הטמונות בשימוש ברקורסיה.
ניזכר בתכנית מהסעיף הקודם שעסקה בהגדרת "מיהו קוסם", ונציג לה שתי שאילתות:
wizard(X) :- known_wizard(X).
wizard(X) :-
parents(Y,Z,X),
wizard(Y),
wizard(Z).
?- wizard(sirius_black).
Yes
?- wizard(harry_potter).
Yes
| השאילתא מוכחת על בסיס החוק הלא רקורסיבי, על סמך העובדה שסיריוס רשום כקוסם מוכר. |
| השאילתא מוכחת בהסתמך על הסעיף הרקורסיבי של ההגדרה, על סמך העובדה ששני הוריו של הארי פוטר הנם קוסמים מוכרים. |
שימו לב לקוד האינטראקטיבי.
כעת נשנה את התכנית על ידי החלפת סדר החוקים של wizard, והחלפת סדר הטענות בגימום בגוף החוק הרקורסיבי שלו:
wizard(X) :-
wizard(Y),
wizard(Z),
parents(Y,Z,X).
wizard(X) :- known_wizard(X).
מבחינה הצהרתית שתי התכניות זהות, הן אומרות בדיוק אותו דבר. אך מבחינה פרוצדורלית הן שונות בתכלית, כפי שרואים מהתשובות של פרולוג לשתי השאילתות שהצגנו קודם:
?- wizard(sirius_black).
ERROR: Out of local stack
?- wizard(harry_potter).
ERROR: Out of local stack
השינויים שעשינו גורמים לתכנית להיקלע ללולאות אינסופיות, אפילו בשאילתא הראשונה שאיננה מצריכה כלל שימוש ברקורסיה לשם הוכחתה!
האם ברור לכם כיצד גרמנו לפרולוג להסתבך בלולאות אינסופיות?
הריצו trace על השאילתות שהצגנו וראו בדיוק מה קורה בעת הנסיון להוכיח אותן.
כשאנו כותבים תכניות בפרולוג עלינו לזכור שמנגנון ההוכחה של השפה קורא את התכנית שורה אחר שורה מלמעלה למטה, עובר על השורות משמאל לימין ועושה שימוש בנסיגה (backtracking) אם הוא נקלע למבוי סתום. כפי שראינו, לסדר הכתיבה תיתכן השפעה מכרעת על התוצאות, ויש לקחת זאת בחשבון.
כלל האצבע לכתיבה בטוחה של חוקים רקורסיביים הוא לכתוב את תנאי העצירה לפני הסעיפים הרקורסיביים, ולמקם את הקריאות הרקורסיביות בתוך טענות גימום בסוף הגימום.
|
