למה 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))))