מבוא

קצת על הבחינה

הקדמה קצרה על מבנה המבחן ודגשים עיקריים.

מזל טוב! עוד מעט אתם נבחנים ובתקווה גדולה מסיימים עם הקורס 🥳

🔍 המבחן מחולק בכללי לשני חלקים:

  • חלק ראשון של שאלות 1 ו-2: שמטרתן להוסיף \ לשנות משהו בארכיטקטורה של השפות. בשאלות אלו צריך להבין הייטב מה בדיוק רוצים ולהרחיב קבצים קבועים לפי הדרישות. השאלות די בנויות על קו מחשבה קבוע אבל דורשות עבודה ומחשבה (והרבה כתיבה).
  • וחלק שני, שאלה 3 של קביעת טיפוסים: שאלה מאוד אלגוריתמית, ולכן מומלץ לתרגל אותה כמה פעמים עד שהאלגוריתם נכנס טוב לראש ואולי גם לכתוב איזו דוגמא בספר למקרה של בלאק אאוט (נגיד אפשר אפילו לפתור את ממן 16 על דף ריק ואז לתפוס שתי ציפורים במכה אחת). אם אתם יודעים את האלגוריתם אפשר להריץ אותה עם 25\25 נקודות מובטחות.

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

כמה טיפים לקראת הבחינה:

  • לפני הבחינה תתרגלו עם דף ועט, אל תכתבו רק תוכניות במחשב אלא תנסו לדמות את תנאי הבחינה המדוייקים.
  • כמו כל קורס - הסוד להצלחה הוא תרגול תרגול ועוד תרגול.
  • לבחינה עצמה תביאו מרקרים או עטים צבעוניים, יעשה לכם סדר בעיניים בשאלה 3.
  • נכון שמותר ומומלץ לכתוב בספר, אבל אל תמלאו אותו בקשקושים, קודם תבינו מה ואיך לפתור ואחכ תכניסו כמה שיותר הערות *רלוונטיות*, עדיף קצת ההערות טובות ורלוונטיות מהמון בלאגן וקשקושים לא ברורים.

בהצלחה! 🎓🚀

שלב 0

המודל המנטלי המתוקן: מתחביר לסמנטיקה

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

המחשב לא יודע לקרוא טקסט, והוא בטח לא מבין מה המשמעות של מילים באנגלית כמו if, while או switch. לכן, תהליך העיבוד מחולק לשלבים מוגדרים:

1

ניתוח לקסיקלי
(Lexer / Scanner)

מתווים למילים

התוכנית שהמשתמש מקליד היא בסך הכל רצף ארוך של תווים (Concrete Syntax). ה-Scanner עובר על התווים הללו ומקבץ אותם לאסימונים (Tokens). הוא מזהה שמקבץ התווים "i" ו-"f" יוצר את המילה השמורה if.

2

ניתוח תחבירי
(Parser)

פיגומים ובניית העץ

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

3

עץ תחביר מופשט
(AST)

הסרת הפיגומים

ברגע שהפרסר סיים לבנות את המבנה ההיררכי וחילץ את הנתונים האמיתיים (ה-Non-Terminals: המשתנים, המספרים והביטויים שעליהם נבצע פעולות), תפקידם של הטרמינלים הסתיים. ממש כמו בבניית בניין - ברגע שהשלד עומד יציב, מפרקים וזורקים את הפיגומים. עץ ה-AST הוא ה"בניין" נטו, ולכן קוראים לו תחביר מופשט (Abstract) – הוא הופשט מכל ה"רעש" התחבירי.

4

מנוע ההערכה
(Interpreter / value-of)

חיים בתוך הבניין

זהו ה-Back-End של השפה. פונקציית value-of מקבלת את ה-AST הנקי. בשלב הזה, למפרש כבר ממש לא אכפת איך המתכנת הקליד את הקוד. לא אכפת לו אם השתמשו בסוגריים עגולים או מרובעים, ואם כתבו if או אולי מילה בעברית כמו אם. למפרש אכפת רק מהסמנטיקה: הוא רואה צומת של תנאי, צומת של אמת וצומת של שקר, ומפעיל עליהם את חוקי הלוגיקה והזיכרון.

מהפיגומים לבניין: דוגמה ויזואלית לעץ AST

כשאנחנו מגדירים בשפה שלנו חוק דקדוקי (Grammar), אנחנו כותבים למשל:
Expression ::= if Expression then Expression else Expression

⚠️ זורקים את הפיגומים:

שימו לב לעץ ממול. עץ ה-AST של משפט if מכיל רק 3 ילדים (ה-Non-Terminals): ביטוי התנאי, ביטוי ה-true, וביטוי ה-false. המילים if, then, else שהיו "הפיגומים" פשוט נזרקו לפח ולא קיימות שם יותר. אנחנו נשארנו עם המשמעות הנקייה (הסמנטיקה).

קוד מקור (תחביר):

if zero?(x) then 1 else 0

ייצוג AST בזיכרון (סמנטיקה):

[if-exp]
(zero?-exp)
|
x
(const-exp)
|
1
(const-exp)
|
0

מפת הקבצים: מי עושה מה?

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

📝 lang.scm

תפקיד: מחלקת הקבלה (Syntax / Front-End)

כאן אנחנו מגדירים איך השפה נראית (תחביר).

  • Scanner (the-lexical-spec): מזהה מילים (מספרים, משתנים). מפריד ל-Tokens.
  • Parser (the-grammar): חוקי התחביר שעל פיהם מזהים פיגומים ובונים את עץ ה-AST.
⚙️ interp.scm

תפקיד: המנוע (Semantics / Back-End)

כאן אנחנו מגדירים מה השפה עושה (סמנטיקה).

  • מכיל את value-of שרצה על העץ המופשט (ללא טרמינלים).
  • מחליטה מה לעשות עם כל צומת (Pattern Matching עם cases).
  • כאן קורית הלוגיקה האמיתית של התוכנית.
💾 data-structures.scm

תפקיד: הזיכרון והערכים (State)

הטיפוסים שקיימים בזמן ריצה.

  • expval: הערך המחושב (מספר, בוליאני, פרוצדורה, מערך).
  • סביבה (Environment): המילון שממפה בין משתנה לערכו או למיקומו בזיכרון.
🚀

אז איך משדרגים שפה? (הקשר לאלגוריתמים)

כאשר מבקשים ממך להוסיף יכולת לשפה (למשל ביטוי switch או לולאת for), עליך להעביר את הפיצ'ר החדש בכל "צינור העיבוד":

  1. הוספה ל-Parser (קובץ lang.scm): מוסיפים כלל ל-the-grammar. פעולה זו גורמת למערכת לייצר צומת חדש לעץ ה-AST. (עונה על: "מה צריך להוסיף לדקדוק?")
  2. טיפול בערכים (קובץ data-structures): רק אם הפיצ'ר מחייב יצירת טיפוס נתונים חדש שעוד לא קיים (מחרוזת, זוג, מערך) נוסיף אותו ל-expval. (לביטוי switch למשל, לא צריך, כי הוא מחזיר ערכים רגילים).
  3. הוספת לוגיקה למנוע (קובץ interp.scm): הולכים לפונקציה value-of, מוסיפים case חדש שיתפוס את הצומת שנוצר, וכותבים את ההיגיון – מה צריך לחשב.
* כעת, כשתיגש לקרוא את האלגוריתמים המפורטים (שאלות 1 ו-2), זכור את המבנה הזה. האלגוריתמים פשוט מפרטים את הסינטקס של Scheme לביצוע שלושת השלבים הללו.
🚀 סימולטור אינטראקטיבי

המסע של פקודה חדשה

נעבור יחד צעד-אחר-צעד: מקבלת הדרישה במבחן, ועד לריצה של לולאת while בתוך המפרש שלנו.

step1.txt
שלב 1 מתוך 6
מרחב עבודה | שליף מהיר

כרטיסיות: פונקציות זהב

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

cases

פירוק צמתי AST

לחץ להיפוך
קוד לדוגמה:
(cases expression exp
  (var-exp (id)
    (apply-env env id)))

שולפת את הנתונים השמורים בתוך צומת מסוג AST ספציפי.

value-of

הערכת ביטוי

לחץ להיפוך
קוד לדוגמה:
(value-of
  (if-exp (var-exp 'x) (num-exp 1) (num-exp 0))
  env)

מקבלת ביטוי וסביבה, ומחזירה את הערך (ExpVal) הסופי לאחר ההרצה במפרש.

apply/extend-env

ניהול זיכרון

לחץ להיפוך
קוד לדוגמה:
(extend-env
  var-name val old-env)

יוצרת סביבה חדשה שבה var מקבל את val, וזוכרת את הסביבה הקודמת. apply-env שולפת ערך מהזיכרון.

Wrappers

המרת ערכים

לחץ להיפוך
קוד לדוגמה:
(let ((v1 (expval->num (value-of e env))))
  (num-val (+ v1 1)))

מחלצת ערכים מתוך ה-ExpVal של המפרש לפעולות סכים (expval->num), ואז עוטפת חזרה (num-val).

map

לולאה על רשימה

לחץ להיפוך
קוד לדוגמה:
(map
  (lambda (exp) (value-of exp env))
  list-of-exps)

לוקחת רשימת ביטויים, ומריצה פונקציה (כמו value-of) על כולם כדי לקבל רשימה של תוצאות.

apply-procedure

הרצת פונקציות

לחץ להיפוך
קוד לדוגמה:
(apply-procedure
  (proc-val (procedure 'x body saved-env))
  (num-val 5))

לוקחת אובייקט פרוצדורה ואת הערך לארגומנט, ומתחילה להריץ את גוף הפונקציה בסביבה החדשה.

let / let*

משתנים מקומיים

לחץ להיפוך
קוד לדוגמה:
(let* ((v1 (value-of exp1 env))
       (v2 (value-of exp2 env)))
  (num-val (+ v1 v2)))

מגדירה משתנים זמניים (כמו v1 ו-v2) כדי לאסוף את התוצאות ולהשתמש בהן באופן קריא.

cons / append

בניית רשימות

לחץ להיפוך
קוד לדוגמה:
(cons (value-of first-exp env)
      (value-of rest-exp env))

מחברת איבר בודד (cons) לתוך רשימה. append מחברת שתי רשימות מלאות לכדי רשימה אחת.

define-datatype

הגדרת AST

לחץ להיפוך
קוד לדוגמה:
(define-datatype expression expression?
  (var-exp (id symbol?))
  (app-exp (rator expression?) (rand expression?)))

מגדירה טיפוס נתונים חדש עם התבניות (Variants) שלו, וסוג המשתנים שכל תבנית דורשת.

lambda

פונקציה אנונימית

לחץ להיפוך
קוד לדוגמה:
(define get-names
  (lambda (lst)
    (map (lambda (v) (get-name v)) lst)))

מייצרת פונקציה 'על המקום'. משמשת המון להעברת פעולות מהירות לתוך map או filter.

cond

תנאים מרובים

לחץ להיפוך
קוד לדוגמה:
(cond
  ((null? lst) 0)
  ((eq? (car lst) 'x) 1)
  (else (+ 1 (count-x (cdr lst)))))

מבנה נקי ל-if שמטפל בכמה תנאים ברצף. מעולה לפונקציות רקורסיביות שמטפלות במקרי קצה.

filter

סינון רשימה

לחץ להיפוך
קוד לדוגמה:
(filter
  (lambda (val) (> (expval->num val) 0))
  list-of-vals)

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

שאלה 1 | שלב 0

מבט על: מפת קבצים ואלגוריתם

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

הבנת הסמנטיקה

אבחון וניתוח התנהגות

lang.scm

עדכון כללי התחביר

data-structures

הוספת ערכים חדשים

interp.scm

כתיבת הלוגיקה

🧩1. הקבצים המשתתפים באלגוריתם

lang.scm

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

data-structures.scm

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

interp.scm

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

🔍סדר הפעולות (האלגוריתם בקצרה)

  • אבחון וסמנטיקה: הבנת השאלה ומה הביטוי מקבל.
  • עריכת lang.scm: הוספת כללי `separated-list` או `arbno`.
  • עריכת data-structures.scm: בדיקה האם נדרש `Variant` חדש ב-expval.
  • עריכת interp.scm: הטמעת הלוגיקה בפונקציית `value-of`.
  • הוצאה לפונקציות עזר: כדי לשמור על `value-of` נקי (למשל, לולאות ואוגרים).

שלב 1.0: מפת דרכים - איך לקרוא את הדקדוק (BNF) של השאלה?

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

מילון סימנים: מה אומר כל סמל?

::=
"מוגדר להיות"

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

Terminals (מילים שמורות)
ברזל / שלד התחביר

מילים כמו switch, foreach, when או סימנים כמו (, ], =>. אלו הם סימני פיסוק של השפה. חשוב: אנחנו לא שומרים אותם ב-AST, הם רק משמשים כ"תמרורים" שעוזרים לפרסר לדעת איפה הוא נמצא.

Non-Terminals
אבני הבניין המשתנות

מילים כמו Expression, Type, identifier. אלו הם נתונים אמיתיים שהמתכנת יכתוב! לכן, כל אחד כזה חייב לקבל שדה משלו בתוך ה-AST שלנו.

{ ... }*(,) או { ... }+(;)
רשימות והכפלות

סוגריים מסולסלים מציינים חזרה.
* אומר 0 או יותר (יכול להיות ריק).
+ אומר 1 או יותר (חייב להיות לפחות אחד).
הסימן בסוגריים העגולים (,) או (;) הוא התו המפריד בין האיברים. משמעות קריטית: זה יתורגם ל-list (רשימה) ב-AST שלנו!

ניתוח מקרים אמיתיים ממבחנים

מקרה בוחן 1: מועד 2021ב 57 (שאלת ה-switch)
Expression ::= switch ( Expression ) { { Type identifier when ( { Expression }+(,) ) => Expression }*(;) } default => Expression

איך המוח שלנו צריך לפרק את זה?

  • הטרמינלים (באדום) הם ה"פיגומים" שלנו. ה-Parser חייב אותם כדי לנווט, אך הם לא יועברו פנימה לתוך ה-AST.
  • ה-Expression הראשון הוא הביטוי שאנחנו בודקים (למשל `e1`).
  • יש לנו בלוק ארוך שחוזר על עצמו * פעמים (רשימת ה-Cases). בתוכו, בכל חזרה יש לנו 4 אלמנטים חשובים: Type, identifier, רשימה של תנאים (ה-Expression שבתוך הפלוס), ו-Expression שהוא התוצאה. זה אומר שיהיו לנו 4 רשימות במקביל ב-AST (או רשימה של אובייקטים המכילים 4 שדות). בקורס נהוג לפרק ל-4 רשימות מקבילות: typs, ids, bools (התנאים), ו-exps (התוצאות).
  • ה-Expression האחרון הוא ה-default, שדה בודד שנקרא לו defexp.

התוצאה (מבנה ה-AST שיגזר מזה):

(switch-exp (e1 typs ids bools exps defexp))
מקרה בוחן 2: מועד 2024ב 87 / 2021ב 87 (שאלת ה-foreach)
Expression ::= foreach (Type identifier in [{ Expression }(,) ] )* do Expression

הקריאה שלנו:

  • אנחנו רואים שיש כאן סוגריים מרובעים [ ] שהם חלק מהטרמינלים (צבועים באדום). בתוכם יש רשימה של Expression (מופרדים בפסיקים).
  • שימו לב לכוכבית *: הבלוק כולו חוזר על עצמו ומכיל בתוכו רשימה פנימית. כפי שלמדנו (בפתרון המקצועי), במקום לייצר ספגטי של "רשימה של רשימות", עלינו לפצל זאת! ניצור ביטוי עזר ב-Grammar (למשל foreach-case-exp) שייצג כל חזרה כזו בנפרד.
  • כך, ה-AST הראשי של הפקודה יאסוף רק רשימה אחת פשוטה של ביטויי-עזר, וגוף אחד בסוף (ה-body).
שיטת העבודה המנטלית במבחן:

כאשר אתם מקבלים את הטופס לידיים, קחו מרקר והדגישו אך ורק את ה-Non-Terminals (המילים שמתחילות באות גדולה כמו Type, Expression וכן המילה identifier). ספרו אותם! המספר שיצא לכם (תוך התחשבות ברשימות * או +) הוא בדיוק מספר השדות שיהיו בפונקציית הבנאי (constructor) של ה-AST שלכם. כך מונעים בלבול בין "מבנה השפה" לבין ה"נתונים האמיתיים".

שלב הבנה - ללא קובץ

הבנת הסמנטיקה

השלב הראשון תמיד דורש אבחון: מהו הביטוי החדש? מה הוא אמור לקבל כארגומנטים? האם מדובר בהערכה "עצלה" (Lazy) ששולפת מידע או בביצוע מפורש?

שלב 1.1: מעבר לשלד - איך לקרוא את הוראות המבחן והדוגמאות?

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

א. פענוח ההוראות המילוליות בטופס

1. כללי סביבה (Environment) וקישור

מה מחפשים? מילים כמו "מבוצע תחת סביבה שבה...", "הערך נקשר למשתנה...", או "static-binding".

התרגום לקוד: זה אומר מתי אנחנו צריכים להשתמש ב-extend-env. למשל, במועד 2021ב 87 (שאלת ה-Generator), נכתב: "יחושבו על פי הסביבה בעת הגדרת ה-generator (static-binding)". המשמעות: חייבים לשמור את ה-env הנוכחי בתוך מבנה הנתונים של ה-generator שמחזירים (ממש כמו שעושים ב-closure)!

2. סדר הערכה (Evaluation Order)

מה מחפשים? תיאור של שלבי הביצוע. "תחילה יחושב X, ואז אם התוצאה Y אז יחושב Z".

התרגום לקוד: האם אנחנו עושים value-of מיד על כל השדות (באמצעות map)? או שזה מבנה תנאי כמו if שבו מעריכים קודם חלק אחד, ולפי התוצאה מחליטים אם להעריך את השני? זה מכתיב את השימוש ב-let או if/cases בתוך המפרש.

3. ניהול זיכרון ומצב (Store/Mutability)

מה מחפשים? מילים כמו "ניתן לשינוי", "immutable", "השמה".

התרגום לקוד: במועד 2020ב 73 (שאלת ה-LET עם המערכים), נכתב במפורש: "המערך לא ניתן לשינוי לאחר הגדרתו". המשמעות: אנחנו לא צריכים לפתוח לו newref בזיכרון, אלא פשוט להחזיר array-val שמחזיק את הערכים הרגילים!

4. שגיאות מיוחדות (Error Handling)

מה מחפשים? "במקרה של שימוש לא תקין, יש להדפיס שגיאה".

התרגום לקוד: מצריך הוספת eopl:error בתוך ה-value-of. במועד 57, שאלת ה-Switch, נכתב שחובה לזרוק שגיאה אם אף מקרה לא תאם. זה מזכיר לנו שאסור שהפונקציה שלנו פשוט "תיפול", אלא עלינו לכתוב מקרה קצה שמטפל בזה מפורשות.

ב. סודות שעולים מתוך הדוגמאות

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

1
הסתרת משתנים (Variable Shadowing)

דוגמה שכיחה: מגדירים let x = 10 ואז בתוך הלולאה (למשל foreach) מגדירים שוב את הטיפוס עם המשתנה x, ובודקים מה יוצא.
המטרה: לוודא שה-extend-env שלך נעשה בסדר הנכון ושהסביבה הפנימית "דורסת" את החיצונית ולא להפך.

2
סוג ערך ההחזרה (Return Type)

דוגמה שכיחה: מסתכלים על השורה של התוצאה (הפלט). האם מודפס שם מספר (num-val 5)? האם מודפסת רשימה? האם מודפס <proc-val>?
המטרה: זה אומר לך בדיוק באיזה Constructor עליך להשתמש בשורת ה-return של ה-value-of. אם במבחן התוצאה היא מערך, אתה חייב לעטוף את התשובה שלך ב-(array-val ...).

3
מקרי קצה (Edge Cases)

דוגמה שכיחה: ביצוע foreach על רשימה ריקה [], או switch ללא מקרים בכלל.
המטרה: להראות לך מהו תנאי העצירה (Base case) ברקורסיה של ה-value-of שלך. האם מחזירים שגיאה? מחזירים 0? מחזירים רשימה ריקה? הדוגמה עונה על זה באופן מוחלט.

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

איך מזהים ואיזה מידע לחפש במלל השאלה?
קראו את פסקת התיאור של הביטוי בעמוד הראשון של המבחן. חפשו את מילות המפתח המגדירות את הקלט:
- אם כתוב "מקבל מזהה (Identifier)" זה רמז שלא מעבירים אותו ל-value-of! משתמשים בו כדי לשלוף מהסביבה עם apply-env.
- אם כתוב "מקבל ביטוי (Expression)" חובה להפעיל עליו value-of כדי להמיר אותו מעץ תחביר (AST) לערך ריצה (ExpVal).
- אם כתוב "עבור כל איבר / סורק את / בודק בזה אחר זה" זה רמז למבנה לולאה, כלומר חובה לפתוח פונקציית עזר ב-interp.scm (ראו שלב 1.5).

🧩דוגמאות מהשטח לניתוח ביטויים:

דוגמה א: שאלת הרפלקציה (2025ב א2) - get-type(x)

הביטוי מוגדר כ-get-type (identifier). הניתוח: הוא לא מקבל "Expression", אלא "identifier". זה אומר שאנחנו לא רצים לעשות value-of על x. אנחנו בסך הכל ניגשים לסביבה בעזרת apply-env כדי לשלוף את הערך שיושב שם.

דוגמה ב: לולאת foreach

הביטוי קולט משתנה, מקבל רשימת ביטויים (או ביטוי שמוערך לרשימה), ומריץ גוף (body) עבור כל אחד מהם. הניתוח: חובה לבצע value-of על הרשימה כולה קודם, לוודא שקיבלנו list-val, ולאחר מכן להריץ את ה-body שוב ושוב בתוך סביבה מורחבת נקודתית שבה המשתנה שווה לערך הנוכחי.

קובץ יעד: lang.scm

עדכון התחביר (Grammar)

כיצד נגדיר לשפת Scheme ולמנתח התחבירי (Parser) את החוקים החדשים שלנו? פה לומדים לתרגם את השאלה לתבנית במדוייק.

שלב 2.0: עדכון ה-Grammar – ללמד את ה-SLLgen שפה חדשה

הקובץ שבו אנו מגדירים את הדקדוק מכיל רשימה של חוקים (בדרך כלל נקרא the-grammar). המטרה שלנו היא לתרגם את נוסחת ה-BNF מהמבחן, שורה אחר שורה, לתחביר ש-SLLgen מבין. כלל ברזל (מודל הפיגומים): הטרמינלים ("המילים השמורות") הם חובה מוחלטת עבור ה-SLLgen (ה-Parser) כדי להבין את מבנה המשפט ולהפריד בין החלקים השונים. ממש כמו פיגומים בבניין, הם מחזיקים את המבנה בזמן הבנייה. לאחר שהסריקה הושלמה והעץ (AST) נוצר, הפיגומים מוסרים: הטרמינלים אינם מועברים כפרמטרים לבנאי (Constructor) של ה-AST, אלא רק ה-Non-Terminals.

מילון התרגום: מ-BNF ל-SLLgen

מילים שמורות וסימנים (Terminals)

מילים כמו switch, [, =>

"switch", "[", "=>"

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

משתנים וסוגים (Non-Terminals)

מילים כמו Expression, Type, identifier

expression, type, identifier

נכתבים כסימבולים (ללא מרכאות, באותיות קטנות). אלו הערכים שייאספו ויועברו כפרמטרים ל-AST.

רשימות מופרדות בתו { ... }*(,)

למשל רשימת פרמטרים שמופרדת בפסיק.

(separated-list expression ",")

הפונקציה תאסוף את כל האיברים ותחזיר רשימה אחת (List) שמכילה אותם. הפסיק או הנקודה-פסיק מושלכים לפח.

חזרות ללא מפריד { ... }*

למשל בלוק שחוזר על עצמו כמה פעמים.

(arbno type identifier)

זהירות: זה לא מחזיר רשימה אחת מעורבבת! SLLgen מפריד את זה חכם: הוא ייצור במקרה הזה שתי רשימות במקביל – רשימה של types ורשימה של identifiers.

תבניות הוספה נפוצות (Patterns)

במבחנים חוזרים על עצמם 3 מבנים מרכזיים. זיהוי התבנית חוסך התלבטויות:

תבנית 1: "המערך / הרשימה" (Separated List)

מתי נשתמש? כשהשאלה עוסקת במערכים, יצירת אובייקטים או פרמטרים. מאופיין בסימנים: [ ] וסוגריים עם פסיק (,).
דוגמה ממבחן: Expression ::= [ { Expression }*(,) ] (כמו מועד 78). 

(expression 
  ("[" (separated-list expression ",") "]") 
  array-exp)

מה ה-AST יקבל? משתנה אחד בלבד! הרשימה כולה נארזת ל-List ומועברת ל-array-exp בתור משתנה יחיד (למשל exps).

תבנית 2: "הלולאה המורכבת" (הפירוק לזוגות - Pair Exp)

מתי נשתמש? כאשר יש בלוק שלם שחוזר על עצמו עם * או +. ישירות ייצור ספגטי קשה לפענוח (רשימות מקבילות). הפתרון החכם: ליצור ביטוי עזר ב-Grammar!
דוגמה ממועד 87: foreach (Type identifier in [ { Expression }(,) ] )* do Expression 

; 1. נגדיר קודם את הבלוק שחוזר על עצמו כביטוי בפני עצמו:
(expression 
  ("(" type identifier "in" "[" (separated-list expression ",") "]" ")") 
  foreach-case-exp)

; 2. הפקודה הראשית תאסוף רשימה פשוטה של הביטויים האלו!
(expression 
  ("foreach" (arbno expression) "do" expression) 
  foreach-exp)

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

תבנית 3: "תנאים מסועפים" (רשימות בתוך רשימות)

מתי נשתמש? כשיש לנו Cases, כמו ב-Switch או ב-Cond.
דוגמה ממועד 57: switch ( Expression ) { {Type identifier when ({Expression}+(,)) => Expression }*(;) } default => Expression 

(expression 
  ("switch" "(" expression ")" "{" 
   (separated-list type identifier "when" "(" (separated-list expression ",") ")" "=>" expression ";") 
   "}" "default" "=>" expression) 
  switch-exp)
בדיקת שפיות עצמית במבחן (Sanity Check):

סיימתם לכתוב את שורת ה-(expression ...) ב-Grammar? עשו בדיקה פשוטה:
ספרו כמה מילים ללא מרכאות וללא סוגריים יש לכם בתוך השורה (למשל expression, type, identifier). המספר הזה חייב להיות זהה למספר השדות שיש לכם בתוך הבנאי (Constructor) של סוג ה-AST שהגדרתם בסוף (למשל switch-exp). אם יש לכם 4 אלמנטים בשורת התחביר, חייבים להיות 4 משתנים ב-define-datatype!

שלב 2.1: איתור ופירוק מקרי קיצון (Edge Cases)

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

1

פיצול חוקים והעמסה (Multiple Production Rules)

איך מאתרים?

מזהים ב-BNF את התו | (או) עבור אותו Expression, או שהשאלה מבקשת לתמוך בשתי צורות של אותה פקודה (למשל, במועד 2024ב 87: פעם אחת פרוצדורה ללא סוגריים מרובעים, ופעם עם סוגריים).

ההשפעה ואיך מתמודדים

SLLgen לא יודע לעשות "אופציונלי". אי אפשר לכתוב חוק אחד שמכיל מצב של "אולי יש סוגריים ואולי אין".
הפתרון: חייבים לכתוב במערך ה-the-grammar שתי שורות נפרדות לחלוטין תחת expression, ולתת לכל אחת מהן שם של בנאי (Constructor) שונה ב-AST! 

; נתיב 1: פרוצדורה רגילה
(expression ("proc" "(" identifier ")" expression) proc-exp)
; נתיב 2: פרוצדורה עם סוגריים מרובעים (העמסה)
(expression ("proc" "[" identifier "]" expression) proc-square-exp)
2

הביטוי הריק - אפס פרמטרים (The Nullary Expression)

איך מאתרים?

מזהים בשורת ה-BNF ביטוי שמורכב אך ורק מטרמינלים (מילים שמורות), בלי שום משתנה או ביטוי פנימי. למשל במועד 2021ב 87 יש את הביטוי empty-exp.

ההשפעה ואיך מתמודדים

סטודנטים נוטים להסתבך כי הם חושבים ש"חייבים לחלץ משהו".
הפתרון: מאחר ואין שום Non-Terminal (כמו identifier או expression), פשוט מצהירים על השם הקבוע, והבנאי של ה-AST יקבל אפס פרמטרים. 

; ב-grammar:
(expression ("empty-exp") empty-exp)
                
; ב-define-datatype: אין שדות לחלץ!
(empty-exp)
3

טרמינלים "מתחזים" (לדוגמה: מקף תחתון _)

איך מאתרים?

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

ההשפעה ואיך מתמודדים

סכנה גדולה! המקף התחתון _ לבדו לא מוגדר כ-identifier ב-Scanner הדיפולטיבי (שדורש שיתחיל באות). אם נתייחס אליו כמשתנה, הקוד יקרוס בשלב הסריקה.
הפתרון: עלינו לטפל בו כטרמינל לכל דבר (כמו מילה שמורה), ולפתוח עבורו חוק דקדוק נפרד. ב-AST נגדיר לו Constructor ייעודי ללא פרמטרים שמייצג "התעלמות". 

; הגדרה של המקף התחתון כטרמינל שיוצר ביטוי מיוחד ב-AST
(expression ("_") wildcard-exp)
4

פתרון מקצועי לרשימות מקוננות: יצירת משתנה עזר (Pair-Exp)

מתי נשתמש?

כאשר שורת ה-BNF כוללת מבנה מורכב שחוזר על עצמו עם arbno ומכיל בתוכו רשימה נוספת או מספר רב של איברים (למשל: { Type id when ({ Expression }+(,)) }*). ניסיון לפרסר הכל יחד ייצור "ספגטי" של list-of (list-of ...) שיהיה סיוט לעבד ב-value-of.

הפתרון: חלוקה ל-2 ביטויים

במקום לדחוף הכל לחוק אחד, נייצר Non-Terminal חדש שייצג כל "בלוק" כזה, ונטמיע אותו כרשימה פשוטה בפקודה הראשית. זה נקרא Helper/Pair Expression. 

; 1. במקום לדחוף הכל ב-arbno, נגדיר את הבלוק כסוג חדש של ביטוי (למשל case-exp):
(expression (type identifier "when" "(" (separated-list expression ",") ")") a-case-exp)

; 2. בפקודה הראשית, פשוט נאסוף רשימה של הביטויים מהסוג החדש!
(expression ("switch" (arbno expression) ...) switch-exp)

זה מאפשר ל-value-of להתמודד עם רשימה פשוטה של AST Nodes (כאשר כל אחד מהם יפעיל קריאה משלו ל-value-of על ידי cases משלו), וחוסך מאיתנו את לולאות ה-map המקוננות!

קובץ יעד: data-structures.scm

מבני נתונים מתקדמים (ExpVal)

הוספת Variant ל-Expval ויצירת פונקציות חילוץ. האם הביטוי החדש מחזיר ערך שאינו Number/Boolean/Proc רגיל?

שלב 3.0: עדכון מבנה הנתונים (define-datatype) – יצירת תבנית הזיכרון

בשלב הקודם (ה-Grammar) חילצנו את הנתונים מהטקסט. כעת אנו מגדירים את ה"קופסה" בזיכרון שתשמור אותם – ה-AST.
חוק הברזל (התאמה חד-חד-ערכית): מספר השדות בקופסה, והסדר שלהם, חייבים להיות זהים לחלוטין למספר ולסדר ה-Non-Terminals שהגדרנו בשורת ה-Grammar. אם הסדר יתהפך, הקוד לא יקרוס בשלב הסריקה, אלא יתפוצץ בשלב ה-value-of עם באגים שקשה מאוד לאתר!

מילון טיפוסים (Predicates): מי השומר בדלת?

לכל שדה בבנאי אנחנו חייבים להצמיד "שומר" (Predicate) שבודק שהמידע שנכנס הוא מהסוג הנכון:

expression?

עבור ביטוי יחיד שחילצנו (כמו e1 או body).

identifier?

עבור שם של משתנה (כמו x או id).

type?

עבור הגדרת טיפוס (אם השפה תומכת ב-Types, כמו int או bool).

(list-of ...)

עוטף כל אחד מהנ"ל במידה והוא נאסף כחלק מרשימה (דרך arbno או separated-list).

שבלונות תרגום מ-Grammar ל-Datatype

בואו נראה איך התבניות שזיהינו בשלב 2 מתורגמות במדויק לשלב 3, צעד אחר צעד:

תבנית 1: "המערך הרגיל" (רשימה בודדת)

כאשר השתמשנו ב-separated-list אחד ב-Grammar.

השלב הקודם (Grammar): ("{" (separated-list expression ",") "}")
השלב הנוכחי (Datatype): (array-exp
  (exps (list-of expression?)))
!
תבנית 2: "משתנה העזר המפוצל" (Pair-Exp) - ממועד 87 (Foreach)

נזכור ממועד 87: השתמשנו בפיצול. יצרנו ב-Grammar משתנה עזר (foreach-case-exp) והפקודה הראשית אספה רק רשימה שלו. כעת ב-Datatype, נגדיר שני בנאים (Constructors) שונים: אחד למקרה-עזר, ואחד לפקודה עצמה. שימו לב כמה זה נקי וללא רשימות מקבילות!

השלב הקודם (Grammar): (expression ("(" type identifier "in" "[" (separated-list ...) ... ) foreach-case-exp)
(expression ("foreach" (arbno expression) "do" expression) foreach-exp)
השלב הנוכחי (Datatype): (foreach-case-exp
  (typ type?)
  (id identifier?)
  (exps (list-of expression?)))

(foreach-exp
  (cases (list-of expression?))
  (body expression?))

ניצלנו מספגטי ה-arbno! כל case מעכשיו הוא אובייקט AST נפרד ויעבור הערכה קלה ופשוטה.

תבנית 3: מקרה הקיצון - שדות ריקים או "מתחזים"

אם נתקלנו במקרים משלב 2.1 (כמו פקודה ריקה או מקף תחתון _ שאספנו כטרמינל):

פקודה ללא נתונים (למשל empty-exp): (empty-exp) ; ללא שדות בכלל!
פרוצדורה בהעמסה (Overloading): (proc-exp (id identifier?) (body expression?))
(proc-square-exp (id identifier?) (body expression?))

בהעמסה (כמו מועד 87 מ-2024ב), שימו לב שיש לנו שני בנאים נפרדים, גם אם הם מקבלים בדיוק את אותם השדות. השם השונה שלהם יעזור לנו בשלב הבא (value-of) לדעת דרך איזה חוק המשתמש נכנס.

איך מדבגים בראש (Mental Debugging):

אם תסתכלו על שורת ה-Grammar ותקריאו בקול רק את ה-Non Terminals משמאל לימין, לדוגמה ב-Switch (מועד 57): "אקספרשן, (טייפ, איי-די, ליסט-של-אקספרשנים, אקספרשן)-*פעמים, אקספרשן".
הקריאה הזו צריכה להתאים בדיוק מוחלט למשתנים ב-Datatype שלך: e1, ואז רשימת typs, רשימת ids, רשימת-של-רשימות של conds, רשימת results, וביטוי defexp בודד בסוף. כל סטייה בסדר הזה, ותקבלו את השגיאה המפורסמת שבה מזהה (id) מנסה בטעות להפוך לביטוי מתמטי.

קובץ יעד: interp.scm

מנוע ההערכה value-of

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

שלב 4.0: עדכון המפרש (interp.scm) – הלב הפועם של value-of

פונקציית value-of היא ה"מעבד" (CPU) של השפה שלנו. היא מקבלת שני דברים: ביטוי (AST) וסביבה (env), ותפקידה להחזיר ערך מחושב (ExpVal). כל תוספת לשפה מתחילה קודם כל בהוספת case חדש בתוך הפונקציה הזו, שקולט את השדות שהגדרנו בשלב 3.

המודל המנטלי הקריטי: באילו נתונים אני נוגע עכשיו?

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

1. עולם ה-AST (גלם)

אלו המשתנים שחילצנו מה-cases (כמו e1, body). הם רק "הוראות יבשות".

אי אפשר לעשות עליהם + או if!
2. עולם ה-ExpVal (קופסאות)

ערכים אחרי שהעברנו אותם ב-value-of. הם עטופים בקופסאות (כמו num-val).

חובה לעשות להם Unbox לפני שימוש.
3. עולם ה-Scheme (נקי)

מספרים אמיתיים או בוליאנים אחרי שעשינו להם למשל expval->num.

מוכן לפעולות מתמטיות ולוגיקה!

4 שבלונות הבסיס (ארגז הכלים המיידי)

מיד לאחר שפתחנו את ה-case הרלוונטי, נשתמש באחת או יותר מהשבלונות הבאות כדי לעבד את הנתונים, לפני שנעביר אותם ללוגיקה מורכבת:

שבלונה 1: הבישול

המרת AST יחיד ל-ExpVal

הפיכת "טקסט מת" לערך מחושב מתוך הסביבה הנוכחית.

(let ((val1 (value-of exp1 env))) ...)
שבלונה 2: בישול המוני

המרת רשימת AST לרשימת ExpVal

שימוש חובה בכל פעם שהגדרנו בשלב ה-Datatype שדה מסוג (list-of expression?).

(let ((vals (map (lambda (exp) (value-of exp env)) exps))) ...)
שבלונה 3: קילוף הקופסה

המרת ExpVal לערך Scheme טהור (Unboxing)

חובה לעשות זאת לפני שמשתמשים בתנאי if אמיתי של סקים, או עושים חישוב מתמטי.

(let ((num (expval->num val1))) ...)
שבלונה 4: האריזה הסופית

המרת ערך Scheme בחזרה ל-ExpVal (Boxing)

חוק ברזל: השורה האחרונה ב-case שלכם תמיד חייבת להחזיר סוג של -val (כמו num-val, bool-val, array-val).

(num-val result)

דוגמה: לחבר הכל יחד (יצירת מערך - מועד 73)

נניח שקיבלנו מה-AST את המבנה (array-exp (exps)). המשתנה exps הוא כרגע "מוצר גלם" מהעולם ה-1 (רשימת AST). הנה איך השבלונות מופעלות כדי להחזיר תוצאה חוקית: 

; בתוך ה- cases expression exp:
                (array-exp (exps)
                  ; 1. שימוש בשבלונת הבישול ההמוני כדי לחשב את כל הביטויים (עולם 1 -> עולם 2)
                  (let ((evaluated-exps 
                          (map (lambda (e) (value-of e env)) exps)))
                    
                    ; 2. שימוש בשבלונת האריזה הסופית. 
                    ; כאן הערכים מועברים לבנאי של המערך בזיכרון, שחייב להיות מוחזר כ-ExpVal.
                    (array-val evaluated-exps)))

מתי אסור לגעת ב-value-of? (Macro / Syntax Expand)

לעיתים השאלה מבקשת להוסיף פקודה חדשה, אך הסמנטיקה שלה מוגדרת במלואה על ידי המרתה לפקודה שכבר קיימת בשפה (התנהגות של "מאקרו" או Derived Expression). לדוגמה: "הוסף פקודת unless שפועלת בדיוק כמו if הפוך".

חוק ברזל: במקרה כזה חל איסור מוחלט להוסיף case חדש בתוך value-of!

אז מה עושים? כל העבודה מתבצעת דרך פונקציית syntax-expand: פונקציה שעוברת על ה-AST מיד לאחר הפארסינג ולפני הריצה ב-value-of, ומתרגמת את ה-AST החדש ל-AST קיים. 

; במקום case ב-value-of, נוסיף case ב-syntax-expand:
(define syntax-expand
  (lambda (exp)
    (cases expression exp
      ; זיהוי הפקודה החדשה ותרגום לפקודה קיימת:
      (unless-exp (cond body)
        ; מחזירים AST מסוג if, שעוטף את התנאי ב-not, ומריץ את הגוף
        (if-exp (call-exp (var-exp 'not) (list (syntax-expand cond)))
                (syntax-expand body)
                (num-exp 0)))
      
      ; על כל שאר סוגי הביטויים: חובה להפעיל syntax-expand על הרכיבים הפנימיים!
      ; . . .
      )))
סכנת הלולאות והסביבות (טיפ מקדים לשלב הבא):

אם אתם רואים שהתחביר שלכם דורש יצירת משתנים חדשים (כמו ב-let או ב-switch מהמבחנים שעברנו עליהם), אל תעשו value-of על ה-body (הגוף העיקרי) מיד!
קודם יש להעריך רק את מה שמשמש כ"תנאי" או כ"ערך ההשמה". רק לאחר מכן, נרחיב את הסביבה (באמצעות פונקציית עזר או extend-env) – ורק בתוכה נקרא ל-value-of על הגוף. על זה בדיוק נדבר בחלק הבא!

קובץ יעד: interp.scm (מחוץ ל-value-of)

פונקציות עזר ומלכודות

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

שלב 4.1: המנוע החכם – ניהול סביבות, לולאות ופונקציות עזר (Helpers)

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

סוד הקסם 1: הרחבת הסביבה (extend-env)

תחשבו על ה-Environment כעל ערימה של דפים. כל פעם שאנחנו מגדירים משתנה חדש (למשל, כשאנחנו נכנסים לתוך איטרציה של לולאת `foreach` או לתוך מקרה `case` ב-`switch`), אנחנו מניחים "דף חדש" על הערימה.
כלל הברזל: קודם כל מחשבים את הערך בסביבה הישנה, ורק אז יוצרים את הסביבה החדשה ומריצים בתוכה את גוף הקוד!

; שבלונת הרחבת סביבה - איך זה נראה בקוד:
(let ((new-env (extend-env var-name calculated-val old-env)))
  (value-of body new-env)) ; הגוף רץ בסביבה החדשה!

2 שבלונות העל לפונקציות עזר (Helpers)

במבחנים , הלוגיקה המורכבת מתחלקת ל-2 סוגים עיקריים של "לולאות" שנממש כפונקציות רקורסיביות:

תבנית 1: המחפש (The Searcher) - כמו מועד 57 (Switch)

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

; פונקציית העזר מקבלת את הערך לבדיקה, את כל הרשימות, ואת הסביבה
                (define switch-helper
                  (lambda (val-to-check typs ids bools exps defexp env)
                    (if (null? typs)
                        ; מקרה בסיס: סיימנו את הרשימות ולא מצאנו התאמה -> נריץ את הדיפולט
                        (value-of defexp env)
                        
                        ; אחרת: נבדוק את השורה הראשונה (ה-car של כל הרשימות)
                        (let ((current-type (car typs))
                              (current-id (car ids))
                              (current-bools (car bools))
                              (current-exp (car exps)))
                          
                          ; 1. האם הטיפוס מתאים? (נניח שיש לנו פונקציית עזר שבודקת התאמת טיפוס)
                          (if (is-type-match? val-to-check current-type)
                              
                              ; 2. הטיפוס מתאים! עכשיו נרחיב את הסביבה עם המשתנה החדש
                              (let ((new-env (extend-env current-id val-to-check env)))
                                
                                ; 3. נבדוק את התנאים הבוליאניים תחת הסביבה *החדשה*
                                (if (check-all-bools? current-bools new-env)
                                    ; הכל עבר? נחשב את התוצאה הסופית!
                                    (value-of current-exp new-env)
                                    ; תנאי בוליאני נכשל? ממשיכים לשורה הבאה ברקורסיה
                                    (switch-helper val-to-check (cdr typs) (cdr ids) (cdr bools) (cdr exps) defexp env)))
                              
                              ; טיפוס לא מתאים? ממשיכים לשורה הבאה (ל-cdr)
                              (switch-helper val-to-check (cdr typs) (cdr ids) (cdr bools) (cdr exps) defexp env))))))
תבנית 2: מיפוי וקיפול פונקציונלי (Map / Fold)

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

; תבנית פונקציונלית טהורה - הערכת רשימת ביטויים ללא אפקטי צד
(define evaluate-list-of-exps
  (lambda (exps env)
    ; map עובר על כל ביטוי, מבצע עליו value-of, ומחזיר רשימה של ExpVals!
    (map (lambda (exp) (value-of exp env)) exps)))

; מה אם צריך הערכה טורית (כמו let*) ולא מקבילית?
; אזהרה חמורה: אסור להשתמש ב-map להערכה טורית כי map משתמש באותה סביבה לכולם!
; במקום זאת, נשתמש ברקורסיה מפורשת שמחזירה את התוצאה האחרונה.
(define eval-sequential
  (lambda (ids exps env)
    (if (null? ids)
        (num-val 1) ; או כל ערך בסיס אחר המסמל סיום
        (let ((val (value-of (car exps) env)))
          ; הרחבת הסביבה עבור השלב הבא! (לא משנים זיכרון, רק מעבירים סביבה חדשה)
          (eval-sequential (cdr ids) (cdr exps) 
                           (extend-env (car ids) val env))))))
סכנה קטלנית: הערכה מקבילית מול הערכה טורית (Sequential Evaluation)

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

כלל ברזל אבסולוטי: אין Store בשאלה 1!

שאלה 1 בקורס עוסקת תמיד בשפות בסיסיות ללא ניהול זיכרון (כמו LET, PROC, LETREC או שפה עם טיפוסים CHECKED). בשפות אלו אין מושג של החסן (Store) ואין מצביעים! אם אתם מוצאים את עצמכם מתלבטים אם להשתמש ב-newref, setref! או deref במסגרת שאלה 1 - אתם עושים טעות קריטית! כל החישובים מבוססים על ערכים טהורים (Values) וסביבות (Environments) בלבד.

מעבדת המפרש: איסוף (Collect)

סימולטור ויזואלי: לולאת איסוף טהורה

נמחיש כיצד מנוע השפה בונה ומריץ את הלולאה for id = exp1 to exp2 collect exp3 – מקבלת הדרישה ועד לקבלת הרשימה הסופית ללא שום תופעות לוואי.

terminal
>> המערכת מוכנה. ממתין לקלט מהסטודנט...
שאלה 1/8
הפרדה ארכיטקטונית

שאלה 1 מול שאלה 2: שינוי המודל המנטלי

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

שפות פונקציונליות טהורות

LET, CHECKED

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

  • ניהול זיכרון נקי (No Store)

    הסביבה (Environment) ממפה משתנה ישירות לערך שלו (ExpVal). ברגע ששלפנו משתנה מהסביבה, אנחנו יכולים לעבוד איתו מיד.

  • מערכת הטיפוסים (Type Checker)

    בשפות ה-CHECKED, הלב של השאלה יתמקד בעדכון checker.scm והוספת אילוצי טיפוסים חזקים.

  • מקרואים ותרגום תחבירי (Macros)

    לעיתים קרובות נתבקש לכתוב syntax-expand ללא התערבות של ה-value-of.

העולם האימפרטיבי

IMPLICIT-REFS

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

  • החסן ומוטציות (The Store)

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

  • דריסת זיכרון (setref!)

    בשונה משאלה 1, פקודות רבות בשאלה 2 מיועדות לאקשן באמצעות setref! בתוספת החזרת ערך דמה לריצוי המפרש.

  • כינויים (Aliasing)

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

ההבדל החזותי: איך הסביבה (Env) ממומשת באמת?

Q1: LET / CHECKED

Environment
x (num-val 5)

מיפוי ישיר. המשתנה מכיר אך ורק את הערך הסופי שלו.

Q2: IMPLICIT-REFS

Environment
x Ref(0)
The Store
[0] (num-val 5)

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

שאלה 2 | שלב 0

מבט על: ארכיטקטורת סביבות ומוטציות

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

זיהוי ארכיטקטורה

Implicit vs Explicit

מבנים ומוטציות

שינוי בזיכרון (setref!)

מניעת זליגה

שמירה על base-env טהור

ביצוע ובדיקה

וידוא refs מול AST

🧩הקבצים הרלוונטיים (מבט על)

lang.scm

מגדיר את מבנה הפקודות והמילים השמורות של השפה. שימו לב להבחנה מתי מזהה נכתב כתחביר קשיח (כמו `event.create()`) ומתי הוא משתנה.

data-structures.scm

בקובץ זה לרוב נוסיף סוג ערך מבוטא חדש (כמו event-val או ptr-val). חשוב להכיר איזו ארכיטקטורה יושבת בפנים (האם הסביבה מצפה ל-References או לערכים מפורשים).

interp.scm

כאן תתרחש רוב העבודה - כתיבת לוגיקת הזיכרון, ביצוע newref, עדכון במקום עם setref!, וטיפול נכון בסביבות מקומיות בלולאות בתוך value-of.

שלב 1.0: מפת דרכים - איך לקרוא את שורת הדקדוק (Grammar)?

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

מילון הסמלים (Lexicon)

  • מילים שמורות (Terminals): מילים כמו foreach, switch, in, או סוגריים { }.
    מה קורה פה בעצם? אלו הם "שלטי הכוונה" עבור הפארסר. הם עוזרים לו להבין איפה מתחיל ונגמר כל חלק, אבל הם לא נשמרים בעץ ה-AST. למילים האלו אין משמעות חישובית – הן רק ה"אריזה" של הביטוי.
  • ביטויים משתנים (Non-Terminals): מילים באותיות רישיות כמו Expression, Identifier, Type.
    מה קורה פה בעצם? זהו המידע האמיתי שהמשתמש מזין, והבשר של הביטוי. כל Non-Terminal כזה חייב להפוך לשדה (Field) בתוך הפונקציה שניצור ב-define-datatype. אלו הנתונים שנעביר אחר כך לחישוב.
  • סימוני חזרות ורשימות * , +: הסימן *(,) או +(,) מציין רשימה שמופרדת בפסיקים.
    מה קורה פה בעצם? כשאנחנו רואים כוכבית או פלוס, אנחנו מבינים שהמשתמש יכול להזין מספר בלתי מוגבל של איברים מאותו סוג. לכן, ב-AST שלנו, השדה הזה לא יהיה סתם expression? אלא רשימה: (list-of expression?). בפארסר נשתמש ב-arbno או separated-list כדי לאסוף אותם.

מפת הקבצים: איך הדקדוק מתפזר לקוד?

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

1
ast.scm (או define-datatype) מגדירים את מבנה הנתונים. כל Non-Terminal הופך למשתנה במבנה, וכל רשימה מקבלת list-of. כאן אנחנו מגדירים "איך נראית קופסת הנתונים שלנו".
2
parser.scm (או the-grammar) מלמדים את המערכת איך לקרוא את הטקסט ולהכניס אותו לקופסה שיצרנו בשלב 1. כאן אנחנו משתמשים במילים השמורות (הטרמינלים) כסימני זיהוי, ואוספים את הביטויים (האי-טרמינלים) לתוך הרשימות.
3
interp.scm (פונקציית value-of) כאן מתרחש ה"קסם". אנחנו שולפים את הנתונים מהקופסה שלנו, מבצעים להם הערכה (Evaluate) בסביבה הנוכחית (ה-Env), ומפעילים עליהם את הלוגיקה הנדרשת (למשל ריצה בלולאה, חיפוש במערך וכו').
דוגמה לפירוק: (שאלה 87, 2024ב)
Expression ::= foreach (Type identifier in [{ Expression }+(,) ])* do Expression
// ניתוח המבנה:
foreach, in, do, [, ] = טרמינלים. יעזרו לפארסר לנווט.
identifier = אי-טרמינל. יהפוך לשדה של שמות המשתנים.
Expression (הראשון) = בגלל שהוא עטוף ב-()*, הוא יהפוך לרשימה של רשימות של ביטויים.
Expression (האחרון) = אי-טרמינל בודד. זהו ה-body (גוף) של הלולאה שיתבצע בסוף.
קובץ יעד: interp.scm / environments.scm

זיהוי ארכיטקטורת הזיכרון

המוקש הגדול ביותר של שאלה 2 הוא ההבדל בין IMPLICIT-REFS ל-EXPLICIT-REFS. הפתרון שלכם ב-interp.scm נראה אחרת לגמרי בהתאם לסוג השפה!

שלב 1.1: מחוץ לדקדוק - איך לפצח את ההנחיות המדויקות ואת הדוגמאות?

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

1. מה לחפש בהנחיות המדויקות (הסמנטיקה של הביטוי)

טווח קשירה וסביבה (Scope & Binding): חפשו האם המשתנים החדשים שנוצרים צריכים להיות זמינים רק בתוך הביטוי הנוכחי (כמו לולאה) או שהם נשמרים לעתיד (כמו פרוצדורה). אם ההנחיה אומרת שהחישוב יתבצע על פי "הסביבה בעת הגדרת הביטוי", מדובר ב-Static Binding, המחייב שמירת סביבה saved-env בתוך ה-AST ושימוש בה בזמן הריצה.
אפקטי לוואי וניהול החסן (The Store): בדקו האם הביטוי משנה ערכים קיימים או מקצה מקומות חדשים בזיכרון. בשפות עם משתנים משתמעים (Implicit-Refs), כל יצירת משתנה חדש מחייבת אותנו להשתמש ב-newref כדי לייצר לו הפניה בהחסן, אחרת לא נוכל לשנות את ערכו בהמשך התוכנית.
ערך החזרה ברירת מחדל (Default Return): מה קורה אם התנאי לא מתקיים? מה קורה אם הרשימה שקיבלנו ריקה? ההנחיות תמיד יציינו זאת במפורש (למשל: "אם לא נותרו ערכים, יוחזר אפס"). זהו בדיוק תנאי העצירה (Base Case) שתצטרכו לכתוב ברקורסיה שלכם.

2. איך לנתח את הדוגמאות (הנדסה לאחור של הרצה יבשה)

זיהוי סדר חישוב הביטויים (Evaluation Order): הביטו בדוגמה וחפשו האם ביטויים קודמים משנים את הסביבה עבור ביטויים שבאים אחריהם. אם שינוי של משתנה בביטוי הראשון משפיע על ערכו בביטוי השני, אתם מבינים מיד שקוד ה-Racket שלכם חייב לבצע הערכה סדרתית (חוטית) של המשתנים, ולא הערכה סימולטנית.
הבנת מבנה הפלט (ExpVal): הדוגמה מראה לכם בדיוק מהו סוג ה-Value שצריך לחזור בסוף הדרך. האם מוחזר מספר פשוט עטוף ב-num-val, או אולי מבנה מורכב יותר כמו רשימה? ודאו שקוד ה-Value-of שלכם עוטף את התוצאה בדיוק בסוג הטיפוס שהדוגמה מציגה.
מקרה בוחן משולב: הנחיה מול דוגמה (מועד 87, 2021ב)
הטקסט מהמבחן (הנחיה):

"הביטוי בונה ומחזיר את ה-generator... יחושבו על פי הסביבה בעת הגדרת ה-generator (כלומר static-binding)"

התרגום לקוד ב-AST: נוסיף שדה saved-env למבנה הנתונים שלנו כדי להקפיא את הסביבה!
הטקסט מהמבחן (דוגמה):

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

התרגום לקוד ב-Value-of: נחזיק משתנה המצביע על המיקום הנוכחי ברשימה. אם הגענו לסוף הרשימה, נפעיל פונקציית eopl:error כדי לזרוק שגיאה כפי שנדרש!

איך מזהים במבחן באיזו ארכיטקטורה אנחנו עובדים?
זה המידע החשוב ביותר לשאלה 2. חפשו בשורה הראשונה של השאלה במבחן את ציון השפה:
- אם כתוב: "נוסיף לשפת יירמוז" אנחנו ב-IMPLICIT-REFS (הפניות משתמעות).
- אם כתוב: "נוסיף לשפת ויפנה" אנחנו ב-EXPLICIT-REFS (הפניות מפורשות).

מה עושים עם זה? זה מכתיב לנו איך להשתמש ב-extend-env כשאנחנו פותחים לולאות או פונקציות (ראו למטה).

IMPLICIT-REFS (משתמעות)

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

איך מרחיבים סביבה (extend-env)?


;; חובה להפעיל newref על הערך!
;; (משמש המון בלולאות for/proc או בהצהרות משתנים)
(extend-env var (newref val) env)

אם תשכחו את ה-newref בהגדרת משתנה הלולאה שלכם, השפה תקרוס ברגע שתנסו לגשת אליו, כי הוא לא יהיה מצביע תקין ל-Store!

EXPLICIT-REFS (מפורשות)

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

איך מרחיבים סביבה (extend-env)?


;; מעבירים את הערך כמו שהוא.
(extend-env var val env)

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

קובץ יעד: lang.scm

עדכון התחביר (הגרמר)

הבנת ה-grammar והגשר בין טקסט ללוגיקה.

שלב 2.0: עדכון התחביר (The Grammar) - הגשר בין טקסט ללוגיקה

למה ואיך אנחנו מוסיפים ל-Grammar?

רשימת ה-the-grammar היא הוראות ההפעלה של הפארסר (מנוע ה-sllgen). הפארסר קורא את הטקסט שהמתכנת כתב ומנסה להרכיב ממנו את ה-AST שלנו. כלל הברזל: מה שנכתוב במרכאות כפולות ("if", "{") משמש כשלט הכוונה בלבד – הפארסר יוודא שזה קיים, אך לא ישמור את זה בזיכרון. מה שנכתוב ללא מרכאות (expression, identifier) זהו "בשר" – הפארסר ייקח את התוכן הזה וידחף אותו לתוך שדות ה-AST שהגדרנו ב-define-datatype, לפי הסדר המדויק!

מילון התרגום: מהשאלה לקוד Scheme

בשאלה (טרמינלים)
foreach, in, { }
בקוד Grammar
"foreach" "in" "{"
בשאלה (אי-טרמינלים)
Expression, Identifier
בקוד Grammar
expression identifier
בשאלה (רשימה רגילה)
{ Expression }*
בקוד Grammar
(arbno expression)
בשאלה (רשימה מופרדת)
{ Expression }*(,)
בקוד Grammar
(separated-list expression ",")

תבניות הוספה נפוצות (Patterns)

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

תבנית 1: העוטף הפשוט (The Basic Wrapper)

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

Expression ::= newarray (Expression , Expression) 

;; Grammar line:
(expression
  ("newarray" "(" expression "," expression ")")
  newarray-exp)
תבנית 2: הרשימה המופרדת (The Separated List)

מאפיין: שימוש בסימון *(,) או +(,). נפוץ במערכים, קריאות לפונקציות מרובות ארגומנטים (tupples).

שימו לב: sllgen מתייחס ל- * ו- + באותה צורה (separated-list).

Expression ::= [ { Expression }*(,) ] 

;; Grammar line:
(expression
  ("[" (separated-list expression ",") "]")
  array-exp)
תבנית 3: הבלוק המורכב (The Complex Arbno) - מועד לפורענות!

מאפיין: כוכבית שעוטפת מספר רכיבים יחד, לפעמים אפילו רשימות בתוך רשימות. נפוץ בשאלות של switch-case או לולאות foreach מורכבות. 


Expression ::= switch Expression {
  { identifier => Expression }*
}
הקסם של sllgen: ב-Grammar נכתוב arbno אחד שעוטף את כולם. אבל כשהפארסר יעביר את זה ל-AST, הוא "יפצל" אותם! ה-AST יקבל רשימות נפרדות: רשימת identifiers, ורשימת expressions. 

;; Grammar line:
(expression
  ("switch" expression "{"
    (arbno identifier "=>" expression)
  "}")
  switch-exp)
קובץ יעד: lang.scm

עדכון תחביר מתקדם

איתור וטיפול במקרי קצה בתחביר השפה.

שלב 2.1: מחוץ לשבלונה - איתור וטיפול במקרי קיצון בתחביר

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

1

המפריד הבוגדני (Custom Separators)

איך מאתרים? רוב הסטודנטים רגילים לראות *(,) ומיד כותבים separated-list עם פסיק ",". אבל לפעמים המבחן דורש מפריד אחר לחלוטין, כמו נקודה-פסיק, חץ, או אפילו מילה שמורה!

בשאלה נכתב: Expression ::= [ { Expression }*(;) ] המפריד פה הוא נקודה-פסיק!
התרגום ל-Grammar: ("[" (separated-list expression ";") "]")
ההשלכה (Impact): הפארסר של sllgen קורא את המפריד כסטרינג מוחלט. אם תכתבו פסיק במקום נקודה-פסיק, התוכנית תעבור הידור (Compile) בהצלחה, אך תיכשל מיד בהרצת הדוגמה הראשונה עם שגיאת Parsing, כי היא לא תמצא את הפסיק שהיא מצפה לו.
2

התנגשות זהויות (Keywords vs. Identifiers)

איך מאתרים? הופעה של מילים דמויות-משתנים בתוך שורת התחביר, כמו default, when, או do.

בשאלה נכתב: Expression ::= switch ... default => Expression
חובה לעטוף במרכאות! ... "default" "=>" expression ...
ההשלכה (Impact): אם נשכח לשים את המילה "default" במרכאות, הפארסר יחפש משהו בשם default (משתנה או Non-Terminal שלא קיים), ויקרוס. כלל ברזל: כל מילה בשורת הדקדוק שאינה Expression, Identifier, או Number – היא טרמינל וחייבת להיות בתוך מחרוזת " ".
3

הרשימה המקוננת (Nested Arbno / Lists)

איך מאתרים? כאשר רואים סימוני חזרות (כוכבית או פלוס) בתוך בלוק שמופעל עליו כבר סימון חזרות. לדוגמה: [ { {identifier}*(,) }* ].

מה קורה מאחורי הקלעים? כפי שהוסבר בתבניות, sllgen מפצל arbno לעמודות מקבילות. כאשר יש רשימה בתוך רשימה, ה-AST לא יקבל סתם (list-of identifier?), אלא רשימה של רשימות: (list-of (list-of identifier?)).

ההשלכה על ה-value-of: זה המוקש האמיתי! ברגע שהמידע נכנס כרשימה של רשימות, אי אפשר לעבור עליו בלולאת map או ברקורסיה רגילה. יהיה עלינו להשתמש במיפוי כפול (Nested map) או רקורסיה בתוך רקורסיה כדי לחלץ את הערכים. אם זיהיתם מצב כזה בדקדוק, סמנו לעצמכם כוכבית אדומה – ה-value-of הולך להיות מורכב!
קובץ יעד: data-structures.scm

עדכון מבנה הנתונים (AST)

בניית השרטוט הארכיטקטוני למפרש.

שלב 3.0: עדכון מבנה הנתונים (AST) - בניית השרטוט הארכיטקטוני

המודל המנטלי: מה זה בעצם AST ואיך הוא נולד?

אם ה-Grammar הוא השוער שמקבל את הטקסט ומפרק אותו, ה-AST (Abstract Syntax Tree) הוא המחסן שבו אנחנו מאחסנים את חלקי הלוגיקה החשובים. אנחנו משתמשים בפקודה define-datatype כדי להגדיר את צורת "קופסאות הנתונים" (Variants) שלנו.

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

חוקי המעבר: מ-Grammar ל-define-datatype

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

מה מופיע ב-Grammar המשמעות הלוגית התרגום לשדה ב-AST
expression ביטוי יחיד שצריך לחשב את ערכו (exp1 expression?)
identifier שם של משתנה (Symbol) (var symbol?)
(arbno ...) או (separated-list ...) רשימה דינמית של רכיבים מאותו סוג (exps (list-of expression?))

שבלונות מבניות קבועות (AST Patterns)

שבלונה 1: הביטוי הבסיסי (The Single Wrapper Variant)

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


; מתוך הגדרת ה-Grammar
("newarray" "(" expression "," expression ")") newarray-exp


(newarray-exp
  (length-exp expression?)
  (init-exp expression?))
שבלונה 2: רשימות ואוספים (The List Variant)

מתאים ל: ביטויי קריאה מרובי ארגומנטים, tuples (מועד 57, 2021ב), או מערכים מוגדרים מראש של ערכים. 


; מתוך הגדרת ה-Grammar
("[" (separated-list expression ",") "]") array-exp


(array-exp
  (exps (list-of expression?)))
שבלונה 3: המבנה המורכב והמבוזר (The Parallel Block Variant)

מתאים ל: לולאות מורכבות (כמו לולאת foreach של שאלון 87, 2021ב) או מבני switch-case. כאן ה-Grammar החזיק רכיב חזרתי מורכב (כמו arbno של Type, של identifier ושל expression ביחד). ה-AST מפצל אותם לרשימות מקבילות באותו אורך! 


; מתוך הגדרת ה-Grammar:
("foreach" "(" identifier "in"
  ("[" (separated-list expression ",") "]") ")"*
  "do" expression) foreach-exp


(foreach-exp
  (vars (list-of symbol?))
  (lists_of_exps (list-of (list-of expression?)))
  (body expression?))
שבלונה 4: קפסולת הסביבה הסטטית (The Static Environment Closure Variant)

מתי היא קורית? זהו מקרה קיצון קלאסי במבחנים (כמו שאלת ה-Generators בשאלות החזרה של 24ב). כאשר בהנחיות המדויקות נכתב במפורש: "הביטויים יחושבו על פי הסביבה בעת הגדרת הביטוי (Static Binding)".

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


(generator-exp
  (var symbol?)
  (exps (list-of expression?))
  (retexp expression?)
  (saved-env environment?)) ; שדה בלתי נראה בגרמר!
קובץ יעד: interp.scm

קובץ interp בסיסי

בניית לוגיקת הבסיס במפרש השפה.

שלב 4.0: הלב הפועם (interp.scm) - כתיבת לוגיקת הבסיס ב- value-of

חוק הברזל של IMPLICIT-REFS: חילוץ המצביע

בשאלה 1, כשחיפשנו משתנה בסביבה קיבלנו את הערך שלו. בשאלה 2 (IMPLICIT-REFS), הסביבה שומרת רק מצביעים (כתובות בזיכרון)!
לכן, פונקציית var-exp במפרש חייבת להשתנות. חובה להשתמש ב-deref כדי לפתוח את המגירה ולקחת את הערך.

// ככה שולפים משתנה בשאלה 2!
(var-exp (var) (deref (apply-env env var)))

תבנית הזהב לשאלה 2: תבנית המוטציה (Mutation)

בשפות עם זיכרון, הרבה פקודות (כמו set, עדכון מערך, או רישום לאירוע) לא נועדו להחזיר תשובה חישובית, אלא לשנות את המידע בזיכרון. מכיוון שהמפרש של EOPL חייב להחזיר משהו, נשתמש בבלוק begin שמבצע את הדריסה (setref!) ואז מחזיר ערך דמה (למשל 27).

// דוגמה קלאסית: ביטוי השמה מחדש (Assignment)

(assign-exp (var exp1)
  (begin
    ;; 1. מחשבים את הערך החדש להשמה
    ;; 2. דורסים את התוכן במגירה הקיימת של המשתנה
    (setref! (apply-env env var) (value-of exp1 env))
    ;; 3. מחזרים ערך דמה חסר משמעות
    (num-val 27)))

תבניות בסיסיות (Patterns) לעדכון value-of

תבנית 2: מרחיב הסביבה (The Environment Extender) זהירות: ניהול זיכרון!

איך זה עובד? כאשר יוצרים משתנה חדש (למשל ב-let), אנחנו מעריכים את הערך שלו, ואז מרחיבים את הסביבה (extend-env) לפני שאנחנו מפעילים את value-of על הגוף (body).

ההבדל הקריטי:
בשפה רגילה (EXPLICIT-REFS):
(extend-env var val env)
בשפה מרומזת (IMPLICIT-REFS, כמו מועד 88 ב-2020): חובה להקצות מקום בזיכרון!
(extend-env var (newref val) env) 

(let-exp (var exp1 body)
  (let ((val1 (value-of exp1 env))) ; Evaluate
    (value-of body ; Evaluate body inside new env
      (extend-env var val1 env))))
תבנית 3: ההשהיה / הסגור (The Closure Variant) פרוצדורות, מחוללים (Generators) וכו'

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

הקשר לסעיפים קודמים: כאן אנחנו מכניסים פנימה את ה-env שקיבלנו, שהופך להיות ה-saved-env שהגדרנו ב-AST בסעיף 3! 


(proc-exp (var body)
  ; No 'let', No evaluation! Just wrap and wait.
  (proc-val (procedure var body env)))

המקרה המורכב: עדכון רשימות ומערכים בזיכרון (Events)

בשאלות של "אירועים" (Events) או מערכים, נדרש לשמור רשימה של ערכים בתוך תא בודד בזיכרון, ולעדכן אותה בהדרגה (למשל, הוספת מאזין חדש).
השיטה היא: למשוך את הרשימה מהזיכרון (deref), לשרשר אליה איבר חדש בסקים (append או cons), ולדחוף את הרשימה החדשה חזרה לאותו תא (setref!).

// דוגמה: הוספת פונקציה לרשימת אירועים ששמורה במצביע event-ref

(add-listener-exp (event-var proc-exp)
  (let* ((event-ref (apply-env env event-var)) ;; הבאת המצביע של האירוע
         (current-list (deref event-ref))      ;; פתיחת המגירה: מה הרשימה כרגע?
         (new-proc (value-of proc-exp env)))   ;; חישוב הפרוצדורה החדשה להוספה
    (begin
      ;; החלפת תוכן המגירה: הרשימה הקיימת + הפונקציה החדשה
      (setref! event-ref (append current-list (list new-proc)))
      (num-val 27)))) ;; החזרת ערך דמה
קובץ יעד: interp.scm (Helpers)

interp מתקדם ופונקציות עזר (Helpers)

יציאה מגבולות ה-value-of: כתיבת לולאות ותנאים סדרתיים.

שלב 4.1: מעבר לגבולות ה-value-of - לולאות, תנאים ופונקציות עזר

אזהרת עומק: האם לייצר חדש או לרכב על הקיים? (Aliasing)

בשאלה 2, הדקדוק רומז לנו מה מצפה שיקרה בזיכרון. שימו לב להבדל הקריטי:

  • מצב 1: הדקדוק מכיל Expression אנו מקבלים ביטוי שיש לחשב. התוצאה שלו צריכה תא חדש בזיכרון! (extend-env var (newref (value-of exp1 env)) env)
  • מצב 2: הדקדוק דורש מזהה ישיר Identifier (Call by Reference) אם מבקשים מזהה קיים, פעמים רבות המטרה היא כינוי (Alias) - להצביע לאותו תא זיכרון כדי ששינויים פנימיים יורגשו בחוץ. אסור לעשות newref! (extend-env new-var (apply-env env old-var) env)

המודל המנטלי: למה צריך פונקציות עזר?

Scheme היא שפה פונקציונלית. אין בה for או while קלאסיים שרצים ומשנים מצב. כאשר השאלה במבחן דורשת מאיתנו לממש מנגנון חזרתי (כמו לעבור על רשימה של משתנים ולבצע עליהם פעולה), אנחנו חייבים לצאת מתוך ה-cases של value-of, ולכתוב פונקציה רקורסיבית חיצונית.

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

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

תבנית 1: "המפענח המקבילי" (Batch Evaluation using Map) לרשימות שאינן תלויות אחת בשנייה

התרחיש: יש לנו רשימה ארוכה של ביטויים (expressions) שחילצנו מה-AST, ואנחנו צריכים להפוך את כולם לערכים (ExpVals) לפני שנמשיך. הם לא משפיעים אחד על השני.

הפתרון: שימוש בפונקציית map המובנית של Scheme. היא לוקחת את פונקציית value-of ומפעילה אותה על כל איבר ברשימה. אין צורך לכתוב רקורסיה מאפס! נפוץ מאוד באתחול מערכים או קריאה לפונקציות מרובות ארגומנטים. 


; בתוך ה-cases של value-of:
(array-exp (exps)
  (let ((vals (map
                (lambda (e) (value-of e env))
                exps)))
    ; עכשיו 'vals' היא רשימה של ExpVals מוכנים!
    ...))
תבנית 2: "מרוץ השליחים" (The Recursive Loop Helper) קריטי ל-foreach ו-switch

התרחיש: איטרציה סדרתית. אנחנו צריכים לעבור על רשימה, ובכל שלב לעדכן את הסביבה או את ההחסן עבור השלב הבא (למשל, לולאת foreach ממועד 87 2021ב, שבה מציבים בכל איטרציה ערך חדש במשתנה הרץ).

המבנה הקבוע של פונקציית העזר:
1. תנאי עצירה (Base Case): האם הרשימה ריקה (null? items)? אם כן, החזר את ערך הדיפולט שנדרש בהוראות המבחן.
2. החילוץ: קח את האיבר הראשון בעזרת (car items).
3. הביצוע וקריאת ההמשך: בצע את הלוגיקה (למשל הרחבת הסביבה עם extend-env - שימו לב: אם מדובר ב-IMPLICIT-REFS, חובה לעטוף את הערך ב-newref. אם מדובר ב-EXPLICIT-REFS, מעבירים את הערך נקי!), ומיד קרא שוב לפונקציה הרקורסיבית עם שאר הרשימה (cdr items) תחת הסביבה החדשה. 

; מחוץ ל-value-of, נגדיר את פונקציית העזר:
(define execute-foreach-loop
  (lambda (var vals body env)
    (if (null? vals) ; 1. Base Case
      (num-val 0) ; הדיפולט מההנחיות
      (let* ((current-val (car vals)) ; 2. Extract
             ; !!! שדה מוקש - תלוי בשפה !!!
             ; שפת IMPLICIT-REFS (יירמוז): (extend-env var (newref current-val) env)
             ; שפת EXPLICIT-REFS (ויפנה):  (extend-env var current-val env)
             (new-env (extend-env var (newref current-val) env)))
        ; מריצים את ה-body עם הסביבה המורחבת
        (value-of body new-env)
        ; 3. Recursive Call להמשך הרשימה
        (execute-foreach-loop var (cdr vals) body env)))))
תבנית 3: "השומר" (The Guard / Filter Condition) כאשר יש בדיקת טיפוסים או מילת when

התרחיש: המבחן דורש שנבצע את הלולאה רק אם תנאי מסוים מתקיים (למשל, when (exp) => ... ממועד 57 2021ב, או סינון לפי Type). אם התנאי לא מתקיים, יש לדלג לאיבר הבא.

איך ממדלים את זה? בתוך פונקציית העזר הרקורסיבית שלנו (מתבנית 2), אנחנו מוסיפים משפט if באמצע הדרך. אם ה-Guard מחזיר אמת - מפעילים את הגוף ואז ממשיכים רקורסיבית. אם ה-Guard מחזיר שקר - מדלגים על הגוף וקוראים ישר לרקורסיה עם (cdr items). 


; בתוך הלוגיקה של פונקציית העזר:
(let ((guard-val (value-of condition-exp env)))
  (if (expval->bool guard-val) ; האם השומר אישר?
    (begin ; התנאי אמת: עשה גם וגם
      (value-of body env)
      (helper-loop (cdr items) env))
    (begin ; התנאי שקר: רק המשך הלאה (דילוג)
      (helper-loop (cdr items) env))))

איך מחברים הכל יחד בתוך ה-value-of?

לאחר שהגדרנו את פונקציית העזר מחוץ ל-value-of, כל מה שנותר הוא לחזור אל ה-cases, לשלוף את הנתונים מה-AST, ולהפעיל אותה ב"שגר ושכח":


(foreach-exp (var vals body)
  ; קריאה לפונקציית העזר החיצונית שיצרנו
  (execute-foreach-loop var vals body env))

2.7 מעבדת המוטציות והזיכרון

סימולטור אינטראקטיבי של מנוע ההרצה בסביבת IMPLICIT-REFS.

2.7 Mutation Lab

מעבדת המוטציות והזיכרון

בואו נראה איך באמת מבצעים שינויים בעולם ה-IMPLICIT-REFS. הפקודה שלנו למעבדה: swap(x, y).

יומן מערכת

>> המערכת מוכנה. ממתין לקלט...
mutation.scm
שאלה 3

אלגוריתם הקשת טיפוסים

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

🔍איך ניגשים לשאלה הזאת?

כל התוכן של שאלה 3 הוא מאוד אלגוריתמי ודורש בעיקר לקלוט את השלבים באופן טכני לחלוטין. מדובר בהבנה של איך לנתח את השאלה מן החוץ פנימה, איך לכתוב את המשוואות (סעיף א') ואיך לבצע Substitution ו-Unification (סעיף ב').

📝מה צריך לעשות תכל'ס?

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

💡תזכורת טכנית לפתרון

  • בסעיף א': מקצים משתני טיפוס (t0, t1...) מלמעלה למטה (מן החוץ פנימה), ורק אז מחלצים את משוואות הטיפוסים (AQ) מלמטה למעלה.
  • בסעיף ב': פותרים לפי גישת החילחול ההדרגתית של האו"פ – מציבים פרימיטיביים קודם (int, bool), מגלים טיפוסי פונקציות בסיסיות, ומחלחלים את הערכים מעלה לביצוע איחוד מבני (Structural Unification) עד שמשתנה המטרה t0 נפתר.