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

שאלה זו עוסקת בשדרוג של שפת "ויהיי" (שפת LET) המתוארת בספר הלימוד בפרק 3 בעמודים 60-74. בשאלה זו, נרצה להוסיף לשפת "ויהיי" ביטוי חדש מסוג לולאת `do` המוגדרת על פי הדקדוק הבא ובאופן המוסבר ומודגם לאחר מכן. להלן הדקדוק של לולאת `do`: ``` Expression ::= do ( { < Identifier Expression Expression > }+ { [ Expression Expression ] }+ ) ``` מבנה הנתונים המייצג את הביטוי: ``` do-exp (ids inits steps bools results) ``` **הסבר לדקדוק:** ביטוי `do-exp` מגדיר כמות שרירותית (לפחות אחד) של משתנים מספריים (`ids`), למשתנים יש ערכים התחלתיים הנתונים ע"י הביטויים `inits`, ובכל מחזור לולאה גדלים הצעדים הנתונים ע"י ביטויים `steps`. כמו כן, ללולאה כמות שרירותית (לפחות אחד) של ביטויים בוליאניים (`bools`), בכל מחזור לולאה נבדקים הביטויים הבוליאניים, והראשון מביניהם שערכו אמת, יגרום ללולאה להיעצר ולהחזיר את ערכו המתאים מתוך ביטוי `results` המתאים לביטוי הבוליאני שנמצא אמת. אם בבדיקת הביטויים הבוליאניים אין ביטוי שערכו אמת, הלולאה תעבור למחזור הבא שלה, כאשר כל אחד מהמשתנים גדל על פי הצעד המתאים לו, ואז שוב נבדקים הביטויים הבוליאניים כמו קודם. הלולאה תתבצע שוב ושוב, עד אשר ימצא מחזור שבו אחד התנאים הבוליאניים היה אמת. (כמובן שיכולה להתרחש לולאה אינסופית אך זו אחריותו של המתכנת ולא של המפרש) **הבהרות:** - אתחול של משתנה לולאה `do` יכול להכיר כבר את המשתנים שכבר אותחלו לפניו. - קידום משתני לולאה נעשה על פי ערכם של המשתנים במצב הנוכחי. **דוגמה 1:** ``` > (run "do( <a 0 4> <b 7 -(a,2)> <c -(b,1) -(a,b)> [zero? (b) -(a,c)] [zero? (-(c,-2)) -(a,5)] ) ") (num-val 3) > ``` בדוגמה זו, התוכנית מורכבת מלולאת `do` המגדירה 3 משתנים `a,b,c`. בתחילה `a` שווה לאפס, `b` שווה ל-7, `c` שווה ל-1 (6- פחות 1). כעת נבדקים התנאים הבוליאניים לפי סדר הופעתם. התנאי הבוליאני הראשון בודק האם ערכו של `b` הוא 0, תנאי זה אינו מתקיים כרגע. התנאי הבוליאני השני בודק האם ערכו של `c` הוא 2-, גם הוא לא מתקיים כרגע. מאחר ואף תנאי בוליאני לא התקיים, הלולאה ממשיכה למחזור הבא שלה, שבו היא תעבוד עם משתנים `a,b,c` שערכם הוא כעת: - `a` שווה ל-4, כי היה לו 0 והתווסף לו 4 - `b` שווה ל-5, כי היה לו 7 והוא גדל ב-2 (a-2), `a` במצבו הנוכחי (לפני שקודם) היה 0 ולכן `a-2` זה 2- - ולכן `b` קטן ב-2 מ-7 לכן 5- - `c` שווה ל-1, כי היה לו 6 והתווסף לו `a-b` (לפני שקודמו) היה 0 ו-7- בהתאמה ולכן `c` קטן ב-7 ונהיה 1- כעת נבדקים שוב התנאים הבוליאניים, וניתן לראות ששוב אף אחד מהם אינו נכון, ולכן הלולאה ממשיכה למחזור הבא שלה, עם משתנים `a,b,c` שערכם הוא: - `a` שווה ל-8, כי היה לו 4 והתווסף לו 4 - `b` שווה ל-7, כי היה לו 5, והוא גדל ב-2 (a-2) שזה 2 - `c` שווה ל-2, כי היה לו 1- והוא גדל ב-(`a-b`) שזה 1- וכעת שוב נבדקים התנאים הבוליאניים (לפי הסדר בו הם כתובים) וכעת התנאי הבוליאני השני מתקיים! ולכן הלולאה נעצרת ומוחזר ערכו של הביטוי הכתוב לצד התנאי הבוליאני שהיה אמת, שבמקרה זה הביטוי הוא `a-5` שערכו הנוכחי הוא 8-5=3 ולכן תוצאת התוכנית היא 3. **דוגמה 2:** ``` > (run "do( [zero? (b) -(a,c)] [zero? (-(c,-2)) -(a,5)] ) ") interp.scm:72:15: do-exp: do loop with no variables are not allowed > ``` בדוגמה זו יש לולאת `do` ללא הגדרת משתנים, על פי הדקדוק הנתון בשאלה נדרש לפחות משתנה אחד ולכן התקבלה הודעת שגיאה מתאימה. **דוגמה 3:** ``` > (run "do( <a 0 4> <b 7 -(a,2)> <c -(b,1) -(a,b)> ) ") interp.scm:74:19: do-exp: do loop with no booleans are not allowed > ``` בדוגמה זו יש לולאת `do` ללא הגדרת תנאים בוליאניים, על פי הדקדוק הנתון בשאלה נדרש לפחות תנאי בוליאני אחד ולכן התקבלה הודעת שגיאה מתאימה. **ממשו והטמיעו** את השינויים הדרושים כפי שהוגדרו והודגמו לעיל בתוך שפת "ויהיי" (שפת LET). בתשובתכם, הקפידו להסביר היכן בדיוק נדרשים שינויים ותוספות בקבצי המפרש, ומהם השינויים והתוספות. **הנחיות כלליות לפתרון:** 1. הקפידו על כתב ברור, ועל קוד מבני ומסודר. 2. הקפידו על פתיחת וסגירת סוגריים במקומות הנכונים. 3. הפתרון אמור לשמור על הגדרות השפה המקוריות (פרט לשינויי כזה נדרש שינויי כזה במפרש בשאלה). 4. על מנת לפשט קוד ארוך, כדאי ורצוי להיעזר בכתיבת פרוצדורות עזר (מחוץ ל-`value-of` או כאלה המוטמעות בתוכו). 5. בפתרונכם, הקפידו על אבחנה וכן שימוש נכון בין ביטוי (`expression`) לבין תוצאת חישוב ביטוי (`expval`) לבין `identifier`. 6. ניקוד יורד על אי ניתוח ומימוש נכון של הדקדוק הנתון בשאלה, כלומר יש להפקיד על זיהוי וטיפול נכון ב-terminals, non-terminals ופעולות של סגור (`)*` או `{ }+`).

רמז: יש להוסיף את `do-exp` לדקדוק ולמבנה הנתונים, ואז לממש את `value-of` עבורו: לאתחל את משתני הלולאה, לבדוק את התנאים הבוליאניים לפי הסדר, ואם אחד מהם אמת — להחזיר את ה-result המתאים, אחרת לקדם את הצעדים ולחזור.

פתרון: **פתרון — הוספת לולאת `do` לשפת LET** **שלב 1: הדקדוק (`define-datatype`)** בקובץ ה-`define-datatype` של `expression`, מוסיפים מקרה חדש: ```scheme (do-exp (ids (list-of identifier?)) (inits (list-of expression?)) (steps (list-of expression?)) (bools (list-of expression?)) (results (list-of expression?))) ``` **שלב 2: הפרסר** מוסיפים כלל פרסור ל-`do`: ```scheme ("do" "(" (arbno "<" (identifier) (expression) (expression) ">") (arbno "[" (expression) (expression) "]") ")") => do-exp) ``` יש לוודא שבפרסור נדרשת לפחות אחת מכל קבוצה (`arbno` בלבד אינו מספיק — נדרש `arbno` עם בדיקת ריקות בעת הפירוש, כפי שמתואר בדוגמאות השגיאה). **שלב 3: `value-of`** ```scheme (do-exp (ids inits steps bools results) (let do-loop ((env env) (vals (map (lambda (init) (value-of init env)) inits))) (if (null? ids) (error 'do-exp "do loop with no variables are not allowed") (if (null? bools) (error 'do-exp "do loop with no booleans are not allowed") (let ((env* (extend-env* ids vals env))) (let check-bools ((bools bools) (results results)) (if (null? bools) ;; אף תנאי לא היה אמת — מקדמים ומחזירים למחזור (do-loop env* (map (lambda (step) (value-of step env*)) steps)) (if (expval->bool (value-of (car bools) env*)) ;; תנאי אמת — מחזירים את התוצאה המתאימה (value-of (car results) env*) (check-bools (cdr bools) (cdr results))))))))) ``` **הבדיקות:** בדיקות הריקות (ללא משתנים / ללא תנאים) מבוצעות בתחילת `value-of`, לפני כל חישוב. **הסבר:** בכל איטרציה, נבנית סביבה חדשה `env*` עם ערכי המשתנים הנוכחיים. לאחר מכן נסרקים התנאים בסדר — אם אחד אמת, מוחזר ה-result המתאים. אחרת, מחושבים הצעדים על בסיס `env*` ונקראת `do-loop` מחדש עם הערכים המעודכנים.