יחידה 6: מצב וזיכרון: מפרשים מבוססי Store

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

הצורך ב-Store: מעבר ממודל פונקציונלי למודל עם מצב

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

במפרש מבוסס Store, הסביבה (Environment) כבר לא ממפה שמות משתנים ישירות לערכים, אלא להפניות (References) לכתובות ב-Store. הערכים עצמם נשמרים בתאים ב-Store.

מושגי יסוד: הפניות, השמה ותופעות לוואי

הפניות (References)

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

• כאשר אנו "מסתכלים" על ערך של משתנה, המפרש מוצא את ההפניה בסביבה, ואז ניגש ל-Store כדי לקרוא את הערך בתא שאליו ההפניה מצביעה.
• כאשר אנו יוצרים משתנה חדש (לדוגמה, באמצעות define או let), המפרש מקצה תא חדש ב-Store, מכניס אליו את הערך ההתחלתי, ויוצר קישור בסביבה מהשם של המשתנה להפניה לתא החדש.

השמה (Assignment)

השמה היא הפעולה המאפשרת לשנות את הערך של תא קיים ב-Store. בשפות רבות, פעולה זו מיוצגת על ידי אופרטור כמו = או פונקציה כמו set! ב-Scheme.

• לדוגמה, ב-Scheme, (set! x 5) יגרום למפרש למצוא את ההפניה של x בסביבה, ולאחר מכן לשנות את הערך בתא ב-Store שאליו x מפנה ל-5.

תופעות לוואי (Side Effects)

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

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

דוגמאות והשלכות מעשיות

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

דוגמה 1: השפעת set!

נניח את הקוד הבא בשפה דמוית Scheme:

(define x 1)
(define y x)
(set! x 2)
y

• במפרש ללא Store: אם set! היה נתמך, הוא היה יוצר קישור חדש ל-x בסביבה המקומית (או שגיאה). y היה נשאר 1, מכיוון שהוא קושר לערך 1 בעת הגדרתו.
• במפרש מבוסס Store:
  1. (define x 1): נוצר תא חדש ב-Store עם הערך 1. הסביבה מקשרת את x להפניה לתא זה.
  2. (define y x): הסביבה מקשרת את y לאותה הפניה שאליה x מקושר. כעת x ו-y מפנים לאותו תא (Aliasing).
  3. (set! x 2): המפרש מוצא את ההפניה של x, ניגש לתא ב-Store שאליו היא מצביעה, ומשנה את ערכו ל-2.
  4. y: המפרש מוצא את ההפניה של y, ניגש לתא ב-Store שאליו היא מצביעה, ומחזיר את ערכו הנוכחי, שהוא 2.

  התוצאה היא 2, וזוהי דוגמה מובהקת לתופעת לוואי ו-Aliasing.

דוגמה 2: פונקציות עם מצב פנימי

מפרש מבוסס Store מאפשר לממש פונקציות "מצבתיות" (stateful functions), למשל מונה:

(define (make-counter)
  (define count 0)
  (lambda ()
    (set! count (+ count 1))
    count))

(define c1 (make-counter))
(c1) ; => 1
(c1) ; => 2

(define c2 (make-counter))
(c2) ; => 1
(c1) ; => 3

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

שאלות לדיון

• כיצד משתנה מימוש הפונקציות lookup ו-extend-environment במפרש מבוסס Store לעומת מפרש מבוסס סביבה בלבד?
• מהם היתרונות והחסרונות העיקריים של הוספת Store למודל המפרש?
• הסבירו כיצד הוספת ה-Store מאפשרת מימוש מבני נתונים משתנים (Mutable Data Structures) כמו רשימות מקושרות שניתן לשנות את תאיהן.
• באיזה אופן תופעות לוואי מקשות על אופטימיזציה של קוד על ידי מהדר?

נקודות לתשובת מודל

• lookup: במפרש מבוסס Store, lookup מחזירה הפניה (כתובת) במקום ערך. לאחר מכן יש צורך ב"dereference" (קריאה מה-Store) כדי לקבל את הערך בפועל. extend-environment: יוצרת תא חדש ב-Store עבור כל משתנה חדש, ומקשרת את שם המשתנה להפניה לתא זה בסביבה החדשה.
• יתרונות: תמיכה בשפות אימפרטיביות, מימוש מבני נתונים משתנים, אפשרות למצב פנימי בפונקציות/אובייקטים, יעילות בשינוי נתונים גדולים (במקום יצירת עותק). חסרונות: מורכבות רבה יותר בניתוח והבנת קוד (בגלל תופעות לוואי ו-Aliasing), קושי באופטימיזציה, פוטנציאל לבאגים קשים לאיתור.
• מבני נתונים משתנים: במפרש מבוסס Store, תאי הרשימה (cons cells) עצמם יכולים להכיל הפניות לתאים אחרים ב-Store. שינוי ה-cdr של תא ברשימה, למשל, משנה את ההפניה בתא זה, במקום ליצור רשימה חדשה לגמרי. זה מאפשר פעולות כמו set-cdr! ב-Scheme.
• אופטימיזציה: תופעות לוואי מונעות אופטימיזציות רבות. לדוגמה, מהדר לא יכול להניח שקריאה לפונקציה עם אותם ארגומנטים תמיד תחזיר את אותה תוצאה (referential transparency) אם יש לה תופעות לוואי. הוא לא יכול לשנות את סדר הביצוע של פעולות או להסיר קוד "מת" בקלות, שכן כל פעולה עלולה לשנות את ה-Store ולהשפיע על שאר התוכנית.