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

שאלה זו עוסקת בשפת IMPLICIT-REFS המתוארת בספר הלימוד בעמודים 113–120. ברצוננו להרחיב את שפה זו בהגדרת מצביע רב-מימדי, וגישה באמצעות הגדרתם. להלן הרקורסיה המגדירה את הביטויים החדשים שיש להוסיף לשפה: **ביטוי `multiptr-exp`:** ``` Expression ::= {&}+ (Expression) multiptr-exp (ptrs data) ``` **ביטוי `multistar-exp`:** ``` Expression ::= {*}+ (Expression) multistar-exp (stars v) ``` **ביטוי `assign-exp` המורחב:** ``` Expression ::= option Identifier = Expression assign-exp (opt id newval) Option ::= ε | @ ``` **הסבר על הביטויים ותפקידם:** לביטוי `assign-exp` המוחדש יש option של `@` או שאינו מופיע (ריקה ε). כאשר ה-option הוא ריקה (ε), ביטוי זה assign-exp כותב ישירות לתא הזיכרון של identifier, כמו set רגיל. כאשר ה-option הוא `@`, ה-identifier חייב להיות שם של משתנה רב-מימדי, ובמקרה זה ביטוי assign-exp יעדכן את הנחון (הערך) שאליו מצביע identifier לפי ערכו של ביטוי newval. ביטוי `multiptr-exp` מאפשר להגדיר מצביע רב-מימדי (מצביע למצביע) על ידי שימוש ב-`&`. הביטוי ptrs הוא רשימת סמני `&` המגדירים את עומק המצביע. הרכיב data הוא ביטוי המייצג את הערך הבסיסי שאליו מצביע המצביע. ביטוי `multistar-exp` הוא ביטוי הפניה (dereference) על מצביע רב-מימדי. ניתן להשתמש בו רק על ביטוי מסוג multiptr-exp; כל ניסיון אחר יגרור שגיאה. להלן מספר דוגמות שימוש: **דוגמה 1:** ```scheme let p = &&&(6) in let q= **(p) in let num = *(q) in -(num, 2) ``` בדוגמה זו p הוא מצביע תלת-מימדי (הלומר, מצביע למצביע למצביע ל-6). המצביע q הוא מצביע חד-מימדי לעבר 6. ולכן num הוא 6 ולכן הביטוי הוא (num-val 4). **דוגמה 2:** ```scheme let p = &&&(6) in let q= **(p) in let num = ****(q) in -(num, 2) ``` בדוגמה זו q מצביע חד-מימדי לעבר 6. ה-let השלישי מנסה לבצע 4 רמות dereference על q אך q הוא רק מצביע חד-מימדי (לא קיימים 4 מצביעים עליו) ולכן אמורה להתקבל שגיאה מתאימה. **דוגמה 3:** ```scheme let p = **(&&&&(6)) in -(*(p), 5) ``` בדוגמה זו p הוא מצביע דו-מימדי על החנות. בגוף ה-let מבצעים פניה עם כניסה אחת עליו מה שמחזיר 6, ולכן ערכו של כל הביטוי הוא (num-val 1). **דוגמה 4:** ```scheme let p = *(zero?(6)) in 9 ``` בדוגמה זו יש ניסיון להפעיל ביטוי star-exp על ביטוי מסוג zero?-exp שאינו מסוג מצביע רב-מימדי ולכן אמורה להתקבל שגיאה מוגדרת. **דוגמה 5:** ```scheme let p = &&&(proc (x) -(x,7)) in (***( p) 9) ``` בדוגמה זו p הוא מצביע תלת-מימדי לפרוצדורה. בגוף ה-let יש פניה אל הפרוצדורה והפעלתה על 9 ולכן התוצאה הינה (num-val 2). **דוגמה 6:** ```scheme let p = &&&(proc (x) -(x,7)) in *(p) ``` בדוגמה זו p הוא מצביע תלת-מימדי לפרוצדורה. בגוף ה-let התוצאה היא מצביע דו-מימדי לפרוצדורה, ולכן ה-expval אמורה להחזיר מצביע רב-מימדי. **דוגמה 7:** ```scheme let p = &&&(proc (x) -(x,7)) in begin set @p = 9; -(***( p) , 2) end ``` בדוגמה זו p הוא מצביע תלת-מימדי לפרוצדורה. בגוף ה-let, `set @p = 9` מעדכן את הנחון שאליו מצביע p להיות 9 במקום הפרוצדורה, ולבסוף מבצעים dereference מלא על p ומחזירים 9-2 ולכן הוא (num-val 7). **דוגמה 8:** ```scheme let p = &&&&(8) in let q= **(p) in begin set @q = 20; -(****(p) , 3) end ``` בדוגמה זו, p הוא מצביע 4-מימדי על 8, q הוא מצביע דו-מימדי המצביע על אותו שרשרת מצביעים כמו p. בגוף ה-begin, `set @q = 20` משנה את הערך שאליו מצביע q (רמה אחת מתחתיו), כלומר מעדכן את תא הזיכרון הבסיסי ל-20. לכן כעת `****(p)` עובר 4 רמות ומגיע לאותו תא בסיסי שכעת מכיל 20, ולכן הניב הוא (num-val 17). **דוגמה 9:** ```scheme let p = &&&&(8) in let q= **(p) in begin set @p = 20; set p = 5; -(** (q) , p) end ``` בדוגמה זו, p הוא מצביע 4-מימדי לאחסון 8, q הוא מצביע דו-מימדי המשתף שרשרת עם p. `set @p = 20` מעדכן את הנחון שאליו מצביע p (רמה אחת מתחתיו) ל-20, כך שגם q (שמצביע לאותה רמה) רואה כעת את הערך 20 בסוף שרשרתו. לאחר מכן `set p = 5` משווה את p עצמו ל-5 (מספר). כעת `**(q)` מבצע dereference דו-מימדי דרך q ומגיע ל-20; ו-p הוא 5. לכן הניב הוא -(20, 5) = (num-val 15). עליך לממש את השינויים הדרושים בתוך שפת IMPLICIT-REFS (שפת **ייחסמוריות**) בתוך קבצי המפרש, הקפד להסביר בקצרה בקבצי המפרש, **ולציין** את השורות הדרושות והמתחנות. **הוראות לחלקים הנלמדים:** 1. הקפד על כתב ברור, ועל קוד מובן ומסודר. 2. הקפד על פתיחות וסגירות במקומות המתאימות. 3. התוצר אמור לשמור על הגדרת השפה הנדרשת שיוגדר לזה במפרש בשאלה. 4. על מנת לפשט קוד ארוך, כדאי להיעזר בפונקציות עזר (מחוץ value-of). 5. בפרט, הקפד על הבחנה ושימוש מכון בין ביטוי (expression) לבין תוצאת חישוב ביטוי (expval) לבין identifier. 6. ניקוד יורד על אי הבחנה ומימוש מכון של הרקורסיה הנחונה בשאלה, כלומר יש להקפיד על הכון ב-terminals, non-terminals הפעולות של פסיקור ( )* או { }+.

רמז: הוסיפו שלושה datatypes: `multiptr-exp` (יוצר שרשרת ref של n רמות), `multistar-exp` (פורם שרשרת ref n פעמים), ו-`assign-exp` מורחב עם option @ (שמבצע dereference לפני הכתיבה). ב-`multiptr-exp`, צרו n תאי זיכרון מקוננים בלולאה.

פתרון: **פתרון שאלה 2 — מימוש מצביעים רב-מימדיים ב-IMPLICIT-REFS** **1. הגדרת datatypes:** ```scheme ; ב-define-datatype expression: (multiptr-exp (ptrs (list-of symbol?)) ; רשימת & (כגון '(& & &)) (data expression?)) (multistar-exp (stars (list-of symbol?)) ; רשימת * (כגון '(* * *)) (v expression?)) (assign-exp (opt (maybe symbol?)) ; ε = #f, @ = '@ (id symbol?) (newval expression?)) ``` **2. הוספה ל-parser:** ```scheme ; multiptr-exp: &&&( expr ) ((arbno "&") "(" expression ")") => (lambda (ptrs data) (multiptr-exp ptrs data)) ; multistar-exp: ***( expr ) ((arbno "*") "(" expression ")") => (lambda (stars v) (multistar-exp stars v)) ; assign-exp: [@ | ε] id = expr ((maybe "@") identifier "=" expression) => (lambda (opt id newval) (assign-exp opt id newval)) ``` **3. ביצוע ב-`value-of`:** ```scheme ; multiptr-exp: יוצר שרשרת של refs (multiptr-exp (ptrs data) (let ((base (value-of data env))) (let loop ((n (length ptrs)) (v base)) (if (= n 0) v (let ((ref (newref! v))) (loop (- n 1) (ref-val ref))))))) ; multistar-exp: פורם שרשרת של refs, מחזיר ערך בסוף (multistar-exp (stars v) (let ((base (value-of v env))) (let loop ((n (length stars)) (cur base)) (if (= n 0) cur (cases expval cur (ref-val (ref) (loop (- n 1) (deref ref))) (else (error 'multistar-exp "expected ref-val, got ~a" cur))))))) ; assign-exp: (assign-exp (opt id newval) (let ((new-v (value-of newval env))) (if (eq? opt '@) ; @ — עדכן את הנחון שאליו מצביע id (dereference assignment) (let ((cur-val (deref (apply-env env id)))) (cases expval cur-val (ref-val (inner-ref) (setref! inner-ref new-v) (num-val 23)) (else (error 'assign-exp "@ requires a multi-level pointer")))) ; ε — עדכן את תא הזיכרון של id בסביבה (כמו set רגיל) (begin (setref! (apply-env env id) new-v) (num-val 23))))) ``` **הסבר:** `multiptr-exp` יוצר שרשרת של n תאי זיכרון: data נשמר בתא הפנימי ביותר, כל תא נשמר בתא חיצוני יותר, וכן הלאה — כך שהתוצאה הסופית היא ref-val המצביע לשרשרת. `multistar-exp` פורם את השרשרת בדיוק n רמות. `assign-exp` עם `@` מעדכן את הערך שאליו מצביע הזיהוי (רמה אחת מתחת), ובלי `@` מעדכן את תא הזיכרון של הזיהוי עצמו. $\blacksquare$