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

שאלה זו עוסקת בשדרוג של שפת ה־PROC המתוארת בספר הלימוד בפרק 3 (עמודים 74–81). מאפשרים להרחיב את שפה זו בביטוי חדש בשם `forsum-exp` המאפשר לגלגל לולאה על רשימת ערכים מספריים, תוך אפשרות לעצירת הלולאה או דילוג על איברים. מרשימת ה-exps מהווה משתנה הלולאה אמור לסקור. מרשימת ה-guards מורכבת מביטויים (guards) יכולים להיות skip או break. הביטוי מחזיר את הסכום של תוצאות הפעולה לכל איבר ברשימה שעליו פעלה הלולאה. התחביר של הביטוי החדש הוא: ``` Expression ::= for/sum [ identifier ({Expression}*(,)) ] { <guard> }* Expression for/end ``` עם ייצוג AST: ``` forsum-exp (id exps guards body) ``` כאשר: ``` guard ::= skip : Expression skip-guard (boolexp) guard ::= break : Expression break-guard (boolexp) ``` הפעולה הכללית של הביטוי החדש: ביטוי `forsum-exp` מורכב מהמרכיבים הבאים: - משתנה הזמן החוזר עליו הלולאה — `id` - מרשימת ה-exps שמהווה את הרשימה שמשתנה הלולאה אמור לסקור - מרשימת ה-guards המורכבת מביטויים שיכולים להיות skip או break (יכולים לחזור על עצמם) — כל סוג guard מורכב מביטוי בוליאני - הביטוי body שהוא גוף הלולאה הלולאה עוברת על האיברים של רשימת הלולאה לפי מיקום id, מתחילה מהאיבר הראשון, ולכל אחד מהם בודקת תחילה אם מתקיים אחד מה-guards (בודקים לפי סדר הגדרתם). במידה ונמצא guard אחד שמתקיים, לא יבוצע גוף הלולאה עבור אותו איבר. אם הביטוי שהתקיים guard הוא מסוג skip, יש להמשיך את הלולאה ולעבור לאיבר הבא; ואם ה-guard שהתקיים הוא מסוג break, יש להפסיק את הלולאה ולהחזיר את הסכום שהצטבר עד לשלב זה. במידה ולא מצאנו guard אחד שמתקיים, יחשב גוף הלולאה והתוצאה תתווסף לסכום הכולל. **דוגמה 1:** ``` (run "for/sum [i (1,2,3,20,5,90)] <skip: zero?(-(i,1))> <break: zero? (-(i,5))> <skip: zero? (-(i,3))> -(i,-5) for/end") => (num-val 32) ``` בדוגמה 1, מוגדרת לולאה עם משתנה i ורשימת ערכים. ללולאה זו 3 guards. לכל האיברים: אם האיבר הוא 1 יש לדלג עליו, אם האיבר הוא 5 יש להפסיק, ואם האיבר הוא 3 יש לדלג. לפיכך הלולאה תפעל רק על האיברים 2 ו-20 (הביניהם 3 ו-1 מדולגים), עליהם הלולאה תחשב את ערכן של גוף הלולאה שמחזיר תוספת 5. לכן הסכום הכולל שיצטבר יהיה 32 (= (20+5) + (2+5)) ולכן הניב הסופי הוא (num-val 32). **דוגמה 2:** ``` (run "for/sum [i ()] <skip: zero?(-(i,1))> <break: zero? (-(i,5))> <skip: zero? (-(i,3))> -(i,-5) for/end") => interp.scm:79:16: forsum-exp: The list for i is empty ``` בדוגמה 2, מוגדרת לולאה עם רשימה ריקה, זה אינו תקין (על פי הרקורסיה המוגדרת) ולכן הורפסה הודעת שגיאה מתאימה. **דוגמה 3:** ``` (run "for/sum [i (1,2,3,20,5,90)] -(i,-5) for/end") => (num-val 151) ``` בדוגמה 3, מוגדרת לולאה שאינה כוללת guards (אפס guards, תקין תחבירית) ולכן הלולאה תפעל על כל האיברים והתוצאה תהיה סכום כל האיברים בתוספת 5 לכל אחד. עליך לממש את השינויים הדרושים בתוך שפת ה-PROC (שפת **ייחסמוריות**) בתוך קבצי המפרש, הקפד להסביר בקצרה בקבצי המפרש, **ולציין** את השורות הדרושות והמתחנות. **הוראות לחלקים הנלמדים:** 1. הקפד על כתב ברור, ועל קוד מובן ומסודר. 2. הקפד על פתיחות וסגירות במקומות המתאימות. 3. התוצר אמור לשמור על הגדרת השפה הנדרשת שיוגדר לזה במפרש בשאלה. 4. על מנת לפשט קוד ארוך, כדאי להיעזר בפונקציות עזר (מחוץ value-of). 5. בפרט, הקפד על הבחנה ושימוש מכון בין ביטוי (expression) לבין תוצאת חישוב ביטוי (expval) לבין identifier. 6. ניקוד יורד על אי הבחנה ומימוש מכון של הרקורסיה הנחונה בשאלה, כלומר יש להקפיד על הכון ב-terminals, non-terminals הפעולות של פסיקור ( )* או { }+.

רמז: הוסיפו `forsum-exp` כ-datatype חדש עם שדות id, exps, guards, body. ב-`value-of`, עברו על רשימת הערכים באמצעות לולאת עזר (loop עם accumulator), ולכל איבר בדקו את ה-guards בסדר — skip מדלג, break מחזיר את הסכום הנוכחי, ואם אף guard לא מתקיים חשבו את body והוסיפו לסכום.

פתרון: **פתרון שאלה 1 — מימוש `forsum-exp` בשפת PROC** יש להוסיף את הביטוי `forsum-exp` למפרש PROC. נדרשים השינויים הבאים: **1. הגדרת תחביר (grammar / define-datatype):** ```scheme ; ב-define-datatype expression: (forsum-exp (id identifier?) (exps (list-of expression?)) (guards (list-of guard?)) (body expression?)) ; הגדרת guard: (define-datatype guard guard? (skip-guard (boolexp expression?)) (break-guard (boolexp expression?))) ``` **2. parsing — הוספה ל-`parse-expression`:** ```scheme (("for/sum" "[" identifier "(" (separated-list expression ",") ")" "]" (arbno "<" guard-production ">") expression "for/end") => (lambda (id exps guards body) (forsum-exp id exps guards body))) ``` וכן parsing של guard: ```scheme (("skip" ":" expression) => (lambda (e) (skip-guard e))) (("break" ":" expression) => (lambda (e) (break-guard e))) ``` **3. ביצוע — הוספה ל-`value-of`:** ```scheme (forsum-exp (id exps guards body) (let ((vals (map (lambda (e) (value-of e env)) exps))) (if (null? vals) (error 'forsum-exp "The list for ~a is empty" id) (let loop ((items vals) (acc 0)) (if (null? items) (num-val acc) (let* ((cur (car items)) (new-env (extend-env id cur env)) (guard-result (apply-guards guards new-env))) (cond ((eq? guard-result 'skip) (loop (cdr items) acc)) ((eq? guard-result 'break) (num-val acc)) (else (let ((v (expval->num (value-of body new-env)))) (loop (cdr items) (+ acc v)))))))))) ``` **עזר — `apply-guards`:** ```scheme (define (apply-guards guards env) (if (null? guards) 'none (let ((g (car guards))) (cases guard g (skip-guard (boolexp) (if (expval->bool (value-of boolexp env)) 'skip (apply-guards (cdr guards) env))) (break-guard (boolexp) (if (expval->bool (value-of boolexp env)) 'break (apply-guards (cdr guards) env))))))) ``` **הסבר:** עבור כל איבר ברשימה, מרחיבים את הסביבה ב-id, בודקים את ה-guards בסדר. אם guard מסוג skip מתקיים — מדלגים ועוברים לאיבר הבא. אם guard מסוג break מתקיים — מחזירים את הסכום שהצטבר עד כה. אם אף guard לא מתקיים — מחשבים את body ומוסיפים לסכום. $\blacksquare$