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

קורס: שפות תכנות

אוניברסיטה: האוניברסיטה הפתוחה

שנה: 2017

סמסטר: ב

נושאים: מפרשים, eval, מודל הסביבה, רקורסיה, let, Scheme, סגורים

רמת קושי: קל-בינוני

שאלה א (7 נקודות) להלן מופיעים ההגדרות של scanner ו-parser של שפת "יוטורג" עיסקו להשלמת הטעם הראשוני של שפה. **ה-scanner:** $$(\text{define } \text{the-lexical-spec}$$ $$'((\text{whitespace } (\text{whitespace}) \text{ skip})$$ $$(\text{comment } (\text{"\#" (arbno (\text{not } \#\backslash\text{newline}))) \text{ skip})$$ $$(\text{identifier}(\text{letter (arbno (or letter digit } \text{\"_\" \"-\" \"?\")))$$ $$\text{symbol})$$ $$(\text{number (digit (arbno digit))) number)$$ $$(\text{number (\"-\" digit (arbno digit))) number)$$ $$))$$ **ה-parser:** $$(\text{define } \text{the-grammar}$$ $$'((\text{program (expression) a-program})$$ $$(\text{expression (number) const-exp})$$ $$(\text{expression (\"-(\" expression \",\" expression \")\"))$$ $$\text{diff-exp})$$ $$(\text{expression (\"zero?\" \"(\" expression \")\")) zero?-exp})$$ $$(\text{expression (\"if\" expression \"then\" expression \"else\" expression)})$$ $$\text{if-exp})$$ $$(\text{expression (identifier) var-exp})$$ $$(\text{expression (\"let\" identifier \"=\" expression \"in\" expression)})$$ $$\text{let-exp})$$ $$(\text{expression (\"proc\" \"(\" identifier \")\") expression})$$ $$\text{proc-exp})$$ $$(\text{expression (\"(\" expression expression \")\")) call-exp})$$ $$(\text{expression}$$ את התשובה יש לכתוב במחברת הבחינה

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

פתרון: השאלה המקורית קטועה. נניח שהמשימה היא להוסיף לשפה מבנה `letrec` המאפשר הגדרת פרוצדורות רקורסיביות, בתחביר `letrec f(x) = <body> in <expr>`. הפתרון כולל שני חלקים: הרחבת הדקדוק ומימוש סעיף מתאים ב-`eval-expression`. **1. הרחבת הדקדוק:** נוסיף את השורה הבאה להגדרת הדקדוק `the-grammar`, כדי לזהות את מבנה ה-`letrec` וליצור עבורו צומת `letrec-exp` בעץ התחביר המופשט (AST): `(expression ("letrec" identifier "(" identifier ")" "=" expression "in" expression) letrec-exp)` **2. מימוש `eval-expression`:** האתגר המרכזי במימוש `letrec` הוא שהפרוצדורה הרקורסיבית צריכה להיות קיימת ב**סביבה** שבה גוף הפרוצדורה עצמו מחושב, כדי לאפשר קריאות עצמיות. לשם כך, ניצור **סביבה רקורסיבית** באמצעות מוטציה. האלגוריתם לחישוב ביטוי `letrec` בסביבה `env` הוא: 1. צור סביבה חדשה, `rec-env`, המרחיבה את `env` עם קשירה חדשה עבור שם הפרוצדורה. בשלב זה, הערך של שם הפרוצדורה אינו ידוע, ולכן נקשור אותו לערך זמני (למשל, `*unassigned*`). 2. בתוך הסביבה החדשה `rec-env`, הערך את הגדרת הפרוצדורה. התוצאה היא **סגור (closure)** המורכב מקוד הפרוצדורה וסביבת ההגדרה שלה, שהיא `rec-env`. חשוב להדגיש שהסגור לוכד את הסביבה `rec-env`, הכוללת את הקשירה (העתידית) לעצמו. 3. כעת, לאחר שנוצר אובייקט הפרוצדורה, בצע מוטציה (למשל, באמצעות `set!`) על הקשירה של שם הפרוצדורה בסביבה `rec-env`, ושנה את ערכה מהערך הזמני לאובייקט הפרוצדורה שזה עתה נוצר. פעולה זו "קושרת את הלולאה" והופכת את הסביבה לשלמה. 4. לבסוף, הערך את גוף ה-`letrec` בסביבה המעודכנת `rec-env`. להלן סעיף מתאים ב-`eval-expression` ב-Scheme המממש לוגיקה זו: `((letrec-exp? exp)` ` (let* ((proc-name (letrec-exp->proc-name exp))` ` (bound-var (letrec-exp->bound-var exp))` ` (proc-body (letrec-exp->proc-body exp))` ` (let-body (letrec-exp->let-body exp))` ` (rec-env (extend-env (list proc-name) (list '*unassigned*) env))` ` (the-proc (make-procedure (list bound-var) proc-body rec-env)))` ` (set-binding-in-frame! ` ` (first-frame rec-env) proc-name the-proc)` ` (eval-expression let-body rec-env)))` במימוש זה, `extend-env` יוצרת מסגרת חדשה בסביבה, `make-procedure` יוצרת את הסגור, ו-`set-binding-in-frame!` מבצעת את המוטציה הנדרשת כדי להשלים את הקשירה הרקורסיבית. $\blacksquare$

שאלה א (7 נקודות)

להלן מופיעים ההגדרות של scanner ו-parser של שפת "יוטורג" עיסקו להשלמת הטעם הראשוני של שפה.

ה-scanner:

(define the-lexical-spec

^{'} ((whitespace (whitespace) skip)

(\text{comment } (\text{"\#" (arbno (\text{not } \#\backslash\text{newline}))) \text{ skip})

(\text{identifier}(\text{letter (arbno (or letter digit } \text{\"_\" \"-\" \"?\")))

symbol)

(\text{number (digit (arbno digit))) number)

(\text{number (\"-\" digit (arbno digit))) number)

))

ה-parser:

(define the-grammar

^{'} ((program (expression) a-program)

(expression (number) const-exp)

(\text{expression (\"-(\" expression \",\" expression \")\"))

diff-exp)

(expression (\overset{z}{¨} ero? ¨ \ddot{(} ¨ expression \ddot{)} \ddot{)}) zero?-exp)

(expression (\ddot{i} f ¨ expression \ddot{t} hen ¨ expression \overset{e}{¨} lse ¨ expression))

if-exp)

(expression (identifier) var-exp)

(expression (\ddot{l} et ¨ identifier \overset{=}{¨} ¨ expression \ddot{i} n ¨ expression))

let-exp)

(expression (\overset{p}{¨} roc ¨ \ddot{(} ¨ identifier \ddot{)} \ddot{)} expression)

proc-exp)

(expression (\ddot{(} ¨ expression expression \ddot{)} \ddot{)}) call-exp)

(expression

את התשובה יש לכתוב במחברת הבחינה

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן 2017 סמסטר ב2017סמסטר ב

★★★★★

מפרשיםevalמודל הסביבהרקורסיהletSchemeסגורים

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

השאלה המקורית קטועה. נניח שהמשימה היא להוסיף לשפה מבנה letrec המאפשר הגדרת פרוצדורות רקורסיביות, בתחביר letrec f(x) = <body> in <expr>. הפתרון כולל שני חלקים: הרחבת הדקדוק ומימוש סעיף מתאים ב-eval-expression.

1. הרחבת הדקדוק:
נוסיף את השורה הבאה להגדרת הדקדוק the-grammar, כדי לזהות את מבנה ה-letrec וליצור עבורו צומת letrec-exp בעץ התחביר המופשט (AST):
(expression ("letrec" identifier "(" identifier ")" "=" expression "in" expression) letrec-exp)

2. מימוש `eval-expression`:
האתגר המרכזי במימוש letrec הוא שהפרוצדורה הרקורסיבית צריכה להיות קיימת בסביבה שבה גוף הפרוצדורה עצמו מחושב, כדי לאפשר קריאות עצמיות. לשם כך, ניצור סביבה רקורסיבית באמצעות מוטציה.

האלגוריתם לחישוב ביטוי letrec בסביבה env הוא:
1. צור סביבה חדשה, rec-env, המרחיבה את env עם קשירה חדשה עבור שם הפרוצדורה. בשלב זה, הערך של שם הפרוצדורה אינו ידוע, ולכן נקשור אותו לערך זמני (למשל, *unassigned*).
2. בתוך הסביבה החדשה rec-env, הערך את הגדרת הפרוצדורה. התוצאה היא סגור (closure) המורכב מקוד הפרוצדורה וסביבת ההגדרה שלה, שהיא rec-env. חשוב להדגיש שהסגור לוכד את הסביבה rec-env, הכוללת את הקשירה (העתידית) לעצמו.
3. כעת, לאחר שנוצר אובייקט הפרוצדורה, בצע מוטציה (למשל, באמצעות set!) על הקשירה של שם הפרוצדורה בסביבה rec-env, ושנה את ערכה מהערך הזמני לאובייקט הפרוצדורה שזה עתה נוצר. פעולה זו "קושרת את הלולאה" והופכת את הסביבה לשלמה.
4. לבסוף, הערך את גוף ה-letrec בסביבה המעודכנת rec-env.

להלן סעיף מתאים ב-eval-expression ב-Scheme המממש לוגיקה זו:

((letrec-exp? exp)
(let* ((proc-name (letrec-exp->proc-name exp))
(bound-var (letrec-exp->bound-var exp))
(proc-body (letrec-exp->proc-body exp))
(let-body (letrec-exp->let-body exp))
(rec-env (extend-env (list proc-name) (list '*unassigned*) env))
(the-proc (make-procedure (list bound-var) proc-body rec-env)))
(set-binding-in-frame!
(first-frame rec-env) proc-name the-proc)
(eval-expression let-body rec-env)))

במימוש זה, extend-env יוצרת מסגרת חדשה בסביבה, make-procedure יוצרת את הסגור, ו-set-binding-in-frame! מבצעת את המוטציה הנדרשת כדי להשלים את הקשירה הרקורסיבית.

■

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