סיכום למבחן - שפות תכנות ומפרשים (EOPL)

1. קבוצות נתונים אינדוקטיביות ודקדוק (BNF)

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

דוגמאות לדקדוק נפוץ (Grammar)

עץ בינארי (Bintree): יכול להיות עלה (מספר) או צומת פנימי המכיל סימבול ושני תתי-עצים.

Bintree ::= Int | (Symbol Bintree Bintree)

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

LcExp ::= Identifier
      ::= (lambda (Identifier) LcExp)
      ::= (LcExp LcExp)

מושג חשוב - Bound Variable: במבנה הלמבדה, המזהה (Identifier) המוצהר הופך להיות "קשור" (Bound) לכל מופע שלו בתוך גוף הביטוי.

2. תכנות מונחה דקדוק (Follow The Grammar)

איך כותבים פונקציה שתעבד את מבני הנתונים האינדוקטיביים שהגדרנו (כמו עץ או LcExp)? הכלל החשוב ביותר בקורס הוא: המבנה של הפונקציה חייב לחקות את מבנה הדקדוק!

📌 המתכון לעבודה עם דקדוק (The Recipe):

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

3. הפשטת נתונים (Data Abstraction)

הפשטת נתונים היא העיקרון של הפרדה מוחלטת בין **איך משתמשים במידע** (הממשק - Interface) לבין **איך המידע שמור בזיכרון** (המימוש - Implementation). אם קוד המפרש שלנו יהיה בלתי-תלוי בייצוג (Representation-Independent), נוכל להחליף את המבנה הפנימי מבלי לשבור את הקוד.

רכיבי הממשק (The Interface)

בנאים (Constructors): פונקציות שאחראיות לקחת נתונים גולמיים ולארוז אותם לתוך טיפוס הנתונים. (לדוגמה: empty-env, extend-env).
מתבוננים (Observers): פונקציות ששואלות שאלות על המידע מבלי לשנות אותו. נחלקים לשניים:
- מנבאים (Predicates): מחזירים בוליאני, בודקים "האם הטיפוס הוא מסוג X?". (לדוגמה: is-zero?, lambda-exp?).
- מחלצים (Extractors): שולפים מידע ספציפי מתוך הטיפוס החוצה. (לדוגמה: lambda-exp->body).

* בהמשך (בסעיף 9), נראה איך הכלי define-datatype יוצר עבורנו את כל הבנאים והמנבאים באופן אוטומטי!

הדגמת "לפני ואחרי" הפשטה: פונקציית `occurs-free?`

כאשר אנו כותבים את הפונקציה occurs-free? (הבודקת אם משתנה מופיע כחופשי בביטוי למבדה), אנו יכולים לעבוד בשתי דרכים:

❌ לפני ההפשטה (תלות מלאה בייצוג כרשימות):

הקוד מפרק את הרשימה ישירות בעזרת פונקציות כמו car ו-cadr. אם נשנה את ייצוג המשתנה או הפונקציה, הקוד יישבר!

(define occurs-free?
  (lambda (search-var exp)
    (cond
      ((symbol? exp) (eqv? search-var exp))
      ((eqv? (car exp) 'lambda)
       (and
         (not (eqv? search-var (car (cadr exp))))
         (occurs-free? search-var (caddr exp))))
      (else
       (or
         (occurs-free? search-var (car exp))
         (occurs-free? search-var (cadr exp)))))))

✅ אחרי ההפשטה (ייצוג מופשט עם cases):

הקוד משתמש בממשק מופשט בלבד דרך התאמת תבניות (Pattern Matching). הוא אינו מודע לאופן שבו הביטוי מיוצג פיזית בזיכרון.

(define occurs-free?
  (lambda (search-var exp)
    (cases expression exp
      (var-exp (id) (eqv? search-var id))
      (lambda-exp (id body)
        (and
          (not (eqv? search-var id))
          (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or
          (occurs-free? search-var rator)
          (occurs-free? search-var rand))))))

4. יסודות השפה (Scheme)

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

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

אין לולאות While/For: עובדים נטו עם פונקציות רקורסיביות ופונקציות מסדר גבוה (כמו map, fold).

5. משתנים וסביבות - משפחת ה-Let

איך קושרים שמות לערכים בתוך בלוק מקומי? סכמה מציעה שלושה מנגנונים שונים:

א. let (קשירה מקבילית - Parallel):

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

(let ((x 5)
      (y (+ x 1))) ; תעוף שגיאה! x לא מוכר עדיין בסביבה החיצונית בה y מחושב
  y)

ב. let* (קשירה טורית/סדרתית - Sequential):

מתורגם מאחורי הקלעים לסדרה של ביטויי let מקוננים. כל משתנה מכיר את המשתנים שהוגדרו מעליו. כאן ה-(+ x 1) יעבוד מצוין ויחזיר $6$:

(let* ((x 5)
       (y (+ x 1))) ; יעבוד מעולה!
  y)

ג. letrec (קשירה רקורסיבית - Recursive Binding):

חובה כדי שפונקציה תוכל לקרוא לעצמה!

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

6. תנאים ובקרת זרימה

מה נחשב ל-True? הכל! ב-Scheme, כל ערך שאינו במפורש #f נחשב לאמת. מספרים, רשימה ריקה '() - הכל מייצג אמת בבדיקות תנאי.

if: חובה לספק שלושה חלקים - תנאי, ביטוי לביצוע במקרה אמת, וביטוי לביצוע במקרה שקר (Else). אי אפשר לכתוב ביטוי if ללא חלופת שקר בשפת EOPL האקדמית.

cond (בדומה ל-Switch-Case): שרשרת בדיקות תנאי עוקבות.
כלל ברזל חשוב למבחן: יש לבדוק תמיד קודם את הטיפוס לפני שבודקים את הערך הפנימי שלו. למשל, יש לבדוק קודם (number? n) ורק אז לבצע בדיקת גודל כמו (> n 0).

7. מבני נתונים (זוגות ורשימות)

רשימה ב-Scheme בנויה כשרשרת של קופסאות זיכרון (צמתים). הפקודה cons מקצה קופסה כזו בזיכרון:

car - שולף את האיבר השמאלי בקופסה (התוכן / הערך).

cdr - שולף את האיבר הימני בקופסה (המצביע להמשך הרשימה / הזוג).

שים לב להבדל הקריטי בבדיקות טיפוסים!

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

• (list? x): בודק באופן רקורסיבי שזו שרשרת תקנית ומאוזנת של זוגות המסתיימת במפורש ברשימה הריקה '() (Null).

8. רקורסיות וניהול זיכרון (TCO)

רקורסיה רגילה (Stack-based Recursion):

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

רקורסיית זנב (TCO - Tail Call Optimization):

כאן, הקריאה הרקורסיבית היא הפעולה האחרונה בהחלט (Tail Position) שמתבצעת בפונקציה.
המהדר מבין שאין צורך לחזור למסגרת הקודמת מאחר שלא נשאר קוד לביצוע בה, ולכן הוא דורס וממחזר את אותה מסגרת זיכרון שוב ושוב! (סיבוכיות מקום יורדת ל-$O(1)$). בדרך כלל ניעזר בפרמטר עזר צובר (Accumulator).

9. טיפוסים מופשטים (ADT) ו-Cases

define-datatype: מאפשר לנו להגדיר טיפוסים מופשטים ומבני נתונים חדשים בצורה בטוחה (Type-Safe). המערכת מוודאת תקינות ויוצרת עבורנו את הבנאים והמנבאים שדיברנו עליהם בשער המבוא.

cases: המנגנון המאפשר לשלוף ולחלץ מידע (Extractor מובנה). זהו מנגנון התאמת תבניות שמפרק את האובייקט לפי הבנאי שייצר אותו.

מלכודת מבחנים נפוצה ביותר!

בענף ה-else בתוך פקודת cases - אסור לפתוח סוגריים למשתנים!
אין לכתוב (else (x y) ...) אלא אך ורק (else ...), אחרת המפרש לא יתקמפל ויקרוס.

10. אדריכלות המפרש - הכרת מבנה הקבצים

כדי לבנות שפת תכנות (כמו LET), הקוד מחולק למספר קבצים, שלכל אחד מהם תפקיד קריטי במערכת (צינור העיבוד - The Pipeline). הבנה של הקבצים הללו היא המפתח למענה על שאלות במבחן.

1. קובץ lang.scm (הלקסר והפארסר)

מכיל שני רכיבים:
א. the-lexical-spec (Lexer) - מגדיר איך הופכים טקסט גולמי (Raw Text) לאסימונים (Tokens) ומתעלם מרווחים/הערות.
ב. the-grammar (Parser) - מגדיר את התחביר עצמו (ה-BNF). כל משפט בשפה נהפך לסוג מסוים של צומת בעץ התחביר (AST).

2. קובץ interp.scm (מנוע ההערכה)

הלב של המפרש. מכיל את הפונקציה value-of (הפונקציה הרקורסיבית העיקרית). היא סורקת את ה-AST שנוצר, ועל ידי התאמת תבניות (Pattern Matching) מחשבת את ערכו של כל צומת תוך שימוש במודל הסביבות.

3. קובץ data-structures.scm (הגדרת הטיפוסים)

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

4. קובץ environments.scm (ניהול טבלת הסמלים)

מספק את פעולות הממשק לעבודה עם הסביבות: empty-env (יצירת סביבה ריקה), extend-env (הרחבת סביבה קיימת עם משתנה וערך חדשים), והחשוב ביותר: apply-env (חיפוש ושליפת ערך של משתנה מתוך הסביבה).

5. קובץ op.scm (הרצת המפרש וטסטים)

אחראי על הפעלת המפרש ומתן נקודת כניסה נוחה להרצה. קובץ זה מכיל את הפונקציה (run "code") המריצה קוד מפרש ומחזירה את תוצאתו, וכן את הפונקציה (run-all) המריצה את סדרת הבדיקות (טסטים) על המפרש.

11. המנתח התחבירי (Lexer & Parser)

בהמשך לקובץ lang.scm שהכרנו, בואו נבין בדיוק מה הוא עושה.

הלקסר (Scanner): לוקח את מחרוזת הטקסט הגולמית והופך אותה לזרם של אסימונים (Tokens). במקביל, הוא מסנן וזורק לפח רווחים מיותרים, הערות קוד ומעברי שורה.
הפרסר (Parser): מקבל את רצף האסימונים מהלקסר ובונה מהם עץ תחביר ממוקד ומופשט (AST - Abstract Syntax Tree) בהתאם לחוקי הדקדוק הנתונים.

למה AST נקרא עץ "מופשט"?

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

12. סביבות לקסיקליות וייצוג פרוצדורלי

על פי מתמטיקה פורמלית, סביבה (Environment) היא פונקציה הממפה ממשתנים לערכים: $g(var_1) = val_1$. לכן, במקום לשמור סביבה כרשימה של זוגות בזיכרון, אפשר לשמור אותה ישירות כ... פונקציה!

ייצוג פרוצדורלי (Procedural Representation):

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

;; הבנאי של סביבה ריקה מחזיר למבדה שמדווחת על שגיאה
(define empty-env
  (lambda ()
    (lambda (search-var)
      (report-no-binding-found search-var))))

;; הבנאי של סביבה מורחבת מחזיר למבדה שמחליטה האם להחזיר את הערך הנוכחי או להמשיך לחפש
(define extend-env
  (lambda (saved-var saved-val saved-env)
    (lambda (search-var)
      (if (eqv? search-var saved-var)
          saved-val
          (apply-env saved-env search-var)))))

;; שליפת ערך מבוצעת פשוט על ידי הפעלת הסביבה (שהיא פרוצדורה) על שם המשתנה
(define apply-env
  (lambda (env search-var)
    (env search-var)))

מתכון לייצוג פרוצדורלי:

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

13. שפת LET

📌 תעודת זהות: שפת LET

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

שפת LET מהווה את המפרש הבסיסי. השפה אינה תומכת בפונקציות, והמשתנים בה הם קבועים ואינם ניתנים לשינוי (Immutable). ראינו את כל הקבצים המרכיבים אותה בסעיף 10.

14. שפת PROC: פונקציות מסוג ראשון (First-Class)

📌 תעודת זהות: שפת PROC

המהות: פונקציות הופכות לאזרח מדרגה ראשונה (First-Class). ניתן לשמור פונקציות במשתנים ולהעביר אותן כארגומנטים.
המנגנון המקיים: ה-Closure (סגור) השומר את קוד הפונקציה יחד עם סביבת ההגדרה הלקסיקלית שלה.
תוספת תחבירית: הגדרה: proc (x) -(x, 1), הפעלה (Application): (f 5)

קלוז'ר (Closure) – הלב הפועם של השפה!

כאשר המפרש נתקל בביטוי הגדרת פונקציה (proc-exp), הוא אינו מריץ אותו. הוא מייצר אובייקט מסוג proc-val ששומר בתוכו את קוד הפונקציה יחד עם צילום מצב של הסביבה שהייתה קיימת ברגע ההגדרה.

(procedure var body saved-env)

בעת הפעלת פונקציה (apply-procedure), גוף הפונקציה מורץ מול סביבת ההגדרה המקורית שצולמה (saved-env), כשהיא מורחבת עם הארגומנט שסופק כקלט. זהו סקופ יציב ולקסיקלי.

15. שפת LETREC: סביבות מעגליות ו-JIT

📌 תעודת זהות: שפת LETREC

המהות: מתן אפשרות לפונקציות לקרוא לעצמן בשמן (רקורסיה), או זו לזו (Mutual Recursion).
המנגנון המקיים: יצירת קלוז'רים רק ברגע החיפוש בזיכרון (Just-In-Time) והזרקת סביבה מעגלית.
תוספת תחבירית: letrec p(x) = body in letrec-body

הקסם של בניית קלוז'ר בזמן אמת (JIT Closure)

הבעיה ב-proc רגיל היא שגוף הפונקציה מוערך מול סביבה שטרם מכילה את שמה. הפתרון: הבנאי extend-env-rec אינו יוצר קלוז'רים מראש, אלא רק רושם "מתכון". יצירת הקלוז'ר נדחית לרגע החיפוש בפונקציה apply-env! כאשר apply-env מוצא התאמה, הוא מרכיב את הקלוז'ר באותו רגע ודוחף פנימה את הסביבה המורחבת עצמה (env), מה שמאפשר מעגליות והיכרות עצמית.

מימוש `apply-env` עם JIT ל-LETREC מתוך ה-PDF:

(define apply-env
  (lambda (env search-var)
    (cases environment env
      (empty-env ()
        (report-no-binding-found search-var))
      (extend-env (saved-var saved-val saved-env)
        (if (eqv? search-var saved-var)
            saved-val
            (apply-env saved-env search-var)))
      ;; כאן קורה הקסם: ברגע החיפוש, מייצרים קלוז'ר חדש ומחדירים לו את הסביבה המעגלית עצמה
      (extend-env-rec (p-name b-var p-body saved-env)
        (if (eqv? search-var p-name)
            (proc-val (procedure b-var p-body env)) ; env מכילה את פונקציית extend-env-rec
            (apply-env saved-env search-var))))))

16. המפרש נטול השמות (Nameless / LEXADDR)

📌 תעודת זהות: שפת LEXADDR

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

אינדקסי דה-ברון (Depth, Position)

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

17. המהפך מ"ערך" ל"זהות ומצב" (The Store)

ברגע שאנו מאפשרים שינוי ערכים של משתנים, משתנים מקבלים זהות פיזית (Identity) המקושרת לכתובת בזיכרון (Store), והתוכן שלהם מייצג את המצב (State) שיכול להשתנות.

Denoted Values ($\text{DenVal}$): מה שהסביבה שומרת (כעת: מצביעים לכתובות).
Expressed Values ($\text{ExpVal}$): הערך האמיתי המוחזר מחישוב.
הסביבה קושרת כעת את שם המשתנה אל כתובת זיכרון (Reference), בעוד שה-Store קושר את כתובת הזיכרון אל הערך הפיזי (Value).

18. שפת EXPLICIT-REFS (ניהול ידני)

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

📌 כלל אתחול הזיכרון (Store Initialization):

בשפה זו (ובכל שפה המשתמשת ב-Store), פונקציית ההערכה הראשית value-of-program מחויבת לקרוא קודם כל לפקודה (initialize-store!) כדי לאפס לחלוטין את הזיכרון הפיזי המשותף לפני הרצת התוכנית.

4 הפקודות המפורשות:

newref(x) - מקצה תא ב-Store ומחזיר את הכתובת.
deref(loc) - שולף את הערך מהכתובת.
setref(loc, val) - דורס/מעדכן את הכתובת. (מחזיר ערך דאמי כמו 23).
begin ... end - בלוק שמשמש כ"פח אשפה" לערכי הדאמי שמחזירות פקודות ההשמה. הוא מריץ רצף ומחזיר את האחרון.

19. שפת IMPLICIT-REFS (ניהול אוטומטי)

מודל כמו של פייתון או JavaScript. הסביבה תמיד מכילה אך ורק כתובות (References)! ההקצאה (newref) והשליפה (deref) מתבצעות אוטומטית מאחורי הקלעים.

L-value מול R-value

R-value (קריאה): המפרש מחפש את המשתנה ומבצע אוטומטית deref כדי להביא את הערך.
L-value (השמה - set x = 10): המפרש פונה לסביבה, מקבל את כתובת הזיכרון, ומבצע setref! ישירות אליה כדי להחליף את הערך.

🔄 רקורסיה ב-IMPLICIT-REFS: הבנאי `extend-env-rec*`

בגלל שהסביבה ב-IMPLICIT-REFS ממפה שמות ישירות לכתובות ב-Store, הרקורסיה ממומשת בצורה שונה מאשר ב-LETREC הסטנדרטית:
• אנו משתמשים בבנאי סביבה מיוחד: extend-env-rec*.
• בנאי זה מייצר קלוז'רים בצורה דינמית ושומר אותם פיזית בתוך ה-Store באמצעות newref.

⚠️ מגבלה קריטית למבחן: בשל אופי המימוש הזה של הזיכרון והסביבות, שפת IMPLICIT-REFS תומכת ברקורסיה של פונקציות בלבד (Recursive Functions), אך אינה תומכת ברקורסיה של מבני נתונים (Recursive Data).

20. זוגות משתנים (MUTABLE-PAIRS)

אפשרות לייצר זוגות (רשימות) שאיבריהן ניתנים לשינוי באמצעות setleft ו-setright. הערכים בזוג עצמם מיוצגים כהפניות (References).

21. מנגנוני העברת פרמטרים (Parameter Passing)

כיצד ארגומנט מועבר לפונקציה? המפרש מנתב אותו דרך פונקציה מתווכת: value-of-operand.

Call-by-Value (לפי ערך)

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

Call-by-Reference (לפי מצביע / הפניה)

המתווך מעביר לפונקציה את כתובת הזיכרון הקיימת עצמה. נוצר Aliasing (כינוי מרובה). שינוי הערך פנימה משנה אותו גם בחוץ.

Call-by-Name (עצלנות)

החישוב מושהה! מועבר Thunk (קופסה עם ה-AST וסביבת ההגדרה). מחושב מחדש בכל פעם שניגשים אליו.

Call-by-Need (עצלנות חכמה)

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

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

22. ★ טבלת השוואה מסכמת של אבולוציית השפות (חשוב למבחן)

תכונה / שפה	LET	PROC	LETREC	EXPLICIT-REFS	IMPLICIT-REFS
פונקציות	❌ לא	✅ כן (אנונימיות ע"י proc)	✅ רקורסיביות ע"י letrec	✅ רקורסיביות ע"י letrec	✅ ע"י extend-env-rec*
תמיכה ברקורסיה	❌	❌	✅ תומך	✅ תומך	✅ לא עבור Data רקורסיבי
סביבה (Bindings)	ערך (Value)	ערך (Value)	ערך (Value)	ערך או מצביע	מצביע (Reference) בלבד
שימוש ב-Store	❌	❌	❌	✅ ידני (newref)	✅ אוטומטי לכל המשתנים
מצב משתנה (Mutable)	❌	❌	❌	✅ ע"י setref	✅ ע"י set
קלוז'ר (Closure)	❌	✅ כן	✅ עם רקורסיה	✅ עם רקורסיה	✅ עם רקורסיה

23. ★ מדריך פרקטי: איך מוסיפים תכונות לשפה

שאלות נפוצות במבחן דורשות הוספה של אופרטור או סוג נתונים חדש. נראה את סדר הפעולות (Pipeline) באמצעות דוגמה מעשית מה-PDF: **הוספת טיפוס מחרוזת (String) ופעולת שרשור (Concat).**

עדכון מבני הנתונים (קובץ data-structures.scm):
עלינו להגדיר את טיפוס הנתונים החדש ב-ExpVal, ולהוסיף לו פונקציית חילוץ (Extractor) בטוחה:

;; הוספה תחת הגדרת ה-datatype של expval
(string-val (val string?))

;; כתיבת פונקציית חילוץ חדשה
(define expval->str
  (lambda (val)
    (cases expval val
      (string-val (str) str)
      (else (report-expval-extractor-error 'string val)))))

עדכון הדקדוק והלקסר (קובץ lang.scm):
1. נוסיף חוק מילוני ב-the-lexical-spec לזיהוי מחרוזת בין מירכאות כפולות:
```
(string (double-quote (arbno (not double-quote)) double-quote) string)
```
2. נוסיף חוקים תחביריים ל-the-grammar עבור ביטוי מחרוזת ופעולת Concat:
```
(expression (string) string-exp)
(expression ("concat" "(" expression "," expression ")") concat-exp)
```

עדכון מנוע הריצה (קובץ interp.scm):
נוסיף זרועות מתאימות בפונקציית value-of לטיפול בביטויים החדשים:

;; הערכת ביטוי מחרוזת פשוטה
(string-exp (str) (string-val str))

;; הערכת פעולת שרשור – מעריכים את שני הקלטים ומשרשרים
(concat-exp (exp1 exp2)
  (let ((val1 (value-of exp1 env))
        (val2 (value-of exp2 env)))
    (let ((str1 (expval->str val1))
          (str2 (expval->str val2)))
      (string-val (string-append str1 str2)))))

24. מבוא: Static vs Dynamic Typing

המטרה במערכות טיפוסים היא לזהות ולתפוס שגיאות לפני שהתוכנית מורצת (Compile-time). סביבת הטיפוסים ($\text{Tenv}$) פועלת בזמן בדיקה סטטית וממפה שמות לטיפוסים מופשטים בלבד.

25. שפת CHECKED (בדיקת טיפוסים מפורשת)

המתכנת מחויב להצהיר במפורש על הטיפוס (למשל: proc (x : int)). הפונקציה type-of סורקת את ה-AST, מוודאת תקינות ומונעת שגיאות מראש.
הצהרה ברקורסיה: ב-letrec חובה להצהיר מראש על טיפוס ההחזרה כדי שהקריאה הפנימית הרקורסיבית תוכל להתבצע חוקית מול ה-$\text{Tenv}$.

⚠️ חוקי ה-IF הנוקשים בזמן בדיקה סטטית:

המהדר הסטטי אינו יודע (ולא מסוגל לחזות) איזה ענף יתבצע בפועל בזמן ריצה. לכן, נקבע כלל ברזל נוקשה:
זרוע ה-then וזרוע ה-else חייבות להיות מאותו הטיפוס בדיוק (למשל, שתיהן מחזירות int).
אם יש אי-התאמה (ענף אחד מחזיר מספר וענף שני מחזיר בוליאני), המערכת תזרוק שגיאת טיפוסים (Type Error) בשלב הקימפול/בדיקה, גם אם בזמן ריצה השגיאה לא הייתה מתרחשת בפועל (למשל כשהתנאי הוא תמיד אמת).

26. שפת INFERRED (הסקה אוטומטית של טיפוסים)

המתכנת משתמש בסימן ? במקום טיפוס. המהדר פותר מערכת משוואות בעזרת אילוצים ואלגוריתם Unification. משתמשים במשתני טיפוס טריים (Gensym, לדוגמה $t_1$). כדי לא להעביר רק תוצאה אחת, מחזירים אובייקט an-answer המכיל את הטיפוס + מילון ההצבות (Substitutions) כדי להעביר את הידע שנצבר הלאה.

27. שלב א': גזירת חוקים ומשוואות (Constraints)

מנוע ה-Inferrer סורק את עץ התחביר (Bottom-Up) ומייצר משוואות:

הביטוי (Expression)	המשוואה המאולצת	משמעות
-(E1, E2)	t1 = int, t2 = int, t_res = int	אופרטורים מתמטיים דורשים תמיד קלטים מספריים.
if E1 then E2 else E3	t1 = bool, t2 = t3, t_res = t2	התנאי בוליאני, והזרועות (Then/Else) חייבות להיות זהות.
proc (x) Body	t_res = t_x → t_body	מייצר טיפוס פונקציה מהקלט לתוצאה.
(Rator Rand)	t_rator = t_rand → t_res	החוק הקריטי! טיפוס הפונקציה המופעלת (Rator) חייב להתאים לטיפוס הארגומנט (Rand) ולתוצאה.

28. שלב ב': אלגוריתם ה-Unification וטבלת ההצבות (Substitutions)

האלגוריתם פותר משוואות (נניח $L = R$) מתוך רשימת המשוואות. הוא מתחזק טבלת הצבות (Substitutions table), ובכל שלב הוא:

זהות (Identity): אם $L$ ו-$R$ הם אותו הטיפוס (כמו $\text{int} = \text{int}$) - מתעלמים.
הצבה (Substitution): אם צד אחד הוא משתנה זמני ($t$), בודקים אם יש צורך לעדכן אילוצים קודמים או עתידיים, ואם כן - מציבים את הערך שלו. חובה לבצע בדיקת הופעה (Occurs Check) לפני!
פירוק (Decomposition): אם מדובר בשתי פונקציות ($t_1 \rightarrow \text{int} = \text{bool} \rightarrow t_2$), מפרקים לשתי משוואות קטנות: $t_1 = \text{bool}$ ו-$\text{int} = t_2$.
שגיאה: סתירה מהותית כמו $\text{int} = \text{bool}$ זורקת שגיאת התאמה. ממשיכים את טבלת ההצבות עד שאין יותר מה להעביר, ואז מתקבל הטיפוס הסופי.

דוגמה מעשית מלאה: הרצת אלגוריתם Substitutions

נראה כיצד אלגוריתם ה-Unification פותר ומסיק את הטיפוס עבור הביטוי הבא:
let f = proc (x) - (x, 1) in (f 10)

1. גזירת אילוצים (Constraints Generation):

עבור proc (x) נניח טיפוס קלט $t_x$ וטיפוס פלט $t_{\text{body}}$.
עבור הגוף -(x, 1) נגזר האילוץ: $t_x = \text{int}$ (כי החיסור מקבל מספרים) וטיפוס הגוף הוא $\text{int}$.
לכן טיפוס ה-proc הוא $t_{\text{proc}} = t_x \rightarrow \text{int}$.
בשל ה-let, טיפוס המשתנה $f$ (נסמן $t_f$) נקשר לטיפוס ה-proc: $t_f = t_{\text{proc}}$.
עבור גוף ה-let שהוא הפעלת פונקציה (f 10): הארגומנט הוא 10 (טיפוס `int`), ולכן $t_f = \text{int} \rightarrow t_{\text{let}}$ (כאשר $t_{\text{let}}$ הוא טיפוס הביטוי כולו).

2. טבלת צעדי ה-Unification ועדכון מילון ההצבות ($\sigma$):

צעד	המשוואה לפתרון	הלוגיקה / פעולת האלגוריתם	מילון ההצבות המצטבר (Substitutions)
1	t_x = int	הצבה פשוטה – שומרים במילון.	[t_x ↦ int]
2	t_proc = t_x → int	מחילים את ההצבה הקודמת: $t_{\text{proc}} = \text{int} \rightarrow \text{int}$. שומרים.	[t_x ↦ int, t_proc ↦ (int → int)]
3	t_f = t_proc	מחילים הצבות: $t_f = \text{int} \rightarrow \text{int}$. שומרים במילון.	[t_x ↦ int, t_proc ↦ (int → int), t_f ↦ (int → int)]
4	t_f = int → t_let	מחילים הצבות על שני הצדדים: $\text{int} \rightarrow \text{int} = \text{int} \rightarrow t_{\text{let}}$.	[t_x ↦ int, t_proc ↦ (int → int), t_f ↦ (int → int)]
5	int → int = int → t_let	פירוק (Decomposition): יוצר 2 תתי-משוואות.	[t_x ↦ int, t_proc ↦ (int → int), t_f ↦ (int → int)]
6	int = int	זהות (Identity): מתעלמים.	[t_x ↦ int, t_proc ↦ (int → int), t_f ↦ (int → int)]
7	int = t_let	מזהים משתנה: קושרים את $t_{\text{let}}$ ל-`int`. שומרים במילון.	[t_x ↦ int, t_proc ↦ (int → int), t_f ↦ (int → int), t_let ↦ int]

הסיכום: הערך הסופי שמופק עבור טיפוס התוכנית כולה הוא int!

29. מקרי קצה ותובנות חשובות

⚠️ למה חייבים לבצע בדיקת הופעה (Occurs Check)?

אם יש פונקציה שמפעילה את עצמה (x x) נקבל משוואה $t_x = t_x \rightarrow t_{\text{res}}$. ללא בדיקה מקדימה, הצבה עיוורת תוביל ללולאה אינסופית ולקריסה. האלגוריתם בודק שמשתנה לא מופיע בתוך המבנה שמנסים להציב אליו.

🔒 בעיית הנעילה המונומורפית (Monomorphic Lock-in)

בשפת INFERRED הבסיסית אין פולימורפיזם אמיתי. ברגע שפונקציית זהות proc(x:?) x (המוסקת כ-$t_x \rightarrow t_x$) מופעלת פעם אחת על מספר, המשתנה $t_x$ ננעל על int! לא ניתן להפעילה שוב על טיפוס אחר באותו הקוד.

שפות תכנות ומפרשים

מבוא: יסודות תיאורטיים (מתוך פרקים 1-2)