מבוא ו-EXPLICIT-REFS

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

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

store.scm (חדש!)

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

lang.scm

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

data-structures.scm

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

environments.scm

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

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

"המפרש הטיפש ביותר בעולם לזיכרון": ה-Store ממומש פשוט כרשימה (List) ב-Racket, וכתובת זיכרון (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
ניתן לדריסה!
מבוא ו-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 מריץ סדרה ומחזיר את הערך של האחרונה.

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

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

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

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

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

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

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

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

;; גם בסביבות רקורסיביות, apply-env יוצר newref בזמן אמת עבור קלוז'רים!
(extend-env-rec* (p-names b-vars p-bodies saved-env)
  (let ((n (location search-var p-names)))
    (if n
      (newref ; <-- התוספת החיונית שנופלים עליה במבחנים!
        (proc-val
          (procedure (list-ref b-vars n) ...)))
      (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

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

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

📥

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

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

👀

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

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

✍️

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

כדי לעדכן משתנה פשוט כותבים set x = 10. המפרש מוצא את הכתובת של x בסביבה ומעדכן ישירות ב-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))))))
שפת IMPLICIT-REFS (ממן)

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

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

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, מוסיפה את הגרסה לרשימה הפנימית, ושומרת בחזרה בעזרת setref!. הגרסה החדשה שומרת את סביבתה הלקסיקלית המעודכנת (env) ללא קשר לגרסאות האחרות!

מנגנון הדיספאץ' (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

שפת 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

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

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

Expression ::= pair ( 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)

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

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

  • רשימות מקושרות: אם ה-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))))

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

חלק 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.

העברת פרמטרים

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 החיצוני השתנה!

העברת פרמטרים

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. הרצה אחת, והתוצאה נשמרת ב-Store ודורסת את ה-Thunk! בפעמים הבאות נקבל מספר מיד. זוהי ההתנהגות בפועל בקוד שראינו.

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

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

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

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