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

שאלה 2 (25 נקודות) שאלה זו עוסקת בשפת "יוטורג" (שפה PROC תיאורטית) המוצגת בעמודים 81-74 בעמודים 3 בפרק 3. שאלה זו עוסקת בהגדרה הפשוטה של פרוצדורות לא רקורסיביות. ברצונינו להחליף את השפה עם ביטויים בוליאניים נוסף על-ידי החדקוד הבא: $$\text{Expression } ::= \text{ check Expression } \{\text{and Expression}\}^* \text{ end}$$ $$\text{check-exp (bexp bexps)}$$ ביטויי check שישור של כמה ביטויים בוליאניים עם פונלות and מופעל. המשמעות של משתנים של check היא בוליאנית, ביטויי check היא בוליאנית, ורקו אם ורקו true הוא עורך, אחרת תנביעתו היא false. הביטויים השיתויים שתשורו על-ידי-ידי short-circuit הערכה, התחתיית בערערות short-circuit, אם עורך של אחד מחביטויים הבוליאניים היא false, הערכה של כל הביטויים check הנותרים היא false. על סמך לעירות תחיברית (parser) לביטויי בוליאני בפוליאני, ביטויי מהחיל בממילה end. בתחביר מופשט, ביטויי check-exp נקראות check הביטויים בבוליאני מופעל - bexps מופעל מופעל וגם - bexps היא רישימה של יתרות הביטויים הבוליאניים.

רמז: המפתח הוא יישום **short-circuit evaluation**: יש לעבור על הביטויים ברשימה ברקורסיה, ולהפסיק מיד (מבלי להעריך את השאר) ברגע שמוצאים ביטוי שמוערך ל-`false`.

פתרון: ## הוספת ביטויי `check` לשפת PROC ### תחביר קונקרטי ומופשט **תחביר קונקרטי:** $$\text{Expression} ::= \texttt{check}\; \text{Expression}\; \{\texttt{and}\; \text{Expression}\}^* \; \texttt{end}$$ **תחביר מופשט (AST):** $$\texttt{check-exp}(\textit{bexp},\, \textit{bexps})$$ כאשר $\textit{bexp}$ הוא הביטוי הבוליאני הראשון, ו-$\textit{bexps}$ היא **רשימה** של שאר הביטויים הבוליאניים. --- ### הגדרת סוג הנתונים (define-datatype) ```scheme ; בתוך ה-datatype של expression: (check-exp (bexp expression?) (bexps (list-of expression?))) ``` --- ### הפרשן (eval-expression) המשמעות של `check-exp` היא **שיתוף AND עם short-circuit evaluation**: - אם **כל** הביטויים מחזירים `true` — הערך הוא `true`. - אם **אחד** מהביטויים מחזיר `false` — מיד מפסיקים (ללא הערכת השאר) ומחזירים `false`. ```scheme (check-exp (bexp bexps) (letrec ((eval-and (lambda (curr rest) (let ((val (expval->bool (eval-expression curr env)))) (if (not val) ; short-circuit: מיד מחזירים false (bool-val #f) ; אחרת: בודקים את השאר (if (null? rest) (bool-val #t) (eval-and (car rest) (cdr rest)))))))) (eval-and bexp bexps))) ``` --- ### הסבר השלבים | שלב | תיאור | |-----|-------| | 1 | מחלצים את הביטוי הנוכחי `curr` ומסביבה `env` | | 2 | מעריכים אותו: `(eval-expression curr env)` | | 3 | אם הערך הוא `false` — **short-circuit**: מחזירים `(bool-val #f)` מיד | | 4 | אם הערך הוא `true` וה**רשימה ריקה** — מחזירים `(bool-val #t)` | | 5 | אחרת — **קריאה רקורסיבית** עם ראש הרשימה הנותרת | --- ### דוגמה לריצה הביטוי: `check true and false and true end` 1. מעריכים `true` → `#t`, ממשיכים. 2. מעריכים `false` → `#f`, **short-circuit** — מפסיקים מיד. 3. `true` השלישי **לא מוערך כלל**. 4. תוצאה: `(bool-val #f)` --- ### הערה על **מודל הסביבה** ה**סביבה** `env` מועברת **ללא שינוי** לכל קריאת `eval-expression` פנימית, כיוון שביטוי `check` אינו מגדיר קשירות חדשות — הוא רק מחשב ביטויים קיימים בסביבה הנוכחית.