תכנות לוגי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

תכנות לוגי מבוסס על תחשיב הפרדיקטים ושונה מפרדיגמות התכנות המקובלות, המבוססות על ארכיטקטורת פון נוימן. התכנות הלוגי מבוסס בראשיתו על האקסיומה: A \quad if \quad B_1 \and B_2 \and... B_n. רוברט קוואלסקי הסיק שאקסיומה זו יכולה להיקרא כפרוצדורה רקורסיבית, כך ש A הינו הראש של הפונ' וכל B_i הינו חלק מהגוף. כלומר, כדי לפתור (להריץ) את A, יש לפתור (להריץ) את  B_1 \and B_2 \and... B_n.

היסטוריה[עריכת קוד מקור | עריכה]

התכנות הלוגי במובן הכללי שלו, נתן בתחילה מקום למספר מימושים, כגון אלו של פישר בלאק (1964), ג'ימס סלייגל (1965), וקורדל גרין (1969). מימושים אלו היו בעצם מערכות ל"פתירת שאילתות" כמו ה Advice Taker שהוצג במאמרו של ג'ון מקארטי(1958). למרות זאת רק ב 1969, אבסיס, שנכתבה על ידי פוסטר ואלקוק, הייתה לשפה הראשונה שעסקה בתכנות לוגי והוכרזה כשפת תכנות.

במובן הצר יותר של התכנות הלוגי, ניתן למצוא אותו כבר בדיונים הראשונים על בינה מלאכותית בסוף שנות ה 60 ותחילת ה 70. למרות שהייתה אכן מבוססת על לוגיקה, פלאנר, אשר פותחה ב MIT הייתה השפה הלוגית הראשונה שנבנתה על פרדיגמת התכנות הפרוצידורלי. המימוש הידוע ביותר של הפלאנר הינו המיקרו-פלאנר שנבנה על ידי ג'רי סוסמן, אגווין חארניאק, וטרי וינוגרד. השימוש בו היה למימוש השפה הטבעית של וינוגרד, והבנתה של תוכנת SHRDLU, דברים אשר היוו התקדמות רצינית ביותר באותה התקופה. מפלאנר עצמה התפתחו בנוסף גם השפות QA-4, POPLER, Conniver, QLISP, ETHER.
הייס וקוואלסקי, גם הם ניסו לקבל את גישת ההכרזה הלוגית לייצוג מידע שהוצגה על ידי פלאנר בצורתה הפרוצידורלית. הייס(1973), פיתח שפת משוואות, GOLUX, שבה ניתן לקבל פרוצדורות שונות באמצעות שינוי של אלגוריתם מציאת הפתרון לשאילתות. קוואלסקי לעומת זאת הראה כיצד ניתן לפתור באמצעות פתרון רדוקטיבי של SL-resolution את השאילתות המוצגות. לבסוף קוואלסקי, בשיתוף עם קולמיראור בעצם בנו את פרולוג על בסיס רעיונות אלו. מכאן והלאה פותחו גם ALF, Godel, Fril ועוד שפות נוספות.
בשנת 1997 הוקמה ועדת "מייסדי התכנות הלוגי" שמטרתה הייתה לתת ל 15 האנשים הללו את מקומם הראוי בהיסטוריה בתור חלוצי התכנות הלוגי.

מאפייני שפה[עריכת קוד מקור | עריכה]

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

1. תחביר -

סט של עובדות, וחוקים המגדירים יחסים בבעיה המוצגת.

2. סמנטיקה -

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

3. סמנטיקת התפעול -

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

תחשיב יחסים בתכנות הלוגי(המובן הרחב)[עריכת קוד מקור | עריכה]

תחביר: סמלים אטומיים: קובעים ומשתנים.

קבועים[עריכת קוד מקור | עריכה]

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

משתנים[עריכת קוד מקור | עריכה]

משתנים ייוצגו באות ראשונה גדולה לדוגמה: X,Y,DingDong, TheWitchIsDead.

ביטוי[עריכת קוד מקור | עריכה]

קבועים או משתנים ייחודיים נקראים ביטוי.

נוסחה אטומית[עריכת קוד מקור | עריכה]

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

predicate-symbol(term1, term2,...termn)

כל נוסחה אטומית הינה פונ'. הרצה של כל פונ' תעשה על ידי השאילתה שתנתן.

עובדה[עריכת קוד מקור | עריכה]

עובדה הינה הגדרה של n אטומים כך ש n>=1 אשר עומדים ביחס מסוים. נסתכל בקטע הקוד הבא:

father(abraham, issac)

שורה זאת לוקחת את שני הקבועים (נשים לב אות קטנה בתחילת המילה) abraham, issac וקובעת שהם עומדים ביחס Father. (כלומר עובדה)

father(Abraham, issac)

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

תבנית[עריכת קוד מקור | עריכה]

לכל פרדיקט שנבנה קיימת תבנית, התבנית בנויה ממספר ביטויים ותוגדר על ידי מספר זה. לדוגמה מספר הביטויים של father שהוגדר קודם הינו 2. אם נגדיר מחדש את father עם מספר ביטויים שונה הפרדיקט לא יוגדר כאותו פרדיקט. נגדיר אותו כ father/1 father/3 father/4 וכדומה.

חוק[עריכת קוד מקור | עריכה]

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

father(X, issac) :- X=abraham

במקרה זה נגיד כי X עומד ביחס father עם issac אמ"מ X=abraham. נשים לב שהפרדיקט "=" כפי שאמרנו קודם הינו פרדיקט אשר בנוי לתוך התכנות הלוגי.
ראש החוק הינו החלק הראשון אשר מגיע לפני הסימן -: בעוד שהחלק השני הינו הגוף. הגוף יכול להיבנות באמצעות יותר מחוק אחד ולהיות מופרדת בפסיקים כמו שנראה בהמשך. כל "," כזה הינו הפרדיקט and. כלומר כדי שהראש יתן ערך true יש לדאוג לכך שכל הערכים בגוף המופרדים בפסיקים יתנו ערך דומה.

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

שאילתה[עריכת קוד מקור | עריכה]

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

?- father(X,Y)

שאילתה זאת תחזיר לנו X=abraham, Y=issac. המשך הרצה של השאילתה עם האקסיומה היחידה שנתנו מעוד מועד יחזיר false. זאת מאחר שאין עוד ערכים שיאמתו את השאילתה. נשים לב כי הרצה של שאילתות יכולה גם להכיל קבועים בלבד ולא משתנים ואפילו להכיל מספר ביטויים שונים להוכחה.

מוסכמות כתיבה[עריכת קוד מקור | עריכה]

  • הגדרת פרוצדורות תעשה בבלוק יחיד ומופרד מפרוצדורות נוספות.
  • כל הגדרה של פרוצדורה תחל בחוזה אשר יתאר את חתימתה (Sygnature specification) ואת היחס שהיא מגדירה (Purpose declaration).
  • עובדות וחוקים בהגדרת פרוצדורה יהיו ממוספרות.

המפרש[עריכת קוד מקור | עריכה]

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

אלגוריתם מענה על שאילתה[עריכת קוד מקור | עריכה]

קלט[עריכת קוד מקור | עריכה]
שאילתה- Q=?-Q1,Q2,...Qn
תוכנית- P
סט ריק - s
איטרטור- is
אלגוריתם[עריכת קוד מקור | עריכה]

1. אם Q=?-true,...,true החזר את s וצא.
2. החלף את שמות המשתנים הקיימים בשמות חדשים.
3. בחר את ביטוי השאילתה הבא שערכו אינו true באמצעות האיטרטור is וקרא לו G
4. בחר את החוק הבא וקרא לו A כך ש

unify(A,G)=s2

אם נמצא החוק המתאים הרץ שאילתה חדשה ללא G עם הסט החדש ואיטרטור חדש.
5. אם ישנם עוד חוקים לאיטרטור, עבור לחוק הבא באיטרטור עם אותם הנתונים.

פלט[עריכת קוד מקור | עריכה]

סט המקיים את ההוכחה או סט ריק.

עצי הוכחה[עריכת קוד מקור | עריכה]

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

  1. אברי העץ מכילים את השאילתות.
  2. ענפיו מסומנים במספרי חוקים וחישובי האחדת תבניות.
  3. איבר הבסיס של העץ הינו השאילתה לפתרון ויסומן על ידי Q. כל תת-עץ הינו דרך הוכחה של איבר הבסיס של אותו העץ.
  4. ענף בעץ בעל חישובים נכונים לכל אורכו מהווה הוכחה של השאילתה. מה שהופך את העץ לעץ הצלחה.
  5. אם עץ ההוכחה סופי ואין עליו מסלולי הוכחה נכונים העץ יקרא עץ כישלון סופי.
  6. אם עץ ההוכחה אין סופי וקיים עליו מסלול הוכחה אמיתי כלשהו העץ יקרא עץ הצלחה אין סופי.
נתבונן בדוגמה הבאה ונבנה עץ הוכחה:


Sygniture: father(F,S)/1
1. father(abraham, issac).
2. father(haran, lot).
3. father(haran, yiscah).
4. father(haran, milcah).


Sygniture: male(P)/2
1. male(issac).
2. male(lot).


Sygniture: female(P)/3
1. female(milcah).
2. female(yiscah).


Sygniture: son(C,P)/4
1. son(X,Y) :- father(Y,X), male(X).


Sygniture: daughter(C,P)/5
1. daugther(X,Y) :- father(Y,X), female(X).


Q= ?- son(S,haran).

אמצע

כפי שניתן לראות העץ הוא עץ הצלחה, תוצאת התחלופות בענף ההצלחה היא:

{X1=S, Y1=haran}=>{S=lot} => {X1=lot, Y1=haran, S=lot}

לבסוף ההגבלה למשתני השאילתה עצמה מחזירה את התשובה, S=lot.

דטרמניסטיות בתכנות הלוגי הבנוי על תחשיב היחסים[עריכת קוד מקור | עריכה]

בהינתן שאילתה Q ותוכנית P ההכרעה האם P מספק את Q היא דטרמניסטית:

עץ הוכחה בנוי ממספר אברים אשר כוללים שאילתות ונוסחאות אטומיות. הנוסחאות האטומיות מורכבות מפרדיקטים, קבועים אשר נמצאים בתוך התוכנית ובשאילתה וכמובן ממשתנים. מכאן שמספר האטומים ומספר השאילתות הקיימות הוא סופי. כלומר, המסלולים בעץ ההוכחה הם סופיים וניתן להכריע בשאלה האם P מספק את Q.

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