Expression Evaluation

כדי להבין כיצד עובד האבלואציה של ביטויים בOCaml. לאחר מכן נבין כיצד נכנסים closures לתמונה הזאת בשביל לאפשר תכונות מסוימות.

נסתכל על קטע הקוד הפשוט הבא

let x = 1 in 
	if true then 2 else x

אנחנו יודעים שהמנגנון של פירוש הסמנטיקה של OCaml הוא מבוסס על substitutions כלומר הinterpreter יראה את קטע הקוד הבא ויבצע החלפה של כל המקומות שבהם מופיע x בתוך קטע הקוד בערך שלו 1 ונקבל if true then 2 else 1. המנגנון הזה טוב אבל הוא לא מושלם, שכן היינו יכולים לדעת מניתוח קוד בצורה אחרת ש if true תמיד מתקיים ופשוט להחזיר 2 על כל הביטוי. בדוגמה הזאת זה נראה משהו זניח, אבל אם זה היה קורה בתוך קוד שיש לו לולאה מאוד ארוכה המנגנון הזה היה יכול לעזור מאוד מבחינת יעילות.

נרצה לממש אינטרפטציה עצלה בדומה לשפת while. כלומר מבוססת מצבים.

סביבה:
היא רשימה מהצורה $(x_1,v_1)\dots (x_n,v_n)$ כך שכל $x_i$ הוא משתנה ו $v_i$ הוא ערך. כמו כן, $(x_1,v_1)$ הוא ראש הרשימה . ראש הרשימה מסומן ב $E(x)$.

הגדים:
יחס ה evaluation מסומן כך $E⊢e\to v$ ומוגדר לפי כללי ההיסק שמיד נגדיר.

נסמן- $(x:v):E$ היא הסביבה המתקבלת מ E על ידי השמת v ל x.

כללי היסק

1. const - ${\displaystyle \frac{}{E⊢v\to v}}$
2. var - ${\displaystyle \frac{E(x)=v}{E⊢x\to v}}$
3. let- ${\displaystyle \frac{E⊢e_1\to v_1(x:v_1):E⊢e_2\to v}{E⊢\text{let x = e1 in e2}\to v}}$

דוגמה:
נראה ש let x = 3 in x $\to$ 3 .

איך לוקחים את הנ״ל לעולם של פונקציות.

כדי לעשות זאת ננסה להוסיף כלל חדש של application

במילים, כדי שההפעלה של $e_1$ על $e_2$ תתן את v צריך ש $e_1$ יהיה פונקציה שמקבל קלט x ומבצעת את הביטוי e. כמו כן צריך ש $e_2$ הקלט לפונקציה יהיה הערך $v_2$ ולבסוף צריך שאם x ממופה ל $v_2$ אז זה יגרום ש $e$ ימופה לv.

נשמע הגיוני, אבל נראה ש הכלל הזה לא עובד באמצעות הניסיון שלנו לבצע את הevaluation על הביטוי הבא

קל לראות שיש כאן בעיה של scopes. שכן איזה x חוזר מהפונקציה f, החיצוני או הפנימי? אם נריץ את הקוד הזה בOCaml נקבל שהפלט לדבר הזה הוא 1.

כעת ננתח לפי הכלל החדש APP שהגדרנו , אנחנו נראה שבסביבה הריקה הביטוי הנ״ל (נסמנו e) יוערך ל 2. לשם הנוחות נסמן את הביטוי שאחרי ה in הראשון כ $e^{\prime }$ .

כמעט סיימנו, הגענו ל $E^{″}⊢f0\to 2$ כאשר- $E^{″}=(x:2)::E^{\prime }=(x:2)::(f:\text{ fun y}\to x)::E$ נראה מה קורה כשנרצה להראות שההפעלה של f על 0 תיתן 2 באמצעות כללי app

ניתן לראות שבסוף קיבלנו ש x נגזר ל2 בגלל הכלל VAR כיוון ש $E^{\prime }$ מכיל את הכלל (x:2) שנכנס אחרי (x:1).

מה הבעיה בכלל הזה?
ההבדל העיקרי הוא ש OCaml עובד לפי static scoping כלומר ההפנייה למשתנה היא תמיד ה top level scope ובהגדרה שלנו השתמשנו ב dynamic scoping כלומר לוקחים את הערך העדכני ביותר מהסביבה (E(x)).

נגדיר את זה-
סקופ דינמי : הערכים של המשתנים בגוף של הפונקציה מקושר לפי הסביבה שבה היא רצה
סקופ סטטי : הערכים של המשתנים בגוף של הפונקציה מקושר לפי הסביבה שבה היא הוגדרה.

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

סגור- closure

כאן נכנס הclosure לתמונה. נגדיר אותו כזוג סדור מהצורה <env,exp> כך ש

• env - הסביבה
• exp- ביטוי מהצורה $\text{ fun x}\to \text{ e}$ .

כעת נוכל לנסח את הכלל APP מחדש

אז כעת השוני העיקרי הוא שאנחנו עובדים עם $E^{\prime }$ הסביבה שבה הפונקציה הוגדרה ולא עם הסביבה E.

כדי לוודא שניתן לגזור פונקציה רק בסביבה שבה היא הוגדרה נשתמש בכלל FUN :

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

אם נחזור כעת, לדוגמה שלנו נוכל להראות ש e ממופה ל1 כמו ב OCaml

closures ו recursion

נזכיר שהsyntax של פונקציה רקורסיבית הוא מהצורה

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

כלל ההיסק של let rec יהיה

בעצם אומרים שהביטוי התחתון בסביבה E ימופה ל v אם $e_2$ ימופה ל v בסביבה $E^{\prime }$. כאשר
$E^{\prime }=(f:<E^{\prime },\text{fun x}\to e_1>)::E$ . גם כאן יש הגדרה רקורסיבית מוזרה אבל נראה למה זה עובד בהמשך.

ניקח את הדוגמה הבאה

נסמן את הביטוי עד ה in ב e. כמו כן נגדיר את שתי הסביבות הבאות

אם כן נתחיל לפתח את כללי הגזירה כמה שאפשר עם הנתונים שיש ברשותנו

כדי לפתוח את הכלל המסומן באדום, נצטרך להגדיר מספר כללים נוספים שכן e הוא ביטוי מהצורה if else. כמו כן יש לנו בפנים ביטויים אריתמטיים.

כעת עם הכללים האלה נוכל להמשיך לפתח את הגזירה

כעת נפתח גם הביטוי המסומן

ונפתח את הביטוי האחרון (באדום)

וסיימנו.

כדי לסכם:

1. ראינו שכדי לבצע evaluation של ביטויים באוקמל חייבים להשתמש בסביבה.
2. כדי שהסקופ יהיה סטטי צריך להשתמש ב closure.
3. בשפות אחרות closure יכול להיות מוגדר אחרת למשל ב java הוא אובייקט עם הרבה שדות ומתודה אחת אבל הרעיון הוא אותו רעיון.

OCaml Scopes

כדי לחשב את let x = e1 in e2 בסביבה כלשהי env
1) Evaluate - נחשב את $e_1$ לערך $v_1$ בסביבה env , $env::e_1\to v$ .
2) Extend - הרחבה של הסביבה כך שהיא מכילה את ההצמדה של המשתנה $x$ ל $v_1$ . $en{v}^{\prime }=env[x\mapsto v_1]$ .
3) Evaluate - נחשב שוב פעם , את $e_2$ לערך $v_2$ תחת הסביבה $en{v}^{\prime }$
4) מחזירים את $v_2$

נדגים על הביטוי let f= fun x -> x in f 0.
הסביבה היא $en{v}_0=[]$ .

1. הביטוי fun x -> x הוא כבר ערך , הפונקציה עצמה.
2. נגדיר $en{v}_1=en{v}_0[f\mapsto funx\to x]=[f\mapsto funx\to x]$
3. נחשב את הביטוי הפנימי f 0 תחת $en{v}_1$.
   1. נחליף את f להיות הפונקציה ואת 0 ל 0
   2. $en{v}_2=en{v}_1[x\mapsto 0]$
   3. תחת הסביבה הזאת קל לחשב ש $x\Rightarrow 0$.

בעצם יצרנו ״סביבת עבודה״ או closure שבה התוצאה x ממופה לערך מסויים. נדגים על קוד קצת יותר מורכב כדי להבין מה הכוונה.

let x = 1 in
	let f = fun y -> x in 
		let x = 2 in
			f 0

הפונקציה הזאת באוקמל מחזירה 1 (בגלל הסקופ הסטטי שדיברנו עליו, כלומר הערך של x בזמן הגדרת הפונקציה הוא הקובע)

אם ניקח את קוד c השקול נקבל

{
	int x = 1
	{
		int f(int y)
		{
			return x;
		}
		{
			int x = 2;
			printf("%d", f(0));
		}
	}
}

בקוד הזה, יוחזר 2 כי הscope הוא דינמי ומה שחשוב זה מה הערך של x בזמן הקריאה לפונקציה.

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

דוגמה 1

let x = 1 in
	let f = fun y -> x in
		let x = 2 in
			let z = f 0 in z

שורה 2 יוצרת את הclosure : $<(x:1)::[],\text{fun y}\to \text{x}>$ ולכן בזמן יצירת הפונקציה זאת הסביבה שלנו.
בשורה 4 קוראים ל closure עם הארגומנט 0 אבל הראנו בכללי הגזירה שמסתכלים על הסביבה שבה הפונקציה הוגדרה ולכן z=1.

דוגמה 2

let x = 1 in
	let f y = x + y in
		let x = 3 in
			let y = 4 in
			 let z = f(x+y) in z 

בשורה 2 יצרנו closure של $<\text{ f y}\to x,[x\mapsto 1]>$ ולכן הסביבה שלנו היא $(x:1)$. בשורה 5 קוראים ל closure של שורה 2 כאשר הסביבה היא $[x\mapsto 3,y\mapsto 4]$ ולכן הארגומנט שנשלח הוא ביחס לסביבה הזאת כלומר 7. בגלל שההפעלה של הפונקציה תלויה בסביבה שבה הפונקציה הוגדרה נקבל ש z=7+1=8 .

בסקופ דינמי- היינו מחשבים את z לפי הערך של x כאשר הפונקציה נקראה ולכן היינו מקבלים $3+7=10$