פרק 3: האחדה

3.1 מהי האחדה?

בפרק הקודם נתקלנו לראשונה במושג ההאחדה בהקשר של מציאת הצבות למשתנים. ראינו כיצד באחת התוכניות פרולוג מצא הצבה עבור X על סמך האחדה (או התאמה) בין השאילתא hate(X, harry) לבין ההנחה hate(uncle_vernon, harry).

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

כך למשל, harry ו-harry מתאימים כי הם אטומים זהים, 33 ו-33 מתאימים כי הם מספרים זהים, המשתנים S ו-S מתאימים, והביטויים המורכבים boy(ron) ו-boy(ron) מתאימים. לעומת זאת, harry ו-ron אינם מתאימים כי הם אינם זהים והם אינם מכילים משתנים שבעזרתם ניתן להפוך אותם לזהים.

בעזרת הצבה למשתנים ניתן לראות ש-X ו-hermione מתאימים (נציב hermione עבור X), וכך גם הביטויים המורכבים hate(X, harry) ו- hate(uncle_vernon, harry) (נציב uncle_vernon עבור X). לעומת זאת, hate(Z, harry) ו-hate(ron, Z) אינם מתאימים כי אין הצבה עבור Z שתהפוך אותם לזהים.

כיצד מחפש פרולוג התאמות והצבות למשתנים? התהליך מתבצע על פי ההגדרה הבאה:

אם ביטוי א' וביטוי ב' הם קבועים, אזי הם מתאימים אם ורק אם הם אותו אטום או אותו מספר.
אם ביטוי א' הוא משתנה וביטוי ב' הוא ביטוי כלשהו, אזי הם מתאימים, ומציבים את ביטוי ב' עבור ביטוי א'. ולהיפך, אם ביטוי ב' הוא משתנה וביטוי א' הוא ביטוי כלשהו, מציבים את ביטוי א' עבור ביטוי ב'. אם שניהם משתנים מציבים אותם זה עבור זה ויש להם אותו ערך.
אם ביטוי א' וביטוי ב' שניהם ביטויים מורכבים, אזי הם מתאימים אם ורק אם מתקיימים שלושת התנאים הבאים:
1. יש להם אותו מתאר ואותו מספר מתוארים.
2. כל המתוארים מתאימים בהתאמה (הראשון לראשון, השני לשני, וכולי).
3. ההצבות למשתנים אינן סותרות (אם הצבנו ron עבור X, לא נוכל להציב ערך אחר עבורו במתואר אחר).
שני ביטויים מתאימים זה לזה אם ורק אם נובע על פי שלושת הסעיפים לעיל שהם מתאימים.

נשתמש בהגדרה לעיל כדי להכריע בדבר התאמתם של הביטויים בדוגמאות הבאות. נשתמש במתאר האחדה שקיים בפרולוג: 2/= (שם המתאר: =, מספר המתוארים: 2).

על סמך סעיף 1 בהגדרה נוכל לקבוע התאמה בין קבועים:

?- =(33,34).
No
?- =(aunt_petunia, aunt_petunia).
Yes

שימו לב שניתן לנסח שאילתות אלה בדרך טבעית יותר, כאשר המתאר = נכתב בין המתוארים:

?- X = hermione.

לאור סעיף 2 בהגדרה, אנו מצפים שההאחדה תצליח והמשתנה X יקבל את ערכו של הקבוע hermione:

X = hermione
Yes

כדאי להבהיר בשלב זה את ההבדל בין מתאר ההתאמה = לבין מתאר השוויון =:=, שנתקלנו בו בפרק 2. = מנסה לבצע האחדה בין הביטויים משני צדדיו, ואיננו מבצע השוואה בין ערכיהם המספריים; זה תפקידו של =:=.

?- 9+2 = 9+2.
Yes
?- 9+2 = 11.
No
?- 9+2 =:= 11.
Yes

כאשר מתאימים בין שני משתנים, ערכיהם נקשרים זה לזה. כאשר יוצב ערך באחד, השני יקבל אותו ערך. על כן אין להתפלא על תגובתו של פרולוג (בגרסת SWI-Prolog):

?- X = Y.
X = _G164
Y = _G164
Yes

פרולוג קשר בין שני המשתנים X ו- Y באמצעות כבילתם למשתנה משותף שלישי, _G164 (אין משמעות לשמו של המשתנה המשותף).

לבסוף, דוגמא להתאמה של ביטויים מורכבים על פי סעיף 3 בהגדרה:

?- hates(aunt_petunia, harry) = hates(X, Y).
X = aunt_petunia
Y = harry
Yes
?- hates(aunt_petunia, harry) = hates(X, X).
No

בשתי הדוגמאות אנו מנסים להתאים ביטויים עם אותו מתאר ואותו מספר מתוארים. בפעם הראשונה ניתן לבצע האחדה, אך לא בפעם השניה, שם ההצבות למשתנה X אינן מתיישבות זו עם זו: בעקבות התאמה למתואר הראשון יוצב בו הערך aunt_petunia ולאחר התאמה עם המתואר השני - harry. ההאחדה נכשלת משום ש- X לא יכול לקבל שני ערכים שונים באותו ביטוי.

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

?- child(X) = X.

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

Not enough memory to complete query!

או:

X = child(child(child(…(X)))).

מה קורה כאן?
פרולוג מנסה להציב עבור X ערך אינסופי, ונתקע בלולאה אינסופית עד שהזכרון שלרשותו אוזל.
בבואנו לכתוב תכניות ולהציג שאילתות בפרולוג, חשוב שנזכור תכונה זו של פרולוג על מנת להימנע מלולאות אינסופיות.

מבוא