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

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

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

שנה: 2018

סמסטר: ב

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

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

א. (7 נקודות) לחילוץ מנתונים ה-scanner וה-parser של שפת "יוויומ". עליכם לחשוף את הטבעה של הביטוי החדש. ב. (18 נקודות) לחילוץ הפנקציודות value-of של שפת "יוויומ" כפי apply-procedure הוא חידוש הנתנים לסימונים היהתיירים החתימות החדשיות לשימוש בטביעה בסימון 79. יש לעדכן את החישוך בפנקציודות value-of. אתה השתובה כיתבו במחברת הבחינה.

רמז: המבנה החדש הוא טופס מיוחד (special form) ולא פרוצדורה. לכן, יש להוסיף תנאי חדש ב-`eval` שיטפל בו, ויצור סביבה מורחבת עבור כל איטרציה של הלולאה.

פתרון: השאלה כפי שהיא מנוסחת אינה ברורה וחסרים בה פרטים מהותיים, כגון הגדרת "הביטוי החדש" בשפת "יוויומ". על כן, הפתרון המוצג להלן מניח כי הביטוי החדש הוא מבנה לולאה, `loop`, בעל התחביר הבא: `(loop <variable> <from> <to> <body>)`. משמעות הביטוי היא ביצוע איטרטיבי של `<body>` כאשר `<variable>` רץ מהערך של `<from>` עד לערך של `<to>` (כולל). ערך הביטוי כולו הוא ערך החישוב האחרון של `<body>`. **א. Scanner ו-Parser** 1. **Scanner**: יש לעדכן את ה-scanner כך שיזהה את המילה השמורה `loop` כטוקן מסוג `KEYWORD`. אין צורך בשינויים נוספים ב-scanner. 2. **Parser**: ה-parser, אשר מקבל רצף טוקנים, צריך לזהות את התבנית של ביטוי ה-`loop`. בשפה דמוית Scheme, הביטוי יתקבל כרשימה. ה-parser יבנה ייצוג פנימי (AST - Abstract Syntax Tree) עבור הביטוי. דרך נפוצה לייצג זאת היא באמצעות **רשימה מתויגת** (tagged list). נגדיר את המבנה והסלקטורים הבאים עבור ביטוי `loop`: ```scheme (define (loop? exp) (tagged-list? exp 'loop)) (define (make-loop var from to body) (list 'loop var from to body)) (define (loop-variable exp) (cadr exp)) (define (loop-from-exp exp) (caddr exp)) (define (loop-to-exp exp) (cadddr exp)) (define (loop-body-exp exp) (car (cddddr exp))) ; מניחים גוף לולאה יחיד ``` ה-parser יזהה רשימה שמתחילה בסמל `loop`, יוודא שהיא מכילה 4 חלקים נוספים, וישתמש ב-`make-loop` כדי ליצור את הייצוג הפנימי. **ב. עדכון המפרש (`value-of`)** ביטוי ה-`loop` הוא **טופס מיוחד (special form)**, מכיוון שהחלקים שלו (`<from>`, `<to>`, `<body>`) לא מוערכים כרגיל (למשל, `<body>` מוערך מספר פעמים). לכן, הטיפול בו צריך להתווסף ישירות לפונקציה הראשית של המפרש, `value-of` (נקרא לה `eval` כמקובל), ולא ל-`apply-procedure` שמטפלת בהפעלת פרוצדורות. נוסיף תנאי חדש לפונקציה `eval`: ```scheme (define (eval exp env) (cond ((self-evaluating? exp) exp) ((variable? exp) (lookup-variable-value exp env)) ((quoted? exp) (text-of-quotation exp)) ... ((loop? exp) (eval-loop exp env)) ; סעיף חדש ... ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL" exp)))) ``` כעת נממש את פונקציית העזר `eval-loop`: ```scheme (define (eval-loop exp env) (let* ((var (loop-variable exp)) (from-exp (loop-from-exp exp)) (to-exp (loop-to-exp exp)) (body-exp (loop-body-exp exp)) (start-val (eval from-exp env)) (end-val (eval to-exp env))) ;; בדיקת טיפוסים (if (not (and (number? start-val) (number? end-val))) (error "Loop bounds must be numbers" start-val end-val) ;; פונקציית עזר איטרטיבית (let loop-iter ((i start-val) (last-val #f)) ; #f כערך ברירת מחדל (if (> i end-val) last-val (let* ((extended-env (extend-environment (list var) (list i) env)) (current-val (eval body-exp extended-env))) (loop-iter (+ i 1) current-val))))))) ``` **הסבר על `eval-loop`:** 1. הפונקציה שולפת את חלקי הביטוי: המשתנה, ביטויי הטווח, והגוף. 2. היא מעריכה את ביטויי הטווח, `from` ו-`to`, ב**סביבה הנוכחית** `env` כדי לקבל את ערכי ההתחלה והסוף. 3. היא מבצעת בדיקת טיפוסים לוודא שגבולות הלולאה הם מספרים. 4. היא משתמשת בפונקציית עזר פנימית, `loop-iter`, כדי לבצע את האיטרציות. פונקציה זו כתובה בצורת **רקורסיית זנב**, ולכן הביצוע שלה מתאר **תהליך איטרטיבי** שאינו צורך מחסנית הגדלה עם כל איטרציה. 5. בכל איטרציה, `loop-iter` מבצעת את הפעולה המרכזית: **הרחבת הסביבה**. היא יוצרת סביבה חדשה, `extended-env`, על ידי הוספת **מסגרת (frame)** חדשה לסביבה `env`. מסגרת זו קושרת את משתנה הלולאה `var` לערך הנוכחי שלו `i`. 6. גוף הלולאה `body-exp` מוערך בתוך הסביבה המורחבת הזו. זה מבטיח שלמשתנה הלולאה יהיה את הערך הנכון ושהוא לא "ידרוס" משתנים קיימים מחוץ ללולאה. 7. הלולאה ממשיכה עד שהמונה `i` עובר את ערך הסיום, ואז הערך האחרון שהתקבל מהערכת הגוף מוחזר כתוצאת ביטוי ה-`loop` כולו. $\blacksquare$

א. (7 נקודות)

לחילוץ מנתונים ה-scanner וה-parser של שפת "יוויומ". עליכם לחשוף את הטבעה של הביטוי החדש.

ב. (18 נקודות)

לחילוץ הפנקציודות value-of של שפת "יוויומ" כפי apply-procedure הוא חידוש הנתנים לסימונים היהתיירים החתימות החדשיות לשימוש בטביעה בסימון 79. יש לעדכן את החישוך בפנקציודות value-of. אתה השתובה כיתבו במחברת הבחינה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2018סמסטר ב

★★★★★

מפרשיםevalמודל הסביבהמסגרותרקורסיה זנביתתהליך איטרטיביScheme

המבנה החדש הוא טופס מיוחד (special form) ולא פרוצדורה. לכן, יש להוסיף תנאי חדש ב-eval שיטפל בו, ויצור סביבה מורחבת עבור כל איטרציה של הלולאה.

השאלה כפי שהיא מנוסחת אינה ברורה וחסרים בה פרטים מהותיים, כגון הגדרת "הביטוי החדש" בשפת "יוויומ". על כן, הפתרון המוצג להלן מניח כי הביטוי החדש הוא מבנה לולאה, loop, בעל התחביר הבא: (loop <variable> <from> <to> <body>). משמעות הביטוי היא ביצוע איטרטיבי של <body> כאשר <variable> רץ מהערך של <from> עד לערך של <to> (כולל). ערך הביטוי כולו הוא ערך החישוב האחרון של <body>.

א. Scanner ו-Parser

1. Scanner: יש לעדכן את ה-scanner כך שיזהה את המילה השמורה loop כטוקן מסוג KEYWORD. אין צורך בשינויים נוספים ב-scanner.

2. Parser: ה-parser, אשר מקבל רצף טוקנים, צריך לזהות את התבנית של ביטוי ה-loop. בשפה דמוית Scheme, הביטוי יתקבל כרשימה. ה-parser יבנה ייצוג פנימי (AST - Abstract Syntax Tree) עבור הביטוי. דרך נפוצה לייצג זאת היא באמצעות רשימה מתויגת (tagged list).
נגדיר את המבנה והסלקטורים הבאים עבור ביטוי loop:

ה-parser יזהה רשימה שמתחילה בסמל loop, יוודא שהיא מכילה 4 חלקים נוספים, וישתמש ב-make-loop כדי ליצור את הייצוג הפנימי.

ב. עדכון המפרש (`value-of`)

ביטוי ה-loop הוא טופס מיוחד (special form), מכיוון שהחלקים שלו (<from>, <to>, <body>) לא מוערכים כרגיל (למשל, <body> מוערך מספר פעמים). לכן, הטיפול בו צריך להתווסף ישירות לפונקציה הראשית של המפרש, value-of (נקרא לה eval כמקובל), ולא ל-apply-procedure שמטפלת בהפעלת פרוצדורות.

נוסיף תנאי חדש לפונקציה eval:

כעת נממש את פונקציית העזר eval-loop:

הסבר על `eval-loop`:
1. הפונקציה שולפת את חלקי הביטוי: המשתנה, ביטויי הטווח, והגוף.
2. היא מעריכה את ביטויי הטווח, from ו-to, בסביבה הנוכחית env כדי לקבל את ערכי ההתחלה והסוף.
3. היא מבצעת בדיקת טיפוסים לוודא שגבולות הלולאה הם מספרים.
4. היא משתמשת בפונקציית עזר פנימית, loop-iter, כדי לבצע את האיטרציות. פונקציה זו כתובה בצורת רקורסיית זנב, ולכן הביצוע שלה מתאר תהליך איטרטיבי שאינו צורך מחסנית הגדלה עם כל איטרציה.
5. בכל איטרציה, loop-iter מבצעת את הפעולה המרכזית: הרחבת הסביבה. היא יוצרת סביבה חדשה, extended-env, על ידי הוספת מסגרת (frame) חדשה לסביבה env. מסגרת זו קושרת את משתנה הלולאה var לערך הנוכחי שלו i.
6. גוף הלולאה body-exp מוערך בתוך הסביבה המורחבת הזו. זה מבטיח שלמשתנה הלולאה יהיה את הערך הנכון ושהוא לא "ידרוס" משתנים קיימים מחוץ ללולאה.
7. הלולאה ממשיכה עד שהמונה i עובר את ערך הסיום, ואז הערך האחרון שהתקבל מהערכת הגוף מוחזר כתוצאת ביטוי ה-loop כולו.

■

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