פרולוג/מבוא ללוגיקה ולשפות תכנות לוגיות

ישנן 4 פרדיגמות של שפות תכנות:

ויקיפדיה: שפת תכנות

1. תכנות תהליכי (Procedural programming) - שפות כגון שפת C, Pascal.
2. תכנות מונחה-עצמים (Object-oriented programming) - שפות כגון C++, Java, פייתון.
3. תכנות פונקציונלי (Functional programming) - שפות כגון APL, Lisp, Scheme.
4. תכנות לוגי (Logic programming) - שפות כגון פרולוג, מרקורי.

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

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

היסק לוגי

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

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

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

• אם
• כל
• רק
• או
• וגם
• לא

כלומר ניתן להרכיב משפט חסר כל משמעות יומיומית, אשר יהיה תקף לוגית:

השמיים עשויים מברזל,

כל ברזל נמס בסוכר.

לכן השמיים נמסים בסוכר.

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

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

פרדיקט (predicate)

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

כל פרמטר של כל פרדיקט יכול להיות כל אחד מאלו:

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

דוגמה

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

jew(abraham).
jew(_someone):-
     mother(_mother,_someone),
     jew(_mother).

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

הצרנה

ויקיפדיה: הצרנה

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

• "כל הציפורים יודעות לעוף"

  יודע_לעוף(X):-ציפור(X).

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

• "כל הדגים יודעים לשחות"

  יודע_לשחות(X):-דג(X).

• "כל הדגים בעלי הכנפיים יודעים לעוף"

  יודע_לעוף(X):-דג(X), בעל_כנפיים(X).

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