שאלת מבחן בשפות תכנות - האוניברסיטה הפתוחה 2024 - מפרשים

בספר הלימוד בעמודות 113–120 מתוארת שפת "יירשגורי" (שפת IMPLICIT-REFS). בשאלה זו נרצה לממש ביטוי חדש המסייע לבצע לולאות מסוגים שונים. ללולאה יש מבנה עם אסטרטגיה יחידה. בכל איטרציה של הלולאה, יש להשתמש בגוף הלולאה. לאסטרטגיות הלולאה כוללות תנאים (guards), באמצעותם ניתן לשלוט על הפסקת הלולאה לפני הזמן. לשם כך נרחיב את שפת "יירשגורי" עם ביטוי חדש בשם `for/proc`. להלן הדקדוק המגדיר את הביטוי החדש ותיאור התנהגות הביטוי: ``` Expression ::= for/proc ( identifier ; | { identifier }*(,) | ; | { Expression }*(,) | ) {< Guard>}* { Expression } forproc-exp (Id Ids Bodies Guards Body) Guard ::= skip : Expression skip-guard (exp) Guard ::= break : Expression break-guard (exp) ``` **הסבר על הדקדוק והתנהגות הביטוי:** לביטוי `forproc` הרכיבים הבאים: - **`Id`** — המשתנה החדש לכרוך בביצוע הלולאה, אינו מוכר כסיום הלולאה. - **`Ids` ו-`Bodies`** — רשימות של שמות פרמטרים וגופי ביטויים בהתאמה. בכל איטרציה, ה-`id` ילקח מרשימת `ids` ויהיה שם הפרמטר בגוף הפרוצדורה שנקבע לפי הביטוי המקביל ברשימת `bodies`. - **`Guards`** — רשימות של `Guard` מסוג שני: `skip` ו-`break`. כל `Guard` מבוטא בביטוי. אם Guard מסוג `skip` מתקיים (מחזיר אמת), הלולאה מדלגת על האיטרציה הנוכחית וממשיכת לאיטרציה הבאה. ב-Guard מסוג `break`, כאשר הביטוי מחזיר אמת, הלולאה מסתיימת לאלתר. בכל איטרציה נבדקים כל ה-Guards בסדרם. - **`Body`** — זהו גוף הלולאה שיש לבצע בכל איטרציה. הלולאה מסתיימת כאשר Guard מסוג `break` מחזיר אמת, או כאשר נגמרים האיברים ברשימות ה-`Ids` וה-`Bodies`. לביטוי `forproc-exp` אין ערך מוחזר, ולכן יש להחזיר ערך פיקטיבי של `num-val 27`. יש לבדוק ולהדפיס שגיאה בכל מקרה של שימוש לא תקין. **יש לממש שגיאות מתאימות.** **דוגמה 1 — להמחשת השימוש בביטוי החדש:** ```scheme (run "let w1=100 in let w2=300 in let w3=500 in begin for/proc (p; [a,b,c,d]; [-(a,1),-(b,2),-(c,3), -(d,4)]) <skip: zero? ((p 2))> <break: zero? ((p 12))> <skip: zero? ((p 200))> { if zero? ((p 1)) then set w1 = 7000 else if zero? ((p 3)) then set w2 = p else set w3=(p w1) }; (w2 w3) end") (num-val 6993) ``` בדוגמה זו, מוגדרים 3 משתנים `w1,w2,w3` המאותחלים לערכים 100,300,500 בהתאמה. לאחר מכן, מבוצעת לולאה `for/proc` עם משתנה לולאה בשם `p`. בלולאה יש 4 פרוצדורות (בכל איטרציה נבחרת `p` עם גוף שונה): - באיטרציה הראשונה, `p` מייצג פרוצדורה בעלת פרמטר `a` וגוף `-(a,1)`. לא אחד מה-Guards מתקיים, ולכן מבוצע גוף הלולאה. מכיוון שה-`p` מקבל `1` ומחשב `-(1,1)=0`, `w1` משתנה להיות 7000. - באיטרציה השנייה, `p` מייצג פרוצדורה בעלת פרמטר `b` וגוף `-(b,2)`. ה-Guard מסוג `skip` מתקיים (כי `-(2,2)=0`), ולכן הלולאה מדלגת לאיטרציה הבאה. - באיטרציה השלישית, `p` מייצג פרוצדורה עם פרמטר `c` וגוף `-(c,3)`. אף אחד מה-Guards לא מתקיים, ולכן מבוצע גוף הלולאה. `w2` משתנה להיות `p` (הפרוצדורה הנוכחית). - באיטרציה הרביעית, `p` מייצג פרוצדורה עם פרמטר `d` וגוף `-(d,4)`. אף אחד מה-Guards לא מתקיים, ולכן מבוצע גוף הלולאה. `w3` משתנה להיות `(p w1)` = `(p 7000)` = `-(7000,4)` = 6996. בסוף הלולאה מבוצע `(w2 w3)`: `w2` הוא הפרוצדורה מאיטרציה 3 (פרמטר `c`, גוף `-(c,3)`), ומופעלת עם `w3=6996`, ומחזירה `-(6996,3)=6993`. **דוגמה 2 — דוגמה שונה מעמ' 9:** ```scheme (run "let w1=100 in let w2=300 in let w3=500 in begin for/proc (p; [a,b,c,d]; [-(a,1),-(b,2),-(c,3), -(d,4)]) < break: zero? ((p 2)) > < break: zero? ((p 12)) > < skip: zero? ((p 200)) > { if zero? ((p 1)) then set w1 = 7000 else if zero? ((p 3)) then set w2 = p else set w3=(p w1) }; -(w1,w2) end") (num-val 6700) ``` בדוגמה זו, הדוגמה רומה לדוגמה הקודמת אך עם Guards שונים. ה-Guard הראשון הוא `break` (ולא `skip`). לכן באיטרציה הראשונה (`p` עם גוף `-(a,1)`): Guard ראשון בודק `zero?((p 2))` = `zero?(-(2,1))` = `zero?(1)` = שקר — ממשיכים. Guard שני בודק `zero?((p 12))` = `zero?(-(12,1))` = `zero?(11)` = שקר — ממשיכים. Guard שלישי בודק `zero?((p 200))` = `zero?(-(200,1))` = שקר — ממשיכים. מבוצע גוף הלולאה: `zero?((p 1))` = `zero?(0)` = אמת, לכן `w1=7000`. לאחר מכן ממשיכים לאיטרציה הבאה. לבסוף הלולאה מסתיימת ומחושב `-(w1,w2)` = `-(7000,300)` = 6700. **יש לממש את הביטויים החדשים** בתוך שפת "יירשגורי" (IMPLICIT-REFS), **הקפידו לשמור על הגדרות הדוגמאות המקוריות** (פרט למקרים בהם הם גורמים לשינויים בתוך הגדרות המקוריות של המפרש בלבד).

רמז: יש לממש לולאה שעוברת על הזוגות `(id, body)` מרשימות `Ids` ו-`Bodies`, בכל איטרציה בונה פרוצדורה ומקשרת את `Id` אליה, ואז בודקת את ה-Guards בסדר: `skip` מדלג לאיטרציה הבאה, `break` מסיים את הלולאה, ואם אף Guard לא הופעל — מבצעים את גוף הלולאה.

פתרון: יש להוסיף לפרשן של שפת IMPLICIT-REFS את הטיפול בביטוי `forproc-exp`. הרעיון: עוברים על כל הזוגות `(id, body)` מ-`Ids` ו-`Bodies` בסדר, בכל איטרציה בונים פרוצדורה עם שם הפרמטר `Id` וגוף `body`, ומפעילים את ה-`Guards` ואז את גוף הלולאה. ```scheme (forproc-exp (id ids bodies guards body) (let loop ((id-list ids) (body-list bodies)) (if (null? id-list) (num-val 27) ; ערך פיקטיבי — הלולאה הסתיימה (let* ((cur-id (car id-list)) (cur-body (car body-list)) ; בניית הפרוצדורה לאיטרציה הנוכחית (p-val (proc-val (procedure cur-id cur-body env)))) ; עדכון הסביבה: מקשרים id לפרוצדורה הנוכחית (let ((new-env (extend-env id p-val env))) ; בדיקת כל ה-Guards בסדרם (let guard-loop ((gs guards)) (if (null? gs) ; אף Guard לא הופעל — מבצעים את גוף הלולאה ומתקדמים (begin (value-of body new-env) (loop (cdr id-list) (cdr body-list))) (let ((g (car gs))) (cases guard g (skip-guard (gexp) (let ((gval (value-of gexp new-env))) (if (expval->bool gval) ; skip — מדלגים על האיטרציה הנוכחית, ממשיכים לבאה (loop (cdr id-list) (cdr body-list)) ; Guard לא מתקיים — ממשיכים לבדוק את ה-Guard הבא (guard-loop (cdr gs))))) (break-guard (gexp) (let ((gval (value-of gexp new-env))) (if (expval->bool gval) ; break — עוצרים את הלולאה ומחזירים ערך פיקטיבי (num-val 27) ; Guard לא מתקיים — ממשיכים לבדוק את ה-Guard הבא (guard-loop (cdr gs))))))))))) ``` **הסבר הלוגיקה:** - הפונקציה `loop` מקבלת את שתי הרשימות `ids` ו-`bodies` ומתקדמת בהן במקביל. - בכל שלב, בונים פרוצדורה מה-`id` הנוכחי (שם פרמטר) וה-`body` הנוכחי (גוף), ומקשרים את `Id` (שם משתנה הלולאה) לפרוצדורה זו בסביבה החדשה. - ה-`guard-loop` עובר על כל ה-Guards בסדרם: `skip` — אם מתקיים, מדלג לאיטרציה הבאה; `break` — אם מתקיים, מסיים את הלולאה ומחזיר `num-val 27`. - אם אף Guard לא הופעל, מבצעים את `body` ומתקדמים לאיטרציה הבאה. - כאשר הרשימות נגמרות, הלולאה הסתיימה ומחזירים `num-val 27`. $\blacksquare$