שאלה 1) 30 נקודות)
בשפת "וישגור" פרוצדורות מחושבות על פי כריכה לקסיקלית. דרך אחרת לחשב פרוצדורות היא
ע"י כריכה דינמית (binding Dynamic .(בכריכה דינמית, גוף הפרוצדורה מחושב באמצעות
הרחבת הסביבה ממנה מתבצעת הקריאה לפרוצדורה. בניגוד לכריכה לקסיקלית שבה גוף
הפרוצדורה מחושב על פי הסביבה בה מוגדרת הפרוצדורה.
נסתכל למשל על התוכנית הבאה בשפת "וישגור" :
let a=3
in let p = proc (x) -(x,a)
a=5
in –(a, (p 2))
בכריכה דינמית, המשתנה a המופיע בגוף הפרוצדורה כרוך לערך 5 ולא לערך 3.
שימו לב, בדוגמא זו שולבה גם יכולת להגדיר מספר ביטויים בתוך ביטוי let.
א) שנו את שפת "וישגור" כך שפרוצדורות יחושבו רק בכריכה דינמית. לשם כך השתמשו
במימוש שבו פרוצדורות מיוצגות ע"י מבנה נתונים.
ב) כזכור שפת "וישגור" מאפשרת כתיבת פרוצדורות שאינן רקורסיביות. בסעיף א' שפת
פרוצדורות רקורסיבי/ות. הסבירו מדוע? "וישגור" שונתה, ופרוצדורות מחושבות בכריכה דינמית, יכולת זו מאפשרת כעת לכתוב
ג) כיתבו באמצעות הפתרון של סעיף א', פרוצדורה רקורסיבית המקבלת פרמטר n
ומחזירה את האיבר ה-n-י בסדרת פיבונצ'י.
13
שאלה 2) 35 נקודות)
א) בשפת "וישגור" (שפת PROC (הוגדר שלפרוצדורה יש רק ארגומנט יחיד. אך ניתן לעקוף
מגבלה זו ולכתוב פרוצדורה עם מספר ארגומנטים ע"י שימוש בפרוצדורות שמחזירות בעצמן
פרוצדורות.
נסתכל למשל על התוכנית הבאה בשפת "וישגור" :
let f = proc (x) proc (y) …
in ((f 3) 4)
טכניקה זו נקראת Currying וכבר נתקלנו בה במסגרת השיעור הראשון בקורס.
כתבו בשפת "וישגור" באמצעות שימוש בטכניקה זו, פרוצדורה בעלת 2 ארגומנטים מסוג
מספר המחזירה תשובה בוליאנית (כמובן בצורת val-exp (של true כאשר אחד המספרים
הוא פי-2 מהשני. אחרת יוחזר false .
למשל, עבור המספרים 6 ו- 3 יוחזר true .
יש לפתור רק על ידי שימוש בדקדוק הקיים של שפת PROC) לא ניתן להרחיב את השפה
במרכיבים חדשים)
ב) להלן תוכנית בשפת "וישגור".
let makemult = proc (maker)
proc (x)
if zero? (x)
then 0
else -(((maker maker) -(x,1)) , -4)
in let times4 = proc (x) ((makemult makemult) x)
in (times4 3)
מהו הערך של תוכנית זו?
ג) כתבו בשפת "וישגור" פרוצדורה בשם f המקבלת פרמטר n ומחזירה את !n.
על ידי שימוש באופן החישוב הבא:
f(0)=1
f(n) = n*f(n-1)
לשם כך השתמשו בטכניקה מסעיף ב', וכן ב- Currying .