מבוא מורחב למדעי המחשב

SCHEME

תוכן

1. בניית תוכנה מורכבת ב-Scheme
   • יסודות התכנון
   • משתנים פשוטים
   • פרוצדורות
   • רקורסיביות ואיטרטיביות
   • סיבוכיות זמן ריצה

2. מבני נתונים (משתנים מורכבים)
   • זוגות
   • רשימות
   • עצים
   • סמלים
   • אוספי אלמנטים שונים
   • Data Directed Programming

 

3. משפט השמה ומודל הסביבות
   • משפט השמה
   • מודל הסביבות
   • משפט השמה לזוגות
   • מחסניות וטורים
   • טבלאות
   • Object Oriented Programming
   • זרמים (streams), זרמים אינסופיים, זרמים מורכבים
   • מערכים

 

4. נספח –  פרוצדורות
   • ספרייה של פרוצדורות המוכרות ע”י המשערך
   • פרוצדורות לפרק 1
   • זוגות ורשימות
   • עצים
   • השמה והשמה בזוגות
   • OOP
   • זרמים
   • מערכים
   • בניית משערך (metacircular evaluator)
   • נושאים שנלמדו בקורס

 

 

 

 

 

פרק 1

בניית תוכנה מורכבת ב-Scheme

 

יסודות התכנון

 

בגדול  כל הדברים  ב-Scheme  זה בעצם משתנים.

 

במשתנים שומרים מידע ונתונים והם  יכולים להיות

1. פשוטים כגון מספרים, ערכים בוליאניים, תווים וכד’.
2. מורכבים יותר כגון זוגות, רשימות עצים וכו’. (ראה פרק 2).
3. פרוצדורות (פונקציות, שגרות).

לכל משתנה יש שם ויש ערך ששמור בזיכרון.  כדי לקבל את ערך המשתנה מספיק לכתוב את שמו:

> mynum

10

 

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

1. בסיסיות: כגון define, lambda, let , שמהוות הגדרה.
2. מיוחדות: (Special forms) כגון if ו-cond.
3. רגילות: כגון+  –  *  /  and  והרבה מאוד אחרים כולל חדשים שאתה כותב.

כדי לקבל את הערך של הפרוצדורה צריך לרשום אותה בסוגריים יחד אם הפרמטרים שלה (אם קיימים).

> (*)

1

> (* 1 2 3 4 5)

120

בין כל שני מילים בתוכנה צריך לשים רווח.

כדי לרשום הערה צריך לשים בהתחלה סימן  ;  הערה תתחשב עד סוף שורה.

משתנים פשוטים

 

הגדרה:

)define שם ערך)

סוגי משתנים :

שגרה שמזהה את הסוג	דוגמאות	סוג
number?	5, -899, 1/9, 4.2357	מספר
boolean?	#t  ,  #f	ערך בוליאני
pair?	(7 . 9),  (“a” . “b”)	זוג
symbol?	‘nil, ‘x	סמל
procedure?	+, -, >, or, list, cons	פרוצדורה
char?	#\a, #\S	תו
string?	“Welcome to Scheme”	מחרוזת
vector?	#(0 (2 2 2 2) “Anna”)	מערך
port?		port

 

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

פרוצדורות

 

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

דרך א’:  דרך מקוצרת (סוכר תחבירי)

1. פרוצדורה ללא  פרמטרים:

הגדרה:

(define (שם_שגרה) גוף)

הפעלה:

(שם_שגרה)

> (define (five) 5)

> (five)

5

1. פרוצדורה אם (לדוגמה) 3 פרמטרים :

הגדרה:

(define (שם_שגרה פרמטר1 פרמטר2 פרמטר3) גוף)

הפעלה:

(שם_שגרה פרמטר1 פרמטר2 פרמטר3)

> (define (average x y z) (/ (+ x y z) 3))

> (average 1 2 3)

2

 

1. פרוצדורה אם מספר פרמטרים משתנה החל מ-0 :

הגדרה:

(define (שם_שגרה . רשימת_פרמטרים) גוף)

הפעלה:

(שם_שגרה)

(שם_שגרה פרמטר1 פרמטר2)

(שם_שגרה פרמטר1 פרמטר2 … פרמטר)

(שלוש נקודות מצבעיות על מספר פרמטרים כלשהו)

> (define (rev . lst) (reverse lst))

> (rev 0 1 2 3 4 5 6 7 8 9)

(9 8 7 6 5 4 3 2 1 0)

1. פרוצדורה אם מספר פרמטרים משתנה החל מן לדוגמה 2 :

הגדרה:

(define (שם_שגרה פרמטר1 פרמטר2 . רשימת_פרמטרים) גוף)

הפעלה:

(שם_שגרה פרמטר1 פרמטר2 פרמטר3)

(שם_שגרה פרמטר1 פרמטר2 פרמטר3 … פרמטר_אחרון)

(שלוש נקודות מצבעיות על מספר פרמטרים כלשהו)

> (define (rev x y . lst) (cons (+ x y) (reverse lst)))

> (rev 0 1 2 3 4 5 6 7 8 9)

(1 9 8 7 6 5 4 3 2)

 

דרך ב’:  כמו משתנה (בעזרת lambda)

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

1. פרוצדורה ללא  פרמטרים :

(define שם_שגרה (lambda () גוף))

1. פרוצדורה אם (לדוגמה) 2 פרמטרים :

(define שם_שגרה (lambda (פרמטר1 פרמטר2) גוף))

1. פרוצדורה אם מספר פרמטרים משתנה החל מ-0 :

(define שם_שגרה (lambda רשימת_פרמטרים גוף))

1. פרוצדורה אם מספר פרמטרים משתנה החל מן לדוגמה 1 :

(define שם_שגרה (lambda (פרמטר1 . רשימת_פרמטרים) גוף))

 

 

משפט “תנאי”          if :

 

משפט “תנאי” בודק האם תנאי הוא “אמת” או “שקר”, ואז מבצע “גוף אמת” או “גוף שקר” בהתאם לתנאי

(if תנאי גוף_אמת גוף_שקר)

אפשר לקצר (זה חוקי, אבל ממש לא מומלץ),  במקרה של תנאי  #f  מחשב לא מבצע כלום :

(if תנאי גוף_אמת)

 

> (if #t 3 5)

3

> (if (= 3 5) 3)

> (if (= 3 5) 3 (* 3 5))

15

 

משפט “בחירה”   cond:

 

במשפט “בחירה” אפשר לרשום כמה שרוצים ביטויים שכל ביטוי כולל בתוכו תנאי וגוף שמתבצע במקרה שהתנאי הוא “אמת”. בסוף רצוי (אך לא הכרחי) להוסיף ביטוי else :

(cond (תנאי1 גוף1)

(תנאי2 גוף2)

. . . . . .

(else גוף_אחרת))

בעצם else = #t.

> (cond ((> 3 2) ‘greater)

((< 3 2) ‘less))

greater

> (cond ((> 3 3) ‘greater)

((< 3 3) ‘less)

(else ‘equal))

equal

> (cond (#f 5)

(else 10))

10

 

סוכר תחבירי  let :

 

במקרים מסוימים קל יותר להשתמש בפרוצדורה הבסיסית let   במקום  lambda. ע”י let יוצרים משתנים פנימיים.  ההגדרות הבאות הן שקולות:

 

((lambda (<var1>. . .<varn>)גוף) <exp1> <exp2> . . . <expn>)

=

(let ((<var1> <exp1>)(<var1> <exp2>) . . . . . . . (<varn> <expn>)) גוף)

 

לדוגמה:

(define (f x y)((lambda (a b) (+ (* x (square a)) (* y b) (* a b))) (+ 1 (* x y)) (- 1 y)))

=

(define (f x y)(let ((a (+ 1 (* x y))) (b (- 1 y))) (+ (* x (square a)) (* y b) (* a b))))

אם מגדירים במקום let את let* אז משתנים פנימיים ישוערכו אחד אחרי השני, ויהיה אפשרי להגדיר משתנה פנימי, שערכו – ביטוי שמשתמש במשתנה הפנימי שקדם לו). לדוגמה

> (let* ((a 2)

(b 3)

(sum (+ a b)))

(* a b sum))

30

 

פרוצדורות-על Highter-Order Procedures     :

 

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

 

Applicative order evaluation מול Normal order evaluation :

 

כמעט כל הפרוצדורות ב-Scheme משוערכות לפי Applicative order evaluation , כלומר קודם משוערכים הפרמטרים ורק אחר-כך מופעלת הפרוצדורה עצמה.

המלה “כמעט” מופיע בגלל הקיום פרוצדורות מיוחדות if וְ cond שמשערכים רק ערכים מתאימים. אפשר להגיד שהן עובדות לפי Normal order evaluation , כלומר משערכים את הפרמטרים כל פעם שצריכים אותם (כשהם מופיעים בגוף השגרה).

 

Normal	Applicative
((lambda (x) (+ x x)) (*3 4))(+ (* 3 4) (* 3 4)) (+ 12 12) 24	((lambda (x) (+ x x)) (*3 4))((lambda (x) (+ x x)) 12) (+ 12 12) 24

 

רקורסיביות ואיטרטיביות

 

פרוצדורה רקורסיבית :

פרוצדורה שמכילה בתוכה לפחות שני ביטויים עיקריים:

• תנאי עצירה – תנאי שכשהוא מתקיים פרוצדורה מחזירה ערך כלשהו
• צעד רקורסיבי – ביטוי שמכיל את קריאה לפרוצדורה שממנה הוא הופעל (קריאה רקורסיבית). ביטוי יכול להימצא בתוך הפרוצדורה או בתוך תת-שגרה של הפרוצדורה הזאת.

דוגמה 1

(define (sum_n_to_0 n)

(if (= n 0) 0

(+ n (sum_n_to_0 (- n 1)))))

> (sum_n_to_0 7)

28

דוגמה 2

(define (sum_n_to_0 n)

(define (iter n sum)

(if (= n 0) sum

(iter (- n 1) (+ sum n))))

(iter n 0))

> (sum_n_to_0 7)

28

 

תהליך רקורסיבי:  תהליך בפרוצדורה רקורסיבית, שהצעד הרקורסיבי שלה הוא פרוצדורה, שיש לה חוץ מהפרמטר שהוא קריאה רקורסיבית גם פרמטרים אחרים, ולכן בכל קריאה רקורסיבית אורך הביטוי גדל. (ראה דוגמה 1)

תהליך איטרטיבי:  תהליך בפרוצדורה רקורסיבית, שהצעד הרקורסיבי שלה הוא פרוצדורה, שאין לה חוץ מהפרמטר שהוא קריאה רקורסיבית אף פרמטר אחר, ולכן בכל קריאה רקורסיבית אורך הביטוי נשאר קבוע. (ראה דוגמה 2)

 

סיבוכיות זמן ריצה

הגדרה:

כדי להשוות איזה משני מימושים של פרוצדורה יעיל יותר משתמשים במושג “סיבוכיות זמן ריצה” Order of growth of process .  יהיה n אורך הקלט שממנו תלויה סיבוכיות הבעיה. ואז נסמן:

 

Θ(f(n)) – סיבוכיות.

O(f(n)) – חסם עליון לסיבוכיות.

Ω(f(n)) – חסם תחתון לסיבוכיות.

T(n) – סיבוכיות הזמן.

S(n) – סיבוכיות מקום.

R(n) – נוסחה לסיבוכיות.

 

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

סוגים של סיבוכיות:

סימון	סוג	דוגמאות
Θ(1)	Constant growth	R(n)=1  R(n)=1000  R(n)=123456
Θ(logn)	Logarithmic growth	R(n)=log4(n)  R(n)=log(10n)+500
Θ(n)	Linear growth	R(n)=40n+7*107  R(n)=0.5n+logn
Θ(nlogn)	“n log n” growth	R(n)=50n*(log(800n))+400n+1000
Θ(n2)	Quadratic growth	R(n)=2n2  R(n)=10n2+40n+logn+8
Θ(n3)	Cubic growth	R(n)=6n3  R(n)=10n3+40n2+logn+50
Θ(2n)	Exponential growth	R(n)=3*2n+100n10-70n4+(logn)4

הסוגים ממוינים מיעיל ביותר עד למסובך ביותר.

בד”כ (אבל לא תמיד) סיבוכיות מקום היא ליניארית Θ(n) לתהליכים רקורסיביים וקבועה Θ(1) לתהליכים איטרטיביים.

פרק 2

מבני נתונים (משתנים מורכבים)

 

זוגות

הגדרה:

זוג (pair) הוא משתנה שיש בו מקום לשמירה של שני משתנים אחרים, שכל אחד מהם יכול להיות כל משתנה שהוא, ואפילו זוג אחר.  זוגות מאוד שימושיים בהגדרת מבני נתונים חדשים. הציור הסכמתי של זוג:

 

 

 

קוֹנסטרָקטוֹר  (constructor)  הוא פרוצדורה שבונה את המבנה נתונים חדש. לזוגות קיים קונסטרקטור  cons שמקבל שני פרמטרים ומחזיר זוג.

סלקטור (selector) הוא פרוצדורה שמקבלת מבנה נתונים ומחזירה אחד מהמשתנים ששמורים במבנה נתונים זה. לזוגות קיימים שני סלקטורים:

car מחזיר איבר ראשון בזוג

cdr מחזיר איבר שני בזוג.

 

אפשר להגדיר זוג כפרוצדורה ואז מימוש של קונסטרקטור ושני סלקטורים יהיה:

(define (cons x y)

(lambda (m)

(cond ((= m 0) x)

((= m 1) y)

(else (error “Argument not 0 or not 1”)))))

 

(define (car z) (z 0))

 

(define (cdr z) (z 1))

 

רשימות

הגדרה:

רשימה זה מבנה נתונים שיכול להיות או רשימה ריקה: ()’   או זוג, שהמשתנה השני בו הוא רשימה.

ציור סכמתי של רשימה:

 

 

כל פעולות המוגדרות עבור הזוגות, מוגדרות גם עבור הרשימות.

 

רשימה שאיבריה <el0>, <el1> …<eln>  אפשר להגדיר ב-Scheme בשלושה דרכים:

1. כמו שהגדרנו זוגות:

(cons <el0>

(cons <el1> (cons … (cons <eln> ‘()))))

 

1. ע”י פרוצדורה list (סוכר תחבירי):

(list <el0>, <el1> …<eln>)

 

1. רשימות שלא כוללת בתוכה שמות של משתנים אלא רק ערכיהם אפשר להגדיר ע”י  ‘  :

‘(<el0>, <el1> …<eln>)

עצים

 

הגדרה:

עץ הוא:  עץ ריק (כלומר בלי צמתים)

או:        עלה (צומת המכיל רק שורש ללא תת-עצים)

או:        שורש וכמה תת-עצים, שכל אחד מהם הוא עץ.

 

עץ בינרי הוא:  עץ ריק (כלומר בלי צמתים)

או:                שורש ושני תת-עצים, ימני ושמאלי, שכל אחד מהם הוא עץ בינרי. (שני  עצים אלו זרים

זה לזה, כלומר אין להם צמתים משותפים).

 

ב-Scheme עץ הוא בעצם רשימה של איברים שחלק מהם הם רשימות. הרשימות אלו גם יכולות לכלול רשימות, וכך האלה.

דוגמא לעץ:

‘(4 (5 7) 2)

דוגמה לעץ בינרי:

‘(((1 () ()) (2 () ())) ((3 () ()) (4 () ())))

 

גם לעצים יש קונסטרקטור וסלקטורים:

קונסטרקטור – בנה-עץ:

(define (make-tree entry left right)

(list entry left right))

סלקטור – הצץ-שורש:

(define (entry tree) (car tree))

סלקטור – תת-עץ-שמאלי:

(define (left-branch tree) (cadr tree))

סלקטור – תת-עץ-ימני:

(define (right-branch tree) (caddr tree))

 

סמלים

הגדרה:

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

 

לסמלים יש קונסטרקטור quote , שמקבל פרמטר אחד – “משהוא” ומחזיר את אותו “משהוא” כסמל. אפשר לקצר ובמקום לדוגמה (quote alpha) לרשום alpha’ , וזה נכון לכל ביטוי.

שים לב, הביטויים הבאים שקולים. הביטוי האמצעי הכי נוח לכתיבה:

(quote (a (b) 3) = ‘(a (b) 3) = (list ‘a (list ‘b) 3)

דוגמאות:

> (quote -)

–

> ‘(+ x 5)

(+ x 5)

 

כדי להשוות שני סמלים משתמשים בפרוצדורה eq? , שמקבלת שני סמלים כפרמטרים ומחזירה ‘אמת’ אם הם שווים ו ‘שקר’ אחרת.

 

 

 

אוספי אלמנטים שונים

 

אפשר לייצג אוסף אלמנטים שונים (sets) בשלושה דרכים:

לכל סוג האלמנטים אפשר לייצג את האוסף ע”י

1. רשימה.

לאלמנטים שאפשר למיין אותם, אפשר לייצג את האוסף ע”י

2. רשימה ממוינת.
3. עץ בינרי.

 

בכל ייצוג נממש 4 פרוצדורות של אוסף אלמנטים:

 

(element-of-set? x set)

(adjoin-set x set)

(union-set s1 s2)

(intersection-set s1 s2)

 

שייך-לקבוצה?

הוסף-לקבוצה

איחוד-קבוצות

חיתוך-קבוצות

 

סיבוכיות זמן ריצה של שלושת ייצוגים:

ייצוג ע”י עץ בינרי	ייצוג ע”י רשימה ממוינת	ייצוג ע”י רשימה	פרוצדורה של אוסף
Θ(logn)	Θ(n)	Θ(n)	element-of-set?
Θ(logn)	Θ(n)	Θ(n)	adjoin-set
Θ(nlogn)	Θ(n)	Θ(n2)	union-set
Θ(nlogn)	Θ(n)	Θ(n2)	intersection-set

Data Directed Programming

 

המטרה של Data Directed Programming היא טיפול בייצוגים השונים של מידע.

כך למשל אפשר לייצג מספר מרוכב בשני דרכים:

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

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

Types
Rectangular	Polar
real-part-rectangular	real-part-polar	real-part	operations
imag-part- rectangular	imag-part-polar	imag-part
magnitude- rectangular	magnitude-polar	magnitude-polar
angle- rectangular	angle-polar	angle-polar

 

מהטבלה הזאת נבנה מבנה נתונים חדש. למבנה נתונים זה יהיו 2 קונסטרקטורים ו4 סלקטורים.

קונסטרקטורים:

(define (make-from-real-imag x y)

((get ‘make-from-real-imag ‘rectangular) x y))

 

(define (make-from-mag-ang r a)

((get ‘make-from-mag-an  g ‘polar) r a))

סלקטורים:

(define (real-part z) (apply-generic ‘real-part z))

(define (imag-part z) (apply-generic ‘imag-part z))

(define (magnitude z) (apply-generic ‘magnitude z))

(define (angle z) (apply-generic ‘angle z))

 

 

 

 

ב-DDP יש לנו שתי פרוצדורות הבסיסיות (מימושם ראה בפרק טבלאות):

(put <op> <type> <item>) – מכניסה את הפרוצדורה לטבלה

(get <op> <type>) – מוציאה את הפרוצדורה מהטבלה

לדוגמה:

 

(put ‘real-part ‘(rectangular) foo) => undef

(get ‘real-part ‘(rectangular)) => foo

 

 

(put ‘a ‘(a b c) foo1) => undef

(get ‘a ‘(a b c)) => foo1

הפרוצדורה החשובה ביותר שמתפלת בכל הפניות לכל הפרוצדורות מהטבלה היא:

(define (apply-generic op . args)

(let ((type-tags (map type-tag args)))

(let ((proc (get op type-tags)))

(if proc

(apply proc (map contents args))

(error

“No method for these types — APPLY-GENERIC”

(list op type-tags))))))

 

עד פה על שימוש בטבלה. אבל כמובן – קודם צריך לבנות אותה

:

בניית Polar implementation

בניית Rectangular implementation

(define (install-polar-package);; internal procedures (define (magnitude z) (car z)) (define (angle z) (cdr z)) … (define (make-from-real-imag x y) (cons (sqrt (+ (square x) (square y))) (atan y x))) ;; interface to the rest of the system (define (tag x) (attach-tag ‘polar x)) (put ‘real-part ‘(polar) real-part) (put ‘imag-part ‘(polar) imag-part) (put ‘magnitude ‘(polar) magnitude) (put ‘angle ‘(polar) angle) (put ‘make-from-real-imag ‘polar (lambda (x y) (tag (make-from-real-imag x y)))) (put ‘make-from-mag-ang ‘polar (lambda (r a) (tag (make-from-mag-ang r a)))) ‘done)

(define (install-rectangular-package);; internal procedures   (define (real-part z) (car z)) (define (imag-part z) (cdr z)) … (define (make-from-mag-ang r a) (cons (* r (cos a)) (* r (sin a))))     ;; interface to the rest of the system   (define (tag x) (attach-tag ‘rectangular x)) (put ‘real-part ‘(rectangular) real-part) (put ‘imag-part ‘(rectangular) imag-part) (put ‘magnitude ‘(rectangular) magnitude) (put ‘angle ‘(rectangular) angle) (put ‘make-from-real-imag ‘rectangular (lambda (x y) (tag (make-from-real-imag x y)))) (put ‘make-from-mag-ang ‘rectangular (lambda (r a) (tag (make-from-mag-ang r a)))) ‘done)

 

Message Passing

Message Passing – זה צורה שונה לייצוג Multiple representation of data .

בייצוג זה כל משתנה ששומר מבנה נתונים הוא לא זוג אלא פרוצדורה.

כך למשל יראו קונסטרקטורים:

(define (make-from-real-imag x y)(lambda (op) (cond ((eq? op ‘real-part) x) ((eq? op ‘imag-part) y) ((eq? op ‘magnitude) (sqrt (+ (square x) (square y)))) ((eq? op ‘angle) (atan y x)) (else (error . . . )))))

(define (make-from-mag-ang r a)(lambda (op) (cond ((eq? op ‘real-part) (* r (cos a))) ((eq? op ‘imag-part) (* r (sin a))) ((eq? op ‘magnitude) r) ((eq? op ‘angle) a) (else (error . . . )))))

ואז הסלקטורים יהיו:

(define (real-part z) (z ‘real-part))

(define (imag-part z) (z ‘imag-part))

(define (magnitude z) (z ‘magnitude))

(define (angle z) (z ‘angle))

 

ואז נשתמש במשתנים בצורה הבאה:     (x ‘real-part) ==> 3

 

פרק 3

משפט השמה ומודל הסביבות

משפט השמה

 

משפט השמה מאפשר לנו לשנות את הערכים של המשתנים אחרי הגדרתם.  ב-Scheme זה נעשה  בעזרת פרוצדורה בסיסית set!.

אפשר לתאר את כל המשתנים כמבני נתונים:

קוֹנסטרָקטוֹר  (constructor)

(define x 10)                         מגדיר את המשתה:

סלקטור (selector)

x                        מחזיר ערך של משתנה:                   אין-שם:

מוּטָטוֹר (mutator)

(set! x “foo”)                    משנה ערך של המשתנה:

 

 

מודל הסביבות (Environment Model)

 

מודל הסביבות – זה שרטוט שמתאר מה עושה משערך כשהוא מפעיל פרוצדורה (תוכנית).

לפי מודל הסביבות אפשר לתאר 5 כללים:

 

1. name-rule

חיפוש ערך של המשתנה

2. define-rule

יצירת משתנה חדש

3. set!-rule

שינוי ערך של המשתנה

4. lambda-rule

יצירת פרוצדורה

5. application

הפעלת פרוצדורה

 

חלקי השרטוט:

1. סביבות – מתוארות כמלבנים שבהם רשומים שמות וערכים של כל המשתנים (כולל פרוצדורות המוגדרות בסביבה). אם ערך של משתנה הוא אובייקט (כגון פרוצדורה, זוג, מערך וכד’) אז במקום ערך יש חץ שמצביע על האובייקט. ליד כל סביבה רשום שמה. אם זאת סביבה גלובלית (כלומר בה נמצאים כל הפרוצדורות המוגדרות במשערך וכד'(מוסתרים), ובה מתחילה הרצת התוכנית) – GE (עם חץ), אחרת E ומספרה הסידורי (כגון E5). לכל סביבה חוץ מסביבה גלובלית, יש חץ שיוצא ממנה ל”סביבת אם” שלה.
2. פרוצדורות – משורטטות ע”י Double Bouble – שרטוט של פרוצדורה שחץ ימני שלה מצביע על הסביבה שבה היא הוגדרה, חץ שמאלי מצביע  על הקוד של השגרה. הקוד מורכב מפרמטרים שפרוצדורה מקבלת(p: )  ומקוד של הגוף (b: ).
3. אובייקטים אחרים:

 

זוגות:                                  רשימות:

 

 

 

מערכים:

 

לדוגמה ככה יכולה להראות מודל סביבות הבאה:

 

חמשת הכללים של מודל הסביבות

 

1. name-rule – מחפשים ערך של המשתנה לפי שמו בסביבה נתונה. אם מצאנו – מחזירים את ערכו, אחרת עוברים לסביבה שעליה מצביע סביבה נתונה. וזה כל עוד לא מגיעים לסביבה הגלובלית. אם משתנה לא מופיע גם ב-GE אז נוצרת שגיאה. אם באותה סביבה יש יותר ממשתנה אחד עם אותו שם, אזי מחזירים ערך של משתנה שהוגדר אחרון מביניהם.

 

2. define-rule – יוצרים משתנה חדש ורושמים את שמו בסביבה הנתונה. אם זה משתנה פשוט, אז ליד השם רושמים גם את הערך של המשתנה, אחרת (משתנה מרוכב או פרוצדורה) מציירים חץ משם אל האובייקט.

 

3. set!-rule – משנים את הערך של המשתנה. את הערך הישן אפשר למחוק עם קו אדום ובמקומו לרשום את הערך החדש. אין זה משנה אם הערך הוא פשוט או אובייקט.

 

4. lambda-rule – מייצרים את האובייקט הפרוצדורלי: משרטטים את Double Bouble , קושרים אותו לסביבה שבה הוא מוגדר, ורושמים את הפרמטרים וקוד ביצוע כפי שהוסבר לעיל.

 

5. application– מפעילים את הפרוצדורה. עושים את זה ב-4 שלבים: (לא מבצעים אותם לפרוצדורות המוגדרות במשערך)
   • מייצרים סביבה חדשה ונותנים לה שם. (E עם מספר סידורי שלה)
   • קושרים את הסביבה החדשה ע”י חץ לסביבה, שעליה מצביע הפרוצדורה המופעלת (ה- Double Bouble שלה).
   • רושמים בסביבה החדשה את הפרמטרים (כמשתנים חדשים) עם ערכיהם.
   • מפעילים את הגוף של הפרוצדורה (קוד ביצוע) עם סביבה החדשה.

 

משפט השמה לזוגות

 

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

ואז מבנה נתונים יהיה:

קוֹנסטרָקטוֹר  (constructor)

(cons x y)                         מגדיר את הזוג החדש:

סלקטורים (selectors)

(car p)                                  מחזיר את האיבר הראשון בזוג:

(cdr p)                                        מחזיר את האיבר השני בזוג:

מוּטָטוֹרים (mutators)

(set-car! p new-x)    משנה את האיבר הראשון בזוג:

(set-cdr! p new-y)       משנה את האיבר השני בזוג:

 

כשבונים את רשימה יאחר כך משנים את ה-cdr-ים שלה ע”י מוטטורים אפשר ליצור לולאה, כך שכשפרוצדורה עוברת על כל איבר ברשימה (לדוגמה כדי לחבר אותם) היא נכנסת ללולאה אינסופית, כלומר הרצת פרוצדורה לא תסתיים.

 

 

 

 

 

 

 

 

 

 

 

 

המימוש האפשרי:

(massage passing style)

(define (cons x y)

(define (set-x! v) (set! x v))

(define (set-y! v) (set! y v))

(define (dispatch m)

(cond ((eq? m ‘car) x)

((eq? m ‘cdr) y)

((eq? m ‘set-car!) set-x!)

((eq? m ‘set-cdr!) set-y!)

(else (error “Underfined operation — CONS” m))))

dispatch)

 

(define (car z) (z ‘car))

 

(define (cdr z) (z ‘cdr))

 

(define (set-car! z new-value)

((z ‘set-car!) new-value))

 

(define (set-cdr! z new-value)

((z ‘set-cdr!) new-value))

 

 

 

מחסניות וטורים

 

מחסנית – מבנה נתונים, שבו איבר אחרון שהוכנס – הוא ראשון שיוצא.

 

קוֹנסטרָקטוֹר  (constructor)

(make-stack)                                     בונה מחסנית ריקה ומחזיר אותה:

סלקטורים (selectors)

(top stack)                   מחזיר את האיבר העליון שבמחסנית (אחרון שהוכנס):

פעולות (operations)

(insert stack elt)                               :elt מחזיר מחסנית חדשה, שבה הוכנס

(delete stack)        מחזיר מחסנית חדשה, שבה הוצא האיבר העליון:

(empty-stack? stack)                                         בודק האם מחסנית-ריקה:

 

המימוש של הפרוצדורות:

גירסה א’ (בלי משפט השמה)

(define (make-stack) nil)

(define (empty-stack? stack) (null? stack))

(define (insert stack elt) (cons elt stack))

(define (delete stack)

(if (empty-stack? stack)

(error “stack underflow – delete”)

(cdr stack)))

(define (top stack)

(if (empty-stack? stack)

(error “stack underflow – top”)

(car stack)))

• (define s make-stack))
• s è ()
• (insert s ‘a) è (a)
• s è ()
• (set! s (insert s ‘b))
• s è (b)

 

גירסה ב’  (עם משפט השמה)

(define (make-stack) (cons ‘stack nil))

(define (stack? stack)

(and (pair? stack) (eq? ‘stack (car stack))))

(define (empty-stack? stack)

(if (not (stack? stack))

(error “object not a stack:” stack)

(null? (cdr stack))))

(define (insert! stack elt)

(cond ((not (stack? stack))

(error “object not a stack:” stack))

(else

(set-cdr! stack (cons elt (cdr stack)))

stack)))

(define (delete! stack)

(if (empty-stack? stack)

(error “stack underflow – delete”)

(set-cdr! stack (cddr stack)))

stack)

(define (top stack)

(if (empty-stack? stack)

(error “stack underflow – top”)

(cadr stack)))

 

• (define s make-stack))
• s è (stack)
• (insert! s ‘a) è (stack a)
• s è (stack a)
• (set! s (insert! s ‘b))
• s è (stack b a)

 

 

טור – מבנה נתונים, שבו איבר ראשון שהוכנס – הוא ראשון שיוצא.

 

גירסה א’ (בלי משפט השמה)

קוֹנסטרָקטוֹר  (constructor)

(make-queue)                                         בונה טור ריק ומחזיר אותו:

סלקטור (accessor)

(front-queue q)            מחזיר את האיבר הראשון שבטור (ראשון שהוכנס):

מוּטָטוֹרים (mutators)

(insert-queue q elt)                               :elt מחזיר טור חדש, שבו הוכנס

(delete-queue q)         מחזיר טור חדש, שבו הוצא האיבר הראשון:

פעולה (operation)

(empty-queue? q)                                                  בודק האם טור-ריק:

 

המימוש של הפרוצדורות:

(define (make-queue) nil)

(define (empty-queue? q) (null? q))

(define (front-queue q)

(if (empty-queue? q)

(error “front of empty queue:” q)

(car q)))

(define (delete-queue q)

(if (empty-queue? q)

(error “delete of empty queue:” q)

(cdr q)))

(define (insert-queue q elt)

(if (empty-queue? q)

(cons elt nil)

(cons (car q) (insert-queue (cdr q) elt))))

 

 

גירסה ב’  (עם משפט השמה) – יעילה יותר

קוֹנסטרָקטוֹר  (constructor)

(make-queue)                                         בונה טור ריק ומחזיר אותו:

סלקטור (accessor)

(front-queue q)            מחזיר את האיבר הראשון שבטור (ראשון שהוכנס):

מוּטָטוֹרים (mutators)

(insert-queue! q elt)                                 :מכניס את האיבר לטור(לזנב)

(delete-queue! q)                         מוציא את האיבר מראש הטור:

פעולות (operations)

(queue? q)                                                   בודק האם משתנה הוא טור:

(empty-queue? q)                                                  בודק האם טור-ריק:

 

 

המימוש של הפרוצדורות:

 

 

 

 

 

 

 

 

 

 

פרוצדורות עזר:

(define (front-ptr q) (cadr q))

(define (rear-ptr q)  (cddr q))

(define (set-front-ptr! q item)

(set-car! (cdr q) item))

(define (set-rear-ptr! q item)

(set-cdr! (cdr q) item))

 

פרוצדורות של מימוש (עם תכנון הגנתי – defensive programming)

(define (make-queue)

(cons ‘queue (cons nil nil)))

(define (queue? q)

(and (pair? q) (eq? ‘queue (car q))))

(define (empty-queue? q)

(if (not (queue? q))                 ;defensive

(error “object not a queue:” q)  ;programming

(null? (front-ptr q))))

(define (front-queue q)

(if (empty-queue? q)

(error “front of empty queue:” q)

(car (front-ptr q))))

(define (insert-queue! q elt)

(let ((new-pair (cons elt nil)))

(cond ((empty-queue? q)

(set-front-ptr! q new-pair)

(set-rear-ptr! q new-pair)

q)

(else

(set-cdr! (rear-ptr q) new-pair)

(set-rear-ptr! q new-pair)

q))))

 

 

 

 

 

 

 

(define (delete-queue! q)

(cond ((empty-queue? q)

(error “delete of empty queue:” q))

(else

(set-front-ptr! q

(cdr (front-ptr q)))

q)))

 

 

 

 

טבלאות

 

טבלה – מבנה נתונים שעוזר לטפל במאגרי מידע גדולים.

יש סוגים שונים של טבלאות, שהם נבדלים במימד (חד-מימדיות, דו-מימדיות, תלת-מימדיות וכד’).

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

 

• דוגמה ציורית לטבלה חד-מימדית: מפתחות – אותיות, ערכים – מספרם הסידורי

 

 

 

 

 

 

 

• דוגמא לטבלה דו-מימדית: מפתחות ראשיים – מדינות, מפתחות משניים – ערים חשובים במדינות, ערכים – מספר התושבים בעיר.

כלומר כדי לקבל מספר תושבים בניו-יורק מטבלה sity צריך לכתוב:

(lookup ‘USA ‘New-York sity) ==> 9200000

ואם אוכלוסייה בעיר גדלה ל 10 מיליון אז משנים את הערך באופן הבא:

(insert! ‘USA ‘New-York 10000000 sity) ==> ok

אבל בהתחלה צריך לבנות את הטבלה וזה עושים באופן הבא:

(define sity (make-table))

ואז ממלאים אותה באותה צורה כמו שמשנים ערכים.

 

מימוש טבלה חד-מימדית

(define (make-table)(list ‘*table*))

(define (assoc key records)

(cond ((null? records) false)

((equal? key (caar records)) (car records))

(else (assoc key (cdr records)))))

 

(define (lookup key table)

(let ((record (assoc key (cdr table))))

(if record

(cdr record)

false)))

(define (insert! key value table)

(let ((record (assoc key (cdr table))))

(if record

(set-cdr! record value)

(set-cdr! table

(cons (cons key value) (cdr table)))))

‘ok)

 

 

מימוש טבלה דו-מימדית (make-table ו- assocנשארים אותו דבר)

(define (lookup key-1 key-2 table)

(let ((subtable (assoc key-1 (cdr table))))

(if subtable

(let ((record (assoc key-2 (cdr subtable))))

(if record

(cdr record)

false))

false)))

 

 

(define (insert! key-1 key-2 value table)

(let ((subtable (assoc key-1 (cdr table))))

(if subtable

(let ((record (assoc key-2 (cdr subtable))))

(if record

(set-cdr! record value)

(set-cdr! subtable

(cons (cons key-2 value)

(cdr subtable)))))

(set-cdr! table

(cons (list key-1

(cons key-2 value))

(cdr table)))))

‘ok)

 

 

 

דוגמה נוספת:

(lookup ‘elections ‘Florida table)

==> Bush

(insert! ‘elections ‘California ‘Gore table)

==> ok

 

 

 

 

 

 

 

כשדיברנו על Data Directed Programming הגדרנו פעולות get ו-put . עכשיו זהו זמן לממש אותם:

(define oper-table (make-table))

(define (put x y v) (insert! x y v oper-table))

(define (get x y) (lookup x y oper-table))

 

Object Oriented Programming

 

OOP מאפשר להפוך את מבנה נתונים ופעולות המוגדרות על מבנה נתונים זה לאובייקט פרוצדורלי חכם, שמכיל בתוכו את נבנה עצמו, את כל הפרוצדורות (פעולות) על המבנה הנתונים, ופרוצדורה עיקרית, שמתפלת בעברת פרמטרים לפרוצדורות האלה – בד”כ dispatch.

ראה דוגמה בפרק “משפט השמה לזוגות”.

 

כלומר, אם בשיטה רגילה כותבים:

(do-something <data> <arg> …)

(do-another-thing <data>)

 

 

בעזרת OOP כותבים:

(<object> ‘do-something <arg>)

 

(<object> ‘do-another-thing)

 

 

כך למשל אפשר להגדיר class של מחסניות:

(define (make-stack)

(let ((top-ptr ‘()))

(define (empty?) (null? top-ptr))

(define (delete!)

(if (null? top-ptr) (error . . .)

(set! top-ptr (cdr top-ptr)))

top-ptr )

(define (insert! elmt)

(set! top-ptr (cons elmt top-ptr))

top-ptr)

(define (top) (if (null? top-ptr) (error . . .)

(car top-ptr)))

(define (dispatch op)

(cond ((eq? op ’empty?) empty?)

((eq? op ‘top) top)

((eq? op ‘insert!) insert!)

((eq? op ‘delete!) delete!)))

dispatch))

 

> (define a (make-stack))

a הוא instance של class המחסניות

 

אפשר להגדיר טור בעזרת שני מחסניות ואז במונחים של OOP class של טורים יהיה subclass של class המחסניות.

 

ואם גם טבלאות להגדיר בשיטת OOP אז מימוש של get ו-put יראה כך:

 

(define operation-table (make-table))

(define get (operation-table ‘lookup-proc))

(define put (operation-table ‘insert-proc!))

 

 

 

 

זרמים (streams), זרמים אינסופיים, זרמים מורכבים

 

זרם – מבנה נתונים מיוחד, שדומה לרשימה, כלומר מורכב מזוגות, שהמשתנה הראשון בהם הוא איבר של הזרם, והמשתנה השני – המשך של הזרם, שלא בנוי, אבל יבנה כשיבקשו זאת (ע”י stream-cdr).

הגדרה יותר פורמלית :

זרם זה מבנה נתונים שיכול להיות או זרם ריק: ()’   או זוג, שהמשתנה השני בו הוא הבטחה לזרם.

 

קוֹנסטרָקטוֹר  (constructor)

cons-stream מקבל שני פרמטרים ומחזיר זרם.

סלקטורים (selectors):

stream-car מחזיר איבר ראשון בזוג של הזרם.

stream-cdr מפעיל את ההבטחה ומחזיר איבר שני בזוג של הזרם.

מימוש של הפרוצדורות:

(define (cons-stream a b)

(cons a (delay b))

 

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

 

 

 

(define (delay exp) (memo-proc (lambda () exp)))

(define (force delayed-object) (delayed-object))

 

(define (memo-proc proc)

(let ((already-run? false) (result false))

(lambda ()

(if (not already-run?)

(begin (set! result (proc))

(set! already-run? true)

result)

result))))

פרוצדורה memo-proc היא מימוש של שיטה שנקראת memoization, שזוכרת אם פרוצדורה כבר הורצה, אם כן – מחזירה את התוצאה של ההרצה, אם לא – מריצה אותה ושומרת את התוצאה, כדי להחזיר אותה פעם הבאה.

מכיוון שזרם לא נבנה מייד כולו אפשר להגדיר זרמים אינסופיים. לדוגמה:

(define ones (cons-stream 1 ones)) è 1 1 1 1 1 1 …

 

 

 

 

 

מערכים

מערך (vector)– מבנה נתונים שגודלו קבוע והוא מאפשר לשמור הרבה מידה להגיע בקלות לכל איבר.

יתרונות – אפשר להגיע לכל איבר בזמן O(1). אפשר קל מאוד לשנות כל איבר. מקל על פעולות חיפוש ומיון.

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

 

 

ציור סכמתי:

 

קוֹנסטרָקטוֹרים  (sconstructor)

#(…)                                                   בונה מערך מ-0  או ויתר איברים:

(vector …)                                          בונה מערך מ-0  או ויתר איברים:

בונה מערך באורך k שאיבריו אפסים:                                  (make-vector k)

בונה מערך באורך k שאיבריו init:                               (make-vector k init)

סלקטורים (accessors)

מחזיר את האורך של המערך (0 = ריק ) :                       (vector-length vec)

מחזיר את האיבר שבמקום k=0…  במערך vec:                  (vector-ref vec k)

מוּטָטוֹר (mutator)

מכניס את האיבר elt למקום k=0… במערך vec:          (vector-set! vec k elt)

פעולות (operations)

בודק האם משתנה הוא מערך:                                                 (vector? obj)

 

חיפוש:

חיפוש במערך דומה לחיפוש ברשימה.

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

(define (bin-search vec x)

(define (search left right)

(if (> left right)

nil

(let* ((mid (average left right))

(mid-item (vector-ref vec mid)))

(cond ((= x mid-item) mid)

((< x mid-item) (search left (- mid 1)))

(else        (search (+ mid 1) right))))))

(search 0 (- (vector-length vec) 1)))

 

(define (average x y)

(round (/ (+ x y) 2)))

הערה:  let* מתחייב על הסדר בו רשומים הדברים(ראה let).            סיבוכיות זמן ריצהΘ(logn)

 

מיון:

מיון בועות(Bubble sort) :

מתחיל מהאיבר האחרון. אם הוא קטן מהקודם לו אז מחליפים. בסוף כל תת שלב הכי קטן יהיה בהתחלה.

(define (bubble-sort vec)

(define n (vector-length vec))

(define (iter i)

(define (bubble j)

(if (>= j i)

(let ((prev (vector-ref vec (- j 1)))

(cur (vector-ref vec j)))

(cond ((> prev cur)

(vector-set! vec (- j 1) cur)

(vector-set! vec j prev)))

(bubble (- j 1)))))

(cond ((< i n)

(bubble (- n 1))

(iter (+ i 1)))))

(iter 1))

 

 

נספח

פרוצדורות

 

ספרייה של פרוצדורות המוכרות ע”י משערך DrScheme

 

פרוצדורות שוויון

תפקיד	מס’ פרמטרים	שם פרוצדורה
משווה בין מספרים	1, …	=
משווה בין מספרים, סמלים וערכים בוליאניים	2	eqv?
משווה בין סמלים וערכים בוליאניים	2	eq?
משווה בין משתנים מכל סוג, כולל רשימות חוץ מפרוצדורות	2	equal?
משווה בין מחרוזות	1, …	string=?
משווה בין תווים	1, …	char=?

 

פרוצדורות בוליאניות

בודק אם פרמטר הוא משתנה בוליאני	1	boolean?
הופך את #t ל #f    ואת #f ל #t	1	not
מחזיר #t אם כל הפרמטרים הם #t ,ו #f אחרת	0, …	and
מחזיר #f אם כל הפרמטרים הם #f ,ו #t אחרת	0, …	or

 

פרוצדורות על המספרים

בודק אם פרמטר הוא מספר	1	number?
בודק אם פרמטר הוא מספר מרוכב,  כגון 5+1i	1	complex?
בודק אם פרמטר הוא מספר ממשי	1	real?
בודק אם פרמטר הוא מספר רציונלי	1	rational?
בודק אם פרמטר הוא מספר שלם	1	integer?
בודק אם פרמטר הוא מספר שלם מדויק,  כגון 6	1	exact?
בודק אם פרמטר הוא מספר שלם לא מדויק,  כגון 6.0	1	inexact?
בודק אם כל המספרים שווים	1, …	=
בודק אם כל מספר קטן ממספר הבא	1, …	<
בודק אם כל מספר גדול ממספר הבא	1, …	>
בודק אם כל מספר קטן או שווה למספר הבא	1, …	<=
בודק אם כל מספר גדול או שווה למספר הבא	1, …	>=
בודק אם פרמטר הוא מספר ששווה לאפס	1	zero?
בודק אם פרמטר הוא מספר חיובי	1	positive?
בודק אם פרמטר הוא מספר שלילי	1	negative?
בודק אם פרמטר הוא מספר אי-זוגי (מוגדר למספרים שלמים)	1	odd?
בודק אם פרמטר הוא מספר זוגי (מוגדר למספרים שלמים)	1	even?
מחזיר הפרמטר הגדול ביותר	1, …	max
מחזיר הפרמטר הקטן ביותר	1, …	min
מחזיר סכום של פרמטרים (כשאין מחזיר 0)	0, …	+
מחזיר מכפלה של פרמטרים (כשאין מחזיר 1)	0, …	*
מחסיר ממספר ראשון את סכום של המספרים האחרים	1, …	–
אם יש פרמטר אחד, אז הערך המוחזר הוא 1 חלקי מספר זה, אחרת תוחזר חילוק של מספר ראשון במכפלה של שאר מספרים	1, …	/
מחזיר מספר אקראי a, כך ש-    פרמטר>≤a0	1	random
מחזיר את ערך המוחלט של הפרמטר	1	abs
מחזיר מנה של חילוק מספר ראשון בשני	2	quotient
מחזיר שארית של חילוק מספר ראשון בשני(remainder 13 4)       =>  1 (remainder -13 4)      => -1 (remainder 13 -4)      =>  1 (remainder -13 -4)     => -1	2	remainder
מחזיר שארית של חילוק מספר ראשון בשני לפי ערך מוחלט(modulo 13 4)          =>  1 (modulo -13 4)         =>  3 (modulo 13 -4)         => -3 (modulo -13 -4)        => -1	2	modulo
מחזיר המחלק המשותף הגדול ביותר של הפרמטרים(ללא פרמטרים מוחזר 0)  (הערך המוחזר תמיד אי-שלילי)	0, …	gcd
מחזיר הכפולה המשותפת הקטנה ביותר של הפרמטרים(ללא פרמטרים מוחזר 1)  (הערך המוחזר תמיד אי-שלילי)	0, …	lcm
מחזיר את המונה של הפרמטר (שבר מצומצם)(numerator (/ 6 4))    =>  3	1	numerator
מחזיר את המכנה של הפרמטר (שבר מצומצם)(denominator (/ 6 4))  =>  2	1	denominator
מחזיר מספר שלם הגדול ביותר שלא גדול מהפרמטר(floor –4.3)           => -5.0 (floor 3.5)            =>  3.0	1	floor
מחזיר מספר שלם הקטן ביותר שלא קטן מהפרמטר(ceiling –4.3)         => -4.0 (ceiling 3.5)          =>  4.0	1	ceiling
מחזיר מספר שלם הקרוב ביותר לפרמטר, שהערך המוחלט שלו לא יהיה גדול מהערך המוחלט של הפרמטר(truncate –4.3)        => -4.0 (truncate 3.5)         =>  3.0	1	truncate
מחזיר ערך השלם הקרוב ביותר לפרמטר(round –4.3)           => -4.0 (round 3.5)            =>  4.0	1	round
מחזיר מספר רציונלי הפשוט ביותר, ששונה מפרמטר הראשון (אי-רציונלי) בלא יותר מפרמטר השני.(rationalize (inexact->exact 0.3) 1/10)  => 1/3	2	rationalize
מחזיר את e בחזקת הפרמטר	1	exp
מחזיר את הלוגריתם אם בסיס e של הפרמטר	1	log
מחזיר סינוס של פרמטר (ברדיאנים)	1	sin
מחזיר קוסינוס של פרמטר (ברדיאנים)	1	cos
מחזיר טנגנס של פרמטר (ברדיאנים)	1	tan
מחזיר ארק-סינוס של פרמטר (ברדיאנים)	1	asin
מחזיר ארק-קוסינוס של פרמטר (ברדיאנים)	1	acos
פרמטר אחד:   מחזיר ארק-טנגנס של פרמטר (ברדיאנים)שני פרמטרים: מחזיר ארק-טנגנס של זווית שמוגרת ע”י פרמטרים כמו ע”י שני ניצבי המשולש, בעזרת נוסחה: (angle (make-rectangular פרמטר1 פרמטר2))  (ראה בהמשך)	1, 2	atan
מחזיר שורש של הפרמטר. למספרים שליליים מוחזר מספר מרוכב	1	sqrt
מחזיר את הפרמטר1 בחזקת פרמטר2 (מספרים רציונליים)	2	expt
מחזיר מספר מרוכב שבו פרמטר ראשון הוא חלק שלם ופרמטר שני הוא חלק המדומה	2	make-rectangular
מחזיר מספר מרוכב שבו פרמטר ראשון הוא אורך הוקטור של מספר מרוכב, ופרמטר שני הוא הזווית	2	make-polar
מחזיר חלק שלם של מספר מרוכב	1	real-part
מחזיר חלק מדומה של מספר מרוכב	1	imag-part
מחזיר את אורך הוקטור של מספר מרוכב	1	magnitude
מחזיר את הזווית של מספר מרוכב	1	angle
מעביר ממספר רציונלי למספר אי-רציונלי, כגון מ 2 ל 2.0	1	exact->inexact
מעביר ממספר אי-רציונלי למספר רציונלי, כגון מ 3.5 ל 7/5	1	inexact->exact
מעביר ממספר למחרוזת. פרמטר שני הוא בסיס של המספר שיכול להיות: 2, 8, 10 או 16. אם אין פרמטר שני – בסיס 10	1, 2	number->string
מעביר ממחרוזת למספר. פרמטר שני הוא בסיס של המספר שיכול להיות: 2, 8, 10 או 16. אם אין פרמטר שני – בסיס 10	1, 2	string->number

 

פרוצדורות על זוגות

בודק אם פרמטר הוא זוג	1	pair?
מחזיר זוג שאיברו הראשון – פרמטר1, ואיברו השני –פרמטר2	2	cons
מחזיר את האיבר הראשון של הזוג	1	car
מחזיר את האיבר השני של הזוג	1	cdr
מכניס את פרמטר2(כלשהו) לאיבר הראשון של הפרמטר1(זוג)	2	set-car!
מכניס את פרמטר2(כלשהו) לאיבר השני של הפרמטר1(זוג)	2	set-cdr!
מקבל זוג ומחזיר משהיה מחזיר רצף הפרוצדורות car וcdr  התאים, כך למשל:(define caddr (lambda (x) (car (cdr (cdr x))))) השם של פרוצדורה מורכב מאות ראשונה c, אחרונה r, וצירוף כלשהו של אותיות a ו d באורך מ-2 עד 4.	1	caarcadr . . . . cdddar cddddr

פרוצדורות על רשימות

בודק אם הרשימה ריקה	1	null?
בודק אם הפרמטר הוא רשימה	1	list?
מחזיר רשימה חדשה, שאיבריה הם פרמטרים	0, …	list
מחזיר אורך הרשימה (מספר האיברים)	1	length
מחבר פרמטרים, שחייבים להיות רשימות, לרשימה אחת	0, …	append
מחזיר את הרשימה החדשה שאיבריה בסדר הפוך	1	reverse
מחזיר את תת-רשימה של רשימה(פרמטר1) החל ממקום שמציין פרמטר2, כולל. (איבר ראשון ברשימה מספרו – 0)	2	list-tail
מחזיר את האיבר של רשימה(פרמטר1), שנמצא במקום שמציין פרמטר2. (איבר ראשון ברשימה מספרו – 0)	2	list-ref
פרמטר1 – משתנה, פרמטר2 – רשימה . אם משתנה נמצא ברשימה – מחזיר תת-רשימה החל מהמשתנה, אחרת  #f.פרוצדורות משתמשות להשוואה ב eq?, eqv? ו- equal? בהתאמה. לדוגמה:                 (memq ‘b ‘(a b c))  è (b c) (member (list ‘a) ‘(b (a) c))   è  ((a) c)	2	memq
	2	memv
	2	member
פרמטר1 – משתנה, פרמטר2 – רשימה של זוגות . אם פרמטר1  הוא איבר ראשון באחד הזוגות – מחזיר את הזוג, אחרת  #f . פרוצדורות משתמשות להשוואה ב eq?, eqv? ו- equal? בהתאמה.	2	assq
	2	assv
	2	assoc

 

פרוצדורות על סמלים

בונה סמל	1	quote
בודק האם הפרמטר הוא סמל	1	symbol?
מעביר את הסמל למחרוזת	1	symbol->string
מעביר את המחרוזת לסמל	1	string->symbol

 

פרוצדורות על פרוצדורות

בודק האם פרמטר הוא פרוצדורה	1	procedure?
פרמטר1 – פרוצדורה, פרמטר אחרון – רשימהמוסיף את הפרמטרים  מ-2 עד לפני אחרון להתחלה של רשימה, ומפעיל את הפרוצדורה על האיברים ברשימה המתקבלת > (apply * (list 3 4)) 12 > (apply + 1 2 3 (list 5 6 7)) 24	2, …	apply
פרמטר1 – פרוצדורה, שאר הפרמטרים – רשימותשני פרמטרים: פרוצדורה צריכה לקבל פרמטר אחד. מוחזרת רשימה שאיבריה הם תוצאות של הפעלת פרוצדורה על כל אחד מאיברי הרשימה(פרמטר2) אחרת          : פרוצדורה צריכה לקבל מספר פרמטרים כמספר הרשימות. אורך הרשימות חייב להיות זהה. מוחזרת רשימה שאיבר n-י בה הוא תוצאה של הפעלת פרוצדורה על כל אחד מאיברי n ברשימות(פרמטרים) > (map cadr ‘((a b) (d e) (g h))) (b e h) > (map (lambda (n) (expt n n)) ‘(1 2 3 4 5)) (1 4 27 256 3125) > (map + ‘(1 2 3) ‘(4 5 6)) (5 7 9)	2, …	map
פרמטר1 – פרוצדורה, שאר הפרמטרים – רשימותשני פרמטרים: פרוצדורה צריכה לקבל פרמטר אחד. מפעילה פרוצדורה על כל אחד מאיברי פרמטר2. לא מוחזר ערך. אחרת          : פרוצדורה צריכה לקבל מספר פרמטרים כמספר הרשימות. אורך הרשימות חייב להיות זהה. מפעילה פרוצדורה על כל אחד מאיברים מקבילים ברשימות(פרמטרים) > (for-each (lambda (x) (display x)) ‘(1 2 3 4 5 6 7 8 9)) 123456789 > (for-each (lambda (x y) (display (* x y)) (display #\space)) ‘(1 2 3) ‘(1 3 5)) 1 6 15	2, …	for-each

 

הדפסות

מדפיס את הפרמטר	1	write
מדפיס את הפרמטר	1	display
מעביר מצביע לשורה הבאה (מדפיס שורה)	1	newline
מדפיס תו	1	write-char

הערה: 4 פרוצדורות האחרונות יכולות לקבל 2 פרמטרים, ואז פרמטר 2 – port שעליו מדפיסים.

 

פרוצדורות לפרק 1

 

1+

פרוצדורה מוסיפה 1 לפרמטר

(define (1+ x) (+ 1 x))

> (1+ 4.2)

5.2

-1+

פרוצדורה מוסיפה 1- לפרמטר

(define (-1+ x) (- x 1))

> (-1+ 4.2)

3.2

average

פרוצדורה מחזירה ממוצע חשבוני של שני פרמטרים

(define (average x y) (/ (+ x y) 2))

> (average 7 1)

4

square

פרוצדורה מחזירה את הפרמטר בריבוע

(define (square x) (* x x))

> (square 5)

25

sqrt

פרוצדורה מחזירה את השורש המקורב של הפרמטר החיובי

(define (sqrt x)

(define (good-enough? guess)

(< (abs (- (square guess) x)) 0.001))

(define (improve guess)

(average guess (/ x guess)))

(define (sqrt-iter guess)

(if (good-enough? guess)

guess

(sqrt-iter (improve guess))))

(sqrt-iter 1.0))

> (sqrt 25)

5.000023178253949

our-print

פרוצדורה מדפיסה פרמטר בשורה חדשה

(define (our-print x)

(newline) (display x) x)

> (our-print 5)

 

5

5

exp-1

מעלה פרמטר1 בחזקת פרמטר2  – רקורסיבי

(define exp-1 (lambda (a b)

(if (= b 0) 1 (* a (exp-1 a (- b 1))))))

> (exp-1 3 4)

81

 

exp-2

מעלה פרמטר1 בחזקת פרמטר2  – איטרטיבי

(define (exp-2 a b)

(define (exp-iter a b product)

(if (= b 0)

product

(exp-iter a (- b 1) (* a product))))

(exp-iter a b 1))

> (exp-2 4 5)

1024

fast-exp-1

מעלה פרמטר1 בחזקת פרמטר2  – מהיר

(define (fast-exp-1 a b)

(cond ((= b 1) a)

((even? b) (fast-exp-1 (* a a) (/ b 2)))

(else (* a (fast-exp-1 a (- b 1))))))

> (fast-exp-1 2 10)

1024

fact

פרוצדורה מחזירה את n! (n עצרת) של הפרמטר(מספר טבעי)  – רקורסיבי

(define (fact n)

(if (= n 1) 1

(* n (fact (- n 1)))))

> (fact 4)

24

ifact

פרוצדורה מחזירה את n! (n עצרת) של הפרמטר(מספר טבעי)  – איטרטיבי

(define (ifact n)

(define (ifact-helper product count n)

(if (> count n) product

(ifact-helper (* product count)

(+ count 1) n)))

(ifact-helper 1 1 n))

> (ifact 5)

120

inverse

הופך את המספר השלם (פרמטר)

(define (inverse x)

(define (add-item x num)

(if (= x 0) num

(add-item (quotient x 10)

(+ (* num 10) (remainder x 10)))))

(if (< x 0)

(- (add-item (- x) 0))

(add-item x 0)))

> (inverse 1234)

4321

> (inverse -3448)

-8443

> (inverse 50000)

5

 

sum-digits

מחזיר סכום ספרות של פרמטר (מספר טבעי)

(define (sum-digits n)

(if (< n 10)

n

(+ (remainder n 10) (sum-digits (quotient n 10)))))

> (sum-digits 1024)

7

> (sum-digits 885324)

30

prime?

בודק האם מספר ראשוני

(define (prime? n)

(= n (smallest-divisor n)))

(define (smallest-divisor n)

(find-divisor n 2))

(define (find-divisor n test-divisor)

(cond ((> (square test-divisor) n) n)

((divides? test-divisor n) test-divisor)

(else (find-divisor n (+ test-divisor 1)))))

(define  (divides? a b)

(= (remainder b a) 0))

> (prime? 13)

#t

> (prime? 14)

#f

fast-prime?

בודק האם מספר ראשוני  – מהיר

(define (expmod base exp m)

(cond ((= exp 0) 1)

((even? exp)

(remainder (square (expmod base (/ exp 2) m)) m))

(else

(remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test n)

(define (try-it a) (= (expmod a n n) a))

(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)

(cond ((= times 0) #t)

((fermat-test n) (fast-prime? n (- times 1)))

(else #f)))

> (fast-prime? 19 3)

#t

binom-coef

מחשב את

(define (binom-coef n k)

(cond ((> k n) 0)

((or (= k 0) (= k n)) 1)

(else (+ (binom-coef (- n 1) (- k 1))

(binom-coef (- n 1) k)))))

> (binom-coef 6 3)

20

 

fib

מחשב את מספר פיבונצ’י  – רקורסיבי ולא יעיל Θ(2ⁿ)

(define (fib n)

(cond ((= n 0) 1)

((= n 1) 1)

(else (+ (fib (- n 1)) (fib (- n 2))))))

> (fib 5)

8

ifib

מחשב את מספר פיבונצ’י  – איטרטיבי ויעיל  Θ(n)

(define (ifib n)

(define (iter n a b)

(cond ((= n 0) b)

((= n 1) a)

(else (iter (- n 1) (+ a b) a))))

(iter n 1 1))

> (ifib 5)

8

> (ifib 100)

573147844013817084101

gcd

מחזיר מחלק משותף הגדול ביותר של שני מספרים

(define (gcd a b)

(if (= b 0)

a

(gcd b (remainder a b))))

> (gcd 20 50)

10

shift

מקבלת פונקציה F (פרמטר1) וערך a (פרמטר2) ומחזירה פונקציה G, כך ש-   G(x) = F(x+a)

(define (shift f a) (lambda (x) (f (+ x a))))

> ((shift square 3) 2)

25

compose

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

(define (compose F G) (lambda (x) (F (G x))))

> ((compose square 1+) 7)

64

> ((compose 1+ square) 7)

50

repeatedly

מקבל פרוצדורה וערך ומחזירה את הפרוצדורה הקוראת לערכים שלה n (פרמטר2) פעמים

(define (repeatedly fn n)

(lambda (x) (if (= n 1)

(fn x)

((compose fn (repeatedly fn (- n 1))) x))))

> (define 5+ (repeatedly 1+ 5))

> (5+ 100)

105

 

accum

פרוצדורת הכללה בסדרות (חיבור כל האיברים מ1 עד 10, כפל ריבועי כל האיברים הזוגיים מ2 עד 6 וכד’)

op – פרוצדורה שמופעלת על כל איברים (לדוגמה חיבור או כפל)

term – פרוצדורה שמופעלת על כל איבר בסדרה בנפרד, ומעבירה אותם לארגומנטים של op

a – איבר ראשון בסדרה

next – פרוצדורה שמקבלת איבר ואומר איזה איבר אחריו

b – איבר אחרון בסדרה (גבול עליון לאיברי הסדרה)

init – לסכום :0     לכפל: 1  לכל השאר לפי דרישות של op

(define (accum op term a next b init)

(if (> a b)

init

(op (term a)

(accum op term (next a) next b init))))

> (define (sum term a next b)

(accum + term a next b 0))

> (define (1+ x) (+ 1 x))

> (define (square x) (* x x))

> (sum square 1 1+ 5)

55

(1² + 2² + 3² + 4² + 5²) = 55          וזה מכיוון ש-

sum

הפרוצדורה דומה ל-accum, רק שהיא עובדת לחיבור בלבד

> (define (sum term a next b)

(if (> a b)

0

(+ (term a)

(sum term (next a) next b))))

 

זוגות ורשימות

 

+

מחזיר סכום של מספר כלשהו של פרמטרים

(define (+ . x)

(define (add-list lst)

(if (null? lst)

0

(add (car lst) (add-list (cdr lst)))))

(add-list x))

map

מוחזרת רשימה שאיבריה הם תוצאות של הפעלת פרוצדורה על כל אחד מאיברי הרשימה

(define (map proc lst)

(if (null? lst)

null

(cons (proc (car lst))

(map proc (cdr lst)))))

> (map (lambda (n) (expt n n))

‘(1 2 3 4 5))

(1 4 27 256 3125)

 

 

lsts – רשימה של רשימות. אורך הרשימות חייב להיות זהה. מוחזרת רשימה שאיבר n-י בה הוא תוצאה של הפעלת פרוצדורה על כל אחד מאיברי n ברשימות

(define (map-all proc . lsts)

(define (iter proc lists)

(if (null? (car lists))

null

(cons (apply proc (map car lists)) (iter proc (map cdr lists)))))

(iter proc lsts))

> (map-all * ‘() ‘() ‘())

()

> (map-all (lambda (x) (+ x 1)) ‘(2 3) )

(3 4)

> (map-all (lambda (x y z) (+ x (* y z))) ‘(2 3) ‘(4 5) ‘(6 7))

(26 38)

for-each

מפעיל פרוצדורה על כל איבר ברשימה. אין ערך המוחזר ולכן מוחזר #t.

(define (for-each proc lst)

(proc (car lst))

(if (not (null? (cdr lst))) (for-each proc (cdr lst)))

#t)

> (for-each (lambda (x) (display x)) ‘(0 1 2 3 4 5))

012345

#t

atom?

בודק שפרמטר לא זוג ולא רשימה ריקה

(define (atom? z)

(and (not (pair? Z)) (not (null? z))))

list-ref

מחזיר איבר מרשימה שבמקום n. (המקומות הם מ-0)

(define (list-ref lst n)

(if (= n 0)

(car lst)

(list-ref (cdr lst)

(- n 1))))

> (list-ref ‘(1 2 3 4 5) 2)

3

length

מחזיר אורך הרשימה

(define (length lst)

(if (null? lst)

0

(+ 1 (length (cdr lst)))))

> (length ‘(1 2 3 4 5 6 0))

7

 

enumerate-interval

בונה רשימה שאיבריה מ-from עד to.

(define (enumerate-interval from to)

(if (> from to)

‘()

(cons from

(enumerate-interval (+ 1 from) to))))

> (enumerate-interval 2 6)

(2 3 4 5 6)

reverse

הופך את הרשימה

(define (reverse lst)

(cond ((null? lst) lst)

(else (append (reverse (cdr lst)) (list (car lst))))))

> (reverse ‘(1 2 (3 4) 5))

(5 (3 4) 2 1)

deep-reverse

הופך את הרשימה וכל תת-רשימות

(define (deep-reverse lst)

(if (pair? lst) (map deep-reverse (reverse lst)) lst))

> (deep-reverse ‘(1 2 (3 4) 5))

(5 (4 3) 2 1)

append

מחבר שתי רשימות לרשימה אחת

(define (append list1 list2)

(cond ((null? list1) list2)

(else

(cons (car list1)

(append (cdr list1) list2)))))

> (append ‘(1 2) ‘(3 4))

(1 2 3 4)

filter

סינון: pred מקבלת כל איבר בנפרד. אם עבורו היא מחזירה #t אז הוא נכנס לרשימה חדשה, אחרת לא נכנס

(define (filter pred lst)

(cond ((null? lst) ‘())

((pred (car lst))

(cons (car lst)

(filter pred (cdr lst))))

(else (filter pred (cdr lst)))))

> (filter even? ‘(1 2 5 7 9 458))

(2 458)

accumulate

מפעיל את הפרוצדורה על האיברים ברשימה

(define (accumulate op init lst)

(if (null? lst)

init

(op (car lst)

(accumulate op init (cdr lst)))))

> (accumulate * 1 ‘(1 2 3 4 5))

120

 

copy

עושה עותק של הרשימה, כך שאם משנים אחת – השנייה לא משתנה

(define (copy l)

(if (null? l) ‘() (cons (car l) (copy (cdr l)))))

 

> (define a ‘(1 2 3 4 5 6 7 8 9 10))

> (define b a)

> (define c (copy a))

> (set-cdr! a ‘(0 0))

> a

(1 0 0)

> b

(1 0 0)

> c

(1 2 3 4 5 6 7 8 9 10)

deep-copy

עושה עותק של הרשימה ושל כל התת-רשימות שלה, כך שאם משנים אחת – השנייה לא משתנה

(define (deep-copy l)

(if (pair? l)

(cons (deep-copy (car l)) (deep-copy (cdr l)))

l))

 

> (define e ‘(1 (2.1 2.2) 3 4 5 6 7 8 9 10))

> (define f e)

> (define g (copy e))

> (define h (deep-copy e))

> (set-cdr! (cddddr e) ‘(0 0))

> (set-car! (cadr e) 2.9)

> e

(1 (2.9 2.2) 3 4 5 0 0)

> f

(1 (2.9 2.2) 3 4 5 0 0)

> g

(1 (2.9 2.2) 3 4 5 6 7 8 9 10)

> h

(1 (2.1 2.2) 3 4 5 6 7 8 9 10)

 

quicksort

בוחר איבר שיהיה PIVOT (מצביע) ומחלק לשלושה חלקים: קטנים ממנו שווים לו וגדולים ממנו, ומפעיל רקורסיבית.  סיבוכיות: Θ(n²)  . אם בכל שלב מחולק לשתי קבוצות שוות בגודלן, אז יוצא עץ מאוזן: Θ(nlogn) .

(define (quicksort l)

(if (null? l)

nil

(let ((pivot (car l)))

(let ((low (filter (lambda (x) (< x pivot)) l))

(high (filter (lambda (x) (> x pivot)) l))

(same (filter (lambda (x) (= x pivot)) l)))

(append

(append (quicksort low) same)

(quicksort high))))))

> (quicksort ‘(17 5 3 56 9 -5 78 90))

(-5 3 5 9 17 56 78 90)

mergesort

מיון-מיזוג: ממיין תוך כדי מיזוג חלקי הרשימה.

סיבוכיות:  Θ(nlogn) .

(define (odd-elements lst)

(define (iter lst n)

(cond ((null? lst) lst)

((odd? n) (cons (car lst) (iter (cdr lst) (+ n 1))))

(else (iter (cdr lst) (+ n 1)))))

(iter lst 0))

(define (even-elements lst)

(define (iter lst n)

(cond ((null? lst) lst)

((even? n) (cons (car lst) (iter (cdr lst) (+ n 1))))

(else (iter (cdr lst) (+ n 1)))))

(iter lst 0))

(define (merge s1 s2)

(cond ((null? s1) s2)

((null? s2) s1)

((< (car s1) (car s2)) (cons (car s1) (merge (cdr s1) s2)))

(else (cons (car s2) (merge s1 (cdr s2))))))

(define (mergesort s)

(cond ((null? s) s)

((null? (cdr s)) s)

(else

(let ((s1 (odd-elements s))

(s2 (even-elements s)))

(merge (mergesort s1) (mergesort s2))))))

 

 

> (odd-elements ‘(1 2 3 4 5 6 7 8))

(2 4 6 8)

> (even-elements ‘(1 2 3 4 5 6 7 8))

(1 3 5 7)

> (merge ‘(1 3 5 7) ‘(2 4 6 8))

(1 2 3 4 5 6 7 8)

> (mergesort ‘(4 7 3 89 12 -5 74 3 8 13 56 12 35 77))

(-5 3 3 4 7 8 12 12 13 35 56 74 77 89)

 

עצים

count-leaves

מחזיר מספר עלים בעץ

(define (count-leaves t)

(accumulate + 0 (map

(lambda (x) (cond ((null? x) 0)

((leaf? x) 1)

(else (count-leaves x))))

t)))

> (count-leaves ‘())

0

> (count-leaves ‘(4 7 9 6 8))

5

> (count-leaves ‘(4 (5 7) 2))

4

> (count-leaves ‘(7 (9 5 7 ()) (((4) 2 1) 6 6) 5))

10

fold-right

תרגיל 5 שאלה 8

(define (fold-right op init lst)

(if (null? lst)

init

(op (car lst)

(fold-right op init

(cdr lst)))))

leaf?

בודק שאיבר הוא עלה (לא זוג)

(define (leaf? x) (not (pair? x)))

 

השמה והשמה בזוגות

make-counter

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

(define make-counter

(lambda (n)

(lambda () (set! n (+ n 1)) n)))

> (define ca (make-counter 0))

> (ca)

1

> (ca)

2

> (define cb (make-counter 0))

> (cb)

1

> (ca)
3

make-counting-proc

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

(define (make-counting-proc pr)

(let ((n 0))

(lambda (x)

(set! n (+ n 1))

(display “applied “)

(display n)

(display ” times”)

(pr x))))

> (define my-length (make-counting-proc length))

> (my-length ‘(a b c))

applied 1 times

3

< (my-length ‘(a b c))

applied 2 times

3

< (my-length ‘(b c))

applied 3 times

2

prev

מקבל פרמטר אחד ומחזיר את הפרמטר, שקיבל בהפעלה הקודמת שלו. בפעם ראשונה הוחזר סמל *first-call*.

(define last-value ‘*first-call*)

(define (prev new)

(define x last-value)

(set! last-value new)

x)

 

< (prev ‘a)

*first-call*

> (prev 3)

a

> (prev (+ 1 5))

3

 

make-prev

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

(define (make-prev last-value)

(lambda (new)

(let ((x last-value))

(set! last-value new)

x)))

 

> (define prev (make-prev ‘*first-call*))

> (prev ‘a)

*first-call*

> (prev 3)

a

> (prev (+ 1 5))

3

 

append!

מחבר שני רשימות ע”י השמה

(define (append! x y)

(define (last l)

(if (null? (cdr l)) l (last (cdr l))))

(cond ((null? x) y)

(else (set-cdr! (last x) y)))

x)

> (define a ‘(1 2 3 4))

> (define b ‘(a b c d))

> (define c (append! a b))

> a

(1 2 3 4 a b c d)

> b

(a b c d)

> c

(1 2 3 4 a b c d)

 

rotate!

מעביר איבר אחרון ברשימה להיות ראשון. כל השאר לא נשארים במקומם היחסיים.

(define (rotate! lst)

(define (iter l x)

(if (null? l) x

(let ((y (car l)))

(set-car! l x)

(iter (cdr l) y))))

(set-car! lst (iter (cdr lst) (car lst)))

lst)

> (rotate! ‘(1 2 3 4))

(4 1 2 3)

> (define a ‘(1 2 3 4))

> (define b (cddr a))

> (define c (rotate! a))

> a

(4 1 2 3)

> b

(2 3)

> c

(4 1 2 3)

reverse!

הופך את הרשימה

(define (reverse! lst)

(define (iter l x)

(if (null? l) x

(let ((y (cdr l)))

(set-cdr! l x)

(iter y l))))

(iter lst ‘() ))

> (reverse! ‘(a b c))

(c b a)

> (define a ‘(1 2 3 4 5 6 7 8 9))

> (set! a (reverse! a))

> a

(9 8 7 6 5 4 3 2 1)

count-pairs

סופר את מספר הזוגות באובייקט (גם אם יש מעגלים – כלומר, אם עוברים איבר אחרי איבר – מקבלים לולאה אינסופית)

(define (count-pairs x)

(let ((lst ‘()))

(define (find l a)

(cond ((null? l) #f)

((eq? a (car l)) #t)

(else (find (cdr l) a))))

(define (count-iter x)

(cond ((or (not (pair? x)) (find lst x)) 0)

(else (set! lst (cons x lst))

(+ (count-iter (car x))

(count-iter (cdr x))

1))))

(count-iter x)))

> (count-pairs ‘(1 2 3 4 5 6))

6

> (define a (cons 3 3))

> (define b (cons a a))

> (define c (cons b b))

> (set-cdr! a c)

> (count-pairs c)

3

circle?

בודק אם רשימה – היא לולאה אינסופית

(define (circle? l)

(define (iter p1 p2)

(cond ((not (pair? p1)) #f)

((or (not (pair? p2))

(not (pair? (cdr p2)))) #f)

(else (set! p1 (cdr p1))

(set! p2 (cddr p2))

(if (eq? p1 p2) #t (iter p1 p2)))))

(iter l l))

> (define a ‘(1 2 3 4 5 6 7 8 9 10))

> (circle? a)

#f

> (define b (cdddr (cddddr a)))

> (set-cdr! b (cdr a))

> (circle? a)

#t

> (circle? b)

#t

 

OOP

Queues in OO style

class של טורים יהיה subclass של class המחסניות.

(define (make-queue)

(let ((stack1 (make-stack)) (stack2 (make-stack)))

(define (reverse-stack s1 s2)

(cond (((s1 ’empty?)) s2)

(else ((s2 ‘insert!) ((s1 ‘top)))

((s1 ‘delete!))

(reverse-stack s1 s2))))

(define (empty?)

(and ((stack1 ’empty?)) ((stack2 ’empty?))))

(define (delete!)

(if ((stack2 ’empty?)) (reverse-stack stack1 stack2))

(if ((stack2 ’empty?)) (error “”)

((stack2 ‘delete!))))

(define (first)

(if ((stack2 ’empty?)) (reverse-stack stack1 stack2))

(if ((stack2 ’empty?)) (error “”)

((stack2 ‘top))))

(define (dispatch op)

(cond ((eq? op ’empty?) empty?)

((eq? op ‘first) first)

((eq? op ‘delete!) delete!)

(else (stack1 op))))

dispatch))

 

> (define q (make-queue))

> ((q ‘insert!) ‘a)

(a)

> ((q ‘insert!) ‘b)

(b a)

> ((q ‘delete!))

(b)

> ((q ‘insert!) ‘c)

(c)

> ((q ‘delete!))

()

 

Tables in OO style

(ראה גם פרק טבלאות)

(define (make-table)

(let ((local-table (list ‘*table*)))

(define (lookup key-1 key-2)

. . .

)

(define (insert! key-1 key-2 value)

. . .

‘ok)

(define (dispatch m)

(cond ((eq? m ‘lookup-proc) lookup)

((eq? m ‘insert-proc!) insert!)

(else (error “Unknown operation — TABLE” m))))

dispatch))

זרמים

stream-null?

בודק אם זרם הוא ריק

(define stream-null? null?)

the-empty-stream

מחזיר זרם ריק

(define the-empty-stream ())

ones

מחזיר זרם של אחדים

(define ones (cons-stream 1 ones))

integers

מחזיר זרם של מספרים טבעיים (החל מ-1)

(define (integers-starting-from n)

(cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

fibs

מחזיר זרם פיבונצ’י (0 1 1 2 3 5 8 13 …)

(define (fibgen a b)

(cons-stream a (fibgen b (+ a b))))

(define fibs (fibgen 0 1))

odds

מחזיר זרם של מספרים טבעיים אי-זוגיים ((1 3 5 7 9 11 …

(define odds (stream-filter odd? integers))

factorials

מחזיר זרם של עצרת ((1 1 2 6 24 120 720 5040 40320 362880 …

(define factorials (cons-stream 1 (mul-streams

(integers-starting-from 2)

factorials)))

stream-ref

מחזיר איבר, שבמקום n בזרם s (המקומות החל מ-0)

(define (stream-ref s n)

(if (= n 0)

(stream-car s)

(stream-ref (stream-cdr s) (- n 1))))

 

stream-map

מוחזר זרם שאיבריו הם תוצאות של הפעלת פרוצדורה על כל אחד מאיברי הזרם

(define (stream-map proc s)

(if (stream-null? s)

the-empty-stream

(cons-stream (proc (stream-car s))

(stream-map proc (stream-cdr s)))))

 

argstreams – רשימה של זרמים. אורך הזרמים חייב להיות זהה (או שהם אינסופיים). מוחזר זרם, שאיבר n-י בו הוא תוצאה של הפעלת פרוצדורה על כל אחד מאיברי n בזרמים.

(define (stream-map proc . argstreams)

(if (stream-null? (car argstreams))

the-empty-stream

(cons-stream

(apply proc (map stream-car argstreams))

(apply stream-map

(cons proc

(map stream-cdr argstreams))))))

 

stream-for-each

מפעיל פרוצדורה על כל איבר בזרם. אין ערך המוחזר.

(define (stream-for-each proc s)

(if (stream-null? s)

‘done

(begin (proc (stream-car s))

(stream-for-each proc

(stream-cdr s)))))

 

stream-filter

סינון: pred מקבלת כל איבר בנפרד. אם עבורו היא מחזירה #t אז הוא נכנס לזרם חדש, אחרת לא נכנס.

(define (stream-filter pred stream)

(cond ((stream-null? stream) the-empty-stream)

((pred (stream-car stream))

(cons-stream (stream-car stream)

(stream-filter pred

(stream-cdr stream))))

(else (stream-filter pred (stream-cdr stream)))))

 

display-stream

מדפיס את הזרם (כל איבר בשורה נפרדת). הזרם חייב להיות סופי.

(define (display-stream s)

(stream-for-each display-line s))

(define (display-line x)

(newline)

(display x))

 

print-stream

מדפיס את ה-n איברים ראשונים בזרם (בשורה) .

(define (print-stream str n)

(if (and (> n 0) (not (stream-null? str)))

(begin (display (stream-car str))

(display ” “)

(print-stream (stream-cdr str) (- n 1)))))

 

stream-enumerate-interval

בונה זרם שאיבריו מ-low עד high

(define (stream-enumerate-interval low high)

(if (> low high)

the-empty-stream

(cons-stream

low

(stream-enumerate-interval (+ low 1) high))))

accumulate-stream

מפעיל את הפרוצדורה על האיברים בזרם.

(define (accumulate-stream combiner initial s)

(if (stream-null? s)

initial

(combiner (stream-car s)

(accumulate-stream combiner

initial

(stream-cdr s)))))

add-streams

מקבל זרמים ומחזיר זרם שהאיבר i בו הוא סכום איברי i של זרמי הפרמטרים.

(define (add-streams . args)

(apply stream-map (cons + args)))

(define b (add-streams ones twos ones integers))

 

mul-streams

מקבל זרמים ומחזיר זרם שהאיבר i בו הוא מכפלה איברי i של זרמי הפרמטרים.

(define (mul-streams . args)

(apply stream-map (cons * args)))

(define b (mul-streams ones twos twos integers))

> (stream-ref b 0)

 

> (stream-ref b 1000)

 

 

מערכים

 

vector-map

vs – רשימה של מערכים. אורך המערכים חייב להיות זהה. מוחזר מערך, שאיבר n-י בו הוא תוצאה של הפעלת פרוצדורה על כל אחד מאיברי n במערכים.

(define (vector-map proc . vs)

(define v (make-vector (vector-length (car vs))))

(define (iter proc vcts n)

(cond ((= n (vector-length v)) v)

(else (vector-set!

v n (apply proc (map (lambda (x)

(vector-ref x n)) vcts)))

(iter proc vcts (+ n 1)))))

(iter proc vs 0))

> (vector-map * #() #() #())

#0()

> (vector-map (lambda (x) (+ x 1)) #(2 3) )

#2(3 4)

> (vector-map (lambda (x y z) (+ x (* y z))) #(2 3) #(4 5) #(6 7))

#2(26 38)

 

vector-filter

סינון: pred מקבלת כל איבר בנפרד. אם עבורו היא מחזירה #t אז הוא נכנס למערך חדש, אחרת לא נכנס

(define (vector-filter pred v)

(define lst ‘())

(define (iter pred v n count)

(cond ((= n -1) count)

((pred (vector-ref v n))

(set! lst (cons (vector-ref v n) lst))

(iter pred v (- n 1) (+ count 1)))

(else (iter pred v (- n 1) count))))

(define (copy-lst-v l v n)

(if (null? l) v

(begin (vector-set! v n (car l))

(copy-lst-v (cdr l) v (+ n 1)))))

(define new-v (make-vector (iter pred v

(- (vector-length v) 1) 0)))

(copy-lst-v lst new-v 0))

> (vector-filter even? (vector 1 2 5 7 9 458 78))

#3(2 458 78)

vector-accumulate

מפעיל את הפרוצדורה על האיברים במערך

(define (vector-accumulate op init v)

(define (iter op init n)

(if (= n (vector-length v))

init

(op (vector-ref v n)

(iter op init (+ n 1)))))

(iter op init 0))

> (vector-accumulate * 1 #(1 2 3 4 5))

120

mergesort

מיון-מיזוג: ממיין תוך כדי מיזוג חלקי המערך.

(define (merge v first middle last)

(define (copy-to f s)

(if (> f s) ‘() (cons (vector-ref v f) (copy-to (+ f 1) s))))

(define (copy-back lst p)

(if (not (null? lst))

(begin (vector-set! v p (car lst))

(copy-back (cdr lst) (+ p 1)))))

(define (iter p s1 s2)

(cond ((null? s1) (copy-back s2 p))

((null? s2) (copy-back s1 p))

((< (car s1) (car s2)) (vector-set! v p (car s1))

(iter (+ p 1) (cdr s1) s2))

(else (vector-set! v p (car s2))

(iter (+ p 1) s1 (cdr s2)))))

(iter first (copy-to first middle) (copy-to (+ middle 1) last)))

 

(define (mergesort v)

(define (iter-sort first last)

(if (< first last)

(let ((middle (floor (/ (+ first last) 2))))

(iter-sort first middle)

(iter-sort (+ middle 1) last)

(merge v first middle last))))

(iter-sort 0 (- (vector-length v) 1))

v)

> (mergesort #(4 7 3 89 12 -5 74 3 8 13 56 12 35 77))

#14(-5 3 3 4 7 8 12 12 13 35 56 74 77 89)

 

Bounded Queue

(define (make-bounded-queue size) (cons ‘queue

(cons (cons 0 0)

make-vector (+ size 1)))))

(define (q-next q n) (if (= n (- (vector-length (cddr q)) 1))

0

(+ n 1)))

(define (queue? q) (eq? (car q) ‘queue))

(define (empty-queue? q) (if (queue? q)

(= (caadr q) (cdadr q))

(error “It isn’t queue”)))

(define (full-queue? q) (if (queue? q)

(= (caadr q) (q-next q (cdadr q)))

(error “It isn’t queue”)))

(define (push! q elt)

(if (full-queue? q) (error “The queue is full”))

(vector-set! (cddr q) (cdadr q) elt)

(set-cdr! q (cons (cons (caadr q) (q-next q (cdadr q))) (cddr q)))

‘ok)

(define (pop! q)

(if (empty-queue? q) (error “The queue is empty”))

(set-cdr! q (cons (cons (q-next q (caadr q)) (cdadr q)) (cddr q)))

‘ok)

(define (top q)

(if (empty-queue? q) (error “The queue is empty”))

(vector-ref (cddr q) (caadr q)))

 

Bounded Stack

(define (make-bounded-stack size) (cons ‘stack

(cons 0 (make-vector size))))

(define (stack? st) (eq? (car st) ‘stack))

(define (empty-stack? st) (if (stack? st)

(= (cadr st) 0)

(error “It isn’t stack”)))

(define (full-stack? st) (if (stack? st)

(= (cadr st) (vector-length (cddr st)))

(error “It isn’t stack”)))

(define (push! st elt)

(if (full-stack? st) (error “The stack is full”))

(vector-set! (cddr st) (cadr st) elt)

(set-cdr! st (cons (+ (cadr st) 1) (cddr st)))

‘ok)

(define (pop! st)

(if (empty-stack? st) (error “The stack is empty”))

(set-cdr! st (cons (- (cadr st) 1) (cddr st)))

‘ok)

(define (top st)

(if (empty-stack? st) (error “The stack is empty”))

(vector-ref (cddr st) (- (cadr st) 1)))

 

 

בניית משערך (metacircular evaluator)

בדיקת סמל

(define (tagged-list? exp tag)

(if (pair? exp)

(eq? (car exp) tag)

#f))

בדיקה

(define (self-evaluating? exp)

(cond ((number? exp) #t)

((string? exp) #t)

(else #f)))

(define (variable? exp) (symbol? exp))

(define (quoted? exp) (tagged-list? exp ‘quote))

(define (assignment? exp) (tagged-list? exp ‘set!))

(define (definition? exp) (tagged-list? exp ‘define))

(define (if? exp) (tagged-list? exp ‘if))

(define (lambda? exp) (tagged-list? exp ‘lambda))

(define (begin? exp) (tagged-list? exp ‘begin))

(define (cond? exp) (tagged-list? exp ‘cond))

(define (let? exp) (tagged-list? exp ‘let))

(define (application? exp)  (pair? exp))

פרוצדורות פרימיטיביות (אלה שכבר מוגדרים במשערך, שבו כותבים משערך חדש)

(define primitive-procedures

(list (list ‘+ +)

(list ‘- -)

(list ‘* *)

(list ‘/ /)

(list ‘= =)

(list ‘< <)

(list ‘> >)

(list ‘<= <=)

(list ‘>= >=)

(list ‘odd? odd?)

(list ‘even? even?)

(list ‘random random)

(list ‘abs abs)

(list ‘sin sin)

(list ‘cos cos)

(list ‘tan tan)

(list ‘car car)

(list ‘cdr cdr)

(list ‘cons cons)

(list ‘null? null?)

(list ‘list list)

(list ‘apply apply)

(list ‘map map)

(list ‘for-each for-each)

(list ‘display display)

;more primitivesבמקום זה אפשר להוסיף פרוצדורות פרימיטיביות נוספות

))

(define (primitive-procedure-names)  (map car primitive-procedures))

(define (primitive-procedure-objects)

(map (lambda (proc) (list ‘primitive (cadr proc)))

primitive-procedures))

טיפול במסגרות (מסגרת – זה זוג שאיבר הראשון שלו – רשימת שמות של משתנים, ואיברו השני רשימת הערכים)

(define (make-frame variables values)

(cons variables values))

(define (add-binding-to-frame! var val frame)

(set-car! frame (cons var (car frame)))

(set-cdr! frame (cons val (cdr frame))))

(define (first-frame env) (car env))

(define (frame-variables frame) (car frame))

(define (frame-values frame) (cdr frame))

הגדרת משתנה (אם כבר הוגדר –  החלפת ערכו)

(define (define-variable! var val env)

(let ((frame (first-frame env)))

(define (scan vars vals)

(cond ((null? vars)

(add-binding-to-frame! var val frame))

((eq? var (car vars))

(set-car! vals val))

(else (scan (cdr vars) (cdr vals)))))

(scan (frame-variables frame)

(frame-values frame))))

חיפוש משתנה בכל הסביבות החל מ-env ועד GE(כולל) לפי חצים של הסביות

(define (lookup-variable-value var env)

(define (env-loop env)

(define (scan vars vals)

(cond ((null? vars)

(env-loop (enclosing-environment env)))

((eq? var (car vars)) (car vals))

(else (scan (cdr vars) (cdr vals)))))

(if (eq? env the-empty-environment)

(error “Unbound variable” var)

(let ((frame (first-frame env)))

(scan (frame-variables frame)

(frame-values frame)))))

(env-loop env))

טיפול בסביבות

(define the-empty-environment ‘())

(define (extend-environment vars vals base-env)

(if (= (length vars) (length vals))

(cons (make-frame vars vals) base-env)

(if (< (length vars) (length vals))

(error “Too many arguments supplied” vars vals)

(error “Too few arguments supplied” vars vals))))

(define (setup-environment)

(let ((initial-env

(extend-environment (primitive-procedure-names)

(primitive-procedure-objects)

the-empty-environment)))

(define-variable! ‘true #t initial-env)

(define-variable! ‘false #f initial-env)

initial-env))

(define the-global-environment (setup-environment))

(define (enclosing-environment env) (cdr env))

שיערוך של סמל

(define (text-of-quotation exp) (cadr exp))

שיערוך של השמה

(define (assignment-variable exp) (cadr exp))

(define (assignment-value exp) (caddr exp))

(define (eval-assignment exp env)

(set-variable-value! (assignment-variable exp)

(eval (assignment-value exp) env)

env)

‘ok)

(define (set-variable-value! var val env)

(define (env-loop env)

(define (scan vars vals)

(cond ((null? vars)

(env-loop (enclosing-environment env)))

((eq? var (car vars))

(set-car! vals val))

(else (scan (cdr vars) (cdr vals)))))

(if (eq? env the-empty-environment)

(error “Unbound variable – SET!” var)

(let ((frame (first-frame env)))

(scan (frame-variables frame)

(frame-values frame)))))

(env-loop env))

שיערוך של הגדרת משתנה

(define (eval-definition exp env)

(define-variable! (definition-variable exp)

(eval (definition-value exp) env)

env))

(define (definition-variable exp)

(if (symbol? (cadr exp))

(cadr exp)

(caadr exp)))

(define (make-lambda parameters body)

(cons ‘lambda (cons parameters body)))

(define (definition-value exp)

(if (symbol? (cadr exp))

(caddr exp)

(make-lambda (cdadr exp)    ;formal params

(cddr exp))))  ;body

 

 

 

שיערוך של if

(define (eval-if exp env)

(if (true? (eval (if-predicate exp) env))

(eval (if-consequent exp) env)

(eval (if-alternative exp) env)))

(define (if-predicate exp) (cadr exp))

(define (if-consequent exp) (caddr exp))

(define (if-alternative exp)

(if (not (null? (cdddr exp)))

(cadddr exp)

‘false))

(define (true? x)

(not (eq? x #f)))

(define (false? x)

(eq? x #f))

 

שירוך של lambda

(define (lambda-parameters exp) (cadr exp))

(define (lambda-body exp) (cddr exp))

(define (make-procedure parameters body env)

(list ‘procedure parameters body env))

 

שיערוך של begin

(define (eval-sequence exps env)

(cond ((last-exp? exps) (eval (first-exp exps) env))

(else (eval (first-exp exps) env)

(eval-sequence (rest-exps exps) env))))

(define (last-exp? seq) (null? (cdr seq)))

(define (first-exp seq) (car seq))

(define (rest-exps seq) (cdr seq))

(define (begin-actions exp) (cdr exp))

(define (sequence->exp seq)

(cond ((null? seq) seq)

((last-exp? seq) (first-exp seq))

(else (make-begin seq))))

(define (make-begin seq) (cons ‘begin seq))

שיערוך של cond

(define (cond-clauses exp) (cdr exp))

(define (cond-else-clause? clause)

(eq? (cond-predicate clause) ‘else))

(define (cond-predicate clause) (car clause))

(define (cond-actions clause) (cdr clause))

(define (cond->if exp)

(expand-clauses (cond-clauses exp)))

(define (make-if predicate consequent alternative)

(list ‘if predicate consequent alternative))

(define (expand-clauses clauses)

(if (null? clauses)

‘false                          ; no else clause

(let ((first (car clauses))

(rest (cdr clauses)))

(if (cond-else-clause? first)

(if (null? rest)

(sequence->exp (cond-actions first))

(error “ELSE clause isn’t last — COND->IF”

clauses))

(make-if (cond-predicate first)

(sequence->exp (cond-actions first))

(expand-clauses rest))))))

שיערוך של let

(define (let-vars exp) (map car (cadr exp)))

(define (let-vals exp) (map cadr (cadr exp)))

(define (let-body exp) (cddr exp))

(define (let->combination exp)

(cons (cons ‘lambda (cons (let-vars exp)

(let-body exp)))

(let-vals exp)))

 

שיערוך של הפעלות של פרוצדות

(define (list-of-values exps env)

(if (no-operands? Exps)

‘()

(cons (eval (first-operand exps) env)

(list-of-values (rest-operands exps) env))))

(define (operator app) (car app))

(define (operands app) (cdr app))

(define (first-operand args) (car args))

(define (rest-operands args) (cdr args))

(define (no-operands? Ops) (null? ops))

(define scheme-apply apply)

(define (apply-primitive-procedure proc args)

(scheme-apply (primitive-implementation proc) args))

(define prim-tag ‘primitive)

(define (make-primitive scheme-proc) (list prim-tag scheme-proc))

(define (primitive-procedure? Exp) (tagged-list? Exp prim-tag))

(define (primitive-implementation prim) (cadr prim))

(define (compound-procedure? Exp) (tagged-list? Exp ‘procedure))

(define (apply procedure arguments)

(cond ((primitive-procedure? Procedure)

(apply-primitive-procedure procedure arguments))

((compound-procedure? Procedure)

(eval-sequence

(procedure-body procedure)

(extend-environment

(procedure-parameters procedure)

arguments

(procedure-env procedure))))

(else

(error

“Unknown procedure type – APPLY” procedure))))

(define (procedure-parameters compound) (cadr compound))

(define (procedure-body compound)       (caddr compound))

(define (procedure-env compound)        (cadddr compound))

 

Read-Eval-Print Loop  (קריאה-חישוב-הדפסה  חזור)

(define input-prompt “;;; M-Eval input:”)

(define output-prompt “;;; M-Eval value:”)

(define (prompt-for-input string)

(newline) (newline) (display string) (newline))

(define (announce-output string)

(newline) (display string) (newline))

(define (user-print object)

(if (compound-procedure? object)

(display (list ‘compound-procedure

(procedure-parameters object)

(procedure-body object)

‘<procedure-env>))

(display object)))

(define (driver-loop)

(prompt-for-input input-prompt)

(let ((input (read)))

(let ((output (eval input the-global-environment)))

(announce-output output-prompt)

(user-print output)))

(driver-loop))

 

פרוצדורה העיקרית של המשערך

(define (eval exp env)

(cond ((self-evaluating? exp) exp)

((variable? exp)

(lookup-variable-value exp env))

((quoted? exp)

(text-of-quotation exp))

((assignment? exp) (eval-assignment exp env))

((definition? exp) (eval-definition exp env))

((if? exp) (eval-if exp env))

((lambda? exp)

(make-procedure (lambda-parameters exp)

(lambda-body exp)

env))

((begin? exp)

(eval-sequence (begin-actions exp) env))

((cond? exp) (eval (cond->if exp) env))

((let? exp) (eval (let->combination exp) env))

((application? exp)

(apply (eval (operator exp) env)

(list-of-values

(operands exp) env)))

(else (error “Unknown expression” exp))))

(driver-loop)                                                                 התחל

 

נושאים שנלמדו בקורס

 

נושא	מס’ הרצאה	מס’ תרגיל
אלמנטים של תכנון	1	1
כלל שפת Scheme	2	1, 2
קשירת שמות (Lexical Scoping)	3, 4	2, 3
Normal\Applicative order evaluation	3
Iterative\Recursive procedures	3	2
סיבוכיות זמן(מקום) ריצה	3, 4, 5	2
cond,else	4	2
בעית מגדלי Hanoi	4
בדיקת Fermat לראשוניות	4, 5
פרוצדורות על	5, 6	3
סוכר תחבירי let	5	3
Public key cryptography (RSA)	6
הגדרת ופעולות על מספרים רציונליים	6, 7
זוגות	6	4
רשימות ופעולות עליהם	7, 8	4, 5
Dotted Tail Notation		4
עצים	8	5
סמלים	9	5
תרגיל גזירה (symbolic diffrentation)	9, 10	5
אוספי נתונים (רשימות ממוינות, עצים)	10	5
Huffman encoding trees	10, 11
Multiple representation of data	12, 13
משפט השמה	14	6
מודל הסביבות	14, 15	6
השמה בזוגות	15	7
מחסניות	15	7, 9
טורים	15	7
טבלאות	16	7
Object Oriented Programming	16	7
זרמים, זרמים אינסופיים	17	8
Memoization	17	8
זרמים של הזרמים	17, 18	9
מערכים	19	9
חיפוש בינארי	19
מיון	19	9
בניית משערך	19, 20, 21	10
Dynamic Scoping	22
תוספות למשערך	22	10