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

שאלה ב (18 נקודות) להלן פונקציות value-of של שפת "יוטורג": הסתירו מה הם השינויים והתוסופות החדשים בהשוואה לשפה בעמוד 79. את התשובה יש לכתוב במחברת הבחינה. **הערות:** - המפעקש לעבודה עם סביבונה אותו משתנה כפי שהוצהר עבור שפה "יוטורג". - המפעקש לעבודה עם החנון (store) הוא אותו משתנה כפי שהוצהר עבור שפה "יוטורג". - בממשפחת הפנתתרונה, יתתן לכתוב פונקציות צור בממקרה הנדרוש. $$;; \text{ value-of : Exp } \times \text{Env} \to \text{ExpVal}$$ $$;; \text{ Page: } 79$$ $$(\text{define } \text{value-of}$$ $$(\text{lambda (exp env})$$ $$(\text{cases expression exp}$$ $$(\text{const-exp (num) (num-val num))$$ $$(\text{var-exp (var) (deref (apply-env env var))))$$ $$(\text{diff-exp (exp1 exp2})$$ $$(\text{let ((val1 (value-of exp1 env))$$ $$(\text{val2 (value-of exp2 env))))$$ $$(\text{let ((num1 (expval->num val1))$$ $$(\text{(num2 (expval->num val2))))$$ $$(\text{num-val (- num1 num2))))))$$ $$(\text{zero?-exp (exp1})$$ $$(\text{let ((val1 (value-of exp1 env)))$$ $$(\text{let ((num1 (expval->num val1)))$$ $$(\text{if (zero? num1) (bool-val \#t) (bool-val \#f))))))$$ $$(\text{if-exp (exp1 exp2 exp3})$$ $$(\text{let ((val1 (value-of exp1 env)))$$ $$(\text{if (expval->bool val1)})$$ $$(\text{(value-of exp2 env})$$ $$(\text{(value-of exp3 env)))))$$ $$(\text{let-exp (var exp1 body})$$ $$(\text{let ((v1 (value-of exp1 env)))$$ $$(\text{(value-of body})$$ $$(\text{(extend-env var (newref v1) env))))))$$ $$(\text{proc-exp (var body})$$ $$(\text{(proc-val (procedure var body env))))$$ $$(\text{call-exp (rator rand})$$ $$(\text{let ((proc (expval->proc (value-of rator env))))$$ $$(\text{(arg (value-of rand env))))$$ $$(\text{(apply-procedure proc arg))))$$

רמז: שימו לב לפעולות החדשות `newref` בביטוי `let-exp` ו-`deref` בביטוי `var-exp`. מהי משמעותן וכיצד הן משנות את תפקיד הסביבה ואת מודל החישוב הכולל של המפרש?

פתרון: השינוי המהותי ביותר במפרש המוצג הוא הוספת תמיכה ב**מצב** (state) לשפה, כלומר, הפיכת המשתנים ל**בני-שינוי** (mutable). המעבר משפה פונקציונלית טהורה לשפה עם מצב מתבצע באמצעות הכנסת **מאגר** (store) ו**הפניות** (references) למודל החישוב. נפרט את השינויים והתוספות: 1. **שינוי במודל הסביבה והוספת מאגר (Store):** * בשפה פונקציונלית ללא מצב (כמו זו שניתן להניח שהייתה בעמוד 79), **הסביבה** (environment) ממפה שמות משתנים ישירות ל**ערכים** שלהם (`ExpVal`). הפעולה `(apply-env env var)` הייתה מחזירה את הערך הקשור למשתנה. * בשפה החדשה, "יוטורג", **הסביבה** ממפה שמות משתנים ל**כתובות** או **הפניות** (`references` / `locations`) במאגר. המאגר, שהוא מבנה נתונים חדש במפרש, ממפה כתובות אלו לערכים. * כתוצאה מכך, מודל החישוב משתנה: כדי למצוא ערך של משתנה, יש קודם למצוא את כתובתו בסביבה, ולאחר מכן לגשת למאגר באמצעות הכתובת כדי למצוא את הערך עצמו. 2. **שינויים ספציפיים ב-`value-of`:** * **`let-exp`**: זהו המקום המרכזי שבו השינוי בא לידי ביטוי. * הביטוי `exp1` מחושב לקבלת ערך `v1`. * במקום להרחיב את הסביבה עם הזוג `(var, v1)`, המפרש יוצר **הפניה חדשה** במאגר באמצעות `(newref v1)`. פעולה זו מקצה תא חדש במאגר, מאתחלת אותו עם הערך `v1`, ומחזירה את כתובתו של התא. * הסביבה מורחבת כך שהמשתנה `var` מקושר ל**כתובת החדשה** שנוצרה, ולא לערך `v1` עצמו. זה הופך את המשתנה שנוצר על ידי `let` למשתנה בר-שינוי. * **`var-exp`**: חישוב ערכו של משתנה השתנה בהתאם. * הפעולה `(apply-env env var)` מחזירה כעת את ה**כתובת** של המשתנה במאגר, ולא את ערכו. * כדי לקבל את הערך עצמו, יש צורך בפעולה חדשה, `deref`, אשר מקבלת כתובת ומחזירה את הערך המאוחסן באותה כתובת במאגר. כלומר, `(deref (apply-env env var))`. * **`proc-exp` ו-`call-exp`**: אופן הטיפול בפרוצדורות נשאר דומה, אך יש לו משמעות חדשה בהקשר של מצב. פרוצדורה עדיין נוצרת כ**סגור** (closure) הלוכד את הסביבה בזמן ההגדרה. כעת, סביבה זו היא סביבה של הפניות. כאשר הפרוצדורה נקראת, היא יכולה לגשת (ואם היה קיים אופרטור השמה, גם לשנות) את המשתנים שהיו בסביבה הלקסיקלית שלה דרך ההפניות במאגר. לסיכום, התוספות העיקריות הן הקונספטים של **מאגר (store)** ו**הפניות (references)**, והפעולות הנלוות `newref` ו-`deref`. שינויים אלו הופכים את השפה משפה פונקציונלית טהורה לשפה אימפרטיבית עם **מצב** ו**תחום לקסיקלי**. $\blacksquare$