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

הרחיבו את שפת LET (שפת "יוויומ") כך שתיתמך ב- if בעומק שרירותי. החידוקים החדשים הם: $$\text{Expression} := \text{if Expression then } \{ \text{Expression}\}^{+0}\text{ else } \{ \text{Expression}\}^{+0}$$ את התחביר החדש של הדקדוק החידוקים המומדרים בתוך הביטויים הם: • $\text{bool}$ היא בעולם בוליאני. • $\text{exps1}$ הם ביטויים המופעלים בתוך; שומרים לתחבורה כאשר עירכו של הביטוי הנוכחי הוא $\text{true}$. חידוק זה ייתרחוף בפקודה זו ייתיילה בעירכו של הביטויים האתרים שנמצאים. • $\text{exps2}$ הם ביטויים המופעלים בתוך; שומרים לתחבורה כאשר עירכו של הביטוי הנוכחי הוא $\text{false}$. חידוק זה ייתרחוף בפקודה זו ייתיילה בעירכו של הביטויים האתרים שנמצאים. לחילוץ דוגמה לשימוש בביטויים החדשים: let $x = 7$ in if zero? $(x)$ then $\{-(x,4); -(x,9); x\}$ else $\{$ if $-(x,3)$ then $\{3\}$ else $\{6\} ; -4 \}$ 2 מופעילים בתוך else-n בנבדוק ערכו. לכן יוציאו בלוק else-n ערכו של הביטוי הראשון מביניהם לאחר בצפיצות. (סוג התיוג של תחזוקה הוא, כמקרה זה: (num-val -4)).

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

פתרון: כדי להרחיב את שפת LET כך שתתמוך בביטוי `if` בעומק שרירותי עם רצפים של ביטויים בענפים, עלינו לבצע שני שינויים עיקריים: הרחבת התחביר המופשט (Abstract Syntax) כדי לייצג את המבנה החדש, והרחבת הסמנטיקה, כלומר, פונקציית ההערכה של המפרש (`eval` או `value-of`), כדי שתטפל במבנה זה. ### 1. הרחבת התחביר המופשט נוסיף סוג ביטוי חדש למבנה העץ התחבירי המופשט (AST) של השפה, שייצג את תנאי ה-`if` החדש. נקרא לסוג ביטוי זה `if-exp`. מבנה הנתונים שלו יכיל שלושה שדות: * `cond-exp`: ביטוי התנאי, שיוערך ראשון. * `then-exps`: רשימת הביטויים שיש להעריך אם התנאי מתקיים (הענף של `then`). * `else-exps`: רשימת הביטויים שיש להעריך אם התנאי אינו מתקיים (הענף של `else`). לדוגמה, את הביטוי: `if zero?(x) then {-(x,4); x} else {-4}` נייצג ב-AST באופן הבא (בכתיב דמוי-Scheme): ```scheme (if-exp (prim-app-exp 'zero? (list (var-exp 'x))) (list (prim-app-exp '- (list (var-exp 'x) (const-exp 4))) (var-exp 'x)) (list (const-exp -4))) ``` ### 2. הרחבת הסמנטיקה (המפרש) כעת נרחיב את פונקציית ההערכה המרכזית של המפרש, `value-of(exp, env)`, כך שתטפל בסוג הביטוי החדש `if-exp`. נוסיף תנאי חדש למפרש: ```scheme (define (value-of exp env) (cond ... (clauses for existing expressions) ... ((if-exp? exp) (let ((cond-val (value-of (if-exp->cond-exp exp) env))) (if (is-true? cond-val) (value-of-sequence (if-exp->then-exps exp) env) (value-of-sequence (if-exp->else-exps exp) env)))) ...)) ``` ההרחבה מסתמכת על שתי פונקציות עזר: **א. `is-true?`**: פונקציה זו קובעת את הכלל לערכי אמת. בשפות רבות (כמו Scheme), כל ערך שאינו `false` נחשב ל-`true`. נאמץ כלל זה: ```scheme (define (is-true? val) (not (and (boolean-val? val) (eq? (boolean-val->val val) #f)))) ``` כלומר, הפונקציה תחזיר `false` רק עבור ערך בוליאני מסוג `(bool-val #f)`, ו-`true` עבור כל ערך אחר (מספרים, כולל 0, וגם `(bool-val #t)`). **ב. `value-of-sequence`**: זוהי **פונקציית מפתח** המטפלת בהערכת רצף של ביטויים. היא מקבלת רשימת ביטויים וסביבה, מעריכה אותם לפי הסדר, ומחזירה את הערך של הביטוי **האחרון** ברצף. הערכים של הביטויים הקודמים נזרקים (אם כי תופעות הלוואי שלהם, אם היו, היו מתרחשות). מימוש רקורסיבי לפונקציה זו: ```scheme (define (value-of-sequence exps env) (if (null? (cdr exps)) ; is it the last expression? (value-of (car exps) env) (begin (value-of (car exps) env) ; evaluate and discard (value-of-sequence (cdr exps) env)))) ``` אם הרשימה `exps` ריקה, התנהגות זו אינה מוגדרת. בשאלה נתון שהרצפים אינם ריקים. ### 3. מעקב אחר הדוגמה נבצע מעקב אחר הערכת הביטוי מהשאלה בסביבה בה `x=7`: `if zero?(x) then {-(x,4); -(x,9); x} else {if -(x,3) then {3} else {6}; -4}` 1. **הערכת התנאי החיצוני**: `value-of(zero?(x), env)` מחזיר `(bool-val #f)` מכיוון ש-$7 \neq 0$. 2. מכיוון שהתנאי שקרי, נעריך את רצף הביטויים בענף ה-`else`. נפעיל את `value-of-sequence` על הרשימה: `[ if -(x,3) then {3} else {6} , -4 ]` 3. `value-of-sequence` מעריכה את הביטוי הראשון ברצף: `if -(x,3) then {3} else {6}`. א. **הערכת התנאי הפנימי**: `value-of(-(x,3), env)` מחשב $7-3=4$ ומחזיר `(num-val 4)`. ב. `is-true?((num-val 4))` מחזיר `#t`, מכיוון שהערך אינו `(bool-val #f)`. ג. לכן, נעריך את רצף ה-`then` הפנימי, שהוא `[ 3 ]`. ד. `value-of-sequence([3], env)` מעריך את `3` ומחזיר `(num-val 3)`. 4. הערך שהוחזר מהביטוי הראשון ברצף, `(num-val 3)`, **נזרק**. `value-of-sequence` ממשיכה לביטוי הבא. 5. כעת `value-of-sequence` מעריכה את הביטוי האחרון ברצף: `-4`. 6. `value-of(-4, env)` מחזיר `(num-val -4)`. 7. מכיוון שזהו הביטוי האחרון, ערך זה, `(num-val -4)`, הוא התוצאה הסופית של `value-of-sequence` ושל ביטוי ה-`if` כולו. התוצאה הסופית היא אכן `(num-val -4)`, כפי שצוין בשאלה.