מבוא ו-EXPLICIT-REFS

ניהול ידני: הקבצים שיוצרים אותה

בפרקים הקודמים (LET, PROC) עבדנו בעולם שבו משתנים אינם משתנים (Immutable). בפרק 4 אנו מכניסים לראשונה את תופעות הלוואי (Side Effects) ואת מערכת ניהול הזיכרון בעזרת קובץ חדש ומרכזי בארכיטקטורה: store.scm.

💡 המהפך הפילוסופי: מ"ערך" ל"זהות ומצב" (Identity vs. State)

כל עוד עבדנו בשפות פונקציונליות (כמו LET ו-PROC), למשתנים לא הייתה "זהות" פיזית, אלא רק ערך מתמטי. ההגדרה x = 5 ייצגה אמת נצחית שאינה משתנה.

ברגע שהכנסנו את ה-Store (הזיכרון הגלובלי המשותף) לשפה, יצרנו את המושג זהות (Identity):

  • הסביבה כבר לא ממפה שם של משתנה ישירות לערכו, אלא למקום פיזי בזיכרון (Reference/כתובת).
  • הערך שנמצא בתוך התיבה – המצב (State) – יכול להשתנות שוב ושוב לאורך זמן (Mutation).
  • הזהות של התיבה (הכתובת שלה, ref-val) נשארת קבועה לאורך כל ריצת התוכנית.

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

store.scm (חדש!)

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

lang.scm

הורחב עם הפקודות newref, deref, setref ו-begin.

data-structures.scm

הטיפוס expval הורחב להכיל ref-val - עטיפה מיוחדת לכתובות זיכרון.

environments.scm

בשפת EXPLICIT, הסביבה נותרת ללא שינוי - משתנה רגיל יכול להצביע למספר, ורק משתנה שנוצר עם newref יקבל כתובת.

צללילה לקובץ store.scm

"המפרש הטיפש ביותר בעולם לזיכרון": ה-Store ממומש פשוט כרשימה (List) ב-Scheme, וכתובת זיכרון (Reference) היא פשוט אינדקס (מספר שלם) בתוך הרשימה הזו.

(define the-store 'uninitialized)

;; הקצאת תא חדש. הערך נדחף לסוף הרשימה ומוחזר האינדקס שלו.
(define newref
  (lambda (val)
    (let ((next-ref (length the-store)))
      (set! the-store (append the-store (list val)))
      next-ref)))

;; שליפת ערך. ניגשים למקום ה-ref ברשימה.
(define deref 
  (lambda (ref)
    (list-ref the-store ref)))

הערה: פונקציית setref! יוצרת עותק חדש של כל רשימת ה-Store עם התא המעודכן ושומרת אותו. זה לא יעיל, אבל עובד מצוין לצורך למידה.

למה בכלל צריך זיכרון מחוץ לסביבה (Environment)?

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

הסביבה (Env)
x -> Ref(0)
➡️
הזיכרון (Store)
Ref(0) -> 5
ניתן לדריסה!

Denoted Values מול Expressed Values ב-EXPLICIT-REFS

בקורסי שפות תכנות, חשוב להבחין בין שני סוגי הערכים:

  • Denoted Values (ערכים השמורים בסביבה): הערכים שמשתנה יכול להיות קשור אליהם ישירות ב-Environment. בשפת EXPLICIT-REFS, ה-Denoted Values כוללים גם מספרים, בוליאנים, ופרוצדורות, וגם כתובות בזיכרון (ref-val). הסיבה לכך היא שמשתנה יכול להיקשר ישירות לערך רגיל (למשל let x = 5 שבו x קשור ישירות למספר 5 בסביבה ולא לכתובת זיכרון).
  • Expressed Values (ערכים שביטוי יכול להחזיר): הערכים שחישוב של Expression יכול להניב. בשפה זו הם כוללים מספרים, בוליאנים, פרוצדורות, וכתובות (ref-val).

מדוע צריך את פקודת newref במפורש? מכיוון שהסביבה יכולה לקשור משתנה ישירות למספר, אין דרך אחרת להגדיר הפניה (Pointer). אנו נדרשים לקרוא ל-newref באופן יזום כדי להפוך Expressed Value (כמו מספר) לכתובת בזיכרון (Reference), ואותה לשמור בסביבה.

📂 חלוקת הקבצים בשפת EXPLICIT-REFS ותוספת ה-Store

שם הקובץ תפקיד ושינויים ב-EXPLICIT-REFS מה התווסף?
store.scm (קובץ חדש!) מנוע הזיכרון הגלובלי (הלוקיישנים). מייצג את ה-Heap הפיזי של התוכנית. empty-store, newref, deref, setref!
data-structures.scm הוספת טיפוס Reference לייצוג כתובות זיכרון בתוך ExpVal. ref-val(location)
interp.scm ביטויי מניפולציה ישירה על הזיכרון כחלק מהערכת value-of. newref-exp, deref-exp, setref-exp
environments.scm הוספת Reference בסביבה (ב-DenVal) במקום ExpVal. var ➔ ref-val(loc)

🧩 משימה: בנה את הארכיטקטורה (הפרדת אחריות)

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

store.scm
lang.scm
interp.scm
data-structures.scm
שורות קוד לשיוך:
מבוא ו-EXPLICIT-REFS

ניהול ידני: Pointers

בשפת EXPLICIT-REFS המתכנת שולט בזיכרון בצורה ידנית ומפורשת (בדומה לשפת C). רוצה זיכרון? תקצה אותו. רוצה לקרוא? תשלוף במפורש.

4 הפקודות החדשות בדקדוק

Expression ::= newref ( Expression )
    newref-exp (exp1)

Expression ::= deref ( Expression )
    deref-exp (exp1)

Expression ::= setref ( Expression , Expression )
    setref-exp (exp1 exp2)

Expression ::= begin Expression {; Expression}* end
    begin-exp (exp1 exps)

מה כל פקודה עושה?

  • newref(val): לוקח ערך, מקצה לו תא ב-Store, ומחזיר את הכתובת (Reference).
  • deref(ref): מקבל כתובת, הולך ל-Store ומחזיר את הערך שיש שם.
  • setref(ref, val): מקבל כתובת וערך, ודורס את התוכן הישן. מחזיר ערך שרירותי (למשל 23).
  • begin: פקודה קריטית! מכיוון ש-setref מבצע שינוי ולא חישוב מתמטי טהור, חובה להריץ רצף פקודות ולספק תוצאה בסוף. begin מריץ סדרה ומחזיר את הערך של האחרונה.
    הקשר אדריכלי (מעבר מפונקציונלי לפקודתי): בפרדיגמה פונקציונלית טהורה אין משמעות לרצף פקודות (Sequence) מכיוון שכל ביטוי מוערך אך ורק כדי לקבל את ערכו. ברגע שמכניסים זיכרון גלובלי משותף (Store), סדר הביצוע קובע את המצב הסופי של הזיכרון (Side Effects). לכן, begin הכרחי כדי לכפות סדר הערכה מוגדר משמאל לימין, ולהבטיח שהאפקט של הפקודה הראשונה יסתיים לחלוטין וישפיע על הזיכרון לפני שהפקודה הבאה בתור מתחילה את הערכתה.

💡 דוגמת קוד בשפה: איך זה נראה למתכנת?

שימו לב לסרבול: יש להשתמש ב-deref בכל פעם שרוצים לגשת לערך שנמצא בכתובת.

let x = newref(0) % מקצה כתובת. x הוא *מצביע* ל-0
in begin
    setref(x, 1) ; % משנה את התוכן של הכתובת ל-1
    -(deref(x), -5) % שולף במפורש את ה-1, ומחסר מינוס 5
   end
% תוצאה: 6

🗑️ ערך ה"דאמי" (23) ופקודת begin בתור "פח אשפה"

כדי שמפרש לא יקרוס, פונקציית value-of מחויבת תמיד להחזיר טיפוס חוקי (expval). לפעולת השמה או עדכון זיכרון כמו setref יש "תופעת לוואי" (היא משנה את ה-Store), אך אין לה ערך מתמטי להחזיר. לכן, המפרש מחזיר ערך שרירותי (Dummy Value) – למשל (num-val 23).

מכיוון שאסור לנו להשתמש בפקודות מוטציה שרירותיות בתוך חישובים אריתמטיים (אחרת ה-"23" יזהם את הנוסחה: למשל, ביטוי כמו +(1, setref(x, 5)) יחזיר 24), אנו זקוקים למנגנון הפרדה.

כאן נכנסת הגאונות של פקודת begin: היא פועלת כ"פח אשפה" אלגנטי. היא מריצה את הפקודות בזו אחר זו, מאפשרת לאפקטים של setref לעדכן את ה-Store, וזורקת לפח את ערכי ה-23 שמוחזרים מהם, עד שהיא מגיעה לביטוי האחרון בבלוק – אותו בלוק מחושב מוחזר כתוצאה הלגיטימית של ה-begin כולו.

🗺️ תרשים מיפוי: ההפרדה בין סביבה (Environment) למאגר הזיכרון (Store)

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

הסביבה (Environment) x ➔ L1 (location 1) מיפוי (deref) מאגר הזיכרון הגלובלי (Store) L1 ➔ num-val(42)

🌳 חוקר עץ ה-AST הדינמי (AST Explorer)

לפניך קטע קוד בשפת היעד. רחף עם העכבר או לחץ על המילים המודגשות כדי לחשוף את הייצוג שלהן בתוך עץ התחביר המופשט (Abstract Syntax Tree) שיוצר המפרש.

% קוד מקור:
let x = newref(0)
  in setref( x, 5)
let var:x newref num:0 setref var:x num:5
הסבר ה-AST:

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

מבוא ו-EXPLICIT-REFS

המפרש: newref, deref, setref

איך פונקציית value-of (ב-interp.scm) מפעילה את הפקודות על מודול הזיכרון שלנו.

(cases expression exp
  ...
  ; 1. הקצאת זיכרון: חשב את הביטוי, צור תא ב-Store, וארוז את הכתובת כ-ref-val
  (newref-exp (exp1)
    (let ((v1 (value-of exp1 env)))
      (ref-val (newref v1))))

  ; 2. קריאה מזיכרון: חשב ביטוי (שחייב להחזיר כתובת), חלץ אותה, ושלוף מה-Store
  (deref-exp (exp1)
    (let ((v1 (value-of exp1 env)))
      (let ((ref1 (expval->ref v1))) ; שלוף את המספר של האינדקס
        (deref ref1))))

  ; 3. כתיבה לזיכרון: חשב כתובת, חשב ערך חדש, ודרוס!
  (setref-exp (exp1 exp2)
    (let ((ref (expval->ref (value-of exp1 env))))
      (let ((v2 (value-of exp2 env)))
        (begin
          (setref! ref v2)
          (num-val 23))))) ; פקודות מחזירות "ערך דאמי" (23) מכיוון שחובה להחזיר ExpVal
          
  ; 4. הרצת בלוק (begin): לולאה שמריצה את כל הפקודות ומחזירה את האחרונה
  (begin-exp (exp1 exps)
    (letrec ((value-of-begins 
               (lambda (e1 es)
                 (let ((v1 (value-of e1 env)))
                   (if (null? es)
                       v1 ; הגענו לפקודה האחרונה - נחזיר אותה
                       (value-of-begins (car es) (cdr es)))))))
      (value-of-begins exp1 exps)))
)

📊 טבלת פעולות על הפניות (References) ב-EXPLICIT-REFS

ביטוי פעולה על ה-Store ערך מוחזר אנלוגיה ב-C
newref(val) מוסיף ערך חדש ל-Store ref-val(loc) malloc + assign
deref(ref) קוראת ערך מה-Store לפי מיקום expval *ptr
setref(ref, val) משנה ערך קיים ב-Store 23 (ערך דמה) *ptr = val

⚙️ מריץ שלבים ויזואלי (value-of Step-by-Step)

בוא נעקוב אחר ביצוע הביטוי let x = newref(42) in deref(x) בתוך ה-Interpreter ונראה כיצד הקוד של המפרש ב-Scheme מגיב ומעדכן את המבנים הפנימיים.

% שפת היעד:
let x = newref(42)
in deref(x)
; interp.scm (קוד מפרש):
(let-exp (var exp1 body)
  (let ((val1 (value-of exp1 env)))
    (value-of body (extend-env var val1 env))))
(newref-exp (exp1)
  (let ((val1 (value-of exp1 env)))
    (ref-val (newref val1))))
(deref-exp (exp1)
  (let ((val1 (value-of exp1 env)))
    (let ((ref1 (expval->ref val1))) (deref ref1))))
מצב המפרש הפנימי (State):
הסביבה (Environment Stack)
Empty Env
מאגר הזיכרון (Store)
[Empty Store]
לחץ על "התחל" או "צעד הבא" כדי להתחיל את מעקב הריצה.
שפת IMPLICIT-REFS

השפה המודרנית: הקבצים שיוצרים אותה

שפת EXPLICIT הייתה מעצבנת לכתיבה. בשפות מודרניות (JavaScript, Python) המפרש מבצע עבורנו את פעולות ההקצאה והקריאה בסתר (Implicitly). שפה זו מספקת חוויית פיתוח חלקה, אך דורשת שינוי ארכיטקטוני עמוק.

הקובץ שעבר רעידת אדמה: environments.scm

ב-IMPLICIT-REFS חל חוק הברזל החדש: הסביבה מכילה תמיד אך ורק כתובות זיכרון! (References).

⚠️ באג ארכיטקטוני נפוץ (תיקון רקורסיה):
במפרשים מבוססי מצב (Stateful), אסור ש-apply-env ייצר newref חדש בזמן אמת עבור פונקציה רקורסיבית (בכל lookup). אם הוא היה עושה זאת, אז ניסיון לשנות את הפונקציה (למשל set f = proc(x) ...) היה מעדכן כתובת זיכרון זמנית חדשה לגמרי שנזרקת מיד, והקריאה הבאה ל-f הייתה מייצרת שוב תא חדש עם הפונקציה המקורית (כך שהמוטציה לא תעבוד!).
הפתרון הארכיטקטוני הנכון הוא ש-newref מתבצע פעם אחת בלבד בעת בניית הסביבה (ב-extend-env-rec) באמצעות ווקטורים (Vectors) המקצים את הכתובות מראש, ו-apply-env פשוט שולה את הכתובת שהוקצתה מראש ללא הקצאות נוספות. 

;; ה-init-env המסורתי הפסיק להשתמש ישירות ב-(num-val 1) ועטף הכל ב-newref
(define init-env 
  (lambda ()
    (extend-env 
      'i (newref (num-val 1))
      (extend-env
        'v (newref (num-val 5)) ...))))

;; בניית הסביבה הרקורסיבית (extend-env-rec): הקצאה חד-פעמית של ווקטור המכיל את ה-References!
(define extend-env-rec
  (lambda (p-names b-vars p-bodies saved-env)
    (let ((vecs (map (lambda (name) (make-vector 1)) p-names)))
      (let ((new-env (extend-env-rec-env p-names vecs saved-env)))
        (for-each
          (lambda (vec b-var p-body)
            (vector-set! vec 0
              (newref (proc-val (procedure b-var p-body new-env)))))
          vecs b-vars p-bodies)
        new-env))))

;; בחיפוש בסביבה (apply-env): שולפים את הכתובת שכבר הוקצתה מראש בתוך הווקטור, ללא newref חדש!
(extend-env-rec-env (p-names vecs saved-env)
  (let ((n (location search-var p-names)))
    (if n
      (vector-ref (list-ref vecs n) 0) ; שולף את הכתובת הקבועה
      (apply-env saved-env search-var))))

lang.scm

הפקודות newref ו-deref נמחקו לחלוטין מהשפה! השארנו רק פקודת השמה אחת שהפכה לפשוטה: set x = 10 (נקראת assign-exp).

interp.scm

כל מקום שמוסיף משתנה לסביבה (כמו פקודת let ו-apply-procedure) עוודכן לקרוא ל-newref, וכל קריאת משתנה (var-exp) קוראת כעת ל-deref באופן סמוי.

store.scm & data-structures.scm

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

📂 חלוקת הקבצים וההבדלים בשפת IMPLICIT-REFS

שם הקובץ מה השתנה מ-EXPLICIT-REFS? השפעה על המפרש
lang.scm הסרת newref, deref, setref מהתחביר. הוספת ביטוי השמה set. הקוד נראה נקי וכמו שפה רגילה (ללא מניפולציה מפורשת על פוינטרים).
data-structures.scm הסביבה (Environment) קושרת כעת מזהה (var) ישירות ל-Reference במקום ל-ExpVal. החזרת DenVal = Ref(ExpVal) ו-ExpVal = {Number, Boolean, Proc}.
interp.scm עדכון value-of לקרוא ל-deref אוטומטית בכל var-exp, ופנייה ל-setref! בתוך set-exp. מנגנון ההשמה והשליפה מתבצע אוטומטית מאחורי הקלעים ("משתנים מרומזים").

🔄 הבדלי ארכיטקטורה: EXPLICIT מול IMPLICIT

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

1. קוד יצירת סביבה (environments.scm):

2. קוד חיפוש משתנה (interp.scm):

מעבדת קריסה אקדמית (Crash Test Lab):

בוא ננסה להריץ את פקודת ההשמה של משתנה פשוט שאינו מצביע: set x = 10.

שפת IMPLICIT-REFS

ניהול אוטומטי: המודל המודרני

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

📥

1. הקצאה סמויה (Allocation)

מתי נוצר משתנה חדש? כאשר אנו קוראים ל-let x = ... או מפעילים פונקציה. ברגעים אלו המפרש מבצע newref ומכניס את הכתובת לסביבה.

👀

2. שליפה סמויה (Deref)

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

✍️

3. השמה סמויה (Set)

כדי לעדכן משתנה פשוט כותבים set x = 10. המפרש מוצא את הכתובת של x בסביבה ומעדכן ישירות ב-Store.

מושג מפתח: L-value מול R-value במפרש

כדי להבין כיצד המפרש יודע מתי לקרוא ערך ומתי לשנות אותו (בלי שהמתכנת יציין deref או setref באופן ידני), משתמשים במודל הכללי של L-value (Location Value) ו-R-value (Read/Right Value):

  • R-value (ערך קריאה/ימין): מייצג את התוכן הממשי השמור בכתובת. כאשר משתנה מופיע בצד ימין של השמה או כחלק מביטוי (למשל x + 1 או (f x)), המפרש זקוק ל-R-value שלו. לכן, פקודת הערכת המשתנה (var-exp) מבצעת deref סמוי אוטומטי על הכתובת שנמצאה בסביבה כדי לחלץ את הערך השמור בתוכה.
  • L-value (ערך מיקום/שמאל): מייצג את הכתובת או המצביע הפיזי בזיכרון (Location). כאשר משתנה מופיע כיעד להשמה (למשל set x = 5), המפרש אינו מעוניין בתוכן הקיים שלו, אלא בכתובת שבה ניתן לכתוב את הערך החדש. לכן, פקודת ההשמה (assign-exp) קוראת ל-apply-env שמחזיר לה את הכתובת בזיכרון (ה-L-value), אך אינה מבצעת עליה deref, אלא קוראת ישירות ל-setref! על אותה כתובת.

⚠️ דליפת זיכרון סמויה (Memory Leak) ולידתו של ה-Garbage Collector

במעבר ל-IMPLICIT-REFS, מתי אנחנו מוחקים מידע מהזיכרון? התשובה המפתיעה היא: אף פעם!

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

מה קרה לתא שהוקצה ב-Store? הוא נשאר שם לנצח! מכיוון שאין לנו יותר מצביע אליו בסביבה, הוא הופך לאובייקט לא נגיש (Unreachable Object).

מכיוון שהמפרש הלימודי שלנו מניח זיכרון אינסופי, התאים הללו מצטברים (Memory Leak). הבנה זו ממחישה בדיוק מדוע שפות המקצות זיכרון באופן סמוי (כמו Java, Python או JavaScript) חייבות להריץ ברקע מנגנון Garbage Collector (איסוף זבל) – מנגנון שסורק את ה-Store, מזהה תאים שאין אליהם שום שרשרת הפניות מהסביבה הפעילה, ומפנה אותם כדי למנוע קריסה של התוכנית מחוסר זיכרון.

סימולטור השוואה: סביבה (Environment) מול זיכרון (Store) הדמיה אינטראקטיבית

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

קוד המקור: 
let x = newref(5)
in setref(x, 10)
לחצו על "בצע צעד" כדי להריץ את השורה הראשונה (הקצאת המשתנה).
טבלת הסביבה (Environment):
משתנה (Var) ערך בסביבה (Denoted Value)
סביבה ריקה

* Denoted Values מייצג את הערכים השמורים ישירות בסביבה.

טבלת הזיכרון (Store):
כתובת (Ref) ערך בזיכרון (Expressed Value)
זיכרון ריק

💡 דוגמת קוד בשפה: כמה זה נראה טבעי!

שימו לב כמה הקוד כעת נקי, ללא שום newref או deref. 

let x = 0 
in begin
    set x = 1; 
    -(x, -5)
   end
% תוצאה: 6
שפת IMPLICIT-REFS

המפרש: הקצאה ושליפה סמויה

כך נראה הקסם מאחורי הקלעים בפונקציית value-of. מודל זה משמש תשתית ל-90% מהשאלות במבחנים הכוללות שינוי זיכרון. 

(cases expression exp
  ...
  ; 1. משתנה רגיל - שליפה אוטומטית (Deref)
  (var-exp (var)
    ; apply-env מחזיר לנו תמיד כתובת (Reference). חובה לעשות deref!
    (deref (apply-env env var)))

  ; 2. פקודת Set - השמה קלה וטבעית למתכנת
  (assign-exp (var exp1)
    (begin
      ; apply-env יביא לנו את הכתובת של var במקום להשתמש ב-ref ידני
      (setref! (apply-env env var) (value-of exp1 env))
      (num-val 27)))

  ; 3. פקודת Let - הקצאה אוטומטית למשתנים חדשים
  (let-exp (var exp1 body)
    (let ((val1 (value-of exp1 env)))
      (value-of body
        ; חובה!! אנו מכניסים לסביבה רק כתובות. לכן עוטפים את הערך ב-newref.
        (extend-env var (newref val1) env))))
)

; ==========================================================
; 4. הקריאה לפונקציה - כאן נוצר ה-Local Scope והעותק העצמאי לפרמטר!
; ==========================================================
(define apply-procedure
  (lambda (proc1 val)
    (cases proc proc1
      (procedure (var body saved-env)
        (value-of body
          ; יצירת תא זיכרון *חדש* עבור הארגומנט במעמד קריאת הפונקציה
          (extend-env var (newref val) saved-env))))))

📊 טבלת השוואה: שינויים ב-value-of מ-EXPLICIT ל-IMPLICIT REFS

ביטוי EXPLICIT-REFS IMPLICIT-REFS
var-exp apply-env → expval ישירות apply-env → ref → deref → expval
let-exp extend-env(var, val) newref(val) → extend-env(var, ref)
assign (set) — לא קיים apply-env → ref → setref(ref, val)
הסביבה מכילה ערכים (expval) ישירות הפניות (references) — מצביעים לתוך ה-Store

🎯 משחק תפקידים: זהה L-value מול R-value בקוד השמה

בתוך קוד ההשמה הבא בשפת IMPLICIT-REFS: set x = +(x, 1). עליך לזהות איזה מופע של המשתנה x מייצג את כתובת התא (L-value) ואיזה מייצג את תוכנו (R-value).

set x = +( x , 1)
לחץ על ה-x שהוא הכתובת אליה נכתוב (L-value)
שפת IMPLICIT-REFS (ממן)

פתרון ממן: העמסת פרוצדורות (Overloading)

מטלה זו משדרגת את שפת IMPLICIT-REFS לאחת היכולות החשובות בשפות מודרניות מונחות עצמים (כמו Java ו-C++): פולימורפיזם מסוג Overloading. משתנה יחיד יכול להחזיק תחתיו מספר רב של מימושי פרוצדורה. המפרש מבצע Dynamic Dispatch (ניתוב דינמי) בזמן ריצה ובוחר את הגרסה המתאימה בהתאם לטיפוס הארגומנט שנשלח אליה בפועל.

💡 הכנה לבחינה: ממן 14 ושאלה 2 במבחן

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

1 השינוי הארכיטקטוני

בשפת IMPLICIT-REFS הרגילה, פרוצדורה נשמרת בזיכרון כרשומה פשוטה (procedure var body env). במטלה זו, אנו משנים את אופי הפרוצדורה כך שתהפוך למכולה (Container) המחזיקה רשימה של מקרים. כל מקרה מייצג גרסה שונה של הפרוצדורה עבור סוג פרמטר שונה (int, bool או func).

שלב א': תחביר השפה (lang.scm)

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

; 1. הגדרת טיפוסים (Type) חדשים בדקדוק
(type ("int") int-type)
(type ("bool") bool-type)
(type ("func") func-type)

; 2. פרוצדורה כעת דורשת ציון טיפוס לפרמטר
(expression 
  ("proc" "(" type identifier ")" expression) 
  proc-exp)

; 3. פעולת ה-Overload הדורסת או מוסיפה גרסה
(expression 
  ("overload" identifier "with" "(" type identifier ")" expression) 
  overload-exp)

שלב ב': מבנה הנתונים (data-structures)

הפרוצדורה מיוצגת כעת כ-overloaded-proc המכיל רשימה של רשימות. כל מקרה מורכב מטיפוס, משתנה, גוף, וסביבה נשמרת (Lexical Scope). 

(define-datatype proc proc?
  (overloaded-proc
    (cases list?))) ; רשימה של (type var body env)

; תמיכה בהדפסה נקייה לקונסולה (expval->printable)
(define expval->printable
  (lambda (val)
    (cases expval val
      (proc-val (p)
        (cases proc p
          (overloaded-proc (cases-list)
            (list 'overloaded-proc 
                  (map (lambda (c) 
                         (list (cadr c) '... 
                               (env->list (cadddr c)))) 
                       cases-list)))))
      (else val))))

2 מנוע הביצוע (interp.scm) וניתוב בזמן ריצה

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

💡 ניהול הזיכרון בעת Overload והקלוז'ר הלקסיקלי

כיוון שאנו בשפת IMPLICIT-REFS, המשתנה המכיל את הפרוצדורה קיים ככתובת בזיכרון. פעולת ה-Overload מבצעת פעולת Side-Effect קלאסית: היא שולפת בעזרת deref את ה-overloaded-proc הקיים, מוסיפה את גרסת הטיפוס החדשה (Case) לרשימה הפנימית, ושומרת בחזרה בעזרת setref!.

ההבדל הארכיטקטוני העמוק (לכידת סביבה לקסיקלית שונה):

כאשר אנו מגדירים מקרה חדש (Case) בתוך ה-Overload, המפרש אורז לתוך ייצוג המקרה את הסביבה הלקסיקלית הנוכחית באותו רגע בדיוק (saved-env של ה-Overload). המשמעות היא שפרוצדורה אחת מסוג overloaded-proc יכולה להחזיק תחתיה מספר מקרים, כאשר כל מקרה "זוכר" סביבה לקסיקלית שונה לחלוטין (הסביבה שבה בוצע ה-overload הספציפי שלו). זה שונה מהשמה רגילה ומבטיח הגנה לקסיקלית מלאה לכל גרסה!

מנגנון הדיספאץ' (Dynamic Dispatch) הפנימי

; 1. מחלץ את הטיפוס (type-rep) מערך בזמן ריצה (expval)
(define get-arg-type
  (lambda (val)
    (cases expval val
      (num-val (num) (int-type))
      (bool-val (bool) (bool-type))
      (proc-val (proc1) (func-type))
      (else (eopl:error 'get-arg-type "Unsupported...")))))

; 2. חיפוש התאמה (Type Matching) ברשימת הגרסאות של הפרוצדורה
(define apply-procedure
  (lambda (proc1 arg)
    (cases proc proc1
      (overloaded-proc (cases-list)
        (let* ((arg-type (get-arg-type arg))
               (matching-case (find-case cases-list arg-type)))
          (if matching-case
              (let ((typ (car matching-case))
                    (var (cadr matching-case))
                    (body (caddr matching-case))
                    (saved-env (cadddr matching-case)))
                ; הרצת הגרסה המתאימה תוך שמירה על עקרון IMPLICIT-REFS
                ; יוצרים תא זיכרון חדש עבור הפרמטר!
                (value-of body (extend-env var (newref arg) saved-env)))
              (eopl:error 'apply-procedure 
                 "No procedure found with ~s argument" arg-type)))))))

3 מעקב ריצה (Trace) - דוגמה מסכמת

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

let sum = 0
in let p = proc (int a) -(a,10)
   in begin
        set sum = -(sum, -(0, (p 100)));                    % 1. הוספת ערך מ-p(int)
        overload p with (bool b) if b then 700 else 1000;   % 2. יצירת גרסה בוליאנית
        set sum = -(sum, -(0, (p zero?(5))));               % 3. הוספת ערך מ-p(bool)
        overload p with (int r) -(r,300);                   % 4. דריסת הגרסה המספרית הקיימת!
        set sum = -(sum, -(0, (p 100)));                    % 5. הוספת ערך מ-p(int) המעודכן
        overload p with (func f) (f 30);                    % 6. יצירת גרסה המקבלת פרוצדורה
        set sum = -(sum, -(0, (p proc (int w) -(w,50))));   % 7. הוספת ערך מ-p(func)
        sum
      end
שלב פעולה (קריאה / השמה) ניתוב (Dispatch) חישוב ערך ה-sum
1 (p 100) גרסת int (הראשונה) 100 - 10 = 90 0 + 90 = 90
2 & 3 (p zero?(5))
ארגומנט מוערך ל-#f		 גרסת bool (חדשה) if #f then 700 else 1000 = 1000 90 + 1000 = 1090
4 & 5 (p 100) גרסת int (מעודכנת) 100 - 300 = -200 1090 + (-200) = 890
6 & 7 (p proc(w)...) גרסת func f(30) -> 30 - 50 = -20 890 + (-20) = 870

תוצאה סופית: 870

🔀 הדמיית נתב הפרוצדורות (Dynamic Dispatch Router)

בשאלת הממ"ן של העמסת פרוצדורות (Overloading), המפרש זקוק לזהות את טיפוס הארגומנט שמתקבל בזמן ריצה ולנתב אותו לפונקציה המתאימה. בחר טיפוס קלט, וצפה באנימציית הניתוב דרך מנגנון get-arg-type.

Input Arg get-arg-type proc-int proc-bool proc-func
לחץ על אחד מסוגי הקלטים למעלה כדי לראות את אנימציית הניתוב והסבר מורחב על התהליך.
שפת MUTABLE-PAIRS

זוגות משתנים: הקבצים שיוצרים אותה

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

pairval1.scm / pairval2.scm

מכילים את המימושים בפועל לאיך שומרים שני ערכים תחת "ישות" אחת בזיכרון.

lang.scm

נוספו הפקודות החשובות: newpair, left, right, setleft, setright.

interp.scm

מעביר את הפקודות מה-AST אל הפונקציות המוגדרות בקבצי המימוש (`setleft` וכו').

קובץ התצורה pairvals.scm

בספר EOPL מוצגים שני מימושים חלופיים לחלוטין של זוגות, שניהם חיים באותה תיקייה תחת הקבצים pairval1.scm ו-pairval2.scm. הקובץ השלישי הוא פשוט מתג (Switch) שמאפשר להחליף ביניהם בקלות לפני ההרצה.

(module pairvals (lib "eopl.ss" "eopl")
  
  ;; כדי לשנות מימוש, מגיבים/מסירים את ההערות:
  
  ;; (require "pairval1.scm")
  ;; (provide (all-from "pairval1.scm"))

  (require "pairval2.scm")
  (provide (all-from "pairval2.scm"))
)

📂 חלוקת הקבצים בשפת MUTABLE-PAIRS (זוגות משתנים)

שם הקובץ מה התווסף ב-MUTABLE-PAIRS? תפקיד ותלות במאגר (Store)
lang.scm הוספת אופרטורים newpair, left, right, setleft, setright. הגדרת ביטויים של זוגות משתנים.
data-structures.scm הוספת variant ל-ExpVal בשם mutpair-val המחזיק reference יחיד לכתובת ב-Store. מידול הזוג בזיכרון (החזקת כתובת הבסיס של התא הראשון).
interp.scm מימוש פעולות הקצאה ושינוי: newpair מקצה שני תאים עוקבים ב-Store, left ניגש לראשון, right לשני. מניפולציה על התאים העוקבים ב-Store.

🧩 תרגיל סידור קוד: מימוש setleft במפרש MUTABLE-PAIRS

סדר את שורות הקוד של פונקציית העדכון של התא השמאלי ב-Mutable Pair (כלומר setleft). השתמש בחצים למעלה/למטה בכל שורה כדי להחליף את המיקומים שלהן.

שפת MUTABLE-PAIRS

מבנה זוגות משתנים: רשימות מקושרות

5 הפקודות החדשות (כמו ב-LISP)

Expression ::= newpair ( Expression , Expression )
    newpair-exp (exp1 exp2)

Expression ::= left ( Expression )
    left-exp (exp1)

Expression ::= right ( Expression )
    right-exp (exp1)

Expression ::= setleft ( Expression , Expression )
    setleft-exp (exp1 exp2)

Expression ::= setright ( Expression , Expression )
    setright-exp (exp1 exp2)

מדוע זוגות הם כה קריטיים?

בעזרת האובייקט הפשוט newpair ניתן לבנות עולמות שלמים:

  • רשימות מקושרות: אם ה-right של הזוג מצביע לזוג נוסף, יצרנו רשימה ארוכה שניתנת לשינוי.
  • עצים וגרפים: אם זוג מצביע לעוד שני זוגות, יש לנו עץ בינארי שבו נוכל לקפוץ מצומת לצומת ולשנות ערכים בזמן ריצה בעזרת setleft / setright.

הערך mutpair-val התווסף ל-expval, כך שכל זוג יכול להיות שמור בתוך משתנה בסביבה או להיות פלט של פונקציה.

סימולטור זוגות משתנים: דיאגרמת קופסאות וחצים (Cons-Cell Box Pointer) הדמיה אינטראקטיבית

חקרו כיצד נבנים ומקודדים מבני נתונים בזיכרון של שפת MUTABLE-PAIRS. בחרו מבנה נתונים, שנו את הקישורים שלו, וראו כיצד החצים והזיכרון משתנים בהתאמה.

שינוי המבנה (Mutations):
תרשים תאי הזיכרון (Cons-Cells):
שפת MUTABLE-PAIRS

המפרש: שני מימושים שונים

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

גישה 1 (pairval1.scm)
מבנה נתונים מפורש עם שני מצביעים

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

;; מבנה הנתונים: זוג המכיל שתי כתובות פנימיות
(define-datatype mutpair mutpair? 
  (a-pair (left-loc reference?) (right-loc reference?)))

;; יצירת הזוג עושה 2 קריאות ל-newref
(define make-pair
  (lambda (val1 val2)
    (a-pair (newref val1) (newref val2))))

;; קריאה לצד ימין - שולפים את הכתובת הימנית וקוראים לה
(define right
  (lambda (p)
    (cases mutpair p
      (a-pair (l-loc r-loc) (deref r-loc)))))

היתרון: בטוח מאוד לשימוש (Type-safe).

גישה 2 (pairval2.scm)
מתכנת C - תאים עוקבים ברצף (Arrays)

גישה מתקדמת יותר הדורשת ש-newref יקצה זיכרון בסדר עולה ברצף. זוג הוא בסך הכל מצביע יחיד p. צד ימין הוא אוטומטית p + 1! 

;; הזוג הוא רק כתובת המספר הבסיסי ב-Store
(define mutpair? reference?)

;; יוצרים שני תאים, אבל מחזירים רק את הראשון!
(define make-pair
  (lambda (val1 val2)
    (let ((ref1 (newref val1)))
      (let ((ref2 (newref val2)))
        ref1)))) ; אנו מסתמכים על כך ש-ref2 הוא ref1+1

;; צד ימין? פשוט מבקשים את הערך בכתובת p+1!
(define right
  (lambda (p)
    (deref (+ 1 p))))

היתרון: חיסכון עצום בזיכרון, פחות אובייקטים.

⚠️ האילוצים וההנחות הסמויות של גישת pairval2:
גישה זו מסתמכת לחלוטין על כך שפונקציית newref ב-store.scm היא דטרמיניסטית ומונוטונית – היא תמיד מקצה תאים חדשים בסדר עולה עוקב ללא קפיצות (כך שכל הקצאה עוקבת מובטחת להיות ממוקמת ב-p + 1).
אם היינו מוסיפים לשפה מערכת איסוף זבל (Garbage Collector - GC) שמפנה תאים שאינם בשימוש או מזיזה תאים בזיכרון כדי למנוע פרגמנטציה (Compaction), שיטה זו של אריתמטיקת מצביעים (Pointer Arithmetic) הייתה קורסת לחלוטין. תחת GC, התא ה"ימני" של הזוג לא בהכרח יישאר ממוקם פיזית בצמידות לתא ה"שמאלי" לאחר סידור מחדש של הזיכרון, מה שהיה גורם לקריאה מ-p+1 להחזיר ערך שגוי או זבל.

⚖️ השוואת מימושים: Ref-to-Ref (מימוש 1) מול Ref-to-Part (מימוש 2)

קריטריון השוואה מימוש 1: Ref-to-Ref (זוג ככתובת לשתי כתובות) מימוש 2: Ref-to-Part (זוג ככתובת לשני ערכים עוקבים)
מבנה ה-mutpair-val בזיכרון mutpair-val(Ref(L_left), Ref(L_right)) mutpair-val(Ref(L_base))
מבנה ב-Store (Heap) שני תאים נפרדים המוקצים במקומות שונים ב-Store. שני תאים המוקצים בצורה רציפה עוקבת: L_base ו- L_base + 1.
יעילות הקצאה (newpair) פחות יעיל (דורש שתי קריאות עצמאיות ל-newref). יעיל ביותר (הקצאה אחת של בלוק רציף).
השמה לתוך זוג (setleft!) משנה את הערך בתא השמאלי שכתובתו שמורה בזוג. מעדכנת ישר את התא בכתובת L_base ב-Store.

📦 אנימטור זיכרון: PairVal1 מול PairVal2

גלה כיצד מיוצגים זוגות משתנים (Mutable Pairs) בשתי הגישות השונות בתוך ה-Store. בחר גישת מימוש, לחץ "Allocate Pair" וראה את המבנה בזיכרון.

גישה 1: PairVal1

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

the-store (Global Heap representation)
L0: -
L1: -
L2: -
L3: -
L4: -
L5: -
L6: -
L7: -
חלק 4: העברת פרמטרים

שיטות לקריאה: הקבצים שיוצרים אותה

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

קובץ המהפכה: interp.scm

עד עכשיו, פונקציית העזר apply-procedure קיבלה את הפונקציה ואת הערך המחושב (ExpVal) של הארגומנט. כעת, אנו מוסיפים פונקציה מתווכת חדשה: value-of-operand!

כאשר מבצעים קריאה לפונקציה בעזרת call-exp (rator rand), במקום לעשות סתם (value-of rand) אנו שולחים את הארגומנט אל המתווך. המתווך יכול להחליט:

  • לייצר עותק של הזיכרון (CBV)
  • למסור את הכתובת הקיימת (CBR)
  • לארוז את העץ בקופסה לעתיד ללא חישוב (CBN / Lazy)

data-structures.scm (עצלנות בלבד)

בשפת call-by-need מתווסף מבנה נתונים בשם thunk, שתפקידו לכלוא בתוכו expression? (עץ שלא חושב עדיין) יחד עם ה-environment? שלו, עד לרגע שבו נזדקק לו.

environments.scm / store.scm

ללא שינוי, ממשיכים לעבוד באותו מודל Reference של IMPLICIT-REFS שבו כל משתנה בסביבה מצביע לתא ב-Store.

📂 חלוקת הקבצים בשפות העברת פרמטרים (CBV, CBR, Call-by-Name, Lazy)

שם הקובץ השפעת מודל העברת הפרמטרים נקודות מרכזיות
lang.scm ללא שינוי משמעותי מדקדוק PROC. קריאה לפונקציות נשארת (f x).
data-structures.scm הוספת Thunk לייצוג ביטויים מושהים ב-Lazy Evaluation. thunk(expression, environment)
interp.scm שינוי ב-value-of בתוך call-exp וב-apply-procedure: החלטה מתי להעריך את האופרנד. ב-CBV מעריכים לפני ההעברה; ב-CBR מעבירים את ה-Reference; ב-Lazy מעבירים Thunk.

🌿 תרשים זרימה אינטראקטיבי: value-of-operand

פונקציית המתווך value-of-operand היא זו שמכריעה האם לייצר תא חדש ב-Store או להעביר הפניה קיימת. בחר ארגומנט ושיטת העברה, והרץ את הניתוב.

1. בחר ארגומנט:
2. בחר שיטה:
Start value-of-operand Is CBR & Operand is Variable? Evaluate Expression (value-of) ➔ Create newref in Store Retrieve Existing Ref (No allocation!) Return New Ref (malloc / append store)
לחץ על Trace כדי לראות את נתיב ההעברה בזיכרון.
העברת פרמטרים

Call by Value (לפי ערך)

השיטה המוכרת משפות IMPLICIT-REFS, Java או Python. הארגומנט מחושב עד הסוף לפני הקריאה לפונקציה, והפונקציה מקבלת תא זיכרון (Reference) חדש לגמרי שהוא בסך הכל "עותק מקומי".

הסבר המנגנון: Copy / Newref

ב-CBV, פונקציית ההפעלה עושה את הפעולה: (extend-env var (newref val) saved-env). בגלל ה-newref הזה, המשתנה var בתוך הפונקציה מוגן. אם נעשה עליו set, הוא ידרוס אך ורק את התא הזיכרון החדש שנוצר, ולא ישפיע על משתנים מחוץ לפונקציה.

מבחן יבש (Trace Test)

let x = 10
in let f = proc (y) 
             begin 
               set y = 20;  % משנים את הפרמטר הפנימי
               y 
             end
   in begin
        (f x); % קריאה לפונקציה עם המשתנה x
        x      % מה יהיה הערך של x כאן?
      end

תשובה: התוצאה היא 10.

כאשר העברנו את x (שיושב בתא 0), המערכת קראה את ה-10 שבתא 0 ויצרה תא חדש (תא 1) עבור y והכניסה לתוכו 10. ההשמה set y = 20 דרסה רק את תא 1! תא 0 של x נשאר 10.

הדמיה השוואתית: העברת פרמטרים CBV מול CBR הדמיה אינטראקטיבית

ראו כיצד משתנים מוקצים בזיכרון (Store) ומקושרים בסביבה (Environment) בכל אחד מהמודלים עבור הקוד:
let x = 10 in let f = proc(y) begin set y = 20; y end in begin (f x); x end

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

Call by Reference (לפי הפניה)

שיטה המוכרת מ-C++ (בעזרת `&`) המעניקה לפונקציה גישה "כירורגית" ומסוכנת לתאי הזיכרון המקוריים של המשתנים שנשלחו אליה. המטרה: לייצר מנגנון של Alias (כינוי נוסף לאותו תא).

מתווך הארגומנטים: value-of-operand 

;; במקום לעשות סתם value-of שמחשב את הערך, המתווך בודק:
(define value-of-operand
  (lambda (exp env)
    (cases expression exp
      
      ;; אם הארגומנט ששלחו לי הוא משתנה נקי (כמו 'x')
      (var-exp (var) 
        ;; אל תעשה deref! פשוט תעביר את הכתובת של 'x' ישירות!
        (apply-env env var)) 
        
      ;; אם זה ביטוי מתמטי (כמו '+ 1 2' או סתם '5')
      (else
        ;; תחשב כרגיל, ותיצור עבורו newref משלו כ-Fallback
        (newref (value-of exp env))))))

;; בפונקציית ההפעלה - אין יותר newref! הפרמטר מקבל את הכתובת הגולמית:
(define apply-procedure
  (lambda (proc1 val)
    ...
    (extend-env var val saved-env)))

מבחן יבש (Trace Test)

ניקח את אותו הקוד מ-CBV:

let x = 10
in let f = proc (y) 
             begin set y = 20; y end
   in begin (f x); x end

תשובה: התוצאה היא 20!

כשהעברנו את x (נניח שתא 0), המתווך value-of-operand תפס את זה, ובגלל שזה var-exp, הוא החזיר לפונקציה את המספר 0 (הכתובת המקורית). הפרמטר y נקשר לתא 0. הפעולה set y = 20 דרסה את תא 0, ולכן x החיצוני השתנה!

🔗 תרשים כינויים (Aliasing) בהעברה לפי מצביע Call-by-Reference

בהעברה לפי מצביע (CBR), המפרש אינו מקצה תא חדש ב-Store עבור פרמטר הפונקציה. במקום זאת, המשתנה הפנימי y מקבל את אותה הכתובת בדיוק של המשתנה החיצוני x. כל שינוי ב-y ישנה מיידית את x.

סביבת הקורא (Caller Env) x ➔ L1 סביבת הפונקציה (Callee Env) y ➔ L1 אותה כתובת (Aliasing) Store (זיכרון משותף) L1 ➔ num-val(99)

💡 תופעת ה-Aliasing (כינוי מרובה) ב-CBR

המונח המדעי החשוב ביותר בהקשר של Call by Reference (CBR) הוא Aliasing (כינוי מרובה).

כאשר אנו שולחים משתנה חיצוני x לפונקציה המקבלת פרמטר y, בטבלת הסביבה (Environment) נוצרים שני שמות שונים (x ו-y) המצביעים לאותו תא זיכרון בדיוק (Store Location). זהו לב העוצמה והסכנה בשיטה זו.

🔥 סכנת ה-Aliasing הכפול:

תיאורטית, אם נפעיל פונקציה המקבלת שני פרמטרים ב-CBR ונשלח לה את אותו המשתנה פעמיים (למשל (f x x)), שני הפרמטרים של הפונקציה arg1 ו-arg2 יקבלו את אותה כתובת זיכרון בדיוק. כלומר, שניהם יהיו כינויים (Aliases) של x, ועדכון של arg1 ישנה באופן מיידי ובלתי צפוי את ערכו של arg2 בגוף הפונקציה!

🔗 הדמיית עריכה חיה: סכנת ה-Aliasing ב-Call by Reference

בשיטת CBR, המשתנה המקומי בתוך הפונקציה (y) הופך לכינוי (Alias) של המשתנה החיצוני (x). שניהם מצביעים לאותה תיבת זיכרון בדיוק. שחק עם ערך המשתנה y וראה את השפעתו המיידית.

שנה את ערך המשתנה y (הפרמטר בגוף הפרוצדורה):
ערוך אותי!
הסבר: מאחר ששני המשתנים x ו-y מצביעים ל-L0, כל עדכון של y (למשל פקודת השמה set) משנה ישירות את הערך ב-L0, ולכן x יקרא את הערך החדש מיד.
משתנה חיצוני (x)
x
Env: x ➔ L0
פרמטר פנימי (y)
y
Env: y ➔ L0
תא זיכרון ב-Store
L0 (Location 0) num-val(10)
העברת פרמטרים

Call by Name / Need (עצלנות)

משפחת ה-Lazy Evaluation (הערכה עצלנית) המוכרת מ-Haskell. למה לחשב ארגומנט מורכב ולבזבז זמן אם הפונקציה בסוף בכלל לא משתמשת בו? במקום תוצאה מחושבת, אנו מעבירים הבטחה: Thunk.

יצירת ה-Thunk והשליפה (Deref) החכמה

;; המתווך: במקום לחשב, נארוז בעטיפת Thunk ונשמור ב-Store!
(define value-of-operand
  (lambda (exp env)
    (cases expression exp
      (var-exp (var) (apply-env env var)) ; מעביר Reference (כמו CBR)
      (else (newref (a-thunk exp env)))))) ; Thunk! לא מריץ value-of!!

;; פריקת ה-Thunk מתרחשת אך ורק כששולפים משתנה:
(var-exp (var) 
  (let* ((ref1 (apply-env env var))
         (w (deref ref1))) ; הבאנו את תוכן התא
    (if (expval? w)
      w ; זה מספר רגיל, תחזיר אותו
      (let ((v1 (value-of-thunk w))) ; זה Thunk! הרץ אותו עכשיו!
        (begin
          (setref! ref1 v1) ; Call-by-Need: שומרים את התוצאה למען העתיד!
          v1)))))

ההבדל בין Name ל-Need

Call by Name: ללא Memoization. בכל פעם שהקוד קורא ל-var-exp, הוא מריץ את ה-Thunk מחדש. זה עלול לחשב המון פעמים את אותה מתמטיקה כבדה.

בשביל Name, פשוט מוחקים את שורת ה-(setref! ref1 v1) מהקוד.

Call by Need (עצלנות חכמה): משתמש ב-Memoization. מריצים את ה-Thunk פעם אחת בלבד, ושומרים את התוצאה ב-Store. להלן שרשרת הפעולות הפיזית בזיכרון:

  1. מצב התחלתי: תא הזיכרון ref1 מחזיק טיפוס thunk (הבטחה עם הביטוי והסביבה הלקסיקלית שלו).
  2. גישה ראשונה (Deref): כאשר מנסים לקרוא את המשתנה בפעם הראשונה, המפרש מבצע deref, מזהה שזה thunk ומריץ את value-of-thunk כדי לחשב את הערך.
  3. עדכון התא (רגע המפנה): המערכת לוקחת את התוצאה המחושבת (ה-Expressed Value) ודורסת את ה-thunk באותו תא ref1 באמצעות פקודת setref!.
  4. גישות עתידיות: מעתה ואילך, התא מכיל את הערך המחושב עצמו (כמו מספר או בוליאני) ולא הבטחה. כל פנייה עתידית מחזירה את המספר מיידית ללא חישוב מחדש.

* הבנה של שרשרת זו מבהירה מדוע המבנה דורש שפת IMPLICIT-REFS, המאפשרת מוטציה ב-Store מאחורי הקלעים כדי לעדכן את תא המשתנה מ-Thunk לערך המוחשי.

למה עצלנות ו-Side Effects שונאים זה את זה?

תארו לכם שהארגומנט שלנו הוא פונקציה שעושה print או מעלה Counter פנימי ב-1, והפרמטר הוא y.

  • ב-CBV: ה-Counter יעלה בדיוק פעם אחת (כשקוראים לפונקציה).
  • ב-CBN (Name): ה-Counter יעלה כל פעם שכותבים y בפונקציה! (תוצאה משוגעת).
  • ב-CBN (Need): ה-Counter יעלה פעם אחת מתישהו בזמן ריצת הפונקציה (מתי שמשתמשים ב-y בפעם הראשונה).

החוסר יכולת לחזות מתי ומי יריץ את ההדפסה הוא הסיבה ששפות פונקציונליות עצלניות כגון Haskell אוסרות על תופעות לוואי לחלוטין!

📊 טבלת השוואה: Call-by-Need לעומת Call-by-Name

מאפיין Call-by-Name Call-by-Need
הערכת ארגומנט נדחית עד לשימוש ראשון נדחית עד לשימוש ראשון
שמירת תוצאה לא — כל גישה מחשבת מחדש כן — Memoization, חישוב פעם אחת בלבד
ייצוג ה-Thunk a-thunk(exp, env) a-thunk(exp, env) → אחרי הערכה: evaluated(val)
ביצועים עלול לחשב ביטויים יקרים פעמים רבות חוסך חישוב כפול — יעיל יותר
שפה מייצגת Algol 60 Haskell

🎁 אנימטור Thunk: עצלנות לפי שם (Name) מול צורך (Need)

בשיטות עצלניות, המפרש מעביר "קופסה סגורה" (Thunk) המכילה את הביטוי הלא-מחושב. בחר שיטה, לחץ "Access Variable" וראה כיצד ה-Thunk נפתח, והאם הערך נשמר בבטון (Memoization) או מחושב מחדש.

Call-by-Name

בגישת Name, בכל פעם שניגשים למשתנה, ה-Thunk נפתח, מעריך מחדש את הביטוי (מריץ את גלגלי השיניים), ומחזיר את הערך. אין שימור זיכרון.

מספר קריאות (Accesses): 0
חישובים שבוצעו בפועל: 0
thunk(+(10,5))
Chest status: CLOSED (Lazy Thunk)