שפות תכנות: הסיכום המלא
כאן תוכלו לקרוא את ארבעת החלקים של הסיכום ברצף למידה אחד, ללא צורך במעבר בין קבצים שונים. הניווט הצדדי מסייע לדפדף במהירות, והוא יעקוב אחריכם אוטומטית לפי מיקומכם בדף.
למה Scheme? ותחביר בסיסי
לפני שמתחילים לבנות מפרשים, עלינו להבין היטב את שפת הקורס שבה הקורס מועבר. שפת התכנות עצמה היא Scheme (שפה מינימליסטית ועוצמתית ממשפחת LISP). לעומת זאת, DrRacket איננה שפה ואיננה הרחבה - היא פשוט סביבת הפיתוח (IDE) שבה אנו משתמשים כדי לכתוב ולהריץ את קוד ה-Scheme שלנו. הבחירה בשפה ממשפחת LISP אינה מקרית: הארכיטקטורה שלה מתאימה באופן מושלם לעיבוד קוד של שפות אחרות.
הפילוסופיה: הכל הוא ביטוי (Everything is an Expression)
בשפות כמו Java או C, יש הבדל ברור בין פקודה
(Statement) שלא מחזירה כלום (כמו if (x>0) {y=1;}), לבין ביטוי
(Expression) שמחזיר ערך (כמו x + 1).
ב-Scheme ההפרדה הזו אינה קיימת! הכל מחזיר ערך. אין דבר כזה
שורת קוד שלא מחושבת למשהו. אם כתבת if, הוא חייב להחזיר ערך. זהו עיקרון קריטי בעולם
השפות הפונקציונליות וזה מה שמאפשר לפונקציית ה-value-of שלנו להחזיר תמיד
expval.
תחביר תחילי מבוסס סוגריים (Prefix Notation)
ב-Scheme, פקודה תמיד נפתחת בסוגריים עגולים. המילה הראשונה מיד לאחר הסוגר השמאלי היא הפונקציה או האופרטור, ושאר המילים המופרדות ברווחים הם הארגומנטים. אין משמעות לרווחים נוספים או שורות חדשות.
; בשפות רגילות: 1 + 2
; ב-Scheme: "הפעל את הפונקציה + על 1 ו-2"
(+ 1 2) ; מחזיר 3
; פעולות מורכבות מקוננות - מחשבים מבפנים החוצה:
; מתמטיקה רגילה: (5 * 2) - (8 / 4)
(- (* 5 2) (/ 8 4)) ; מחזיר 8
; גם קריאה לפונקציה מוגדרת-משתמש (למשל my-func) נראית זהה:
(my-func arg1 arg2)למה התחביר הזה מושלם למפרשים? מכיוון שהוא מונע דו-משמעות (Ambiguity). המחשב אף פעם לא צריך לתהות לגבי סדר פעולות חשבון (קדימות אופרטורים). הקוד עצמו כבר כתוב בצורה של עץ (AST)!
משתנים ופונקציות: define, let, letrec
שמירת מידע בזיכרון היא פעולה בסיסית. Racket מציעה מספר דרכים לקשור (Bind) ערכים למשתנים, בהתאם לטווח ההכרה (Scope) הנדרש.
הגדרות גלובליות:
define
משמש להגדרת משתנים שיהיו מוכרים בכל הקובץ. במקביל, המילה
lambda מייצרת פונקציה אנונימית. שילוב של שניהם מייצר פונקציה רגילה.
; הגדרת קבוע גלובלי
(define pi 3.14159)
; פונקציה אנונימית המקבלת x ומחזירה x+1
(lambda (x) (+ x 1))
; קשירת הפונקציה האנונימית לשם
(define add-one
(lambda (x)
(+ x 1)))
; הפעלת הפונקציה
(add-one 5) ; -> 6משתנים מקומיים: let
יוצר משתנים שחיים רק בתוך הבלוק הספציפי. חשוב: המשתנים המוגדרים ב-let אינם מכירים זה את זה בזמן ההגדרה, ולא יכולים לקרוא לעצמם.
; מבנה: (let ((var1 val1) (var2 val2)) body)
(define calc-area
(lambda (width)
(let ((length 10)
(height 5))
; רק כאן length ו-height מוכרים
(* width length height))))
(calc-area 2) ; -> 100הבעיה עם פונקציות מקומיות: הכירו את
letrec
מה קורה אם אנחנו רוצים לכתוב פונקציה רקורסיבית (למשל עצרת -
Factorial) כמשתנה מקומי בתוך פונקציה אחרת? אם נשתמש ב-let,
הפונקציה לא תכיר את השם של עצמה כשתנסה לקרוא לעצמה!
לשם כך נועד ה-letrec (Let Recursive). הוא פועל בדיוק כמו
let, אך הוא "מכריז" על כל השמות מראש, כך שהמשתנים יכולים לפנות לעצמם ולמשתנים האחרים המוגדרים
לצידם. אנו נשתמש בו המון כדי לכתוב פונקציות loop מקומיות לטיפול ברשימות במבחנים.
; דוגמה קלאסית: לולאה רקורסיבית מקומית (מופיעה כמעט בכל פתרון מבחן)
(define count-down
(lambda (start)
(letrec ((loop
(lambda (n)
(if (= n 0)
"Done!"
; בזכות letrec, ה-loop מכיר את עצמו!
(loop (- n 1))))))
(loop start)))) ; התנעה ראשונית של הלולאהזרימת בקרה: if ו-cond
ב-Scheme לוגיקה תנאית חייבת להיות ביטוי שמחזיר ערך. נסקור את שני המבנים העיקריים לשליטה בזרימת התוכנית: התנאי הבסיסי, ותנאי מרובה אפשרויות שיהיה "סוס העבודה" שלנו במפרש.
התנאי הבסיסי: if
מבנה ה-if ב-Scheme הוא פשוט וקשיח: הוא חייב לכלול תנאי, ביטוי לאמת, וביטוי לשקר. אי אפשר לכתוב if ללא else!
(if condition-expr true-expr false-expr)
(define get-absolute-value
(lambda (n)
(if (< n 0)
(* n -1) ; מבוצע אם אמת
n))) ; מבוצע אם שקר (else)
; שים לב: הערכים הבוליאניים בסקים הם #t (אמת) ו-#f (שקר)
(if #t "Yes" "No") ; -> "Yes"תנאים מרובים: cond
כאשר יש לנו סדרה של תנאים (כמו if-else-if-else בשפות אחרות או
switch-case), נשתמש במבנה cond. המפרש שלנו ישתמש ב-cond המון (למשל בפונקציות
החיפוש).
(define analyze-number
(lambda (n)
(cond
; [תנאי] [מה להחזיר אם התנאי מתקיים]
((> n 0) "Positive")
((< n 0) "Negative")
((= n 0) "Zero")
; בלוק else אופציונלי שיתפוס כל מקרה אחר
(else "Not a number"))))💡 טריק למבחן: ביצוע מספר פעולות עם
begin
אמרנו ש-if מקבל רק ביטוי אחד במקרה של אמת וביטוי אחד לשקר. מה עושים אם רוצים לבצע מספר פעולות (למשל: גם לשנות ערך בזיכרון וגם להחזיר מספר)?
כאן נכנסת המילה begin. היא לוקחת רשימה של פקודות, מריצה אותן
אחת אחרי השנייה, ומחזירה רק את התוצאה של הפקודה האחרונה. זהו כלי חובה כשעובדים
עם השמות (Store) במבחן!
(if (> x 0)
(begin
(setref! my-ref 10) ; פעולה 1 (תופעת לוואי)
(num-val 27)) ; פעולה 2 (הערך שיוחזר מה-if כולו)
(num-val 0))רשימות מקושרות (Lists) ורקורסיה
המבנה הנתונים השולט בשפת LISP (List Processing) הוא כמובן הרשימה. כשתקבלו שאלת מבחן שמבקשת ליישם Tuple, Array, או מבנה Foreach - אתם תעבדו עם רשימות. הבנת האופרטורים של הרשימה והתבנית הרקורסיבית היא קריטית.
האטום של הרשימה: ה-cons
אין באמת "מערכים" רציפים ב-Scheme. כל רשימה מורכבת משרשור של זוגות (Cons cells). תארו לעצמכם קופסה עם שני תאים. התא הראשון נקרא car ומחזיק את הערך. התא השני נקרא cdr ומחזיק חץ (מצביע) לקופסה הבאה.
- cons - הפונקציה שיוצרת את הזוג (הקופסה).
- car - שולף את האיבר ה"נוכחי" מהקופסה.
- cdr (מבוטא "קוּ-דֶר") - שולף את שארית הרשימה.
- '() או null - מסמל את סוף השרשרת.
דוגמאות לשימוש (הבנה מעשית)
; הרכבת רשימה בעזרת cons
(define my-list (cons 1 (cons 2 (cons 3 '()))))
; הדרך המקוצרת והשקולה לחלוטין:
(define my-list (list 1 2 3))
; חילוץ איברים:
(car my-list) ; -> 1
(cdr my-list) ; -> '(2 3) (רשימה שמכילה את 2 ו-3)
; איך נוציא את האיבר השני? נעשה cdr כדי לזרוק את הראשון,
; ואז car כדי להוציא את מה שנשאר בהתחלה.
(car (cdr my-list)) ; -> 2
; Scheme מספקת קיצור דרך לנוחות:
(cadr my-list) ; -> 2
; בדיקות עצירה
(null? my-list) ; -> #f
(null? '()) ; -> #tהתבנית הקדושה: רקורסיה על רשימה (List Traversal)
מכיוון שאין ב-Scheme לולאות for או while
(שפת Lisp בסיסית היא ללא state), הדרך היחידה לעבור על רשימה היא באמצעות פונקציה רקורסיבית.
התבנית הזו מופיעה כמעט בכל פתרון של שאלת מבחן מורכבת! התבנית מורכבת תמיד מ-2
שלבים: מה עושים כשהרשימה ריקה, ומה עושים כשיש בה איברים.
; דוגמה: פונקציה המקבלת רשימת מספרים ומחזירה רשימה שבה הכל הוכפל ב-2
(define double-list
(lambda (lst)
; 1. תנאי העצירה: אם הרשימה ריקה, נחזיר רשימה ריקה כדי לסיים את השרשרת.
(if (null? lst)
'()
; 2. הלוגיקה: ניקח את האיבר הראשון (car lst), נכפיל אותו,
; ונחבר אותו (בעזרת cons) לתוצאת הפעלה הרקורסיבית על שאר הרשימה (cdr lst).
(cons (* (car lst) 2)
(double-list (cdr lst))))))
(double-list (list 1 2 3)) ; -> '(2 4 6)שימו לב ל-map: הפעולה של "לעבור על רשימה ולהפעיל
פונקציה על כל איבר" היא כה נפוצה, שקיימת פונקציה מובנית שעושה זאת בשם map. למשל,
במבחן כשיש לכם tuple-exp(exps) עם רשימת ביטויים שצריך להעריך את כולם בסביבה, אפשר
פשוט לכתוב: (map (lambda (e) (value-of e env)) exps)
פונקציות מתקדמות: map, filter, foldr
כדי לשלוט ב-Scheme ולפתור מטלות כמו ממ"ן 11, עלינו להכיר פונקציות מסדר גבוה (Higher-Order Functions). אלו פונקציות שמקבלות פונקציה אחרת כפרמטר, ומאפשרות לנו לבצע פעולות מורכבות על רשימות בשורת קוד אחת, ללא צורך בכתיבת רקורסיה מפורשת.
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? כדי לפתור את הבעיה של כתיבת רקורסיות מייגעות שוב ושוב עבור פעולות דומות, וכדי לייצר הפשטה (Abstraction) לעיבוד רשימות.
- מה לומדים מזה? אנו לומדים כיצד פונקציה יכולה לקבל פונקציה אחרת כארגומנט, וכיצד פעולת "הקיפול" (Fold) מהווה תשתית מתמטית שעליה ניתן לבסס כמעט כל מניפולציה של רשימה.
הפונקציה map
עוברת על כל איבר ברשימה, מפעילה עליו פונקציה, ומחזירה רשימה חדשה של התוצאות. (שומרת על גודל הרשימה המקורית).
; הכפלת כל האיברים פי 2
(map (lambda (x) (* x 2)) '(1 2 3))
; מחזיר: '(2 4 6)הפונקציה filter (הכנה לממ"ן)
מקבלת פרדיקט (פונקציה שמחזירה אמת/שקר) ורשימה, ומחזירה רק את האיברים שעבורם הפרדיקט החזיר אמת.
שימוש ב-Filter המובנית:
; סינון זוגיים בלבד
(filter even? '(1 2 3 4 5 6))
; מחזיר: '(2 4 6)מימוש רקורסיבי מאפס (שאלה 2א בממ"ן):
(define my-filter
(lambda (pred lst)
(cond
((null? lst) '()) ; תנאי העצירה: רשימה ריקה
; אם האיבר הראשון מקיים את התנאי, נשמור אותו ב-cons
((pred (car lst))
(cons (car lst) (my-filter pred (cdr lst))))
; אחרת, נתעלם ממנו ונמשיך רקורסיבית לשאר הרשימה
(else
(my-filter pred (cdr lst))))))מלכת הרשימות: foldr (קיפול ימני)
הפונקציה foldr (Fold Right) היא החשובה ביותר במטלות
(ובחיים כשמתכנתים פונקציונלית). היא מאפשרת "לקפל" רשימה לערך בודד על ידי הפעלת פונקציה המשלבת כל
איבר עם התוצאה של קיפול שאר הרשימה (מימין לשמאל).
מבנה: (foldr func initial-value list)
func- פונקציה המקבלת שני ארגומנטים: האיבר הנוכחי מהרשימה (curr), והתוצאה המצטברת (acc) משאר הרשימה.initial-value- ערך ההתחלה, שמוחזר כשהרשימה ריקה.
; דוגמה: סכימת כל האיברים ברשימה
(foldr (lambda (curr acc) (+ curr acc)) 0 '(1 2 3))
; חישוב מאחורי הקלעים: (+ 1 (+ 2 (+ 3 0))) => 6💡 מימוש פונקציות בעזרת foldr
אפשר לממש כמעט כל פונקציית רשימה (כולל map, filter, append) בעזרת foldr, וזה נדרש בממ"ן!
איך לממש filter עם foldr? החשוב הוא להבין ש-acc מייצג את הרשימה שכבר סוננה (מהסוף אחורה). עלינו לבדוק את curr (האיבר הנוכחי שעליו אנו עובדים): אם הוא מקיים את התנאי נחבר אותו ל-acc (בעזרת cons), ואם לא, פשוט נחזיר את acc כמות שהוא כדי לדלג עליו.
; שלד למימוש filter בעזרת foldr
(define my-filter
(lambda (pred lst)
(foldr (lambda (curr acc)
(if (pred curr)
(cons curr acc) ; הוסף את האיבר לרשימה הנבנית
acc)) ; דלג עליו, שמור על מה שנאסף עד כה
'() ; ערך האתחול הוא רשימה ריקה, אליה נאגור איברים
lst)))סימולטור פעולות רשימה מסדר גבוה (Map, Filter, Foldr) הדמיה אינטראקטיבית
עקבו אחר עיבוד הרשימה '(1 2 3 4) שלב אחר שלב באמצעות הפעולות הפונקציונליות השונות:
הרצת שלבים:
מצב הרשימה:
רקורסיות מורכבות: append ו-powerset
בחלק מהמטלות תדרשו לכתוב אלגוריתמים רקורסיביים שלא רק עובדים על איבר אחד, אלא משלבים רשימות קיימות ליצירת קומבינציות חדשות, ממש כמו בשאלות הקשורות למבנים מתמטיים של קבוצות.
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? אנו צריכים ללמוד לפתור בעיות קומבינטוריות שבהן עלינו להרכיב ולמזג נתונים (כמו בניית קבוצת חזקה).
- מה לומדים מזה? הבנה של אלגוריתם "לקחת או לא לקחת" המהווה אבן יסוד בבניית
תתי-קבוצות, ולמידת השילוב העוצמתי של
mapו-appendבתוך רקורסיה.
1. שרשור רשימות: איך עובד append?
שרשור שתי רשימות דורש בנייה מחדש. אי אפשר פשוט "להדביק" אותן. הגישה היא "לפרק" את הרשימה הראשונה בעזרת רקורסיה על ה-cdr, וכשמגיעים לקצה שלה (כשהיא ריקה), להחזיר את הרשימה השנייה - וכל הקריאות הקודמות כבר יוסיפו ב-cons את איברי הרשימה הראשונה אליה.
; מימוש רקורסיבי ל-append (מחבר את lst1 ל-lst2)
(define my-append
(lambda (lst1 lst2)
(if (null? lst1)
lst2 ; אם הראשונה ריקה, נחזיר את השנייה במלואה (זה הבסיס!)
; אחרת, נחבר את האיבר הראשון להמשך השרשור
(cons (car lst1)
(my-append (cdr lst1) lst2)))))מימוש append עם foldr (שאלה 1ב בממ"ן): במקום לכתוב
רקורסיה מפורשת כנ"ל, ניתן לקפל את הרשימה הראשונה lst1 מימין לשמאל באמצעות
cons, כאשר ערך האתחול של הקיפול הוא הרשימה השנייה lst2. כך נוצר שרשור
אלגנטי ביותר ללא רקורסיה מפורשת!
(define my-append-fr
(lambda (lst1 lst2)
; אנו מקפלים את lst1, ומלבישים את האיברים ב-cons מעל lst2
(foldr cons lst2 lst1)))2. קבוצת חזקה (Powerset)
איך מייצרים את כל תתי-הקבוצות האפשריות מתוך רשימה? תרגיל קלאסי (ומופיע כמעט תמיד במטלה 11).
העיקרון המנחה (אלגוריתם "לקחת או לא לקחת"):
כדי למצוא את Powerset של רשימה, נשאל את עצמנו מה עושים עם האיבר הראשון. תת-קבוצות יכולות להיות אלו שכוללות אותו, ואלו שלא כוללות אותו.
- אלו שבלעדיו: זה בדיוק שווה ל-(powerset (cdr lst)). ניקח את זה כבסיס!
- אלו שאיתו: ניקח את הבסיס שמצאנו כרגע, ולכל תת-קבוצה בו נוסיף (cons) את
האיבר המקורי ששמרנו. נוכל לעשות זאת בקלות בעזרת
map.
דוגמת חשיבה לקוד עובד:
; תנאי העצירה: קבוצת החזקה של קבוצה ריקה היא רשימה המכילה רשימה ריקה '(()
(define powerset
(lambda (lst)
(if (null? lst)
'(()) ; רשימה המכילה רשימה ריקה
(let ((rest-ps (powerset (cdr lst))))
(append
rest-ps ; כל תתי הקבוצות בלי האיבר הראשון (car lst)
; בעזרת map, נעבור על rest-ps ונוסיף את (car lst) לכל איבר בפנים:
(map (lambda (subset) (cons (car lst) subset)) rest-ps))))))
ADT פולינומים: define-datatype
שימוש מתקדם בטיפוסי נתונים אלגבריים (ADT) לייצוג
מבנה מתמטי מורכב (פולינום) באמצעות כלי ה-define-datatype של הקורס.
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? פולינום הוא מקרה מבחן מצוין לייצוג ביטויים מתמטיים מורכבים במחשב, והוא מהווה הכנה ישירה לאופן שבו נממש את ביטויי השפה (Expressions) במפרש בפרק 3.
- מה לומדים מזה? הבנה עמוקה של עמודי התווך של ADT (בנאים, בוררים, פרדיקטים),
הפרדת ממשק ממימוש, והבנת הניתוח של עץ רקורסיבי בעזרת
cases.
הספציפיקציה של פולינום
פולינום יכול להיות או פולינום ריק (אפס) או מורכב מגורם (Term - חזקה ומקדם) ומשאר הפולינום.
(define-datatype poly poly?
(zero-poly)
(extend-poly
(coeff number?)
(exp number?)
(rest-poly poly?)))החילוץ מתוך ה-ADT
כדי לגשת למידע, עלינו לכתוב פונקציה שעושה cases
(Pattern Matching) על הפולינום שקיבלנו.
(define poly->list
(lambda (p)
(cases poly p
(zero-poly () '())
(extend-poly (coeff exp rest)
(cons (list coeff exp)
(poly->list rest))))))מימוש מלא לממן 12 (שאלה 1)
כדי שהמימוש יהיה מושלם, עלינו לספק גם את שאר הפונקציות הנדרשות
מהספציפיקציה האלגברית. שימו לב לשימוש בבנאים שיצרנו ב-define-datatype ולצורת כתיבת
הבוררים שמחזירים שגיאה בעת הפעלה על הפולינום הריק.
; בנאים (Constructors) שעוטפים את ה-datatype
(define zero (lambda () (zero-poly)))
(define make-poly (lambda (coeff exp rest) (extend-poly coeff exp rest)))
; פרדיקט (Predicate) הבודק אם פולינום הוא אפס
(define is-zero?
(lambda (p)
(cases poly p
(zero-poly () #t)
(extend-poly (coeff exp rest) #f))))
; בוררים (Selectors)
(define coeff
(lambda (p)
(cases poly p
(zero-poly () (eopl:error 'coeff "Cannot get coeff of zero polynomial"))
(extend-poly (coeff exp rest) coeff))))
(define degree
(lambda (p)
(cases poly p
(zero-poly () (eopl:error 'degree "Cannot get degree of zero polynomial"))
(extend-poly (coeff exp rest) exp))))
(define rest
(lambda (p)
(cases poly p
(zero-poly () (eopl:error 'rest "Cannot get rest of zero polynomial"))
(extend-poly (coeff exp rest) rest))))
; חיבור שני פולינומים בעזרת הבנאי
(define add-poly
(lambda (p1 p2)
(cases poly p1
(zero-poly () p2)
(extend-poly (coeff exp rest-p)
(extend-poly coeff exp (add-poly rest-p p2))))))
; חישוב ערך הפולינום עבור X מסוים בעזרת עזר: expt מובנה בסביבת DrRacket
(define calc-poly
(lambda (p x)
(cases poly p
(zero-poly () 0)
(extend-poly (coeff exp rest-p)
(+ (* coeff (expt x exp))
(calc-poly rest-p x))))))💡 טיפ למבחן: עיבוד מסובך של עץ ADT
שאלה 1 מבקשת לכתוב גם פונקציית print-poly שמדפיסה
פולינום ממוין מהחזקה הגדולה לקטנה וללא מקדמי אפס. במקום לנסות לכתוב לוגיקה מורכבת שרצה ישירות על
עץ ה-cases הרקורסיבי, הגישה המנצחת היא: להמיר קודם את העץ לרשימה
שטוחה!
בזכות poly->list שכתבנו, אנו מקבלים רשימה של זוגות
((coeff exp) (coeff exp) ...). על הרשימה הזו קל מאוד להפעיל filter
(להסיר מקדמי 0) ולהפעיל פונקציית sort למיון חזקות, ולאחר מכן לעבור עליה בלולאה
ולהדפיס ברוגע.
הכלים של הקורס: define-datatype
שפות תכנות פועלות על ידי מניפולציה של מבני נתונים
מורכבים (כמו עצי AST, סביבות מורחבות, וערכים חישוביים). ספר הקורס (EOPL) פיתח ספריה מיוחדת
המרחיבה את Racket ומקלה על יצירת טיפוסי נתונים אלגבריים (Algebraic Data Types).
זהו הכלי שנמצא בכל קובץ data-structures.scm.
למה צריך define-datatype?
ב-Scheme רגיל, היינו מייצגים מבנים מסובכים בעזרת רשימות (למשל, לייצג
סביבה כ-(list 'extend-env var val prev-env)). אבל זה מועד לשגיאות וקשה לקריאה.
define-datatype מאפשר להגדיר "קופסת אב" (למשל: Type כללי
שנקרא expression), שיכולה ללבוש מספר צורות שונות (Variants) (למשל:
ביטוי מספרי, ביטוי תנאי, קריאה לפונקציה). המערכת בודקת עבורנו אוטומטית שכל צורה מקבלת בדיוק את
השדות המתאימים לה, מאמתת את הטיפוסים שלהם, ומייצרת פונקציות בנאיות (Constructors) מאחורי הקלעים.
דוגמה קלאסית: הערכים בשפה (expval)
בשפת LET, ביטוי שמחשב המפרש יכול להחזיר מספר או בוליאני.
אנו מגדירים את קופסת האב expval ואת הצורות האפשריות שלה:
; שם-הטיפוס | פונקציית-הבדיקה-הכללית
(define-datatype expval expval?
; צורה (Variant) 1: ערך מספרי
(num-val
; (שם-השדה | פונקציית-בדיקת-טיפוס)
(num number?))
; צורה 2: ערך בוליאני
(bool-val
(bool boolean?)))הקוד הזה מייצר אוטומטית פונקציות כמו
(num-val 5) שיוצרות את הקופסה בזיכרון.
דוגמה 2: מבנה הסביבות (environment)
סביבה יכולה להיות ריקה (Root), או מורחבת. זהו מבנה שקורא לעצמו (Recursive Datatype):
(define-datatype environment environment?
; צורה 1: סביבה ריקה (ללא שדות כלל)
(empty-env)
; צורה 2: סביבה מורחבת (מכילה 3 שדות)
(extend-env
(bvar symbol?)
(bval expval?)
; שימו לב! השדה הזה בודק שהוא מקבל environment!
(saved-env environment?)))💡 במבחן: כשהוספת פיצ'ר דורשת סוג חדש של ערך
נניח ובמבחן מבקשים ממך להוסיף מערך (Array) או
רשימה (Tuple). הדבר הראשון שעליך לעשות הוא ללכת
ל-data-structures.scm ולהוסיף Variant חדש לתוך ההגדרה הקיימת של
expval. למשל:
(define-datatype expval expval?
... ; existing variants
(array-val
; השדה יהיה רשימה שמכילה כתובות זיכרון (במקרה של שפת Explicit Refs)
(refs (list-of reference?))))פירוק נתונים: פקודת cases
החצי השני של המטבע! אם
define-datatype "אורז" נתונים לתוך קופסה שחורה בזיכרון, פקודת cases
היא הדרך הבטוחה והיחידה "לפתוח" את הקופסה, לבדוק איזו צורה (Variant) יש בפנים,
ולחלץ את המידע לתוך משתנים שנוכל לעבוד איתם.
Pattern Matching (התאמת תבניות)
פקודת ה-cases עובדת כמו מתג חכם. אנו נותנים לה טיפוס כללי (למשל
expval) ואת המשתנה שאנחנו רוצים לבדוק. היא בודקת באיזה Variant מדובר, וכשהיא מוצאת
התאמה, היא מחלצת את השדות הפנימיים לתוך שמות חדשים (שמופיעים בסוגריים) שזמינים לשימוש רק בתוך
אותו בלוק.
השימוש הנפוץ ביותר של cases הוא ב"חולצים"
(Extractors): פונקציות שמטרתן לקבל קופסה כללית (expval) ולהחזיר ערך
נקי (למשל מספר או בוליאני).
דוגמה אופיינית מ-data-structures.scm
; פונקציית Extract ששולפת מספר מקופסת expval
(define expval->num
(lambda (v)
; פתח את המשתנה v, תוך ידיעה שהוא מטיפוס expval
(cases expval v
; אם הוא מהצורה num-val:
; חלץ את השדה הפנימי אל תוך משתנה חדש בשם 'num'
; והרץ את הקוד שאחריו (שפשוט מחזיר את num)
(num-val (num) num)
; חובה לספק בלוק else לתפוס שגיאות (במקרה ש-v היה בכלל bool-val)
(else (eopl:error 'expval->num "Expected number, got ~s" v)))))הלב של המפרש: cases expression
כל פונקציית value-of (הפונקציה המרכזית
ב-interp.scm שמריצה את התוכנית) היא למעשה פקודת cases אחת ענקית שרצה
על ה-AST (העץ התחבירי). העץ מוגדר תחת הטיפוס expression.
זה המקום שבו אנחנו לוקחים צומת בעץ (למשל צומת תנאי), מחלצים את הביטויים הפנימיים שלו, ומפעילים עליהם לוגיקה:
(define value-of
(lambda (exp env)
(cases expression exp
; ... צמתים אחרים ...
; הנה איך מטפלים בצומת IF:
; חולצים את 3 תתי-העצים אל תוך המשתנים exp1, exp2, exp3
(if-exp (exp1 exp2 exp3)
; מעריכים את תנאי הבדיקה (exp1) בעזרת קריאה רקורסיבית
(let ((val1 (value-of exp1 env)))
; חולצים את הערך הבוליאני מתוך קופסת ה-expval
(if (expval->bool val1)
; אם אמת, מעריכים את תת-העץ של האמת
(value-of exp2 env)
; אחרת מעריכים את תת-העץ של השקר
(value-of exp3 env)))))))סימולטור פירוק מבני נתונים (define-datatype & cases) הדמיה אינטראקטיבית
נניח שהגדרנו טיפוס נתונים עבור צורות הנדסיות shape. בחרו ערך כדי לראות כיצד פקודת
cases מפרקת אותו ומתאימה אותו לבלוק הנכון:
1. בחרו ערך לבדיקה (s):
פקודת cases במפרש:
ADT פולינומים: ספציפיקציה ומימוש
בממן 12 אנו נדרשים לתאר, להגדיר ולממש טיפוס נתונים מופשט (ADT) המייצג פולינום מהצורה $p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_k x^k$. נלמד איך מאפיינים ADT בשלושה שלבים: חתימות, ספציפיקציה אלגברית, ומימוש בפועל בעזרת הכלים של EOPL.
א' - אפיון הפעולות (Signatures / Types)
בחלוקה הקלאסית של ADT, אנו מחלקים את הממשק לשלושה סוגי פונקציות:
| סוג הפעולה | שם הפונקציה וחתימה | תיאור |
|---|---|---|
| בנאים (Constructors) | zero : () -> Poly make-poly : Int x Int -> Poly add-poly : Poly x Poly -> Poly |
יוצרים מופעים חדשים של הטיפוס. `zero` מייצג את פולינום האפס. `make-poly` מייצג איבר בודד (מקדם וחזקה). `add-poly` מחבר שני פולינומים. |
| בוררים (Selectors) | degree : Poly -> Int coeff : Poly x Int -> Int print-poly : Poly -> List calc-poly : Poly x Number -> Number |
שולפים מידע מתוך הטיפוס. `degree` מחזיר את הדרגה הגבוהה ביותר. `coeff` מחזיר מקדם לחזקה נתונה. `print-poly` ממיר לרשימת זוגות ממוינת. `calc-poly` מחשב עבור X מסוים. |
| פרדיקטים (Predicates) | is-zero? : Poly -> Bool | בודקים תנאים ומחזירים ערך בוליאני. בודק האם הפולינום הוא פולינום האפס. |
ב' - ספציפיקציה אלגברית (Algebraic Specification)
הספציפיקציה האלגברית מגדירה את הלוגיקה והסמנטיקה של הטיפוס על ידי יצירת משוואות המקשרות בין הבוררים/פרדיקטים לבנאים השונים. עבור פולינום $p$ כלשהו, מספרים $c, e$ ומספר $x$:
- (is-zero? (zero)) = true
- (is-zero? (make-poly c e)) = (c == 0)
- (is-zero? (add-poly p1 p2)) = (is-zero? p1) ∧ (is-zero? p2) (לאחר צמצום איברים)
- (coeff (zero) e_search) = 0
- (coeff (make-poly c e) e_search) = if (e == e_search) then c else 0
- (coeff (add-poly p1 p2) e_search) = (coeff p1 e_search) + (coeff p2 e_search)
- (degree (zero)) = 0
- (degree (make-poly c e)) = if (c == 0) then 0 else e
- (degree (add-poly p1 p2)) = max(e) for all exponents where (coeff (add-poly p1 p2) e) ≠ 0, or 0 if all are 0.
- (calc-poly (zero) x) = 0
- (calc-poly (make-poly c e) x) = c * x^e
- (calc-poly (add-poly p1 p2) x) = (calc-poly p1 x) + (calc-poly p2 x)
ג' - מימוש מלא ב-Scheme/Racket (interp.scm & data-structures.scm)
; 1. הגדרת טיפוס הנתונים בעזרת define-datatype
(define-datatype poly poly?
(zero)
(make-poly
(coeff number?)
(exponent number?))
(add-poly
(p1 poly?)
(p2 poly?)))
; 2. מימוש הפרדיקט is-zero?
(define is-zero?
(lambda (p)
(cases poly p
(zero () #t)
(make-poly (c e) (= c 0))
(add-poly (p1 p2) (and (is-zero? p1) (is-zero? p2))))))
; 3. מימוש הבורר coeff (מחזיר מקדם לחזקה נתונה)
(define coeff
(lambda (p search-exp)
(cases poly p
(zero () 0)
(make-poly (c e) (if (= e search-exp) c 0))
(add-poly (p1 p2) (+ (coeff p1 search-exp) (coeff p2 search-exp))))))
; פונקציית עזר להוצאת כל החזקות בפולינום לצורך בירור דרגה ומיון
(define get-exponents
(lambda (p)
(cases poly p
(zero () '())
(make-poly (c e) (list e))
(add-poly (p1 p2) (append (get-exponents p1) (get-exponents p2))))))
; 4. מימוש הבורר degree (החזקה הגבוהה ביותר בעלת מקדם שונה מ-0)
(define degree
(lambda (p)
(let ((exps (get-exponents p)))
(letrec ((highest-deg
(lambda (lst max-so-far)
(cond
((null? lst) max-so-far)
((and (> (car lst) max-so-far) (not (= (coeff p (car lst)) 0)))
(highest-deg (cdr lst) (car lst)))
(else (highest-deg (cdr lst) max-so-far))))))
(highest-deg exps 0)))))
; 5. מימוש הבורר calc-poly (חישוב ערך הפולינום עבור x)
(define calc-poly
(lambda (p x)
(cases poly p
(zero () 0)
(make-poly (c e) (* c (expt x e)))
(add-poly (p1 p2) (+ (calc-poly p1 x) (calc-poly p2 x))))))
; פונקציות עזר עבור print-poly (הסרת כפילויות)
(define remove-duplicates
(lambda (lst)
(cond
((null? lst) '())
((member (car lst) (cdr lst)) (remove-duplicates (cdr lst)))
(else (cons (car lst) (remove-duplicates (cdr lst)))))))
; 6. מימוש הבורר print-poly
; מחזיר רשימה של זוגות (מקדם, חזקה) ממוינת בסדר יורד של חזקות, ללא מקדמי 0
(define print-poly
(lambda (p)
(let ((exps (remove-duplicates (get-exponents p))))
(let ((sorted-exps (sort exps >))) ; מיון מובנה בסביבת DrRacket
(letrec ((build-list
(lambda (lst)
(cond
((null? lst) '())
(else
(let ((c (coeff p (car lst))))
(if (= c 0)
(build-list (cdr lst)) ; התעלם ממקדמי אפס
(cons (list c (car lst)) (build-list (cdr lst))))))))))
(build-list sorted-exps))))))💡 דגש למבחן ולמטלות
כאשר מבקשים מיון או הדפסה של ADT שמיוצג כעץ (כמו
add-poly(p1, p2)), הדרך הפשוטה ביותר היא להפריד את המימוש לשני
שלבים: שלב 1: איסוף כל הנתונים לרשימה שטוחה (באמצעות פונקציית עזר רקורסיבית פשוטה
כמו get-exponents). שלב 2: ביצוע המניפולציה (מיון, סינון, כיווץ) על הרשימה השטוחה
בעזרת הפונקציות הסטנדרטיות של Scheme. גישה זו מונעת סיבוכיות מיותרת בעיבוד העץ.
המנתח התחבירי: SLLGen Lexer
המפרש שלנו לעולם אינו עובד ישירות על מחרוזות של
טקסט חופשי (Raw Text). השלב הראשון בכל ריצה הוא תהליך ה-Parsing (ניתוח תחבירי).
הצעד הראשון בתהליך הזה מתבצע על ידי הלקסר (Lexer / Scanner), והוא מוגדר בקובץ
lang.scm.
מה התפקיד של הלקסר? (The Lexical Spec)
הלקסר דומה לאדם שקורא טקסט בשפה שהוא לא מכיר, אבל יודע לזהות את האותיות והמילים. הוא קורא את קובץ הטקסט תו-אחר-תו, וחותך אותו לאסימונים (Tokens) לפי חוקים קבועים מראש (ביטויים רגולריים). הלקסר אינו בודק האם התחביר הגיוני או חוקי, הוא רק מזהה את חלקיקי המידע.
- הוא מתעלם לחלוטין מרווחים, טאבים, ושורות חדשות (אלא אם הוגדר אחרת).
- הוא יודע לזהות מהי מחרוזת, מהו מספר (המורכב מספרות), ומהו שם של משתנה (Identifier).
- הוא מסנן החוצה הערות (Comments) כדי שלא יפריעו בהמשך למפרש.
איך זה נראה בקוד? (lang.scm)
הלקסר של EOPL נקרא SLLGen, וכך נראית ההגדרה הקלאסית שלו בתוך השפות של הקורס:
(define the-lexical-spec
'(
; (שם-הטוקן | תבנית-זיהוי | פעולה)
; 1. כל תו שהוא מסוג 'רווח' - בצע עליו skip (התעלם והמשך הלאה)
(whitespace (whitespace) skip)
; 2. כל שורה שמתחילה באחוז '%' - היא הערה. בצע skip.
; הפירוש: תו '%' ואז רצף שרירותי (arbno) של תווים שאינם ירידת שורה.
(comment ("%" (arbno (not #\newline))) skip)
; 3. מזהה (Identifier/Variable). מיוצג כ-symbol.
; חייב להתחיל באות, ויכול להמשיך באותיות, ספרות או תווים מיוחדים.
(identifier
(letter (arbno (or letter digit "_" "-" "?")))
symbol)
; 4. מספרים. מיוצג כ-number.
; ספרה אחת לפחות, אולי עם מינוס בהתחלה עבור מספרים שליליים.
(number (digit (arbno digit)) number)
(number ("-" digit (arbno digit)) number)
))💡 דוגמה מהמבחן: הוספת מחרוזות (Strings)
בשאלות מבחן שבהן מבקשים מכם להוסיף תמיכה במחרוזות (למשל, מילים
שמתחילות בסימן @ כפי שהופיע באחת הדוגמאות בספר), תצטרכו להוסיף שורה
ל-the-lexical-spec כדי שהלקסר בכלל ידע לקרוא את זה:
(string-token ("@" letter (arbno letter)) string)
בניית העץ: SLLGen Parser (הדקדוק)
לאחר שהלקסר חילק את הטקסט לאסימונים (Tokens), נכנס
לפעולה הפרסר (Parser). תפקידו הוא לקחת את שורת המילים ולוודא שהן יוצרות משפט
בעל משמעות לפי חוקי הדקדוק (Grammar). אם המשפט חוקי, הוא בונה ממנו עץ
תחבירי מופשט (AST) המורכב מאותן קופסאות (define-datatype) שלמדנו עליהן
בפרק 2.
האנטומיה של חוק דקדוק
קובץ lang.scm מגדיר את the-grammar בעזרת
סדרה של חוקים. כל חוק (כל שורה) מייצר אוטומטית שדה (Variant) חדש בתוך ה-datatype המרכזי של השפה
(שנקרא לרוב expression).
מבנה סטנדרטי של שורה ב-Grammar:
( LHS ( RHS (Terminals & Non-Terminals) ) Variant-Name )- LHS (Left Hand Side): לאיזה משפחה הכלל הזה שייך (תמיד
expressionבקורס שלנו). - Terminals (בתוך מרכאות ""): מילים שמורות בשפה (כמו
"if","then","-",","). המתכנת כותב אותן, הפרסר מוודא שהן קיימות בסדר הנכון, ואז זורק אותן לפח! הן לא מגיעות לעץ ה-AST. - Non-Terminals: מילים ללא מרכאות (כמו
expression,identifier,number). אלו ביטויים רקורסיביים שיש לחשב. אלו הערכים האמיתיים שיישמרו כצמתים (Nodes) בעץ! - Variant-Name: השם של הצומת שייווצר (כמו
if-expאוdiff-exp). זהו השם שיקפוץ לנו ב-cases expressionבתוך המפרש.
דוגמה לתרגום: מהטקסט אל העץ
נניח שזה חוק הדקדוק שלנו לפעולת חיסור:
(expression ("-" "(" expression "," expression ")") diff-exp)והמתכנת כתב את הקוד הבא: -(55, 11).
פונקציית
scan&parse תהפוך את המחרוזת הזו לעץ הבא (שימו לב שאין בעץ פסיקים או סוגריים):
#(struct:const-exp 55)
#(struct:const-exp 11))
מפרק עצי ה-AST האינטראקטיבי הדמיה אינטראקטיבית
שלב 1: מחרוזת קוד
שלב 2: אסימונים (Lexer Tokens)
הלקסר מחלק את הטקסט כולל מילים שמורות וסימני פיסוק (Terminals בצהוב).
שלב 3: עץ ה-AST שנוצר בפרסר
הפרסר מסנן את סימני הפיסוק המיותרים ובונה עץ היררכי רקורסיבי (בירוק - צמתים שמכילים נתונים).
איך קוראים דקדוק מורכב במבחן?
במבחן תמיד ייתנו לכם הרחבת דקדוק שכוללת רשימות. הפרסר משתמש בסמלים מיוחדים כדי להגיד שיש כאן איבר שחוזר על עצמו כמה פעמים (כמו מערך).
דוגמה מהמבחן על Switch-Case:
Expression ::= switch Expression { {Type identifier when (Expression ) => Expression}+(,) default => Expression }
- הסוגריים
{}*(,)או{}+(,)מסמנים שכל מה שבפנים חוזר על עצמו 0 או יותר פעמים (כוכבית) או 1 או יותר פעמים (פלוס), ומופרד באמצעות פסיק,. - כשהפרסר קורא את החוק הזה ובונה ממנו את הצומת (למשל
switch-exp), הוא יארוז את כל החזרות האלו לתוך רשימות (list-of) מקבילות! לכן המפרש יצטרך לקבל משתנים שהם רשימות: רשימה של identifiers, רשימה של condition expressions וכו'.
ניהול מצב וזיכרון: Environments
סביבה (Environment) היא הפנקס או טבלת הסמלים (Symbol Table) שבה המפרש רושם אילו משתנים קיימים ומה הערך (או כתובת הזיכרון) הקשור אליהם. אופן בניית הסביבות קובע את חוקי טווח ההכרה (Lexical Scoping) של השפה.
למה לא מילון רגיל? (מודל הבצל)
למה אנחנו לא משתמשים פשוט בטבלת Hash או מילון רגיל כדי לשמור משתנים? הסיבה היא ששפות מחשב מאפשרות הסתרה (Shadowing). משתנה פנימי בתוך פונקציה יכול להסתיר משתנה חיצוני בעל אותו שם, וכשהפונקציה מסתיימת - המשתנה החיצוני צריך "לחזור לחיים".
כדי לפתור זאת, הסביבה בקורס בנויה כרשימה מקושרת (Linked
List). כל פקודת extend-env יוצרת שכבה חדשה (כמו שכבת בצל) ששומרת
רק משתנה אחד, ומחזיקה מצביע (Pointer) לסביבה הקודמת. הסביבה החיצונית המקורית מעולם לא נהרסת!
מבנה הנתונים השכבתי (data-structures)
(define-datatype environment environment?
; תחתית הבצל - סביבה ריקה ללא משתנים (השורש)
(empty-env)
; סביבה המכילה שכבה חדשה:
(extend-env
(bvar symbol?) ; שם המשתנה (למשל 'x')
(bval expval?) ; הערך שלו (למשל 5)
(saved-env environment?))) ; הצבעה לסביבה החיצוניתלמשל, הקוד let x=1 in let y=2 in x+y ייצר
בזיכרון:
[y=2] -> [x=1] -> EmptyEnv.
הדמיית שרשרת סביבות והסתרה (Shadowing) הדמיה אינטראקטיבית
נריץ מעקב של פונקציית החיפוש apply-env על הסביבה שנוצרת עבור הקוד הבא:
let x=1 in let y=2 in let x=3 in x+y.
חיפוש משתנה בסביבה:
מבנה שרשרת הסביבות (מבנה נתונים):
פונקציית החיפוש המרכזית: apply-env
פונקציה זו (היושבת ב-environments.scm) אחראית למצוא ערך
של משתנה. היא עובדת בצורה רקורסיבית מבריקה שמממשת את רעיון ה-Shadowing:
- היא מסתכלת על ה"שכבה" הנוכחית של הסביבה (הבצל החיצוני ביותר).
- אם שם המשתנה שמחפשים (
search-var) תואם למשתנה בשכבה (bvar), היא מצאה! היא מחזירה את הערך. ההסתרה עובדת אוטומטית כי מצאנו את ההגדרה הטרייה ביותר! - אם לא, היא קולפת את השכבה, וקוראת לעצמה שוב באופן רקורסיבי על
ה-
saved-env(השכבה הפנימית יותר). - אם היא הגיעה ל-
empty-envועדיין לא מצאה כלום, המשמעות היא שהמשתנה אינו מוגדר - נזרקת שגיאה!
(define apply-env
(lambda (env search-var)
(cases environment env
; מקרה בסיס: הגענו לסוף הרשימה ולא מצאנו
(empty-env ()
(eopl:error 'apply-env "Unbound variable ~s" search-var))
; מקרה רקורסיבי: פותחים את השכבה הנוכחית
(extend-env (bvar bval saved-env)
(if (eqv? search-var bvar)
bval ; מצאנו! נחזיר את הערך
; לא מצאנו, נמשיך לחפש בשכבות הפנימיות
(apply-env saved-env search-var))))))ייצוג פרוצדורלי של סביבות: תיאוריה ומימוש
בספר EOPL (עמוד 40) מוצג ייצוג אלטרנטיבי וחשוב לסביבות: **ייצוג פרוצדורלי (Procedural Representation)**. בניגוד לייצוג המבוסס על מבני נתונים (Linked List בעזרת `define-datatype`), בייצוג הפרוצדורלי הסביבה עצמה היא **פונקציה (Lambda)** שממתינה לקבל משתנה ומחזירה את ערכו.
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? סביבה היא מושג הליבה של מפרשים. אנו רוצים להמחיש שאין חובה לייצג זיכרון כמבנה נתונים פיזי, אלא אפשר לייצגו כפונקציה התנהגותית לכל דבר.
- מה לומדים מזה? עיקרון הדואליות (Dualism) של תכנות פונקציונלי (החלפת מבנה נתונים בפרוצדורה), הבנת תפקיד ה-Closure בשימור מצב (הסביבה זוכרת את המשתנים בהקשר שבו נוצרה), ולמידת מודל ה-Continuations לצורך ניהול זרימה ושגיאות.
קוד המימוש הפרוצדורלי הבסיסי
כאן אנו לא משתמשים
ב-define-datatype! כל סביבה מוחזרת כפונקציה של ארגומנט אחד:
; 1. סביבה ריקה: פונקציה שזורקת שגיאה תמיד
(define empty-env
(lambda ()
(lambda (search-var)
(eopl:error 'apply-env "No binding for ~s" search-var))))
; 2. הרחבת סביבה: מחזירה פונקציה חדשה שמבצעת השוואה
(define extend-env
(lambda (saved-var saved-val saved-env)
(lambda (search-var)
(if (eqv? search-var saved-var)
saved-val ; אם זה המשתנה שלנו, נחזיר את הערך
(apply-env saved-env search-var))))) ; אחרת, נמשיך לסביבה האב
; 3. חיפוש בסביבה: פשוט מריץ את הסביבה כפונקציה!
(define apply-env
(lambda (env search-var)
(env search-var)))בעיית "הקופסה השחורה" (The Black-Box Problem)
בייצוג פרוצדורלי, הסביבה היא פונקציה בלבד. אין לנו שום דרך להסתכל "פנימה" או לדעת אילו משתנים מוגדרים בה בלי להפעיל אותה בפועל.
הבעיה בממן 12: אנו צריכים לכתוב פונקציה
(is-num? e x) הבודקת האם המשתנה x קיים בסביבה e והאם
ערכו מספרי.
אם נפעיל סתם כך (apply-env e x) והמשתנה
אינו קיים, הפונקציה empty-env תזרוק שגיאה קריטית (Crash)
ותעצור את ריצת התוכנית. כדי לפתור זאת נדרשת גישה מיוחדת.
פתרון 1: שימוש במנגנון תפיסת שגיאות ב-Racket (הכי נקי ומתאים לריצה)
בסביבת DrRacket (ובשפת Racket), ניתן לעטוף את הקריאה
ל-apply-env במנגנון תפיסת
חריגות with-handlers .
אזהרה קריטית למבחן: זה לא Scheme תקני!
with-handlers אינו
חלק משפת Scheme הסטנדרטית. שימוש בו במבחן תיאורטי עלול להוביל להורדת נקודות. במבחן, יש
להשתמש תמיד בפתרון 2 (העברת Failure Callback)!
#f (מכיוון שאין כריכה כזו, ובפרט אין כריכה למספר). אם הוא מצליח, אנו בודקים האם
הערך הוא מספר בעזרת number?.
(define is-num?
(lambda (e x)
(with-handlers
; תפוס כל שגיאה/כישלון והחזר #f
([exn:fail? (lambda (exn) #f)])
; גוף החישוב: נסה לבצע חיפוש, ובדוק האם התוצאה היא מספר
(number? (apply-env e x)))))פתרון 2: סגנון שאלות מבחן (העברת Failure Callback)
במבחנים רבים, במקום להשתמש במנגנון שגיאות של Racket, מניחים כי
פונקציית החיפוש apply-env (והסביבה עצמה) מעודכנת לקבל פרמטר נוסף: פונקציית
כישלון (Failure Continuation / Callback) שתופעל במקרה שהמשתנה אינו נמצא, במקום
לקרוס.
מימוש סביבה פרוצדורלית תומכת כישלון:
; empty-env מקבל כעת את פונקציית הכישלון ומפעיל אותה
(define empty-env
(lambda ()
(lambda (search-var fail-cont)
(fail-cont))))
; extend-env מעביר את פונקציית הכישלון הלאה
(define extend-env
(lambda (saved-var saved-val saved-env)
(lambda (search-var fail-cont)
(if (eqv? search-var saved-var)
saved-val
(apply-env saved-env search-var fail-cont)))))
; apply-env מעביר את פונקציית הכישלון
(define apply-env
(lambda (env search-var fail-cont)
(env search-var fail-cont)))כתיבת הפתרון is-num? תחת מודל זה:
(define is-num?
(lambda (e x)
(apply-env e x
; 1. פונקציית הכישלון: אם המשתנה לא נמצא, החזר #f
(lambda () #f)
; 2. פונקציית ההצלחה: במבחנים לפעמים apply-env מחזיר ישירות את הערך
; ואז נבדוק את הערך המוחזר בעזרת number? בחוץ:
)))
; כלומר, אם apply-env החזיר ערך ללא קריסה:
(define is-num?
(lambda (e x)
(let ((val (apply-env e x (lambda () #f))))
(number? val))))ארכיטקטורת מפרש EOPL: הקבצים שיוצרים אותה
לפני שניגש לקוד השפה, חשוב להבין כיצד בנוי הפרויקט. כל מפרש בקורס מורכב מאוסף של קבצים בעלי תפקידים מוגדרים המרכיבים יחד את צינור העיבוד (Pipeline) משלב הקריאה ועד לתוצאה.
"-(5, 2)"
(diff-exp ...)
(num-val 3)
💡 סימולטור ארכיטקטורה אינטראקטיבי
לחצו על אחד השלבים בצינור העיבוד למעלה כדי לחשוף את תפקידו ומאחורי הקלעים שלו במפרש EOPL.
חלוקת התפקידים בקבצים
lang.scm- מכיל את הגדרות הלקסר והגרמטיקה (באמצעות SLLGen). מגדיר את כללי התחביר ואת שמות צומתי העץ התחבירי.data-structures.scm- מגדיר את מבני הנתונים בעזרתdefine-datatype. מכיל אתexpval, פונקציות חולצים (Extractors), והגדרת טיפוסים כמוproc(פרוצדורות) בשפות מתקדמות.environments.scm- מנהל את הזיכרון הלקסיקלי. מכיל פונקציות כמוextend-envליצירת שכבת זיכרון חדשה ו-apply-envלשליפת ערך מהזיכרון.interp.scm- הלב הפועם. מכיל את פונקצייתvalue-of, שעוברת על העץ (באמצעותcases expression) ומחשבת את התוצאה עבור כל צומת.top.scm- קובץ ההרצה המחבר הכל ומספק את פונקציית ה-(run "code").
💡 מדריך למבחן: הוספת פיצ'ר חדש למפרש
כמעט כל שאלה במבחן דורשת הוספת פיצ'ר. סדר הפעולות הקבוע הוא:
- עדכון הגרמטיקה: הוסיפו שורה ל-
the-grammarב-lang.scmכדי שהמחשב יכיר את המילים השמורות וידע לבנות את הצומת (AST node). - (במידת הצורך) עדכון ערכים: אם הפיצ'ר מחזיר סוג נתון חדש (למשל רשימה),
הוסיפו Variant ל-
expvalב-data-structures.scmיחד עם Extractor מתאים. - הסמנטיקה: הוסיפו סעיף ל-
cases expressionבתוך פונקצייתvalue-ofב-interp.scmהמגדיר מה הפיצ'ר עושה (אילו ביטויים הוא מעריך, איך הוא מרחיב סביבה, מה הוא מחזיר).
מבוא: השפה הבסיסית ביותר
שפת LET מניחה את התשתית לקורס כולו. היא אינה שפת
תכנות מלאה (אין בה פונקציות או לולאות), אלא פועלת כמו "מחשבון משוכלל". היא יודעת לחשב ביטויים
מתמטיים, להריץ תנאים (if), והכי חשוב - לשמור משתנים מקומיים בעזרת let. בשפה זו,
הכל קבוע (Immutable). מרגע שמשתנה הוגדר, לא ניתן לשנות את ערכו.
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? כדי להציב את מסד הנתונים וההתנהגות המינימליים ביותר של מפרש (שמירת ערכים קבועים, ביטויים ותנאים), מבלי להסתבך עם סביבות סבוכות (כמו פונקציות). זוהי נקודת ההתחלה המאפשרת לבנות את תשתית הלקסר והפארסר.
- מה לומדים מזה? את ההבדל החשוב שבין ExpVal (הערך המוחזר מביטוי לאחר חישוב) לבין DenVal (הערך הנשמר בזיכרון של המשתנה בסביבה). בנוסף, מבינים כיצד AST מנותח בצורה רקורסיבית.
תחביר השפה (lang.scm)
הדקדוק של LET מגדיר מהם הביטויים החוקיים. שימו לב לשם
הצומת שייווצר בעץ (למשל const-exp או let-exp).
; מספר בסיסי
(expression (number) const-exp)
; פעולת חיסור מתמטית
(expression
("-" "(" expression "," expression ")")
diff-exp)
; תנאי
(expression
("if" expression "then" expression "else" expression)
if-exp)
; שימוש במשתנה רגיל
(expression (identifier) var-exp)
; הגדרת משתנה חדש!
(expression
("let" identifier "=" expression "in" expression)
let-exp)מושגי יסוד: ExpVal מול DenVal
בספר (EOPL) תפגשו שני מושגים קריטיים של מפרשים:
- Expressed Value (ExpVal): איזה סוג של ערכים יכול ביטוי (Expression) להחזיר כתוצאה חישובית?
- Denoted Value (DenVal): איזה סוג של ערכים אפשר לשמור בתוך משתנה בסביבה (Binding)?
בשפת
LET:
ExpVal = DenVal = {Number, Boolean}.
כלומר, ביטוי מחזיר רק מספר או בוליאני,
ומשתנה שומר רק מספר או בוליאני.
מבנה הנתונים: עטיפת הערכים (data-structures.scm)
בגלל שפונקציית value-of שלנו צריכה להחזיר תמיד סוג אחד
כללי של נתון, אנו עוטפים את המספרים והבוליאנים של סקים (Racket) בתוך קופסה שנקראת
expval.
(define-datatype expval expval?
; קופסה למספר
(num-val
(value number?))
; קופסה לערך בוליאני
(bool-val
(boolean boolean?)))
; פונקציית חולץ (Extractor) לדוגמה:
(define expval->num
(lambda (v)
(cases expval v
(num-val (num) num)
(else (eopl:error 'expval->num "Expected number!")))))המפרש וMulti-Let
הלב הפועם של כל השפות בקורס הוא הפונקציה
value-of. תפקידה הוא לקבל צומת של ה-AST וסביבה זיכרונית, ולחשב את התוצאה. בחלק זה
גם נלמד כיצד להרחיב את השפה לתמיכה במספר השמות במקביל, שאלת מבחן קלאסית.
הלוגיקה הבסיסית ב-let-exp (הקמת סביבות)
בואו נבין בדיוק מה קורה בשורות האחרונות כשאנחנו כותבים בקוד
שלנו: let x = 5 in -(x, 1)
; --- הלב של השפה: פקודת LET (מתוך interp.scm) ---
(let-exp (var exp1 body)
; 1. מחשבים את הערך של ההשמה (הצד הימני)
(let ((val1 (value-of exp1 env)))
; 2. מריצים את הגוף (body) בתוך *סביבה מורחבת* המכילה את ההשמה החדשה!
(value-of body
(extend-env var val1 env))))- המפרש רואה
let-expומפרק אותו:var = 'x',exp1 = 5,body = -(x, 1). - מעריך את
exp1(המספר 5) בסביבה הנוכחית. התוצאה היא(num-val 5). - המהלך הקריטי: משתמש ב-
extend-envלייצר שכבת זיכרון חדשה (x שווה 5). - מעריך את ה-
bodyבתוך הסביבה החדשה.
הכנה למבחן: מימוש Multi-Let
בגרסה הבסיסית, let מגדיר משתנה בודד. אחת ההרחבות הנפוצות
במבחן היא לאפשר כתיבת מספר הגדרות יחדיו: let x = 1 y = 2 in -(x, y).
כיצד נממש זאת?
שלב 1: עדכון הגרמטיקה (lang.scm)
נשתמש במילת המפתח arbno (מספר שרירותי) כדי
לדרוש 0 או יותר זוגות של (מזהה = ביטוי):
(expression
("let" (arbno identifier "=" expression) "in" expression)
let-exp)שימו לב: משום שהשתמשנו ב-arbno, הצומת
let-exp ייצר כעת רשימה: identifier הופך
ל-(list-of symbol?) ו-expression הופך
ל-(list-of expression?).
שלב 2: עדכון המפרש (interp.scm)
מכיוון שקיבלנו רשימות של משתנים ורשימה של ביטויים (b-vars
ו-b-exps), נשתמש ב-map כדי לחשב את כל הביטויים, ובפונקציית העזר
extend-env* שמרחיבה את הסביבה עבור רשימות.
(let-exp (b-vars b-exps body)
; הפעלת value-of על כל רשימת הביטויים בעזרת map
(let ((b-vals (map (lambda (exp) (value-of exp env)) b-exps)))
; הערכת הגוף בתוך סביבה שהורחבה בעזרת כל המשתנים וערכיהם יחדיו
(value-of body
(extend-env* b-vars b-vals env))))פתרון ממן: המרות טיפוסים ולולאת do
שאלות ממן במפרשים בוחנות את היכולת שלנו להרחיב את השפה בפיצ'רים שקיימים בשפות מודרניות. כאן נצלול לפתרון של שתי שאלות עומק מהמטלות, כולל הבנת השאלה המקורית, הדוגמאות, וניתוח המעקב (Trace) של המפרש.
שאלה 1: מערכת המרת טיפוסים (Casting)
Type ::= int int-type ()
Type ::= bool bool-type ()
ההמרה פועלת כך:
- מספר לבוליאני: כל מספר שאינו 0 מומר ל-#t, ו-0 מומר ל-#f.
- בוליאני למספר: #t מומר ל-1, #f מומר ל-0.
- בנוסף, נשנה את ביטוי ה-if-exp כך שיבצע המרה נרמזת לביטוי הבוליאני שלו.
🎯 הפן הפדגוגי: מה המטרה כאן?
במקום שגיאות ריצה (Crashes) כשהמשתמש מכניס ערך מטיפוס לא צפוי, אנו
לומדים כיצד ללמד את המפרש להתגמש ולנסות להמיר אותו. זוהי בדיוק ההתנהגות של שפות דינמיות כמו
JavaScript (שבה if (1) עובד כמו if (true)). בנוסף, זהו תרגול מצוין
של הוספת משפחה חדשה (Type) לדקדוק הלקסר.
ניתוח דוגמאות ההרצה ומעקב (Trace)
if 9 then 100 else 200
התוצאה: 100 (המרה נרמזת).
איך המפרש עובד: ה-`if-exp` שלנו קורא
ל-value-of על 9. הוא מקבל num-val(9). במקום לזרוק שגיאה שזה לא
בוליאני, מנגנון ה-Cases החדש שלנו מזהה שמדובר במספר שאינו 0, ולכן ממיר אותו אוטומטית
ל-#t בזיכרון. לכן ה-if פונה לביטוי האמת (100).
-(100, <int>(zero?(0)))
התוצאה: 99 (המרה מפורשת).
איך המפרש עובד: פונקציית החיסור מנסה לחסר
בין 100 לתוצאה של צד ימין. צד ימין הוא cast-exp לטיפוס
int-type של zero?(0). הביטוי הפנימי מחזיר
bool-val(#t). ה-cast-exp מקבל זאת, רואה שביקשנו
int-type, וממיר את ה-#t למספר num-val(1). החיסור מתבצע: 100
פחות 1, והתוצאה 99.
מימוש טכני - הקוד שלנו
1. קובץ lang.scm - הוספת חוקי ה-Lexer וה-Parser:
(type ("int") int-type)
(type ("bool") bool-type)
(expression ("<" type ">" "(" expression ")") cast-exp)2. קובץ interp.scm - מימוש cast-exp והמרה
נרמזת ב-if-exp:
; בתוך פונקציית value-of:
(cast-exp (typ exp1)
(let ((val (value-of exp1 env)))
(cases type typ
(int-type ()
(cases expval val
(num-val (num) val)
(bool-val (bool) (if bool (num-val 1) (num-val 0)))
(else (eopl:error 'value-of "Cannot cast to int: ~s" val))))
(bool-type ()
(cases expval val
(bool-val (bool) val)
(num-val (num) (if (zero? num) (bool-val #f) (bool-val #t)))
(else (eopl:error 'value-of "Cannot cast to bool: ~s" val)))))))
; שינוי if-exp להמרה נרמזת:
(if-exp (exp1 exp2 exp3)
(let ((val1 (value-of exp1 env)))
(let ((is-true (cases expval val1
(bool-val (b) b)
(num-val (n) (not (zero? n))) ; המרה נרמזת!
(else (eopl:error 'if "Condition must be bool or num")))))
(if is-true (value-of exp2 env) (value-of exp3 env)))))שאלה 2: לולאת do מתקדמת
do-exp (ids inits steps bools results)
- המשתנים מאותחלים באופן סדרתי ("אתחול של משתנה יכול להכיר את המשתנים שכבר אותחלו לפניו").
- בכל מחזור הלולאה נבדקים התנאים הבוליאניים לפי סדר. הראשון שאמת עוצר את הלולאה ומחזיר את תוצאתו.
- אם אין תנאי אמת, המשתנים מקודמים בצעדים (Steps). קידום המשתנים נעשה במקביל על פי ערכם של המשתנים במצב הנוכחי.
🎯 הפן הפדגוגי: מנגנון לולאות פונקציונליות
זוהי שאלת הדגל של הקורס! היא מלמדת אותנו את ההבדל הקריטי בין
סדרתי (Sequential) ל-מקבילי (Parallel) במפרשים. המשתנים באתחול נוצרים בשרשרת,
אבל בקידום (הצעדים) כולם מחושבים יחד לפני העדכון. בנוסף, השאלה מדגימה איך לממש "לולאה" שרצה
לנצח ללא שום פעולת set! פיזית, אלא אך ורק על ידי קריאה רקורסיבית לסביבה
חדשה (Lexical Shadowing) שמסתירה את הערכים הישנים.
מעקב זרימה לדוגמת המטלה (Trace)
do(
<a 0 4>
<b 7 -(a,2)>
<c -(b,1) -(a,b)>
[zero? (b) -(a,c)]
[zero? (-(c,-2)) -(a,5)]
)שלב האתחול (סדרתי):
aמקבל0.bמקבל7(הוא לא תלוי ב-a באתחול).cמקבל-(b,1). כיוון שזה סדרתי, c רואה את b, ולכן הוא מקבל-(7,1) = 6.
איטרציה 1 (סביבה: a=0, b=7, c=6):
- בדיקת תנאים: התנאי הראשון
zero?(7)נכשל. התנאי השניzero?(-(6,-2)) -> zero?(8)נכשל. הלולאה ממשיכה! - חישוב צעדים (במקביל, לפי סביבה נוכחית):
- ל-
aנוסיף4➔ מ-0 ל-4. - ל-
bנוסיף-(0,2) = -2➔ מ-7 ל-5. - ל-
cנוסיף-(0,7) = -7➔ מ-6 ל-1-.
איטרציה 2 (סביבה חדשה: a=4, b=5, c=-1):
- בדיקת תנאים: התנאי הראשון
zero?(5)נכשל. התנאי השניzero?(-(-1,-2)) -> zero?(1)נכשל. הלולאה ממשיכה. - חישוב צעדים (במקביל):
- ל-
aנוסיף4➔ מ-4 ל-8. - ל-
bנוסיף-(4,2) = 2➔ מ-5 ל-7. - ל-
cנוסיף-(4,5) = -1➔ מ-1- ל-2-.
איטרציה 3 (סביבה חדשה: a=8, b=7, c=-2):
- בדיקת תנאים: התנאי הראשון
zero?(7)נכשל. - התנאי השני:
zero?(-(-2,-2)) -> zero?(0)➔ אמת! - הלולאה נעצרת ומחזירה את תוצאת התנאי השני:
-(a,5), ומכיוון ש-a הוא 8 ➔ מוחזר הערך 3!.
מימוש טכני - הקוד שלנו
קובץ lang.scm - SLLGen יארוז את הרשימות המקבילות
אוטומטית:
(expression
("do" "("
(arbno "<" identifier expression expression ">")
(arbno "[" expression expression "]")
")")
do-exp)קובץ interp.scm - פונקציות העזר והלולאה הראשית
ב-value-of:
; פונקציית עזר לאתחול סדרתי. שימו לב שהיא מעדכנת את ה-env ככל שמתקדמים.
(define eval-inits
(lambda (ids inits env)
(if (null? ids)
env
(let ((val (value-of (car inits) env)))
(eval-inits (cdr ids) (cdr inits) (extend-env (car ids) val env))))))
; מנוע הלולאה:
(do-exp (ids inits steps bools results)
(let ((init-env (eval-inits ids inits env)))
(letrec
((loop
(lambda (curr-env)
(let ((res (check-conditions bools results curr-env)))
(if res
(car res) ; עטפנו את התוצאה ב-list במידה והוחזר #f (כדי להבדיל מכשלון בתנאי)
(let ((new-vals (eval-step-values ids steps curr-env)))
; הסתרת הערכים הישנים באמצעות extend-env-multi וריצה מחודשת
(loop (extend-env-multi ids new-vals curr-env))))))))
(loop init-env))))שפת PROC: הקבצים שיוצרים אותה
שפת PROC יורשת את המבנה משפת LET, אך מוסיפה את היכולת ליצור ולהפעיל פונקציות. השינויים המרכזיים מתבטאים בתוספת של ה-Closure והוספת הקריאה לפונקציות.
חלוקת הקבצים בשפת PROC
lang.scm- התווספו שני כללים חדשים לדקדוק:proc-exp(יצירת פונקציה) ו-call-exp(הפעלת פונקציה).data-structures.scm- הקובץ עבר שדרוג משמעותי:- התווסף ה-variant החדש ל-expval:
proc-val. - התווסף טיפוס נתונים חדש לגמרי:
procהמגדיר את הקלוז'ר (שומר את הפרמטר, גוף הפונקציה והסביבה השמורה).
- התווסף ה-variant החדש ל-expval:
interp.scm- התווספה לוגיקה ל-value-ofעבור יצירת פונקציות, והתווספה פונקציית העזר הקריטיתapply-procedureהאחראית על פתיחת הקלוז'ר והרצת הפונקציה בסביבתה השמורה.environments.scm- נותר כמעט ללא שינוי לעומת LET, שכן ניהול הזיכרון הבסיסי נשאר זהה (רשימות מקושרות).
💡 מדריך למבחן: הוספת פיצ'רים ב-PROC
כשמבקשים להרחיב את PROC (למשל Multi-parameter), הפוקוס שלכם יהיה כפול:
- ה-Closure (ב-data-structures): איך מבנה הפונקציה ישמור כעת מספר
ארגומנטים במקום אחד? (במקום לשמור
symbol?נשמורlist-of symbol?). - ההפעלה (ב-interp): ב-
apply-procedureתצטרכו להשתמש ב-extend-env*כדי לייצר סביבה מורחבת עבור מספר משתנים במקביל רגע לפני הרצת הפונקציה.
מבוא שפת PROC: פונקציות מסוג ראשון
שפת PROC (קיצור של Procedure) עושה את הקפיצה המשמעותית ביותר בקורס – היא הופכת את השפה מ"מחשבון" לשפת תכנות אמיתית. היא עושה זאת באמצעות רעיון פילוסופי עמוק: פונקציות הן אזרחים מסוג ראשון (First-Class Citizens).
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? כדי לאפשר שימוש חוזר בקוד (Code Reuse) והפשטה פרוצדורלית. פונקציות מאפשרות לנו לארוז לוגיקה תחת שם ולהריץ אותה מתי שנרצה, מה שחוסך קוד כפול ומאפשר בניית תוכניות מורכבות.
- מה לומדים מזה? את הכוח שבהחזקת פונקציה במשתנה (כמו כל משתנה מספרי אחר), את ההפרדה העמוקה שבין הגדרת הפונקציה (Abstraction) שמתבצעת בזמן ההשמה, לבין הפעלת הפונקציה (Application) שמתבצעת מאוחר יותר. בנוסף, נלמד כיצד סביבה (Closure) נשמרת.
תוספות לדקדוק (lang.scm)
בשפת PROC, אנחנו לא קוראים לזה פונקציה אלא
proc. הוספנו בסך הכל שני כללי תחביר:
; 1. יצירת פונקציה (Abstraction)
; מקביל ל-lambda בסקים. יש לה פרמטר אחד וגוף.
(expression
("proc" "(" identifier ")" expression)
proc-exp)
; 2. הפעלת פונקציה (Application / Call)
; התחביר הוא פשוט סוגריים. הביטוי השמאלי הוא הפונקציה (operator)
; והביטוי הימני הוא הארגומנט (operand).
(expression
("(" expression expression ")")
call-exp)הקפיצה ב-ExpVal ו-DenVal
אם פונקציה יכולה להישמר במשתנה ולחזור כתוצאה של חישוב, זה אומר שמערכת הטיפוסים שלנו משתנה דרסטית!
- ExpVal: {Number, Boolean, Procedure}
- DenVal: {Number, Boolean, Procedure}
כלומר, מעכשיו פונקציית apply-env עשויה להחזיר לנו
פונקציה שלמה מתוך קופסת proc-val, ונוכל להעביר פונקציות כארגומנטים לפונקציות
אחרות (Higher-Order Functions).
איך הקוד נראה בשפת PROC?
בואו נראה איך המתכנת כותב קוד בשפה שלנו. מאחר ואין לשפה מנגנון לשמירת
פונקציות בצורה גלובלית, משתמשים ב-let כדי לתת לפונקציה שם:
% מגדירים פונקציה שמקבלת x ומחסרת ממנו 1.
% ושומרים אותה במשתנה בשם f.
let f = proc (x) -(x, 1)
in
% לאחר מכן, מפעילים אותה על המספר 10
(f 10)
% התוצאה: 9הקלוז'ר וסקופ לקסיקלי מול דינמי
פונקציה היא לא סתם שורות קוד. כדי שהיא תזכור את המשתנים החיצוניים שסבבו אותה כשהיא נוצרה, היא חייבת להיות "ארוזה" במבנה מיוחד שנקרא סגור לקסיקלי (Closure). זה מוביל לדיון החשוב ביותר בקורס לגבי ניהול משתנים (Scoping).
הבעיה הקלאסית: באיזה משתנה נשתמש?
התבוננו בקוד הבא שכתוב בשפת PROC. שאלה זו (על הטיותיה) מופיעה כמעט בכל מבחן:
let x = 3
in let f = proc (z) -(z, x) % הפונקציה משתמשת ב-x (משתנה חופשי!)
in let x = 4 % כאן x השתנה ל-4.
in (f 10) % הפעלת הפונקציה.השאלה הגדולה: כשהפונקציה רצה בסוף ומחשבת
-(z, x) (כלומר 10 פחות x), באיזה x היא תשתמש? ב-3 או ב-4?
Lexical Scoping (לקסיקלי)
התוצאה: 7.
הפונקציה מצלמת את הסביבה ברגע הגדרתה. מכיוון שכשהיא נוצרה (בשורה 2) הערך של x בסביבה היה 3, ה-Closure שמר את 3. זה המודל התקני בו שפות מודרניות (ו-PROC) משתמשות.
Dynamic Scoping (דינמי)
התוצאה: 6.
הפונקציה מתעלמת מסביבת ההגדרה ובודקת את הסביבה ברגע ההפעלה. ברגע ההפעלה (בשורה 4), העדכון האחרון בזיכרון (Call Stack) קבע כי x שווה 4 ולכן זה הערך שיחושב.
מבנה ה-Closure ב-EOPL (data-structures.scm)
כדי לאפשר Lexical Scoping הלכה למעשה, שפת PROC אורזת את הפונקציה יחד עם הסביבה השמורה:
(define-datatype proc proc?
(procedure
(var symbol?) ; הפרמטר (למשל 'z')
(body expression?) ; עץ ה-AST של גוף הפונקציה
(saved-env environment?))) ; הסביבה השמורה!! זה הצילום מסך!הדמיה השוואתית: סקופ לקסיקלי מול דינמי (Lexical vs Dynamic Scoping) הדמיה אינטראקטיבית
ראו כיצד מנוע ההרצה מחפש משתנים בכל אחד מהמודלים עבור הקוד:
let x = 3 in let f = proc(z) -(z, x) in let x = 4 in (f 10)
בקרה:
שרשרת הסביבות ברגע חישוב גוף הפונקציה:
מנוע ההפעלה והרחבה לריבוי ארגומנטים
השינוי ב-interp.scm מחולק לשני שלבים:
יצירת ה-Closure (צילום הסביבה), ופתיחתו להרצה (apply-procedure). לאחר מכן, נראה כיצד מרחיבים את
השפה לריבוי ארגומנטים - שאלה פופולרית מאוד במבחנים.
יצירה והפעלה במפרש
; --- שלב 1: הגדרת הפונקציה (proc-exp) ---
; כשהמחשב קורא את הטקסט "proc (x) ...", הוא לא מריץ את הגוף!
; הוא אורז את ה-env הנוכחי בתוך ה-Closure (שלב הצילום)
(proc-exp (var body)
(proc-val (procedure var body env)))
; --- שלב 2: קריאה לפונקציה (call-exp) ---
(call-exp (rator rand)
; משיגים את הקלוז'ר (proc) ואת הערך של הארגומנט (arg)
(let ((proc (expval->proc (value-of rator env)))
(arg (value-of rand env)))
; מפעילים בעזרת מנוע היישום
(apply-procedure proc arg)))
; --- מנוע היישום: פותח את הקלוז'ר! ---
(define apply-procedure
(lambda (proc1 val)
(cases proc proc1
(procedure (var body saved-env)
; מריצים את הגוף בתוך הסביבה ה*שמורה*!
; המשתנה (var) יקבל את הערך (val), והכל מולבש מעל הזיכרון ההיסטורי.
(value-of body
(extend-env var val saved-env))))))הכנה למבחן: מימוש מולטי-ארגומנטים (Multi-parameter PROC)
בגרסה הרגילה, הפונקציה מקבלת פרמטר אחד. במבחנים נדרש פעמים רבות
להרחיב לכתיבה בסגנון: proc (x, y, z) -(x, -(y, z))
וקריאה מתאימה (f 1 2 3).
שינויי קוד מרכזיים להרחבה זו:
- בגרמטיקה (lang.scm): נשתמש ב-separated-list וב-arbno.
("proc" "(" (separated-list identifier ",") ")" expression) proc-exp("(" expression (arbno expression) ")") call-exp
- ב-data-structures.scm (טיפוס proc):
(vars (list-of symbol?)) במקום var בודד.
- ב-interp.scm (call-exp):
כיוון שיש לנו
rands(רשימה של ארגומנטים), נחשב את כולם בעזרתmap:
(args (map (lambda (rand) (value-of rand env)) rands)) - ב-apply-procedure:
שימוש בפונקציית
extend-env*שמרחיבה עבור רשימת משתנים ורשימת ערכים במקביל:
(extend-env* vars args saved-env)
פתרון ממן: סביבה דינמית, קארינג ורפלקציה
מטלה זו בוחנת את ההבנה העמוקה ביותר של שפת PROC באמצעות 3 שינויים ארכיטקטוניים מרתקים: שינוי מודל הזיכרון, מעקף מגבלות שפה באמצעות טכניקות מבוססות פונקציות בלבד, והוספת יכולת לראות "פנימה" אל תוך הטיפוסים בזמן ריצה.
1 כריכה דינמית ורקורסיה טבעית
במודל הרגיל של שפת PROC אנו משתמשים בכריכה לקסיקלית (Lexical Scoping) - פונקציה
תמיד זוכרת מאיפה היא באה. היא לוקחת איתה בתוך ה-Closure את הסביבה שבה היא הוגדרה.
בשאלה זו התבקשנו לשנות את המפרש לעבוד בכריכה דינמית (Dynamic Scoping) - פונקציה
מתעלמת מהמקום שבו נולדה, ופועלת לפי הסביבה של אתר הקריאה (Call-site) ברגע
ההפעלה שלה.
דוגמה והרצה ידנית
let a=3
in let p = proc (x) -(x,a)
in let a=5
in -(a, (p 2))- בכריכה לקסיקלית (התנהגות רגילה): הפונקציה
pמצלמת את הסביבה[a=3]. כשנקרא ל-(p 2)היא תחפש אתaותמצא 3. החישוב:2 - 3 = -1. התוצאה הסופית:5 - (-1) = 6. - בכריכה
דינמית: הפונקציה מתעלמת מ-
[a=3]. כשאנו קוראים לה מתוך הסביבה[a=5], ה-aשבגופה יקבל 5! החישוב:2 - 5 = -3. התוצאה הסופית:5 - (-3) = 8.
שינויי הקוד ב-interp.scm
כל מה שצריך לעשות הוא להעביר את סביבת אתר
הקריאה (env) מה-call-exp ישר לתוך apply-procedure
במקום להשתמש ב-saved-env.
; שלב א: קריאה לפונקציה מזהה את הסביבה
(call-exp (rator rand)
(let ((proc (expval->proc (value-of rator env)))
(arg (value-of rand env)))
; מעבירים את ה-env כפרמטר שלישי!
(apply-procedure proc arg env)))
; שלב ב: פתיחת הפונקציה מתבססת עליו
(define apply-procedure
(lambda (proc1 val env)
(cases proc proc1
(procedure (var body saved-env)
; מרחיבים את הסביבה הדינמית (env) במקום saved-env
(value-of body (extend-env var val env))))))💡 כוחה של סביבה דינמית: רקורסיה ללא Letrec!
בסעיף ב' של השאלה נדרשנו לכתוב פונקציית פיבונצ'י. בגלל שאנחנו בכריכה דינמית, רקורסיה עובדת באופן טבעי עם let בלבד. מדוע? משום שברגע שגוף הפונקציה מתחיל לרוץ, הוא מחפש את שמו של המשתנה בסביבת הקריאה - ושם הפונקציה כבר מוגדרת!
let fib = proc (n)
if zero?(-(n, 1))
then 1
else if zero?(-(n, 2))
then 1
else -((fib -(n, 1)), -(0, (fib -(n, 2))))
in (fib 5)* שימו לב להמרת חיבור לחיסור כפול: x + y מבוטא
בשפת PROC כ--(x, -(0, y)).
2 קארינג (Currying) ורקורסיית Maker
שפת PROC הסטנדרטית מאפשרת רק ארגומנט אחד לפונקציה, ואין בה רקורסיה מובנית (ללא
letrec). בשאלה זו אנו לומדים כיצד לעקוף את שתי המגבלות הללו: מעבר למספר ארגומנטים
מבוצע באמצעות Currying (פונקציה שמחזירה פונקציה), ורקורסיה מבוצעת באמצעות העברת
הפונקציה לעצמה (טכניקת Maker).
סעיף א: בדיקת זוגיות משותפת
פונקציית same-parity הבודקת אם שני
מספרים בעלי אותה זוגיות ב-Currying מלא. הקוד מבוסס על רקורסיית ה-Maker עבור
is-even.
; ה-Maker בונה בדיקת זוגיות ברקורסיה עמוקה
let is-even-maker = proc (maker)
proc (n)
if zero?(n)
then zero?(0) ; true
else if zero?(-(n, 1))
then zero?(1) ; false
else ((maker maker) -(n, 2))
in let is-even = proc (n) ((is-even-maker is-even-maker) n)
; Currying לקבל 2 משתנים (x, y)
in let same-parity = proc (x)
proc (y)
if (is-even x)
then (is-even y)
else if (is-even y) then zero?(1) else zero?(0)
in ((same-parity 4) 4) ; יחזיר #tסעיף ב: הרצת תוכנית Maker
תוכנית המממשת כפל ב-4 בצורה רקורסיבית מתוחכמת בעזרת Maker.
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)מעקב ההרצה מתבצע מהבסיס למעלה:
- x=0: returns 0
- x=1: returns -(((M M) 0) , -4) = -(0, -4) = 4
- x=2: returns -(((M M) 1) , -4) = -(4, -4) = 8
- x=3: returns -(((M M) 2) , -4) = -(8, -4) = 12
ולכן הערך המוחזר של התוכנית הוא 12.
סעיף ג: סכום בעזרת Currying ו-Maker
המטלה דורשת סכום מספרים 1 עד n. הנוסחה הקלאסית מבוצעת על ידי Accumulator (צובר) שעובר כפרמטר נוסף באמצעות Currying. כך מיישמים פעולה שדורשת שני ארגומנטים טבעיים (רקורסיה מעולה ונקייה!):
; מחשב סכום מ-n ל-0 בעזרת משתנה צובר (acc)
let sum-maker = proc (maker)
proc (n)
proc (acc)
if zero?(n)
then acc
else (((maker maker) -(n, 1)) -(acc, -(0, n)))
in let f = proc (n) (((sum-maker sum-maker) n) 0)
in (f 4) ; יחזיר 10 3 רפלקציה בזמן ריצה (Reflection)
בדרך כלל, למשתנים בזמן ריצה אין זהות, אלא רק ערך (ExpVal). בפיצ'ר ה-Reflection אנו נותנים
לתוכנית יכולת "לשאול" משתנים על הטיפוס שלהם בעזרת פעולת get-type. הפעולה מחזירה סוג
חדש של תשובה, שאותה ניתן לבדוק. הדבר מאפשר לפונקציות לשנות את התנהגותן לפי הטיפוס שמוזן להן
(Runtime Type Checking).
1. התחביר (lang.scm)
(expression
("get-type" "(" identifier ")")
get-type-exp)
(expression
("isBool?" "(" expression ")")
is-bool?-exp)
(expression
("isNum?" "(" expression ")")
is-num?-exp)
(expression
("isProc?" "(" expression ")")
is-proc?-exp)2. מבנה נתונים (data-structures.scm)
אנו מוסיפים סוג תשובה חדש ל-ExpVal בשם
type-val.
(define-datatype type-rep type-rep?
(num-type)
(bool-type)
(proc-type))
(define-datatype expval expval?
(num-val (value number?))
(bool-val (boolean boolean?))
(proc-val (proc proc?))
(type-val (t type-rep?)))3. מנוע ההפעלה (interp.scm)
(get-type-exp (id)
(let ((val (apply-env env id)))
(cases expval val
(num-val (num) (type-val (num-type)))
(bool-val (bool) (type-val (bool-type)))
(proc-val (proc) (type-val (proc-type)))
(type-val (t) (eopl:error '...)))))
(is-num?-exp (ex)
(let ((val (value-of ex env)))
(cases expval val
(type-val (t)
(cases type-rep t
(num-type () (bool-val #t))
(else (bool-val #f))))
(else (bool-val #f)))))
; * בדומה מממשים את is-bool? ו-is-proc?מעקב על תוכנית המבחן המסכמת
let a = 10
in let p = proc (w) -(w,a)
in let q = proc (something)
let t = get-type(something)
in if isNum?(t) then (p something)
else if isBool?(t) then if something then 500 else 800
else (something 50)
in (q zero?(a))- ההפעלה החיצונית: קריאה ל-
qעם הערך שלzero?(10). התוצאה היא#f, ולכןsomethingבסביבה שלqנשמר כערך בוליאני שקר. - זיהוי הטיפוס (Reflection): הפקודה
get-type(something)שולפת את הערך, מזהה שזהוbool-valומחזירה מבנה נתונים חדש -type-val(bool-type), אשר נשמר בתוךt. - ניתוב דינמי: התנאי
isNum?(t)נכשל כיוון שמדובר בטיפוס בוליאני ולא מספרי. התנאיisBool?(t)מצליח. - הכרעה סופית: אנו נכנסים לענף ה-then ומבצעים את התנאי
if something then 500 else 800. מכיוון ש-somethingבעצמו הוא ערך שקר, מוחזר המספר 800.
שפת LETREC: הקבצים שיוצרים אותה
שפת LETREC מציגה לראשונה את הפתרון ללולאות מבוססות פונקציה דרך רקורסיה. השינוי המהותי ביותר בשפה מתרחש תחת מנוע הזיכרון (הסביבה).
חלוקת הקבצים בשפת LETREC
lang.scm- התווסף הדקדוק שלletrec-expהמאפשר הגדרת פונקציה.data-structures.scm- המהפך של השפה: טיפוסenvironmentקיבל את הצורהextend-env-rec. במקום לשמור ערכים שמחושבים מראש, סביבה זו שומרת את המתכון ליצירת הפונקציה (שם הפונקציה, שם הפרמטר והגוף).environments.scm- כאן טמון הקסם של השפה: בתוךapply-envנוסף תנאי למקרה שלextend-env-recשמייצר את ה-Closure בזמן אמת.interp.scm- תהליך ההערכה (value-of) פשוט מוסיף את סביבת המתכון כשהוא נתקל ב-letrec-expופונה להרצת ה-body הראשי.
💡 מדריך למבחן: הוספת פיצ'רים ב-LETREC
עיקר שאלות המבחן יעסקו בהרחבת הרקורסיה (כמו Mutual Recursion או רקורסיה מרובת פרמטרים). המיקוד יהיה בקבצי הסביבה:
- data-structures.scm: עדכון סביבת
extend-env-recשתחזיק רשימות של שמות, רשימות של פרמטרים ורשימות של גופים. - environments.scm: עדכון מנגנון ה-JIT בתוך
apply-envכך שיחפש באינדקס ספציפי בתוך הרשימות הללו על מנת לבנות את הקלוז'ר הנכון.
פרדוקס הרקורסיה: הביצה והתרנגולת
שפת PROC היא נהדרת, אבל יש לה חיסרון קטלני אחד: אי אפשר לכתוב בה רקורסיה (Recursion). פונקציה לא יכולה לקרוא לעצמה. שפת LETREC פותחה אך ורק כדי לפתור את הפרדוקס הזיכרוני הזה ולספק לנו שפה שלמה לחלוטין מבוססת LISP.
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? כדי לתמוך ברקורסיה ובמנגנון קריאה עצמית. ללא רקורסיה, השפה שלנו חסרת יכולת לבצע חזרתיות (לולאות) והיא חלשה מדי.
- מה לומדים מזה? כיצד מתגברים על בעיית המעגליות של משתנה שצריך להכיר את עצמו כדי להיווצר, אך כדי להיווצר הוא חייב להיות מוכר קודם. נלמד לייצג סביבות מעגליות באמצעות קשירה בזמן ריצה (JIT Binding).
למה רקורסיה נכשלת ב-PROC?
נניח והיינו מנסים לכתוב פונקציית עצרת (Factorial) בשפת PROC הקיימת:
% הגדרנו את fact כמשתנה שאמור להחזיק פונקציה
let fact = proc (n)
if zero?(n) then 1 else *(n, (fact -(n,1)))
in
(fact 5)מה יקרה מאחורי הקלעים? המפרש יקרוס. למה?
- המפרש מתחיל מימין. הוא רואה
proc (n) ...ויוצר Closure. - הוא מצלם את הסביבה באותו רגע ושומר אותה ב-
saved-env. - אבל, באותו רגע, המשתנה
factעדיין לא קיים בסביבה!! השםfactנכנס לזיכרון רק אחרי שהצד הימני סיים את החישוב כולו. - כאשר הפונקציה תופעל ותנסה לעשות את הקריאה הרקורסיבית
(fact -(n,1)), הפונקציהapply-envתחפש אתfactבתוך ה-saved-envשלה (מזמן הצילום), לא תמצא אותו, ותזרוק שגיאת Unbound Variable.
סביבות מעגליות ורקורסיה הדדית
הפתרון של ספר הקורס הוא גאוני ואלגנטי. במקום לנסות ליצור "קלוז'ר שמצביע על קלוז'ר" בזמן ההגדרה (מה שיוצר לולאה אינסופית שמקריסה את המחשב), משנים את מבנה הסביבה כך שתחזיק את "המתכון" להרכבת הפונקציה רק כשצריך אותה.
עדכון הסביבות (data-structures.scm)
אנו מוסיפים צורה שלישית ל-environment. סביבה מסוג
extend-env-rec אינה מחזיקה expval כמו סביבה רגילה, אלא שומרת את
ההוראות (שם, פרמטר, גוף).
(define-datatype environment environment?
(empty-env)
(extend-env ...)
; הסביבה המעגלית מיועדת רק לפונקציות רקורסיביות:
(extend-env-rec
(p-name symbol?) ; שם הפונקציה (fact)
(b-var symbol?) ; פרמטר (n)
(p-body expression?) ; גוף (AST)
(saved-env environment?)))השינוי ב-interp.scm
הטיפול ב-letrec-exp פשוט מכניס את סביבת
המתכון הזו מתחת להערכת הגוף הראשי. הפונקציה טרם נוצרה!
(letrec-exp (p-name b-var p-body letrec-body)
(value-of letrec-body
; בתוך סביבה מורחבת מסוג רקורסיבי
(extend-env-rec p-name b-var p-body env)))הכנה למבחן: רקורסיה הדדית (Mutual Recursion)
במבחן מבקשים לעיתים לתמוך בהגדרת מספר פונקציות רקורסיביות יחד בבלוק
אחד, אשר יכולות לקרוא אחת לשנייה (למשל פונקציית even? הקוראת ל-odd?
והפוך). זה מוכר כ-extend-env-rec* או ריבוי הצהרות letrec.
מבנה הסביבה המורחב: נשתמש ברשימות עוקבות מקבילות (Parallel Lists) במקום במשתנה בודד:
(extend-env-rec*
(p-names (list-of symbol?))
(b-vars (list-of symbol?))
(p-bodies (list-of expression?))
(saved-env environment?))כיצד apply-env עובד עם רשימות אלו?
החיפוש ייעשה בעזרת פונקציית עזר למציאת האינדקס של
הפונקציה המבוקשת בתוך רשימת p-names. אם הפונקציה נמצאה באינדקס i,
נשלוף את הפרמטר והגוף מאותו האינדקס (באמצעות list-ref על b-vars
ו-p-bodies) ונרכיב מהם את הקלוז'ר בו במקום.
תרשים מעגל הסביבות של LETREC הסבר חזותי
כשפונקציה רקורסיבית מוגדרת בתוך letrec, המפרש מייצר סביבה מיוחדת מסוג
extend-env-rec. בעת חיפוש שם הפונקציה ב-apply-env, נוצר קלוז'ר שסביבתו
השמורה היא הסביבה הזו עצמה, ובכך נוצר מעגל (Circular Reference) המאפשר רקורסיה:
הקסם של apply-env: יצירה בזמן אמת
מתי הפונקציה נוצרת בפועל ואיך היא סוף סוף מכירה את עצמה? הכל קורה ברגע החיפוש! (Just-In-Time Evaluation). זהו הטריק המבריק ביותר של שפות תכנות פונקציונליות.
עדכון אלגוריתם החיפוש (environments.scm)
הוספנו מקרה שלישי ל-cases בתוך הפונקציה
apply-env האגדית:
(define apply-env
(lambda (env search-var)
(cases environment env
(empty-env () ...)
(extend-env (...) ...)
; הגענו לשכבה מעגלית.
; נבדוק האם המשתנה שמחפשים הוא הפונקציה שלנו:
(extend-env-rec (p-name b-var p-body saved-env)
(if (eqv? search-sym p-name)
; אמת! חיפשו את הפונקציה הזו.
; ברגע זה בדיוק אנחנו מייצרים את ה-Closure במקום ואורזים אותו!
; שימו לב: אנחנו נותנים ל-Closure את env.
; ה-env הזה כולל את שכבת ה-extend-env-rec של עצמה! וכך נסגר המעגל.
(proc-val (procedure b-var p-body env))
; שקר. חיפשו משהו אחר, נמשיך הלאה בסביבה השמורה.
(apply-env saved-env search-sym))))))הלוגיקה (סגירת המעגל)
בואו נחזור לדוגמה שלנו עם העצרת (fact) ונעקוב מה קורה
כשהיא קוראת לעצמה (fact -(n,1)):
- כשהקוד מגיע לקריאה ל-
fact, הוא עושהvalue-ofעל המשתנה, מה שגורם לקריאה ל-apply-env. - החיפוש יורד בשרשרת ומגיע לשכבה
extend-env-recשבה שם הפונקציה הוא "fact". יש התאמה! - הקסם קורה: אנו מייצרים Closure. במקום לתת לו את
saved-env(שאינה כוללת את fact), אנו נותנים לו אתenvשל הרגע. הסביבה הזו היא בעצמה שכבת ה-extend-env-recשלfact. - ה-Closure נארז ומוחזר למפרש כערך חישובי (ExpVal).
- בתוך הגוף הרקורסיבי, הפונקציה מנסה שוב להפעיל את
fact. היא הולכת לסביבה השמורה שלה, ושוב נכנסת ל-apply-env, שמייצר שוב את ה-Closure במקום, וכך הלאה עד לתנאי העצירה!
לסיכום: LETREC מאפשרת רקורסיה על ידי בניית סביבה שמחכה שישאלו עליה, וכששואלים עליה, היא בונה ומחזירה קלוז'ר המכיל אותה עצמה.
כתובות לקסיקליות: הקבצים שיוצרים אותה
הארכיטקטורה משתנה מהותית. קוד המקור עובר כעת שלב מקדים של תרגום לפני שהוא רץ. במקום Interpreter בלבד, יש לנו כעת מערכת משולבת של "קומפיילר" ומפרש קל משקל.
חלוקת הקבצים המעודכנת
translator.scm(קובץ חדש) - קובץ הליבה החדש של השלב הסטטי. המודול עובר על העץ המקורי ומרכיב עץ חדש (Nameless AST) בעזרת סביבה סטטית (`Senv`) שמחשבת את המיקומים (הכתובות).data-structures.scm- הקובץ התפצל לשניים: סביבה סטטית (`extend-senv` המחזיקה רק שמות), וסביבת זמן ריצה (`nameless-environment`) שהפכה מרשימה מקושרת מורכבת לרשימת סקים פשוטה (`list-of expval`). גם ה-Closure כבר לא שומר את שם המשתנה שלו.interp.scm- הפך לרזה ומהיר יותר. מתעסק אך ורק בהשמת ערכים על רשימה שטוחה ושליפה לפי אינדקס.
💡 מדריך למבחן: הוספת פיצ'רים בכתובות לקסיקליות
הוספת פיצ'ר כאן דורשת להעביר אותו בכל הצינור:
- lang.scm: הוספת התחביר פעמיים! פעם למקור ופעם לעץ ה-Nameless.
- translator.scm: כתיבת תנאי המתרגם את הפעולה מצומת מילולי לצומת נטול שמות (תוך עדכון או חיפוש ב-Senv).
- interp.scm: כתיבת כלל החישוב בפועל לצומת נטול השמות שנוצר ב-Nameless AST.
כתובות לקסיקליות: קומפילציה ותרגום
עד כה, סביבת הזיכרון שלנו עבדה באמצעות חיפוש שמות (Strings / Symbols) על פני שרשרת. זהו תהליך ארוך ולא יעיל הדורש $O(d)$ זמן, כאשר $d$ הוא העומק הלקסיקלי. בפרק זה, אנו מחלקים את העבודה לשלב של "קומפילציה" (תרגום מראש) ושלב ריצה, ובכך נפטרים משמות המשתנים כליל!
🎯 הפן הפדגוגי: מה לומדים ולמה?
- למה הוספנו את זה? כדי לפתור את חוסר היעילות של חיפוש מילולי בזיכרון. זהו השלב המקשר בין קוד מקור אנושי לבין קוד מכונה/קוד ביניים (Bytecode) יעיל. הרי במעבד אין שמות למשתנים, יש רק כתובות.
- מה לומדים מזה? את ההפרדה הקריטית בין זמן קומפילציה (Static Analysis) לזמן ריצה (Runtime). אנו לומדים כיצד ניתוח לקסיקלי סטטי מאפשר לנו לדעת מראש בדיוק היכן משתנה יימצא בזיכרון, וכך להמיר חיפוש מחרוזות לגישה ב-$O(1)$ באמצעות אינדקס של מערך.
איך זה עובד? (המרת שמות לכתובות)
בזמן הקומפילציה אנו מעבירים את ה-AST המקורי דרך מודול שנקרא
translator.scm. הוא עובר על הקוד יחד עם סביבה דמה הנקראת הסביבה הסטטית
(Senv). הסביבה הסטטית שומרת רק את שמות המשתנים (ללא ערכם, שעדיין
לא ידוע), ומטרתה לחשב את העומק של כל משתנה.
הצומת הרגיל var-exp(var) מתורגם בעץ התחבירי
החדש לצומת nameless-var-exp(n) המכיל אינדקס מספרי בלבד.
; קוד המקור (עם שמות אנושיים)
let x = 3 in let y = 4 in -(x, y)
; לאחר התרגום (AST של שפת Nameless)
; שימו לב: השמות x ו-y הוסרו מה-let ומאופרציית החיסור לחלוטין!
(nameless-let-exp 3
(nameless-let-exp 4
(diff-exp (nameless-var-exp 1) (nameless-var-exp 0))))המשתנה הפנימי ביותר y מקבל את האינדקס 0 (האחרון
שהוכנס לזיכרון והקרוב ביותר לסקופ), והמשתנה x מקבל את האינדקס 1.
מחשב כתובות לקסיקליות אינטראקטיבי הדמיה אינטראקטיבית
עמדו עם העכבר או לחצו על המשתנים שבתוך פעולת החיסור בשורה התחתונה כדי לראות כיצד מתבצע התרגום הסטטי לאינדקסים (Nameless Variables):
חישוב מול הסביבה הסטטית (Senv):
קוד התרגום המרכזי (translator.scm)
המנגנון שעובר על העץ ובאופן שיטתי מחליף כל הופעה של שם בכתובת המחושבת מהסביבה הסטטית.
(define translation-of
(lambda (exp senv)
(cases expression exp
; קריאה למשתנה מתורגמת לאינדקס המספרי בעזרת הסביבה הסטטית
(var-exp (var)
(nameless-var-exp
(apply-senv senv var)))
; הגדרת המשתנה (let) משמיטה את שם המשתנה מהצומת החדש
; ומרחיבה את הסביבה הסטטית עבור בדיקת הגוף הפנימי (body)
(let-exp (var exp1 body)
(nameless-let-exp
(translation-of exp1 senv)
(translation-of body
(extend-senv var senv))))
; אותו הדבר בדיוק מתרחש בפונקציה (proc)!
(proc-exp (var body)
(nameless-proc-exp
(translation-of body
(extend-senv var senv))))
...)))המפרש נטול השמות: Nameless Interpreter
לאחר שלב התרגום, אנו מקבלים עץ מסוג
Nameless-program. עץ זה מועבר לפונקציה value-of שונה לחלוטין. השינוי המהפכני כאן
מתרחש בניהול הזיכרון – הסביבה הופכת לרשימה פשוטה של ערכים, ללא כל קשר לטקסט המקורי. מהירות הריצה
עולה דרמטית.
סביבת Nameless-env פשוטה ויעילה
בקובץ data-structures.scm, הסביבה
(Environment) היא כעת בסך הכל רשימה שטוחה של expval. השליפה מתבצעת בעזרת הפקודה
המובנית list-ref שמגיעה במהירות לאיבר ה-n.
; מבנה הסביבה
(define nameless-environment?
(lambda (x) ((list-of expval?) x)))
; הרחבה - פשוט שמים את הערך בראש הרשימה! (cons)
(define extend-nameless-env
(lambda (val nameless-env)
(cons val nameless-env)))
; שליפה - גישה ישירה לפי אינדקס n המקומפל
(define apply-nameless-env
(lambda (nameless-env n)
(list-ref nameless-env n)))גם ה-Closure עבר דיאטה
טיפוס הפרוצדורה המקומפל (Nameless) אינו צריך יותר לשמור את שם הפרמטר שלו (b-var). הפרמטר פשוט יקבל את האינדקס 0 בעת כניסה לגוף הפונקציה בזמן ריצה.
(define-datatype proc proc?
(procedure
; שימו לב! אין כאן (var symbol?) בשדות!!
(body expression?)
(env nameless-environment?)))פונקציית value-of במפרש המקומפל
כך נראית התוצאה הסופית בקובץ interp.scm. מנוע
ההרצה הפך להיות יעיל, רזה, ומשולל התעסקות עם מחרוזות מילוליות.
(define value-of
(lambda (exp nameless-env)
(cases expression exp
; הגישה למשתנה קוראת ישר לאינדקס מהסביבה
(nameless-var-exp (n)
(apply-nameless-env nameless-env n))
; השמת ה-let פשוט מוסיפה את הערך המחושב (val)
; להיות האיבר הראשון ברשימת הסביבה
(nameless-let-exp (exp1 body)
(let ((val (value-of exp1 nameless-env)))
(value-of body
(extend-nameless-env val nameless-env))))
; יצירת הפונקציה לוקחת רק את הגוף והסביבה (ללא משתנים)
(nameless-proc-exp (body)
(proc-val
(procedure body nameless-env)))
...)))ניהול ידני: הקבצים שיוצרים אותה
בפרקים הקודמים (LET, PROC) עבדנו בעולם שבו משתנים
אינם משתנים (Immutable). בפרק 4 אנו מכניסים לראשונה את תופעות הלוואי (Side
Effects) ואת מערכת ניהול הזיכרון בעזרת קובץ חדש ומרכזי בארכיטקטורה:
store.scm.
store.scm (חדש!)
מודול הזיכרון הראשי. מגדיר מערך גלובלי השומר את הערכים, ומספק את פונקציות הליבה להקצאה וקריאה.
lang.scm
הורחב עם הפקודות newref, deref,
setref ו-begin.
data-structures.scm
הטיפוס expval הורחב להכיל
ref-val - עטיפה מיוחדת לכתובות זיכרון.
environments.scm
בשפת EXPLICIT, הסביבה נותרת ללא שינוי -
משתנה רגיל יכול להצביע למספר, ורק משתנה שנוצר עם newref יקבל כתובת.
צללילה לקובץ store.scm
"המפרש הטיפש ביותר בעולם לזיכרון": ה-Store ממומש פשוט כרשימה (List) ב-Racket, וכתובת זיכרון (Reference) היא פשוט אינדקס (מספר שלם) בתוך הרשימה הזו.
(define the-store 'uninitialized)
;; הקצאת תא חדש. הערך נדחף לסוף הרשימה ומוחזר האינדקס שלו.
(define newref
(lambda (val)
(let ((next-ref (length the-store)))
(set! the-store (append the-store (list val)))
next-ref)))
;; שליפת ערך. ניגשים למקום ה-ref ברשימה.
(define deref
(lambda (ref)
(list-ref the-store ref)))הערה: פונקציית setref!
יוצרת עותק חדש של כל רשימת ה-Store עם התא המעודכן ושומרת אותו. זה לא יעיל, אבל עובד מצוין
לצורך למידה.
למה בכלל צריך זיכרון מחוץ לסביבה (Environment)?
עד עכשיו, הסביבה (Environment) קשרה ישירות בין שם לערך:
x -> 5. אי אפשר היה לשנות את הערך של x ללא יצירת סביבה חדשה לגמרי. כדי
לאפשר למשתנה להשתנות (Mutation), אנו מפצלים את התהליך:
x -> Ref(0)
Ref(0) -> 5
ניתן לדריסה!
ניהול ידני: Pointers
בשפת EXPLICIT-REFS המתכנת שולט בזיכרון בצורה ידנית ומפורשת (בדומה לשפת C). רוצה זיכרון? תקצה אותו. רוצה לקרוא? תשלוף במפורש.
4 הפקודות החדשות בדקדוק
Expression ::= newref ( Expression )
newref-exp (exp1)
Expression ::= deref ( Expression )
deref-exp (exp1)
Expression ::= setref ( Expression , Expression )
setref-exp (exp1 exp2)
Expression ::= begin Expression {; Expression}* end
begin-exp (exp1 exps)
מה כל פקודה עושה?
- newref(val): לוקח ערך, מקצה לו תא ב-Store, ומחזיר את הכתובת (Reference).
- deref(ref): מקבל כתובת, הולך ל-Store ומחזיר את הערך שיש שם.
- setref(ref, val): מקבל כתובת וערך, ודורס את התוכן הישן. מחזיר ערך שרירותי (למשל 23).
- begin: פקודה קריטית! מכיוון ש-
setrefמבצע שינוי ולא חישוב מתמטי טהור, חובה להריץ רצף פקודות ולספק תוצאה בסוף.beginמריץ סדרה ומחזיר את הערך של האחרונה.
💡 דוגמת קוד בשפה: איך זה נראה למתכנת?
שימו לב לסרבול: יש להשתמש ב-deref בכל פעם שרוצים לגשת
לערך שנמצא בכתובת.
let x = newref(0) % מקצה כתובת. x הוא *מצביע* ל-0
in begin
setref(x, 1) ; % משנה את התוכן של הכתובת ל-1
-(deref(x), -5) % שולף במפורש את ה-1, ומחסר מינוס 5
end
% תוצאה: 6המפרש: newref, deref, setref
איך פונקציית value-of
(ב-interp.scm) מפעילה את הפקודות על מודול הזיכרון שלנו.
(cases expression exp
...
; 1. הקצאת זיכרון: חשב את הביטוי, צור תא ב-Store, וארוז את הכתובת כ-ref-val
(newref-exp (exp1)
(let ((v1 (value-of exp1 env)))
(ref-val (newref v1))))
; 2. קריאה מזיכרון: חשב ביטוי (שחייב להחזיר כתובת), חלץ אותה, ושלוף מה-Store
(deref-exp (exp1)
(let ((v1 (value-of exp1 env)))
(let ((ref1 (expval->ref v1))) ; שלוף את המספר של האינדקס
(deref ref1))))
; 3. כתיבה לזיכרון: חשב כתובת, חשב ערך חדש, ודרוס!
(setref-exp (exp1 exp2)
(let ((ref (expval->ref (value-of exp1 env))))
(let ((v2 (value-of exp2 env)))
(begin
(setref! ref v2)
(num-val 23))))) ; פקודות מחזירות "ערך דאמי" (23) מכיוון שחובה להחזיר ExpVal
; 4. הרצת בלוק (begin): לולאה שמריצה את כל הפקודות ומחזירה את האחרונה
(begin-exp (exp1 exps)
(letrec ((value-of-begins
(lambda (e1 es)
(let ((v1 (value-of e1 env)))
(if (null? es)
v1 ; הגענו לפקודה האחרונה - נחזיר אותה
(value-of-begins (car es) (cdr es)))))))
(value-of-begins exp1 exps)))
)השפה המודרנית: הקבצים שיוצרים אותה
שפת EXPLICIT הייתה מעצבנת לכתיבה. בשפות מודרניות (JavaScript, Python) המפרש מבצע עבורנו את פעולות ההקצאה והקריאה בסתר (Implicitly). שפה זו מספקת חוויית פיתוח חלקה, אך דורשת שינוי ארכיטקטוני עמוק.
הקובץ שעבר רעידת אדמה: environments.scm
ב-IMPLICIT-REFS חל חוק הברזל החדש: הסביבה מכילה תמיד אך ורק כתובות זיכרון! (References). כתוצאה מכך, הפונקציות שמייצרות סביבות צריכות לייצר תאים ב-Store באופן עצמאי.
;; ה-init-env המסורתי הפסיק להשתמש ישירות ב-(num-val 1) ועטף הכל ב-newref
(define init-env
(lambda ()
(extend-env
'i (newref (num-val 1))
(extend-env
'v (newref (num-val 5)) ...))))
;; גם בסביבות רקורסיביות, apply-env יוצר newref בזמן אמת עבור קלוז'רים!
(extend-env-rec* (p-names b-vars p-bodies saved-env)
(let ((n (location search-var p-names)))
(if n
(newref ; <-- התוספת החיונית שנופלים עליה במבחנים!
(proc-val
(procedure (list-ref b-vars n) ...)))
(apply-env saved-env search-var))))lang.scm
הפקודות newref ו-deref
נמחקו לחלוטין מהשפה! השארנו רק פקודת השמה אחת שהפכה לפשוטה:
set x = 10 (נקראת assign-exp).
interp.scm
כל מקום שמוסיף משתנה לסביבה (כמו פקודת let
ו-apply-procedure) עוודכן לקרוא ל-newref, וכל קריאת משתנה
(var-exp) קוראת כעת ל-deref באופן סמוי.
store.scm & data-structures.scm
נשארו כמעט ללא שינוי לעומת EXPLICIT-REFS. הזיכרון פועל באותה צורה, פשוט קוראים לו פחות באופן ידני.
ניהול אוטומטי: המודל המודרני
שינוי הפרדיגמה הגדול: Denoted Values הם רק כתובות (References)! השפה מקצה זיכרון כשהיא צריכה, וקוראת זיכרון אוטומטית כשאנחנו מבקשים משתנה.
1. הקצאה סמויה (Allocation)
מתי נוצר משתנה חדש? כאשר אנו קוראים
ל-let x = ... או מפעילים פונקציה. ברגעים אלו המפרש מבצע newref
ומכניס את הכתובת לסביבה.
2. שליפה סמויה (Deref)
כאשר כותבים בקוד שם של משתנה (למשל
x), הסביבה מחזירה כתובת בזיכרון, ואז המפרש מבצע עליה deref באופן
אוטומטי לחלוטין כדי לחלץ ולמסור את הערך האמיתי.
3. השמה סמויה (Set)
כדי לעדכן משתנה פשוט כותבים
set x = 10. המפרש מוצא את הכתובת של x בסביבה ומעדכן ישירות ב-Store.
סימולטור השוואה: סביבה (Environment) מול זיכרון (Store) הדמיה אינטראקטיבית
בחר שפה כדי לראות כיצד המשתנה מוקצה ומעודכן בזיכרון. שימו לב להבדל בערכים של ה-Environment (האם המשתנה מצביע לערך מפורש של כתובת או למיקום פיזי בזיכרון):
קוד המקור:
let x = newref(5) in setref(x, 10)
טבלת הסביבה (Environment):
| משתנה (Var) | ערך בסביבה (Denoted Value) |
|---|---|
| סביבה ריקה | |
* Denoted Values מייצג את הערכים השמורים ישירות בסביבה.
טבלת הזיכרון (Store):
| כתובת (Ref) | ערך בזיכרון (Expressed Value) |
|---|---|
| זיכרון ריק | |
💡 דוגמת קוד בשפה: כמה זה נראה טבעי!
שימו לב כמה הקוד כעת נקי, ללא שום newref או
deref.
let x = 0
in begin
set x = 1;
-(x, -5)
end
% תוצאה: 6המפרש: הקצאה ושליפה סמויה
כך נראה הקסם מאחורי הקלעים בפונקציית
value-of. מודל זה משמש תשתית ל-90% מהשאלות במבחנים הכוללות שינוי זיכרון.
(cases expression exp
...
; 1. משתנה רגיל - שליפה אוטומטית (Deref)
(var-exp (var)
; apply-env מחזיר לנו תמיד כתובת (Reference). חובה לעשות deref!
(deref (apply-env env var)))
; 2. פקודת Set - השמה קלה וטבעית למתכנת
(assign-exp (var exp1)
(begin
; apply-env יביא לנו את הכתובת של var במקום להשתמש ב-ref ידני
(setref! (apply-env env var) (value-of exp1 env))
(num-val 27)))
; 3. פקודת Let - הקצאה אוטומטית למשתנים חדשים
(let-exp (var exp1 body)
(let ((val1 (value-of exp1 env)))
(value-of body
; חובה!! אנו מכניסים לסביבה רק כתובות. לכן עוטפים את הערך ב-newref.
(extend-env var (newref val1) env))))
)
; ==========================================================
; 4. הקריאה לפונקציה - כאן נוצר ה-Local Scope והעותק העצמאי לפרמטר!
; ==========================================================
(define apply-procedure
(lambda (proc1 val)
(cases proc proc1
(procedure (var body saved-env)
(value-of body
; יצירת תא זיכרון *חדש* עבור הארגומנט במעמד קריאת הפונקציה
(extend-env var (newref val) saved-env))))))פתרון ממן: העמסת פרוצדורות (Overloading)
מטלה זו משדרגת את שפת IMPLICIT-REFS לאחת היכולות החשובות בשפות מודרניות מונחות עצמים (כמו Java ו-C++): פולימורפיזם מסוג Overloading. משתנה יחיד יכול להחזיק תחתיו מספר רב של מימושי פרוצדורה. המפרש מבצע Dynamic Dispatch (ניתוב דינמי) בזמן ריצה ובוחר את הגרסה המתאימה בהתאם לטיפוס הארגומנט שנשלח אליה בפועל.
1 השינוי הארכיטקטוני
בשפת IMPLICIT-REFS הרגילה, פרוצדורה נשמרת בזיכרון כרשומה פשוטה
(procedure var body env). במטלה זו, אנו משנים את אופי הפרוצדורה כך שתהפוך למכולה
(Container) המחזיקה רשימה של מקרים. כל מקרה מייצג גרסה שונה של הפרוצדורה עבור סוג פרמטר שונה
(int, bool או func).
שלב א': תחביר השפה (lang.scm)
מוסיפים טיפוס חוקים חדש ומעדכנים את הגדרת הפרוצדורה וההעמסה:
; 1. הגדרת טיפוסים (Type) חדשים בדקדוק
(type ("int") int-type)
(type ("bool") bool-type)
(type ("func") func-type)
; 2. פרוצדורה כעת דורשת ציון טיפוס לפרמטר
(expression
("proc" "(" type identifier ")" expression)
proc-exp)
; 3. פעולת ה-Overload הדורסת או מוסיפה גרסה
(expression
("overload" identifier "with" "(" type identifier ")" expression)
overload-exp)שלב ב': מבנה הנתונים (data-structures)
הפרוצדורה מיוצגת כעת כ-overloaded-proc
המכיל רשימה של רשימות. כל מקרה מורכב מטיפוס, משתנה, גוף, וסביבה נשמרת (Lexical Scope).
(define-datatype proc proc?
(overloaded-proc
(cases list?))) ; רשימה של (type var body env)
; תמיכה בהדפסה נקייה לקונסולה (expval->printable)
(define expval->printable
(lambda (val)
(cases expval val
(proc-val (p)
(cases proc p
(overloaded-proc (cases-list)
(list 'overloaded-proc
(map (lambda (c)
(list (cadr c) '...
(env->list (cadddr c))))
cases-list)))))
(else val))))2 מנוע הביצוע (interp.scm) וניתוב בזמן ריצה
כיצד מתבצע הקסם? פעולת ה-overload שולפת את הכתובת של המשתנה בסביבה הלקסיקלית
הנוכחית, ופונה ישירות אל ה-Store כדי לעדכן את רשימת המקרים. בזמן הפעלת הפרוצדורה
ב-call-exp, אנו מנתחים את הטיפוס בזמן ריצה (Runtime Type) של הארגומנט, ומחפשים
ברשימה את הגרסה התואמת.
💡 ניהול הזיכרון בעת Overload
כיוון שאנו בשפת IMPLICIT-REFS, המשתנה המכיל את הפרוצדורה קיים
ככתובת בזיכרון. פעולת ה-Overload עושה פעולת Side-Effect קלאסית: שולפת בעזרת
deref, מוסיפה את הגרסה לרשימה הפנימית, ושומרת בחזרה בעזרת setref!.
הגרסה החדשה שומרת את סביבתה הלקסיקלית המעודכנת (env) ללא קשר לגרסאות האחרות!
מנגנון הדיספאץ' (Dynamic Dispatch) הפנימי
; 1. מחלץ את הטיפוס (type-rep) מערך בזמן ריצה (expval)
(define get-arg-type
(lambda (val)
(cases expval val
(num-val (num) (int-type))
(bool-val (bool) (bool-type))
(proc-val (proc1) (func-type))
(else (eopl:error 'get-arg-type "Unsupported...")))))
; 2. חיפוש התאמה (Type Matching) ברשימת הגרסאות של הפרוצדורה
(define apply-procedure
(lambda (proc1 arg)
(cases proc proc1
(overloaded-proc (cases-list)
(let* ((arg-type (get-arg-type arg))
(matching-case (find-case cases-list arg-type)))
(if matching-case
(let ((typ (car matching-case))
(var (cadr matching-case))
(body (caddr matching-case))
(saved-env (cadddr matching-case)))
; הרצת הגרסה המתאימה תוך שמירה על עקרון IMPLICIT-REFS
; יוצרים תא זיכרון חדש עבור הפרמטר!
(value-of body (extend-env var (newref arg) saved-env)))
(eopl:error 'apply-procedure
"No procedure found with ~s argument" arg-type)))))))3 מעקב ריצה (Trace) - דוגמה מסכמת
בחינת דוגמת ההרצה מתוך המטלה המדגימה החלפה, עדכון ודריסה של גרסאות הפרוצדורה p.
let sum = 0
in let p = proc (int a) -(a,10)
in begin
set sum = -(sum, -(0, (p 100))); % 1. הוספת ערך מ-p(int)
overload p with (bool b) if b then 700 else 1000; % 2. יצירת גרסה בוליאנית
set sum = -(sum, -(0, (p zero?(5)))); % 3. הוספת ערך מ-p(bool)
overload p with (int r) -(r,300); % 4. דריסת הגרסה המספרית הקיימת!
set sum = -(sum, -(0, (p 100))); % 5. הוספת ערך מ-p(int) המעודכן
overload p with (func f) (f 30); % 6. יצירת גרסה המקבלת פרוצדורה
set sum = -(sum, -(0, (p proc (int w) -(w,50)))); % 7. הוספת ערך מ-p(func)
sum
end| שלב | פעולה (קריאה / השמה) | ניתוב (Dispatch) | חישוב | ערך ה-sum |
|---|---|---|---|---|
| 1 | (p 100) |
גרסת int (הראשונה) |
100 - 10 = 90 |
0 + 90 = 90 |
| 2 & 3 | (p zero?(5))ארגומנט מוערך ל-#f |
גרסת bool (חדשה) |
if #f then 700 else 1000 = 1000
|
90 + 1000 = 1090 |
| 4 & 5 | (p 100) |
גרסת int (מעודכנת) |
100 - 300 = -200 |
1090 + (-200) = 890 |
| 6 & 7 | (p proc(w)...) |
גרסת func |
f(30) -> 30 - 50 = -20 |
890 + (-20) = 870 |
תוצאה סופית: 870
זוגות משתנים: הקבצים שיוצרים אותה
עד כה השתמשנו במשתנים "פשוטים". בפרק זה השפה מורחבת לתמיכה במבני נתונים מתקדמים (Mutable Pairs), בדומה לרשימות בסיסיות או אובייקטים. זה מאפשר בניית נתונים המקושרים זה לזה באמצעות מצביעים.
pairval1.scm / pairval2.scm
מכילים את המימושים בפועל לאיך שומרים שני ערכים תחת "ישות" אחת בזיכרון.
lang.scm
נוספו הפקודות החשובות: newpair,
left, right, setleft, setright.
interp.scm
מעביר את הפקודות מה-AST אל הפונקציות המוגדרות בקבצי המימוש (`setleft` וכו').
קובץ התצורה pairvals.scm
בספר EOPL מוצגים שני מימושים חלופיים
לחלוטין של זוגות, שניהם חיים באותה תיקייה תחת הקבצים pairval1.scm
ו-pairval2.scm. הקובץ השלישי הוא פשוט מתג (Switch) שמאפשר להחליף ביניהם בקלות
לפני ההרצה.
(module pairvals (lib "eopl.ss" "eopl")
;; כדי לשנות מימוש, מגיבים/מסירים את ההערות:
;; (require "pairval1.scm")
;; (provide (all-from "pairval1.scm"))
(require "pairval2.scm")
(provide (all-from "pairval2.scm"))
)מבנה זוגות משתנים: רשימות מקושרות
5 הפקודות החדשות (כמו ב-LISP)
Expression ::= pair ( Expression , Expression )
newpair-exp (exp1 exp2)
Expression ::= left ( Expression )
left-exp (exp1)
Expression ::= right ( Expression )
right-exp (exp1)
Expression ::= setleft ( Expression , Expression )
setleft-exp (exp1 exp2)
Expression ::= setright ( Expression , Expression )
setright-exp (exp1 exp2)
מדוע זוגות הם כה קריטיים?
בעזרת האובייקט הפשוט pair ניתן לבנות עולמות
שלמים:
- רשימות מקושרות: אם ה-
rightשל הזוג מצביע לזוג נוסף, יצרנו רשימה ארוכה שניתנת לשינוי. - עצים וגרפים: אם זוג מצביע לעוד שני זוגות, יש לנו עץ בינארי שבו נוכל
לקפוץ מצומת לצומת ולשנות ערכים בזמן ריצה בעזרת
setleft/setright.
הערך mutpair-val התווסף
ל-expval, כך שכל זוג יכול להיות שמור בתוך משתנה בסביבה או להיות פלט של פונקציה.
סימולטור זוגות משתנים: דיאגרמת קופסאות וחצים (Cons-Cell Box Pointer) הדמיה אינטראקטיבית
חקרו כיצד נבנים ומקודדים מבני נתונים בזיכרון של שפת MUTABLE-PAIRS. בחרו מבנה נתונים, שנו את הקישורים שלו, וראו כיצד החצים והזיכרון משתנים בהתאמה.
שינוי המבנה (Mutations):
תרשים תאי הזיכרון (Cons-Cells):
המפרש: שני מימושים שונים
היופי בספר הוא הדגמת שתי ארכיטקטורות שונות לגמרי לשמירת הזוגות בזיכרון, בלי שהמתכנת (הלקוח של השפה) ישים לב לשינוי!
גישה 1
(pairval1.scm)
מבנה נתונים מפורש עם
שני מצביעים
גישה "גבוהה": הטיפוס mutpair עצמו הוא עטיפה
(Record) המכילה בדיוק שתי כתובות זיכרון נפרדות.
;; מבנה הנתונים: זוג המכיל שתי כתובות פנימיות
(define-datatype mutpair mutpair?
(a-pair (left-loc reference?) (right-loc reference?)))
;; יצירת הזוג עושה 2 קריאות ל-newref
(define make-pair
(lambda (val1 val2)
(a-pair (newref val1) (newref val2))))
;; קריאה לצד ימין - שולפים את הכתובת הימנית וקוראים לה
(define right
(lambda (p)
(cases mutpair p
(a-pair (l-loc r-loc) (deref r-loc)))))היתרון: בטוח מאוד לשימוש (Type-safe).
גישה 2
(pairval2.scm)
מתכנת C - תאים עוקבים
ברצף (Arrays)
גישה מתקדמת יותר הדורשת ש-newref יקצה זיכרון
בסדר עולה ברצף. זוג הוא בסך הכל מצביע יחיד p. צד ימין הוא אוטומטית
p + 1!
;; הזוג הוא רק כתובת המספר הבסיסי ב-Store
(define mutpair? reference?)
;; יוצרים שני תאים, אבל מחזירים רק את הראשון!
(define make-pair
(lambda (val1 val2)
(let ((ref1 (newref val1)))
(let ((ref2 (newref val2)))
ref1)))) ; אנו מסתמכים על כך ש-ref2 הוא ref1+1
;; צד ימין? פשוט מבקשים את הערך בכתובת p+1!
(define right
(lambda (p)
(deref (+ 1 p))))היתרון: חיסכון עצום בזיכרון, פחות אובייקטים.
שיטות לקריאה: הקבצים שיוצרים אותה
שאלות תיאורטיות על העברת פרמטרים הן ודאיות בכל
מבחן. בפרקים אלו השפה משנה את החוקים הבסיסיים של כיצד ארגומנטים נארזים ונשלחים לפונקציות. נסקור
אילו קבצים ספגו את עיקר המהפכה עבור call-by-reference ו-call-by-need.
קובץ המהפכה: interp.scm
עד עכשיו, פונקציית העזר apply-procedure
קיבלה את הפונקציה ואת הערך המחושב (ExpVal) של הארגומנט. כעת, אנו מוסיפים
פונקציה מתווכת חדשה: value-of-operand!
כאשר מבצעים קריאה לפונקציה בעזרת
call-exp (rator rand), במקום לעשות סתם (value-of rand) אנו שולחים
את הארגומנט אל המתווך. המתווך יכול להחליט:
- לייצר עותק של הזיכרון (CBV)
- למסור את הכתובת הקיימת (CBR)
- לארוז את העץ בקופסה לעתיד ללא חישוב (CBN / Lazy)
data-structures.scm (עצלנות בלבד)
בשפת call-by-need מתווסף מבנה נתונים בשם
thunk, שתפקידו לכלוא בתוכו expression? (עץ שלא חושב עדיין) יחד
עם ה-environment? שלו, עד לרגע שבו נזדקק לו.
environments.scm / store.scm
ללא שינוי, ממשיכים לעבוד באותו מודל Reference של IMPLICIT-REFS שבו כל משתנה בסביבה מצביע לתא ב-Store.
Call by Value (לפי ערך)
השיטה המוכרת משפות IMPLICIT-REFS, Java או Python. הארגומנט מחושב עד הסוף לפני הקריאה לפונקציה, והפונקציה מקבלת תא זיכרון (Reference) חדש לגמרי שהוא בסך הכל "עותק מקומי".
הסבר המנגנון: Copy / Newref
ב-CBV, פונקציית ההפעלה עושה את הפעולה:
(extend-env var (newref val) saved-env). בגלל ה-newref הזה, המשתנה
var בתוך הפונקציה מוגן. אם נעשה עליו set, הוא ידרוס אך ורק את התא
הזיכרון החדש שנוצר, ולא ישפיע על משתנים מחוץ לפונקציה.
מבחן יבש (Trace Test)
let x = 10
in let f = proc (y)
begin
set y = 20; % משנים את הפרמטר הפנימי
y
end
in begin
(f x); % קריאה לפונקציה עם המשתנה x
x % מה יהיה הערך של x כאן?
endתשובה: התוצאה היא 10.
כאשר העברנו את x (שיושב בתא 0), המערכת קראה את ה-10 שבתא 0
ויצרה תא חדש (תא 1) עבור y והכניסה לתוכו 10. ההשמה set y = 20 דרסה רק
את תא 1! תא 0 של x נשאר 10.
הדמיה השוואתית: העברת פרמטרים CBV מול CBR הדמיה אינטראקטיבית
ראו כיצד משתנים מוקצים בזיכרון (Store) ומקושרים בסביבה (Environment) בכל אחד מהמודלים עבור הקוד:
let x = 10 in let f = proc(y) begin set y = 20; y end in begin (f x); x end
בקרה:
Environment (הסביבה לקסיקלית):
Store (הזיכרון הגלובלי):
Call by Reference (לפי הפניה)
שיטה המוכרת מ-C++ (בעזרת `&`) המעניקה לפונקציה גישה "כירורגית" ומסוכנת לתאי הזיכרון המקוריים של המשתנים שנשלחו אליה. המטרה: לייצר מנגנון של Alias (כינוי נוסף לאותו תא).
מתווך הארגומנטים: value-of-operand
;; במקום לעשות סתם value-of שמחשב את הערך, המתווך בודק:
(define value-of-operand
(lambda (exp env)
(cases expression exp
;; אם הארגומנט ששלחו לי הוא משתנה נקי (כמו 'x')
(var-exp (var)
;; אל תעשה deref! פשוט תעביר את הכתובת של 'x' ישירות!
(apply-env env var))
;; אם זה ביטוי מתמטי (כמו '+ 1 2' או סתם '5')
(else
;; תחשב כרגיל, ותיצור עבורו newref משלו כ-Fallback
(newref (value-of exp env))))))
;; בפונקציית ההפעלה - אין יותר newref! הפרמטר מקבל את הכתובת הגולמית:
(define apply-procedure
(lambda (proc1 val)
...
(extend-env var val saved-env)))מבחן יבש (Trace Test)
ניקח את אותו הקוד מ-CBV:
let x = 10
in let f = proc (y)
begin set y = 20; y end
in begin (f x); x endתשובה: התוצאה היא 20!
כשהעברנו את x (נניח שתא 0), המתווך
value-of-operand תפס את זה, ובגלל שזה var-exp, הוא החזיר לפונקציה את
המספר 0 (הכתובת המקורית). הפרמטר y נקשר לתא 0. הפעולה set y = 20 דרסה
את תא 0, ולכן x החיצוני השתנה!
Call by Name / Need (עצלנות)
משפחת ה-Lazy Evaluation (הערכה עצלנית) המוכרת מ-Haskell. למה לחשב ארגומנט מורכב ולבזבז זמן אם הפונקציה בסוף בכלל לא משתמשת בו? במקום תוצאה מחושבת, אנו מעבירים הבטחה: Thunk.
יצירת ה-Thunk והשליפה (Deref) החכמה
;; המתווך: במקום לחשב, נארוז בעטיפת Thunk ונשמור ב-Store!
(define value-of-operand
(lambda (exp env)
(cases expression exp
(var-exp (var) (apply-env env var)) ; מעביר Reference (כמו CBR)
(else (newref (a-thunk exp env)))))) ; Thunk! לא מריץ value-of!!
;; פריקת ה-Thunk מתרחשת אך ורק כששולפים משתנה:
(var-exp (var)
(let* ((ref1 (apply-env env var))
(w (deref ref1))) ; הבאנו את תוכן התא
(if (expval? w)
w ; זה מספר רגיל, תחזיר אותו
(let ((v1 (value-of-thunk w))) ; זה Thunk! הרץ אותו עכשיו!
(begin
(setref! ref1 v1) ; Call-by-Need: שומרים את התוצאה למען העתיד!
v1)))))ההבדל בין Name ל-Need
Call by Name: ללא Memoization. בכל פעם
שהקוד קורא ל-var-exp, הוא מריץ את ה-Thunk מחדש. זה עלול לחשב המון פעמים את אותה
מתמטיקה כבדה.
בשביל Name, פשוט מוחקים את שורת
ה-(setref! ref1 v1) מהקוד.
Call by Need: משתמש ב-Memoization. הרצה אחת, והתוצאה נשמרת ב-Store ודורסת את ה-Thunk! בפעמים הבאות נקבל מספר מיד. זוהי ההתנהגות בפועל בקוד שראינו.
למה עצלנות ו-Side Effects שונאים זה את זה?
תארו לכם שהארגומנט שלנו הוא פונקציה שעושה print או
מעלה Counter פנימי ב-1, והפרמטר הוא y.
- ב-CBV: ה-Counter יעלה בדיוק פעם אחת (כשקוראים לפונקציה).
- ב-CBN (Name): ה-Counter יעלה כל פעם שכותבים
yבפונקציה! (תוצאה משוגעת). - ב-CBN (Need): ה-Counter יעלה פעם אחת מתישהו בזמן ריצת הפונקציה (מתי שמשתמשים ב-y בפעם הראשונה).
החוסר יכולת לחזות מתי ומי יריץ את ההדפסה הוא הסיבה ששפות פונקציונליות עצלניות כגון Haskell אוסרות על תופעות לוואי לחלוטין!
למה צריך מערכות טיפוסים (Type Systems)?
עד עכשיו, השפות שבנינו (LET, PROC, IMPLICIT-REFS)
היו שפות שבדקו טיפוסים בזמן ריצה (Run-time / Dynamic Typing). מה זה אומר? אם
המתכנת עשה טעות וכתב -(5, true), המפרש שלנו התחיל לעבוד, ניסה לעשות
expval->num לבוליאני, ואז קרס עם שגיאה באמצע הריצה.
הבעיה עם גילוי שגיאות מאוחר
דמיינו מערכת להטסת חללית. הפונקציה deployParachute()
נקראת רק כאשר גובה החללית יורד מתחת ל-1000 מטר. אם בפונקציה הזו יש שגיאת טיפוס (למשל, מנסים
להכפיל פונקציה במספר), אנחנו נגלה את זה רק בזמן שהחללית נופלת! זה מאוחר מדי.
המטרה של פרק 7 היא ליצור שפות שתופסות את השגיאות האלו לפני שהתוכנית בכלל מתחילה לרוץ (Compile-time / Static Typing).
מה זה "טיפוס" (Type)?
טיפוס הוא תווית שמודבקת לכל ביטוי בשפה, שאומרת "איזה סוג של מידע יצא מכאן בסוף?". בשפות שלנו יש שלושה טיפוסים מרכזיים:
- int - עבור כל המספרים.
- bool - עבור אמת ושקר.
- T1 -> T2 - עבור פונקציות. פונקציה שמקבלת טיפוס T1 ומחזירה טיפוס T2
(למשל: פונקציה שמקבלת int ומחזירה bool תיכתב כ-
int -> bool).
איך בודקים קוד בלי להריץ אותו?
הטריק הוא לבנות מפרש מקביל. אם למדנו שהפונקציה value-of
רצה על ה-AST ומחשבת ערכים, אנחנו נבנה פונקציה חדשה שנקראת type-of.
היא תרוץ על אותו ה-AST, אבל במקום לחשב מספרים, היא תחשב טיפוסים.
במקום סביבה רגילה (Environment) ששומרת [x=5], היא תשתמש
בסביבת טיפוסים (Type Environment) ששומרת [x=int].
הדמיה השוואתית: בדיקת טיפוסים סטטית מול מפרש ריצה הדמיה אינטראקטיבית
ראו כיצד מערכת בדיקה סטטית (Type Checker) תופסת שגיאות טיפוס לפני ההרצה, לעומת מפרש רגיל (Interpreter) המגלה שגיאות רק בזמן ריצה וקורס.
בקרה:
צינור העיבוד ומצב הסביבה:
קבצי המקור של שפת CHECKED
שפת CHECKED היא שפה בעלת מערכת טיפוסים סטטית המוכרזת במפורש. בואו נראה אילו קבצים מגדירים אותה וכיצד הם משתלבים בארכיטקטורה של השפה.
checker.scm (חדש!)
לב מערכת הטיפוסים. מכיל את הפונקציה type-of
ואת ייצוג סביבת הטיפוסים (Tenv).
lang.scm
מגדיר את הדקדוק המעודכן, הכולל ביטויי טיפוסים (Types) והערות טיפוס על משתנים.
interp.scm & data-structures.scm
המפרש וערכי הריצה. שים לב: הם אינם כוללים בדיקות טיפוסים בזמן ריצה! אנו מסתמכים ב-100% על ה-Type Checker.
top.scm
הקובץ המקשר שמנהל את ה-Pipeline הדו-שלבי: בדיקה סטטית (Type Check) ולאחר מכן ריצה (Evaluation).
צינור העיבוד הדו-שלבי (EOPL Pipeline)
בשפות הקודמות, הקוד עבר ישירות לפענוח (Parsing) ולאחר מכן לריצה. בשפת CHECKED אנו מוסיפים שלב ביניים קריטי:
🚀 Zero-Cost Abstraction
בגלל שהוכחנו סטטית שאין שגיאות טיפוס, מפרש הריצה
ב-interp.scm רץ מהר יותר ופשוט יותר. אין צורך לבדוק ב-if-exp
האם התנאי הוא בוליאני, או ב-diff-exp האם האיברים הם מספרים. הבטיחות מובטחת
מראש!
שפת CHECKED (בדיקה סטטית)
שפת CHECKED היא השפה הראשונה שמוסיפה Type Checking (בדיקת טיפוסים). היא דורשת מהמתכנת להכריז במפורש (Explicit Annotations) על הטיפוס של כל פרמטר בפונקציה. זה מזכיר מאוד את שפת C או Java.
הדקדוק החדש (lang.scm)
נוסף לנו מבנה תחבירי חדש שנקרא
Type, ושינינו את הגדרת הפונקציה (proc) כך שתדרוש את הטיפוס של הפרמטר שלה:
% הגדרות הטיפוסים בשפה:
Type ::= int
Type ::= bool
Type ::= (Type -> Type)
% השינוי בפונקציות ורקורסיה:
Expression ::= proc (Identifier : Type) Expression
Expression ::= letrec Type Identifier (Identifier : Type) = Expression in Expression
איך הקוד נראה?
כדי להגדיר פונקציה שמקבלת x ומחסרת ממנו 1, המתכנת
חייב להצהיר ש-x הוא מסוג int.
let f = proc (x : int) -(x, 1)
in (f 10)בלולאת letrec ההכרזה ארוכה אפילו יותר, כי
צריך להצהיר גם על טיפוס החזרה של הפונקציה עצמה:
letrec int fact (n : int) =
if zero?(n) then 1 else *(n, (fact -(n,1)))
in (fact 5)השוואה לשפות קודמות
בשפת PROC הישנה, פונקציות היו "דינמיות" לחלוטין. ב-CHECKED אנו מעבירים חלק מהאחריות למערכת הטיפוסים הסטטית. נשים לב להבדל התחבירי והסמנטי המרכזי:
| נושא | שפת PROC (דינמית) | שפת CHECKED (סטטית) |
|---|---|---|
| הגדרת פונקציה | proc (x) ... |
proc (x : int) ... |
| שגיאת טיפוסים | מתגלה רק בזמן ריצה כשמנסים לחשב את הביטוי. | מתגלה בשלב ה-Compilation (בדיקת הטיפוסים הסטטית) ללא הרצת קוד. |
| הגדרת רקורסיה | letrec f(x) = ... |
letrec bool f(x : int) = ...
|
מנוע הבדיקה: type-of
הפונקציה type-of היא המקבילה המושלמת
ל-value-of, אבל במקום לעבוד בעולם של טיפוסים (Types). היא רצה לאורך עץ ה-AST
ומוודאת שכל פעולה היא חוקית.
מימוש type-of ב-checker.scm
(define type-of
(lambda (exp tenv) ; tenv = Type Environment!
(cases expression exp
; 1. מספר: הטיפוס שלו הוא תמיד int
(const-exp (num) (int-type))
; 2. שליפת משתנה מסביבת הטיפוסים (Tenv)
(var-exp (var) (apply-tenv tenv var))
; 3. חיסור מתמטי:
(diff-exp (exp1 exp2)
(let ((ty1 (type-of exp1 tenv))
(ty2 (type-of exp2 tenv)))
(check-equal-type! ty1 (int-type) exp1)
(check-equal-type! ty2 (int-type) exp2)
(int-type)))
; 4. בדיקת אפס (zero?):
(zero?-exp (exp1)
(let ((ty1 (type-of exp1 tenv)))
(check-equal-type! ty1 (int-type) exp1)
(bool-type)))
; 5. פקודת תנאי (if):
(if-exp (exp1 exp2 exp3)
(let ((ty1 (type-of exp1 tenv))
(ty2 (type-of exp2 tenv))
(ty3 (type-of exp3 tenv)))
(check-equal-type! ty1 (bool-type) exp1)
(check-equal-type! ty2 ty3 exp)
ty2))
; 6. ביטוי Let:
(let-exp (var exp1 body)
(let ((exp1-type (type-of exp1 tenv)))
(type-of body (extend-tenv var exp1-type tenv))))
; 7. יצירת פונקציה (proc):
(proc-exp (var var-type body)
(let ((result-type (type-of body (extend-tenv var var-type tenv))))
(proc-type var-type result-type)))
; 8. הפעלת פונקציה (call):
(call-exp (rator rand)
(let ((rator-type (type-of rator tenv))
(rand-type (type-of rand tenv)))
(cases type rator-type
(proc-type (arg-type result-type)
(begin
(check-equal-type! arg-type rand-type rand)
result-type))
(else (eopl:error 'type-of "Rator not a proc type!")))))
; 9. רקורסיה (letrec):
(letrec-exp (p-result-type p-name b-var b-var-type p-body letrec-body)
(let ((tenv-for-letrec-body
(extend-tenv p-name (proc-type b-var-type p-result-type) tenv)))
(let ((p-body-type
(type-of p-body (extend-tenv b-var b-var-type tenv-for-letrec-body))))
(check-equal-type! p-body-type p-result-type p-body)
(type-of letrec-body tenv-for-letrec-body))))
)))🧠 סביבת טיפוסים (Tenv) מול סביבת ריצה (Env)
חשוב להבין את ההפרדה המוחלטת בין שני סוגי הסביבות:
- סביבת ריצה (Environment): מופעלת ב-
value-of, שומרת שמות של משתנים ומקשרת אותם לערכי ריצה אמיתיים כמו מספרים או קלוז'רים (למשל:x = num-val(5)). - סביבת טיפוסים (Type Environment - Tenv): מופעלת ב-
type-of, שומרת שמות של משתנים ומקשרת אותם לטיפוסים הסטטיים שלהם (למשל:x = int-type). סביבה זו קיימת רק בזמן הקומפילציה!
מחולל טיפוסים מסדר גבוה (High-Order Type Builder) הדמיה אינטראקטיבית
בנו טיפוסים של פונקציות מסדר גבוה (פונקציות שמקבלות או מחזירות פונקציות) וראו כיצד מיוצגים
הטיפוסים במפרש checker.scm של EOPL ומה משמעותם התחרותית.
התוצאה המיוצרת:
פונקציה המקבלת מספר שלם ומחזירה מספר שלם.
קבצי המקור של שפת INFERRED
שפת INFERRED מאפשרת להשמיט את הגדרות הטיפוסים
באמצעות שימוש בסימן שאלה ?. כדי לבצע את פלא הסקת הטיפוסים, המפרש משתמש במערכת קבצים
מתוחכמת יותר.
מבנה הקבצים החדש
-
inferrer.scm (מחליף את
checker.scm)
מבצע את בדיקת הטיפוסים הסטטית. בניגוד ל-
type-ofהקודם שהחזיר טיפוס, כאן הוא מחזירan-answer- מבנה הכולל את הטיפוס המוסק ואת טבלת ההצבות (Substitutions) המעודכנת. -
substitutions.scm (חדש!)
מנהל מילון שממפה משתני טיפוס זמניים (Type Variables כמו $t_1, t_2$) לטיפוסים אמיתיים שהתגלו במהלך הריצה (למשל $int, bool$). מספק פונקציות חיוניות כמו
extend-subst(הוספת אילוץ) ו-apply-subst-to-type(שליפת המידע המעודכן). -
unifier.scm (חדש!)
מנוע האיחוד. הפונקציה
unifierמקבלת שני טיפוסים וסביבת הצבות. היא מנסה לאלץ את שני הטיפוסים להיות זהים. אם היא מצליחה, היא מחזירה סביבת הצבות חדשה הכוללת את המסקנות החדשות. אם יש התנגשות בלתי אפשרית (למשל $int$ מול $bool$), היא קורסת עם Type Error. -
equal-up-to-gensyms.scm (חדש!)
מודול עזר לבדיקות המשווה בין שני טיפוסים שנוצרו אוטומטית, ומוודא שהמבנה שלהם זהה ללא תלות במספר הסידורי הייחודי שהמפרש נתן להם במהלך יצירת משתנים זמניים.
הארכיטקטורה של הסקת טיפוסים
כאשר המפרש נתקל בסימן ? (המיוצג תחבירית כ-no-type בדקדוק), הוא
מייצר עבורו משתנה טיפוס טרי (Fresh Type Variable). בקוד הוא נראה כ-%tvar-type
עם מספר סידורי רץ (למשל tvar1, tvar2, tvar3).
בזמן ריצת ה-Inferrer על עץ התוכנית, אנו אוספים משוואות ומעבירים אותן ל-Unifier. ה-Unifier מעדכן את מאגר ה-Substitutions שמייצג את כל ה"ידע הקיים" שיש לנו על המשתנים הזמניים. כל משוואה שנפתרת מעשירה את הידע הזה.
בסיום ריצת אלגוריתם ההסקה, אנו מפעילים apply-subst-to-type על משתנה הטיפוס
הראשי של התוכנית. פונקציה זו מחליפה את כל משתני הטיפוס הזמניים בטיפוסים האמיתיים שהסקנו
בעזרת המילון.
הסקה אוטומטית: שפת INFERRED
שפת CHECKED היא בטוחה, אבל הופכת את הקוד למסורבל.
מתכנתים לא רוצים לכתוב (x : int) בכל מקום. שפות מתקדמות כמו TypeScript או Haskell
מאפשרות הסקת טיפוסים (Type Inference). המהדר חכם מספיק להסתכל על הקוד ולנחש לבד
מה צריך להיות הטיפוס!
הדקדוק: סימן השאלה (?)
בשפת INFERRED, המתכנת יכול לכתוב סימן שאלה ?
במקום לכתוב את הטיפוס. הוא אומר למפרש: "תגלה לבד".
; הטיפוס הוסתר בעזרת ?
let f = proc (x : ?) -(x, 1)
in (f 10)המטרה של האלגוריתם היא לפענח מה מסתתר מאחורי כל סימן שאלה בתוכנית, על ידי איסוף רמזים ופתרון משוואות.
שלושת השלבים להסקה
איך אלגוריתם כזה עובד? ממש כמו פתרון מערכת משוואות במתמטיקה (נעלמים $x, y$):
- מיפוי משתנים זמניים: מעניקים משתנה זמני (Type Variable המסומן באות $t$) לכל סימן שאלה ולכל ביטוי משמעותי בקוד.
- איסוף אילוצים (Constraints): עוברים על ה-AST ומייצרים משוואות לפי החוקים (למשל, חיסור דורש $int$).
- הצבה (Unification): פותרים את המשוואות בשיטת האלימינציה. ככל שפותרים יותר משוואות, ערך הנעלמים נחשף, עד שכל ה- $t$-ים הופכים לטיפוסים אמיתיים!
שלב 1: יצירת המשוואות (Constraints)
השלב הראשון בהפעלה הוא לקחת את התוכנית, להעניק שמות (Type Variables) לכל ביטוי, ולהוציא מהקוד את החוקים (המשוואות) שהוא מחייב. כל פעולה מתמטית או לוגית מפיקה משוואה.
חוקי הגזירה (The Rules)
בואו נכיר את התבניות. נניח שסימנו ביטוי $E$ במשתנה טיפוס $t_E$. אילו רמזים נוכל לדלות?
zero? בודקת האם מספר הוא 0. לכן: הקלט
$t_{E1} = int$. התוצאה של הפעולה כולה היא תמיד $bool$.Rator על הארגומנט Rand, והפעולה
כולה מחזירה תוצאה שנסמן ב-$t_{Res}$, אזי הפונקציה עצמה חייבת להיות מהמבנה: $t_{Rator} =
t_{Rand} \r\rightarrow t_{Res}$.שלב 2: פתרון המשוואות (Unification)
לאחר שיצרנו את כל המשוואות (רשימת ה-Equations), אנחנו מתחילים "לנקות" אותן בעזרת טבלה של שתי עמודות: עמודת המשוואות (Equations) שעוד צריך לפתור, ועמודת ההצבות (Substitutions) שבה אנו שומרים עובדות מוגמרות שמצאנו.
איך פותרים (אלגוריתם ההצבה)?
אנו עוברים על עמודת המשוואות אחת-אחת (מלמעלה למטה) ומפעילים את החוקים הבאים:
- זהות: אם הגענו למשוואה כמו $int = int$ או $t_1 = t_1$, פשוט מוחקים אותה. אין לה משמעות.
- גילוי משתנה (Substitution): אם הגענו למשוואה מהצורה $t_1 = int$ (או $t_1 = t_2 \r\rightarrow bool$). מצאנו עובדה! מעבירים אותה לעמודת ההצבות. אבל, החלק החשוב ביותר: עוברים על כל שאר המשוואות שנותרו, ובכל מקום שכתוב $t_1$, מוחקים וכותבים במקומו את הערך החדש!
- פירוק פונקציות: אם הגענו למשוואה המורכבת משני חצים, למשל $t_1 \r\rightarrow int = bool \r\rightarrow t_2$. כדי שזה יהיה שווה, צד שמאל של החץ חייב להיות שווה לשמאל, והימני לימני. לכן, מוחקים את המשוואה הזו ומפצלים אותה לשתי משוואות חדשות בתחתית הרשימה: $t_1 = bool$ ו-$int = t_2$.
- שגיאת טיפוס (Failure): אם הגענו למצב של התנגשות מהותית, למשל $int = bool$, או $int = t_1 \r\rightarrow t_2$, האלגוריתם קורס. המשמעות: יש שגיאת טיפוס בקוד! המפרש פולט Type Error.
פתרון משוואות טיפוסים אינטראקטיבי (Unification Solver) הדמיה אינטראקטיבית
עקבו אחר אלגוריתם ה-Unification הפותר את משוואות הטיפוסים עבור הקוד הבא:
letrec f(x) = -(x, 1) in f(5)
בקרה:
רשימת משוואות (Equations):
טבלת הצבות (Substitutions):
דוגמאות הפעלה צעד-אחר-צעד
נראה כיצד האלגוריתם פועל בצורה שיטתית - החל משלב גזירת המשוואות (מבפנים החוצה) ועד לפתרונן והסקת הטיפוס הסופי.
דוגמה 1: היכרות עם let ומתמטיקה
מעקב אילוצים:
- נסמן את $x$ ב-$t_x$.
- נסמן את הביטוי
5ב-$t_1$. מאחר ו-5 הוא מספר, נוצרת משוואה: $t_1 = int$. - חוק ה-let קובע ש-$t_x = t_1$. לכן מסקנה ראשונה: $t_x = int$.
- הביטוי הפנימי
-(x, 3)מסומן כ-$t_2$. חיסור דורש שמאל=int וימין=int. הערך הימני 3 הוא אכן int. הערך השמאלי הוא $x$, ולכן דרוש $t_x = int$. זה תואם לחלוטין למסקנה שלנו ולכן הכל תקין. - תוצאת החיסור היא int. ולכן $t_2 = int$.
- התוכנית כולה מחזירה את תוצאת גוף ה-let. לכן $t_{prog} = int$.
דוגמה 2: זיהוי טיפוס פרמטר בעזרת תנאי (if)
שלבי הפתרון:
- נסמן את $x$ כ-$t_x$. הפונקציה עצמה מסומנת ב-$t_{proc} = t_x \r\rightarrow t_{body}$.
- נסתכל על התנאי:
zero?(x). הפעולה zero? דורשת שהקלט שלה יהיה מספר. מכאן נוצר האילוץ החשוב: $t_x = int$. (בלי שהצהרנו במפורש, המהדר מסיק ש-x הוא מספר!). - נסתכל על ה-then: הפלט הוא 1, לכן $t_{then} = int$.
- נסתכל על ה-else: הפלט הוא x, לכן $t_{else} = t_x$.
- חוק ה-if דורש ששני הענפים יהיו זהים: $t_{then} = t_{else}$. נציב את מה שגילינו: $int = t_x$. זה תואם בדיוק לסעיף 2.
- גוף הפונקציה ($t_{body}$) שווה לטיפוס ה-if שהוא $int$.
- הטיפוס הסופי של הפונקציה: $t_{proc} = t_x \r\rightarrow t_{body} = int \r\rightarrow int$.
דוגמה 3: פונקציות מסדר גבוה (Higher Order)
בדוגמה זו אין שום רמז "חיצוני" (כמו חיסור או מספר). איך עובדים נטו עם משוואות ההפעלה?
- נסמן את הפרמטרים: $f$ כ-$t_f$, ו-$x$ כ-$t_x$.
- הביטוי המרכזי הפנימי הוא
(f x). נסמן את תוצאת ההפעלה הזו כ-$t_{res}$. - נפעיל את חוק ה-Call-Exp: אנו מפעילים את f על x והתוצאה היא $t_{res}$. לכן $t_f$ חייב להיות פונקציה מ-$t_x$ ל-$t_{res}$. נוצרת המשוואה: $t_f = t_x \r\rightarrow t_{res}$.
- כעת נבנה את התוכנית בחזרה החוצה. הפונקציה הפנימית `proc(x:?)` מחזירה את ההפעלה. לכן הטיפוס שלה: $t_{inner} = t_x \r\rightarrow t_{res}$.
- הפונקציה החיצונית `proc(f:?)` מחזירה את הפונקציה הפנימית. לכן הטיפוס שלה: $t_{outer} = t_f \r\rightarrow t_{inner}$.
- נציב את הכל פנימה:
$t_{outer} = (t_x \r\rightarrow t_{res}) \r\rightarrow (t_x \r\rightarrow t_{res})$ - מכיוון שלא מצאנו שום קשר ל-int או bool, המשתנים $t_x$ ו-$t_{res}$ נשארים נעלמים עד סוף התוכנית. זה מצב חוקי ונקרא פולימורפיזם (Polymorphism) - הפונקציה הזו יכולה לקבל כל פונקציה וכל משתנה שמתאימים לה.
מקרי קצה ושגיאות טיפוס
אלגוריתם ה-Inference נתקל לעיתים בתוכניות מורכבות הכוללות קריאות רקורסיביות, או בתוכניות המכילות שגיאת טיפוס אמיתית שאינה ניתנת לפתרון.
דוגמה 4: רקורסיה עמוקה (letrec)
נשתמש בשיטת חילוץ המשוואות:
- הפרמטר וגוף ה-letrec: נסמן את הטיפוס של פונקציית ה-letrec כ-$t_{res}$ ואת הפרמטר ב-$t_x$. הטיפוס של הפונקציה f הוא במפורש $t_f = t_x \r\rightarrow t_{res}$.
- התנאי:
zero?(x)מסיק ש-$t_x = int$. - בלוק ה-then: מחזיר 0, לכן הטיפוס של then הוא $int$. מכיוון שתוצאת גוף הפונקציה חייבת להתאים, נסיק כי $t_{res} = int$. אז עד כה אנו יודעים ש-$f: int \r\rightarrow int$.
- בלוק ה-else: יש פה חיסור גדול, לכן תוצאתו $int$. (התאמה מושלמת ל-then).
- הקריאה הרקורסיבית: מבצעים
(f -(x,1)). אנו קוראים ל-f עם פרמטר שהוא חיסור (ולכן הוא int). הטיפוס של f מצפה ל-int. התוצאה של f חוזרת כ-$t_{res}$ שהוא int. הערך הזה הולך לפעולת החיסור החיצונית שמצפה ל-int. הכל מסתדר בצורה מושלמת! - התוצאה: התוכנית כולה מחזירה את הפונקציה
f, שטיפוסה הוא $int \r\rightarrow int$.
דוגמה 5: מניעת רקורסיה אינסופית בטיפוסים (Occurs Check)
מתי האלגוריתם נשבר? ננסה להסיק את הטיפוס של הפונקציה המבלבלת הבאה שמפעילה ארגומנט על עצמו (Self-Application):
מעקב אחר אלגוריתם ה-Unification:
- 1. נסמן את $x$ במשתנה טיפוס זמני: $t_x$.
- 2. הביטוי המרכזי הוא הפעלה:
(Rator Rand)=(x x). נסמן את תוצאת ההפעלה (הטיפוס שחוזר ממנה) ב-$t_{res}$. - 3. נפעיל את חוק ההפעלה
(Call-Exp Constraint Rule):
ה-Rator הוא $x$ (מסוג $t_x$).
ה-Rand הוא $x$ (מסוג $t_x$).
משוואת הפעלת פונקציה דורשת: הטיפוס של ה-Rator שווה לחץ בין טיפוס ה-Rand לטיפוס התוצאה. נציב ונקבל:$$t_x = t_x \r\rightarrow t_{res}$$ - 4. ה-Unifier מקבל את המשוואה
הזו ומנסה לבצע אלימינציה. הוא בודק במילון (Substitutions) ואז מבצע בדיקת שייכות (Occurs
Check):
האם משתנה הטיפוס $t_x$ מופיע בתוך הביטוי $t_x \r\rightarrow t_{res}$? - 5. התשובה היא **כן** ($t_x$ מופיע ממש בצד שמאל של החץ).
- 6. התרסקות! ה-Unifier זורק שגיאת Occurs Check Violation. הפונקציה אינה ניתנת לטיפוס (Not Typeable) בשפת INFERRED!
אם האלגוריתם לא היה בודק זאת, היינו נכנסים ללולאה אינסופית בנסיון לפתור את הטיפוס. לא ניתן לכתוב ב-INFERRED פונקציה שמקבלת את עצמה ללא מערכת טיפוסים מורכבת יותר (כמו Recursive Types).
דוגמה מסכמת: הסקה בפונקציות מקוננות
נבצע כעת מעקב מלא אחר ה-Inferrer וה-Unifier עבור תוכנית מורכבת. דוגמה זו מסכמת את כל השלבים - משלב חלוקת המשתנים, דרך בניית 13 המשוואות, ועד לפתרונן בשיטת האלימינציה וההצבות.
in let p = proc(x: ?) if (x 5) then (q 10) else (q 20)
in (p q)
שלב א': איסוף ויצירת משוואות
ה-Inferrer סורק את ה-AST ומעניק משתנה $t$ לכל ביטוי:
| הביטוי (Expression) | משתנה הטיפוס | המשוואות שנוצרות (Constraints) / הסבר |
|---|---|---|
| y | $t_y$ | פרמטר של הפונקציה q |
| -(y, 10) | $t_1$ | 1. $t_y = int$ 2. $t_1 = int$ (חיסור דורש ומחזיר int) |
| zero?(-(y, 10)) | $t_2$ | 3. $t_1 = int$ (קלט חייב להיות int) 4. $t_2 = bool$ (תוצאת zero? היא בוליאנית) |
| proc(y:?)... | $t_q$ | 5. $t_q = t_y \r\rightarrow t_2$ (פונקציה מהפרמטר לגוף) |
| --- עוברים לחלק השני של הקוד --- | ||
| x | $t_x$ | פרמטר של הפונקציה p |
| (x 5) | $t_3$ | 6. $t_x = int \r\rightarrow t_3$ (x מופעל כפונקציה על המספר 5, ומחזיר את t_3) |
| (q 10) | $t_4$ | 7. $t_q = int \r\rightarrow t_4$ (q מופעל כפונקציה על 10, ומחזיר את t_4) |
| (q 20) | $t_5$ | 8. $t_q = int \r\rightarrow t_5$ (q מופעל על 20, ומחזיר את t_5) |
| if (x 5) then... | $t_{if}$ | 9. $t_3 = bool$ (תנאי ה-if חייב להיות
בוליאני) 10. $t_4 = t_5$ (שני ענפי ה-if זהים) 11. $t_{if} = t_4$ (תוצאת ה-if) |
| proc(x:?)... | $t_p$ | 12. $t_p = t_x \r\rightarrow t_{if}$ (הפונקציה p) |
| (p q) | $t_{prog}$ | 13. $t_p = t_q \r\rightarrow t_{prog}$ (התוכנית כולה - p מופעלת על q) |
שלב ב': אלגוריתם ההצבות (Unification)
ה-Unifier מקבל את 13 המשוואות שמצאנו, ומפעיל אלימינציה שלב אחר שלב. הערכים מחלחלים (Substitute) במורד המשוואות ומעשירים את טבלת ההצבות.
המשוואות שעוד נותרו:
- 1. $t_y = int$
- 2. $t_1 = int$
- 3. $t_1 = int$
- 4. $t_2 = bool$
- 5. $t_q = t_y \r\rightarrow t_2$
- 6. $t_x = int \r\rightarrow t_3$
- 7. $t_q = int \r\rightarrow t_4$
- 8. $t_q = int \r\rightarrow t_5$
- 9. $t_3 = bool$
- 10. $t_4 = t_5$
- 11. $t_{if} = t_4$
- 12. $t_p = t_x \r\rightarrow t_{if}$
- 13. $t_p = t_q \r\rightarrow t_{prog}$
מילון ההצבות (Substitutions) שמתגבש:
- $\r\rightarrow t_y = int$ (ממשוואה 1)
- $\r\rightarrow t_1 = int$ (משוואות 2,3 - נמחקות)
- $\r\rightarrow t_2 = bool$ (ממשוואה 4)
- נציב את ty ו-t2 בתוך משוואה 5: $\r\rightarrow t_q = int \r\rightarrow bool$
- נציב את tq החדש בתוך 7 ו-8:
$int \r\rightarrow bool = int \r\rightarrow t_4 \implies t_4 = bool$
$int \r\rightarrow bool = int \r\rightarrow t_5 \implies t_5 = bool$
$\r\rightarrow t_4 = bool, \ t_5 = bool$ - ממשוואות 9, 11 נובע:
$\r\rightarrow t_3 = bool$
$\r\rightarrow t_{if} = bool$ (כי t4 הוא bool) - נציב את t3 במשוואה 6: $\r\rightarrow t_x = int \r\rightarrow bool$
- נבנה את משוואה 12 (הפונקציה p) עם tx ו-tif: $\r\rightarrow t_p = (int \r\rightarrow bool) \r\rightarrow bool$
-
השלב הסופי! נציב את tp ואת tq
במשוואה 13:
$(int \r\rightarrow bool) \r\rightarrow bool = (int \r\rightarrow bool)
\r\rightarrow t_{prog}$
$\implies t_{prog} = bool$ 🎯
סיכום האלגוריתם
בסיום המעקב, ה-Inferrer מחזיר שהאלגוריתם סיים בהצלחה ללא סתירות, וטיפוס
התוכנית הסופי ($t_{prog}$) הוא bool. אם הוא היה נתקל בסתירה - למשל אם $t_3$ היה
אמור להיות גם $int$ וגם $bool$, האלגוריתם היה עוצר וזורק Type Error.
פתרון מטלת סיכום: הסקה עם פונקציות מסדר גבוה
במחלקה זו ננתח ונפתור צעד-אחר-צעד את שאלת ההסקה
המרכזית עבור ביטוי המשלב let, פונקציות מסדר גבוה, והעברה של פונקציות כפרמטרים בשפת
INFERRED.
in (p proc (b: int) zero? (b))
שלב א': הקצאת משתני טיפוס ויצירת משוואות
כדי להסיק את טיפוס הביטוי, ה-Inferrer סורק את ה-AST ומקצה משתנה טיפוס זמני לכל תת-ביטוי ולכל מזהה (Identifier) ללא טיפוס מוצהר:
| תת-הביטוי / משתנה (Expression) | משתנה הטיפוס | המשוואות שנוצרות (Constraints) / הסבר פדגוגי |
|---|---|---|
| E_0 (התוכנית כולה) | \(t_{prog}\) | הטיפוס הסופי של ביטוי ה-let כולו. לפי חוק ה-let,
מתקיים: \(t_{prog} = t_{body}\)
(טיפוס הגוף). |
| a | \(t_a\) | פרמטר ללא טיפוס מוצהר של הפונקציה p. מקבל משתנה טיפוס
חופשי. |
| 6 | \(t_1\) | 1. \(t_1 = int\) (קבוע מספרי הוא תמיד מספר שלם) |
| (a 6) | \(t_2\) | 2. \(t_a = t_1 \rightarrow t_2\) (הפעלת פונקציה: a מופעלת על 6 ומחזירה את תוצאת הגוף t_2) |
| proc (a: ?) (a 6) | \(t_{rhs}\) | 3. \(t_{rhs} = t_a \rightarrow t_2\) (טיפוס הפונקציה הוא מטיפוס הפרמטר לטיפוס הגוף) |
| p | \(t_p\) | 4. \(t_p = t_{rhs}\) (קשירת המשתנה p לערך הימני ב-let) |
| --- גוף ה-let: (p proc (b: int) zero? (b)) --- | ||
| b | \(t_b\) | 5. \(t_b = int\) (פרמטר בעל הצהרת טיפוס מפורשת b: int) |
| zero? (b) | \(t_3\) | 6. \(t_b = int\) (קלט של zero? חייב להיות
מספר) 7. \(t_3 = bool\) (פלט של zero? הוא תמיד בוליאני) |
| proc (b: int) zero? (b) | \(t_{arg}\) | 8. \(t_{arg} = t_b \rightarrow t_3\) (טיפוס פונקציית הארגומנט) |
| (p proc...) (גוף ה-let) | \(t_{body}\) | 9. \(t_p = t_{arg} \rightarrow t_{body}\) (הפעלת הפונקציה p על הארגומנט; התוצאה היא t_body) |
שלב ב': פתרון המשוואות (Unification & Substitution)
כעת, ה-Unifier מתחיל לפתור את מערכת המשוואות שהגדרנו באמצעות מעברים, הפשטות והצבות דו-כיווניות:
המשוואות שנאספו:
- (1) \(t_1 = int\)
- (2) \(t_a = t_1 \rightarrow t_2\)
- (3) \(t_{rhs} = t_a \rightarrow t_2\)
- (4) \(t_p = t_{rhs}\)
- (5) \(t_b = int\)
- (6) \(t_b = int\)
- (7) \(t_3 = bool\)
- (8) \(t_{arg} = t_b \rightarrow t_3\)
- (9) \(t_p = t_{arg} \rightarrow t_{body}\)
- (10) \(t_{prog} = t_{body}\)
שלבי צמצום והצבה:
-
קביעת טיפוסים ישירים:
ממשוואה (1): \(t_1 \mapsto int\)
ממשוואה (5) ו-(6): \(t_b \mapsto int\)
ממשוואה (7): \(t_3 \mapsto bool\) -
הצבה ב-\(t_a\):
נציב את \(t_1 = int\) במשוואה (2):
\(t_a \mapsto int \rightarrow t_2\) -
בניית טיפוס הפונקציה \(t_{rhs}\) וקשירת \(t_p\):
נציב את \(t_a\) במשוואה (3):
\(t_{rhs} = (int \rightarrow t_2) \rightarrow t_2\)
מכיוון ש-\(t_p = t_{rhs}\) (משוואה 4), נקבל:
\(t_p \mapsto (int \rightarrow t_2) \rightarrow t_2\) -
בניית טיפוס הארגומנט \(t_{arg}\):
נציב את \(t_b = int\) ו-\(t_3 = bool\) במשוואה (8):
\(t_{arg} \mapsto int \rightarrow bool\) -
איחוד (Unification) של טיפוסי \(t_p\):
נציב את \(t_p\) ואת \(t_{arg}\) במשוואה (9):
\( (int \rightarrow t_2) \rightarrow t_2 = (int \rightarrow bool) \rightarrow t_{body} \)
נפרק את השוויון בין שתי פונקציות (שמאל לשמאל, ימין לימין):- צד שמאל: \( int \rightarrow t_2 = int \rightarrow bool
\)
מפירוק נוסף מקבלים: \(int = int\) (זהות) וכן \(t_2 \mapsto bool\). - צד ימין: \(t_2 = t_{body}\).
- צד שמאל: \( int \rightarrow t_2 = int \rightarrow bool
\)
-
מציאת טיפוס הגוף \(t_{body}\):
מכיוון ש-\(t_2 = bool\) וכן \(t_{body} = t_2\), נובע ישירות ש:
\(t_{body} \mapsto bool\) -
הסקה סופית של טיפוס התוכנית:
ממשוואה (10): \(t_{prog} = t_{body}\). לכן:
\(t_{prog} \mapsto bool\) 🎯
💡 תובנה פדגוגית מהפתרון
בתוכנית זו, הפונקציה p היא פונקציה מסדר גבוה. היא מקבלת פונקציה כלשהי
a ומפעילה אותה על המספר 6.
מאחר ו-p מפעילה את a על קלט מסוג int, המהדר מסיק באופן
אוטומטי ש-a חייב להיות מטיפוס המקבל int (כלומר
int -> t_2).
כאשר אנו מפעילים את p בגוף התוכנית על הארגומנט
proc (b: int) zero? (b), שטיפוסו הוא int -> bool, מתבצעת התאמה מלאה!
משתנה הטיפוס \(t_2\) מתאחד עם bool, ולכן תוצאת הפונקציה כולה (וגם תוצאת התוכנית
כולה) היא bool.