שפות תכנות — מרחב למידה אישי

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

מהו מפרש (Interpreter)?

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

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

מפרש (Interpreter)

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

מהדר (Compiler)

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

מרכיבי הליבה של מפרש בסיסי

לולאת קריאה-הערכה-הדפסה (REPL)

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

REPL (Read-Eval-Print Loop): לולאה אינטראקטיבית המקבלת קלט (Read), מעריכה אותו (Eval), מציגה את התוצאה (Print), וחוזרת על התהליך (Loop).

קריאה (Read): קבלת קלט מהמשתמש (לרוב ביטוי בשפת היעד) וניתוחו למבנה נתונים פנימי (למשל, עץ תחביר מופשט - AST).
הערכה (Eval): ביצוע הביטוי שנקרא, כלומר חישוב ערכו. זהו לב ליבו של המפרש.
הדפסה (Print): הצגת תוצאת ההערכה למשתמש בצורה קריאה.
לולאה (Loop): חזרה על התהליך שוב ושוב.

ביטויים (Expressions)

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

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

ליטרלים: ערכים קבועים כמו מספרים (לדוגמה: 10, -3.14), ערכים בוליאניים (#t, #f), מחרוזות.
משתנים: הפניות לערכים המאוחסנים בסביבה (לדוגמה: x, my-var).
קריאות לפונקציות / יישום פרוצדורות: ביצוע פונקציה עם ארגומנטים (לדוגמה: (+ 2 3), (my-func 'hello)).
ביטויי תנאי: קביעת מסלול ביצוע על בסיס תנאי (לדוגמה: (if (> x 0) x (- x))).
הגדרות (define) / למדא (lambda): יצירת קשירות חדשות או פונקציות אנונימיות.

הערכה רקורסיבית (Recursive Evaluation)

הליבה של כל מפרש היא פונקציית ה"הערכה" (לרוב נקראת eval או interpret). פונקציה זו מקבלת ביטוי וסביבה (environment), ומחזירה את ערכו של הביטוי. המפתח להערכת ביטויים מורכבים הוא הערכה רקורסיבית: פונקציית ה-eval קוראת לעצמה באופן רקורסיבי על תתי-הביטויים של הביטוי הנוכחי.

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

דוגמה מבנית להערכת ביטוי if:

(eval (if (

פונקציית ה-eval תפעל כך:

תזהה שמדובר בביטוי if.
תעריך את תנאי הביטוי: (eval '(.

בהתאם לתוצאת הערכת התנאי (#t או #f), תבחר את אחד משני הענפים ותעריך אותו: אם התנאי #t: (eval '10 env) אם התנאי #f: (eval '20 env)

דפוס זה חוזר על עצמו עבור כל סוגי הביטויים המורכבים, תוך פירוקם למרכיביהם והערכה רקורסיבית של כל מרכיב. סביבות (Environments) כדי שמפרש יוכל לטפל במשתנים, הוא זקוק למנגנון שישייך שמות (סימבולים) לערכים. זהו תפקידה של הסביבה. סביבה היא מפה (או רשימת קשירות) הממפה שמות משתנים לערכים שלהם. סביבות מאפשרות לנו לממש עקרונות כמו היקף (scope) לקסיקלי. סביבה (Environment): מבנה נתונים (לרוב רשימת קשירות או מפה) המאחסן את ההתאמה בין שמות משתנים לערכים שלהם בהקשר מסוים של ביצוע התוכנית. כאשר פונקציית ה-eval מעריכה ביטוי המכיל משתנה, היא משתמשת בסביבה הנוכחית כדי למצוא את ערכו של המשתנה. כאשר נוצרים היקפים חדשים (לדוגמה, בביטוי let או בעת קריאה לפונקציה), נוצרות סביבות חדשות המרחיבות את הסביבה הקיימת או מקושרות אליה. הערכה רקורסיבית וניהול סביבות: זהו אחד הנושאים המרכזיים והמורכבים ביותר בבניית מפרש, ולרוב מוקד לשאלות במבחנים. ההבנה כיצד פונקציית ה-eval עוברת באופן רקורסיבי על עץ התחביר המופשט (AST) וכיצד היא מעבירה ומשנה את הסביבה בכל שלב היא קריטית. טעות בניהול הסביבה (לדוגמה, אי-לכידת הסביבה הנכונה עבור פונקציית למדא, או אי-הסרת סביבה מקומית לאחר סיום ביטוי let) תוביל לשגיאות לוגיות קשות, כגון שימוש בערך שגוי של משתנה או חוסר יכולת למצוא משתנה כלל. יש לוודא שהסביבה הנכונה תמיד זמינה לכל תת-ביטוי, ושהיקף המשתנים נשמר כראוי (לרוב היקף לקסיקלי). שאלות לדיון מהם היתרונות והחסרונות העיקריים של שפת תכנות מפורשת לעומת שפה מהודרת? תנו דוגמאות לשימושים אופייניים לכל אחת. הסבירו כיצד לולאת REPL תורמת לתהליך הפיתוח והניפוי שגיאות של שפות תכנות. אילו אתגרים עשויים להתעורר במימוש שלב ה"קריאה" (Read) עבור שפה מורכבת? תארו כיצד הייתם מרחיבים מפרש בסיסי (כמו זה שראינו) כדי לתמוך בביטוי let* (שבו קשירות יכולות להתייחס לקשירות קודמות באותו let*). אילו שינויים נדרשים בפונקציית ה-eval ובניהול הסביבה? הסבירו את ההבדל בניהול הסביבה בין הערכת ביטוי (define x 10) לבין הערכת ביטוי ((lambda (y) (+ y x)) 5), בהנחה ש-x כבר הוגדר בסביבה החיצונית. התייחסו למושג "סגור" (closure). נקודות לתשובת מודל יתרונות/חסרונות מפרש מול מהדר: מפרש - גמישות, ניפוי שגיאות קל, ניידות, איטי יותר. שימושים: סקריפטים, שפות דינמיות. מהדר - ביצועים מהירים, אופטימיזציות, זמן הידור. שימושים: מערכות הפעלה, משחקים. תרומת REPL: אינטראקטיביות, בדיקה מהירה של קטעי קוד, ניפוי שגיאות בזמן ריצה, למידת השפה. אתגרי "קריאה": טיפול בתחביר מורכב, שגיאות תחביר, ניתוח לקסרי ופרסינג. הרחבה ל-let*: דורש הערכה סדרתית של כל קשירה ב-let*. כל קשירה חדשה מרחיבה את הסביבה שנוצרה על ידי הקשירות הקודמות באותו let*, לפני הערכת גוף הביטוי. פונקציית מצאתם טעות או שחסר משהו?