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

שאלה 2 (25 נקודות) שאלה זו עוסקת בשפת "יוויומ" (שפת PROC בנוסף בפרק 3 בעמודים 81-74. שפה זו בהרחבה וההודעה של פונקציונות לא רקורסיביות. ברצונו להרחיב את השפה עם ביטויים בחדוש שתאבילויים נחון על-ידי הדקדוק הבא: $$\text{Expression} := \text{mapsum Expression } [\{ \text{Expression}\}^{*0}]$$ $$\text{mapsum-exp (prc exps)}$$ כאשר, • prc היא בעולם פונקציוני המחזיקה פנקציודות המחזוקים מסמפור וממחוקים מסמפור. • exps הם ביטויים המופעלים בתוך; אם 0 יתכנו מהבטויים הוא שחזוקים הם בטויים מספרים. הפנקציודות prc מפעילה את סכום התוצאות הסגורום בתוך sps שנמצא לאחר. לחילוץ דוגמה לשימוש בביטויים החדשים: let $p=$ proc $(x) -(x,1)$ in mapsum $p [6; -(9,2); 2]$ בדוגמה זו, הפנקציודות p מפעילה על כל אחד מהביטויים בתוך 3-מ אתר המביטויים בבטוויהם, וממחוקים של כל הרצעות של p על כל אחד מהביטויים בבטוויהם בתוך mapsum p על כל (num-val 12) בקבוק זה.

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

פתרון: על מנת להרחיב את המפרש לתמיכה בביטוי `mapsum`, יש להוסיף מקרה חדש לפונקציית ההערכה המרכזית של המפרש, `value-of`. ביטוי `mapsum` מקבל **פרוצדורה** ורשימת ביטויים. הסמנטיקה שלו היא להפעיל את הפרוצדורה על הערך של כל אחד מהביטויים ברשימה, ולאחר מכן לסכום את כל התוצאות. ההנחה היא שהפרוצדורה מקבלת ארגומנט מספרי יחיד ומחזירה ערך מספרי, וכן שכל הביטויים ברשימה מחושבים לערכים מספריים. התוספת לקוד של `value-of` תטפל במבנה העץ התחבירי המופשט (AST) החדש, `mapsum-exp`. להלן מימוש אפשרי ב-Scheme, בהנחה של קיום פונקציות עזר סטנדרטיות במפרש כמו `value-of-rands`, `apply-procedure`, וכן קונסטרוקטורים וסלקטורים עבור **ערכים מבוטאים** (`expval`) כגון `num-val`, `proc-val`, `expval->num` ו-`expval->proc`. ```scheme (define value-of (lambda (exp env) (cases expression exp ... (mapsum-exp (prc-exp exps) (let ((proc (value-of prc-exp env))) (expval->proc proc (lambda (p) ; p is the actual procedure value (let ((arg-vals (value-of-rands exps env))) (letrec ((apply-and-sum (lambda (vals) (if (null? vals) (num-val 0) (let ((res1-val (apply-procedure p (list (car vals)))) (rest-sum-val (apply-and-sum (cdr vals)))) (let ((n1 (expval->num res1-val)) (n-rest (expval->num rest-sum-val))) (num-val (+ n1 n-rest)))))))) (apply-and-sum arg-vals))))))) ... ))) ``` ### הסבר על המימוש: 1. **חישוב הפרוצדורה**: ראשית, הביטוי `prc-exp` מחושב ב**סביבה** הנוכחית `env` באמצעות קריאה ל-`value-of`. התוצאה היא **ערך פרוצדורה** (`proc-val`). 2. **בדיקת טיפוס והפשטה**: פונקציית העזר `expval->proc` מוודאת שהערך שהתקבל הוא אכן פרוצדורה, ומחלצת ממנו את אובייקט הפרוצדורה `p` עצמו. שלב זה מהווה **בדיקת טיפוסים** בזמן ריצה. 3. **חישוב הארגומנטים**: פונקציית העזר `value-of-rands` מופעלת על רשימת הביטויים `exps`. היא מחשבת כל ביטוי ברשימה ומחזירה רשימה של ערכים מבוטאים, `arg-vals`. 4. **הפעלה וסכימה רקורסיבית**: הפונקציה הרקורסיבית המקומית `apply-and-sum` מבצעת את עיקר הלוגיקה: * **מקרה הבסיס**: אם רשימת הערכים `vals` ריקה, הפונקציה מחזירה `(num-val 0)`, מכיוון שסכום של קבוצה ריקה של מספרים הוא 0. * **הצעד הרקורסיבי**: אם הרשימה אינה ריקה, הפונקציה: a. מפעילה את הפרוצדורה `p` על הערך הראשון ברשימה `(car vals)` באמצעות `apply-procedure`. b. קוראת לעצמה **רקורסיבית** על יתרת הרשימה `(cdr vals)` כדי לחשב את סכום יתר התוצאות. c. משתמשת ב-`expval->num` כדי לחלץ את הערכים המספריים מהתוצאה הנוכחית ומהסכום הרקורסיבי. פעולה זו מוודאת שערך ההחזרה של `p` הוא אכן מספרי. d. מסכמת את שני המספרים ומחזירה את התוצאה עטופה ב-`num-val`. 5. **הפעלה ראשונית**: הקריאה `(apply-and-sum arg-vals)` מתחילה את התהליך הרקורסיבי על רשימת הערכים המחושבים. התהליך שנוצר הוא **תהליך רקורסיבי** קלאסי.