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

שאלה זו עוסקת בשפת "ויירמוז" (IMPLICIT-REFS) המתוארת בספר הלימוד בעמודים 113-120. בשאלה זו, נרצה לאפשר הוספת הגנה אופציונלית למשתנים מפני ניסיון להשמת ערך או עדכון ערך קיים הגורם להפרה של ההגנה על המשתנה. למשל אם הוגדר משתנה בשם `w` והוצהרה עבורו הגנה עד כך שהוא אמור לקבל תמיד ערך מספרי, אזי אם יהיה ניסיון לתת לו ערך שאינו מספרי (הפרה של ההגנה עליו) אזי תודפס הודעת שגיאה מתאימה ותיעצר ריצת התוכנית. אם משתנה הוגדר ללא הגנה עליו כלל, אזי ניתן יהיה לשנותו לכל סוג ערך שנחפוץ, למשל אם ערכו כרגע מספרי, ניתן יהיה לשנותו להיות פרוצדורה או ערך בוליאני. להזכירכם, בשפת "ויירמוז" משתנים מוחזקים בסביבה וערכם נמצא בחסן, ומהסביבה ישנו reference למקום בחסן שם נמצא הערך של המשתנה. בשפת "ויירמוז" ישנה עבודה עם משתנים ומתן ערכים במסגרת הביטויים הבאים: - בביטוי `let` בו מגדירים משתנה ונותנים לו ערך. - בהגדרת פרוצדורה לה יש פרמטר, וכאשר מפעילים את הפרוצדורה שולחים לפרמטר ערך. - בביטוי `set-exp` בו רוצים למשתנה קיים לשנות את ערכו הנוכחי לערך אחר. לשם מתן אפשרות למתכנת להציב הגנה אופציונלית על משתנים, נשנה את התחביר של ביטוי `let-exp` ושל ביטוי `proc-exp` לפי הדקדוקים הבאים: להלן הדקדוקים החדשים המגדירים מחדש את ביטויי `let-exp` ו-`proc-exp`: ``` Expression ::= let Guard Identifier = Expression in Expression ``` ``` let-exp (grd id exp1 body) ``` ``` Expression ::= proc ( Guard Identifier ) Expression ``` ``` proc-exp (grd var body) ``` ``` Guard ::= ε | # | ? | @ ``` **הסבר התחביר:** - `Guard` `#` — המציין שהמשתנה אמור להיות תמיד מספרי במהלך ריצת התוכנית. - `Guard` `?` — המציין שהמשתנה אמור להיות תמיד ערך בוליאני לאורך ריצת התוכנית. - `Guard` `@` — המציין שהמשתנה אמור להיות תמיד מסוג פרוצדורה (כלשהי) לאורך ריצת התוכנית. - או המילה הריקה (פשוט כלום – זה מה שמייצג `ε`) ובמקרה כזה אין למשתנה כזה שום הגנה. **ביטוי `let-exp` החדש** — מאפשר להגדיר משתנה עבור ה-`let` עם אפשרות לההגנה עליו. **ביטוי `proc-exp` החדש** — מאפשר להוסיף הגנה אופציונלית על שם הפרמטר של הפרוצדורה. להלן מספר דוגמאות להמחשת העבודה עם משתנים מוגנים ולא מוגנים: **דוגמה 1:** ``` > (run "let # q = zero?(9) in q") guard-violation: expression #(struct:zero?-exp #(struct:const-exp 9)) violate let guard > ``` בדוגמה זו מוגדרת משתנה `q` עם הגנה `#` עם ערך מספרי. מאחר ומנסים להציב לו ערך בוליאני המפר את ההגנה עליו, הודפסה הודעת שגיאה מתאימה. **דוגמה 2:** ``` > (run "let @ q=proc (# w) -(w,1) in (q zero? (9))") guard-violation: argument violate procedure bound variable w guard > ``` בדוגמה זו, מוגדרת משתנה `q` עם הגנה `@` עם ערך מסוג פרוצדורה. ל-`q` אכן ניתנת פרוצדורה כערך. לפרוצדורה יש פרמטר `w` עם הגנה `#` עם ערך מספרי, בגוף ביטוי ה-`let` נעשית קריאה לפרוצדורה עם ארגומט `w` שאינו מספרי המפר את ההגנה עליו, ולכן התקבלה השגיאה. **דוגמה 3:** ``` > (run "let # w = 8 in set w = zero?(9)") guard-violation: assign expression violate variable w guard > ``` בדוגמה זו, מוגדרת משתנה `w` עם הגנה `#` עם ערך מספרי, המשתנה אכן מקבל ערך מספרי של 8. לאחר מכן, יש ניסיון לשנותו לערך בוליאני המפר את ההגנה עליו, ולכן התקבלה הודעת השגיאה. **דוגמה 4:** ``` > (run "let w = 8 in begin set w = zero?(9); if w then 1 else 2 end") (num-val 2) > ``` דוגמה זו ממחישה הגדרת משתנה `w` ללא שום הגנה, בתחילה ניתן למשתנה ערך מספרי של 8. לאחר מכן, הוצב במשתנה ערך אחר (בוליאני) — ואין כאן שום הפרה מאחר ואין שום הגנה. **ממשו והטמיעו** את השינויים הדרושים בתוך שפת "ויירמוז" (שפת IMPLICIT-REFS) לתמיכה בהתנהגות החדשה הדרושה במול משתנים. ייתכנו מספר כיוונו פתרון אפשריים. בתשובתכם, הקפידו להסביר היכן בדיוק נדרשים שינויים ותוספות במרכיבים השונים של המפרש, ומהם השינויים והתוספות. **הנחיות כלליות לפתרון:** 1. הקפידו על כתב ברור, ועל קוד מבני ומסודר. 2. הקפידו על פתיחת וסגירת סוגריים במקומות הנכונים. 3. הפתרון אמור לשמור על הגדרות השפה המקוריות (כגון אופן ניהול הסביבה וסוגי הערכים בה, אופן ניהול החסן והערכים שניתן לשמור בו, וכדומה). 4. על מנת לפשט קוד ארוך, כדאי ורצוי להיעזר בכתיבת פרוצדורות עזר (מחוץ ל-`value-of` או כאלה המוטמעות בתוכו). 5. בפתרונכם, הקפידו על אבחנה וכן שימוש נכון בין ביטוי (`expression`) לבין תוצאת חישוב ביטוי (`expval`) לבין `identifier`. 6. ניקוד יורד על אי ניתוח ומימוש נכון של הדקדוק הנתון בשאלה, כלומר יש להפקיד על זיהוי וטיפול נכון ב-terminals, non-terminals ופעולות של סגור (`)*` או `{ }+`).

רמז: יש להרחיב את `let-exp` ו-`proc-exp` כך שיכילו שדה `grd` (Guard), לאחסן את ההגנה יחד עם כתובת המשתנה בחסן (או לשמור אותה במבנה נפרד), ובכל השמה (`let`, קריאת פרוצדורה, `set-exp`) לבדוק שהערך החדש תואם לסוג ההגנה של המשתנה לפני עדכון החסן.

פתרון: **פתרון — הוספת הגנות על משתנים לשפת IMPLICIT-REFS** **שלב 1: עדכון הדקדוק** מגדירים טיפוס Guard: ```scheme (define-datatype guard guard? (num-guard) ; # (bool-guard) ; ? (proc-guard) ; @ (no-guard)) ; ε ``` מעדכנים את `expression`: ```scheme (let-exp (grd guard?) (var identifier?) (exp1 expression?) (body expression?)) (proc-exp (grd guard?) (var identifier?) (body expression?)) ``` **שלב 2: הפרסר** ```scheme ("let" (guard) (identifier) "=" (expression) "in" (expression)) => let-exp) ("proc" "(" (guard) (identifier) ")" (expression)) => proc-exp) ``` פונקציית פרסור של `guard`: ```scheme (define parse-guard (lambda () (cond ((scanner-peek-token-eq? '#) (scanner-consume!) (num-guard)) ((scanner-peek-token-eq? '?) (scanner-consume!) (bool-guard)) ((scanner-peek-token-eq? '@) (scanner-consume!) (proc-guard)) (else (no-guard))))) ``` **שלב 3: פונקציית בדיקת הגנה** ```scheme (define check-guard (lambda (grd val msg) (cases guard grd (num-guard () (if (num-val? val) (void) (error 'guard-violation msg))) (bool-guard () (if (bool-val? val) (void) (error 'guard-violation msg))) (proc-guard () (if (proc-val? val) (void) (error 'guard-violation msg))) (no-guard () (void))))) ``` **שלב 4: עדכון `value-of`** ב-`let-exp`: ```scheme (let-exp (grd var exp1 body) (let* ((val (value-of exp1 env)) (_ (check-guard grd val (string-append "expression " (expression->string exp1) " violate let guard")))) (value-of body (extend-env var (newref val) env)))) ``` ב-`proc-exp` — שומרים את ה-guard בתוך פרוצדורה: ```scheme (proc-exp (grd var body) (proc-val (procedure grd var body env))) ``` בהפעלת פרוצדורה (`apply-procedure`): ```scheme (define apply-procedure (lambda (proc1 arg) (cases proc proc1 (procedure (grd var body saved-env) (check-guard grd arg "argument violate procedure bound variable guard") (value-of body (extend-env var (newref arg) saved-env)))))) ``` ב-`assign-exp` (`set-exp`): ```scheme (assign-exp (var exp1) (let* ((val (value-of exp1 env)) (ref (apply-env env var)) (grd (get-guard-for-ref ref))) (check-guard grd val (string-append "assign expression violate variable " var " guard")) (setref! ref val) (num-val 23))) ``` **הערה:** על מנת לתמוך בבדיקת ה-guard גם ב-`set-exp`, יש לשמור את ה-guard יחד עם ה-reference, למשל בטבלת hash גלובלית מ-reference ל-guard, או להרחיב את מבנה החסן כך שכל תא כולל גם ערך וגם guard.