מחשבים

טיפים על הדרך

מכבי

מאורסים

חוק וסדר

בית

פורומים

למתכנתים שבינינו

שפת SCHEME


שלום אורח. באפשרותך להתחבר או להירשם
הצג 15 הודעות בעמוד

1 2

סך הכל 2 דפים.

הצג תגובות לאשכול מהסוף להתחלה

נשלח ב-27/7/2011 16:35

שפת SCHEME

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

נשלח ב-27/7/2011 16:44

פרק 1 - הכרות עם Scheme

התוכנית הראשונה אותה נכיר היא התוכנית שמדפיסה "!Hello World" בחלון ה-console.
ע"י שימוש בעורך האהוב עליך צור קובץ בעל הסיומת scm כלומר hello.scm ובו התוכן הבא:

;The first program

(begin

(display "Hello, World!")

(newline))

השורה הראשונה היא הערה, כאשר Scheme רואה נקודה ופסיק (;), היא מתעלמת מהם ומכל השורה הבאה אחריהם.
השימוש ב- begin הוא הדרך של Scheme להציג סדרה של תת תבניות. במקרה שלנו ישנם שתי תת תבניות .הראשונה נקראת הפרוצדורה display, אשר מציגה את הארגומנטים שלה (כלומר את: "!Hello World") ל-console (או למסך). פונקציה זו מלווה ע"י פרוצדורה נוספת והיא newline ,היורדת שורה.

על מנת להריץ את תוכנית ,דבר ראשון עליך להפעיל את Scheme. זה בד"כ נעשה ע"י הקלדת השם של קובץ הריצה של Scheme בשורת הפקודה של מערכת ההפעלה.
לדוגמא, במקרה של MzScheme נקליד mzscheme ב-prompt של מערכת ההפעלה.
פעולה זו קוראת ל-listener של Scheme, אשר קורא את הקלט הדרוש ,מעריך אותו ומדפיס את התוצאה (אם יש) ואח"כ מחכה שוב לקלט מן המשתמש. על כן יש המכנים זאת מעגל : "קריאה-הערכה-הדפסה".
יש לשים לב שה-listener דומה למערכת ההפעלה אשר מונעת ע"י פקודות, קוראת אותן, מריצה ואח"כ מחכה לעוד. כמו למערכת ההפעלה גם ל-listener של Scheme יש prompt משלו בד"כ <, אך הוא יכול להיות גם אחרת.
ב-prompt של ה-listener, נטעין את הקובץ hello.scm ע"י הפקודה:

(load "hello.scm")

Scheme תריץ את תוכן הקובץ תדפיס Hello World ותרד שורה. לאחר מכן יקבל המשתמש שוב את ה-prompt של ה-listener המחכה לקלט נוסף מן המשתמש.
מכיוון שה-listener מאוד "להוט" לקבל קלט, המשתמש לא חייב לכתוב את התוכניות בקובץ ולהטעין אותו. ישנה אפשרות נוספת, פשוטה יותר, במיוחד כאשר המשתמש רוצה להריץ דברים שוב ושוב, והיא להקליד ביטויים ישירות ל-prompt ה-listener ולראות מה מתרחש. לדוגמא לאחר הקשת התבנית:

(begin (display "Hello, World!")

(newline))

נקבל תוצאה:
!Hello, World

למעשה ניתן להקיש ישירות "!Hello World" ל-listener ונקבל את התוצאה הבאה:

"!Hello, World"

מכיוון שזו תוצאת ההערכה של ה-listener ל-"!Hello World".
בשיטה השניה התוצאה הייתה מעט שונה, מלבד השוני הניכר לעין, ישנו הבדל משמעותי נוסף בין שתי התוכניות.
התוכנית הראשונה (עם הפרוצדורה begin) אינה מבצעת הערכה לדבר ו-"!Hello World" נפלט כתופעת לוואי מהפרוצדורות display ו-newline הכותבות ל-standard output.
בתוכנית השניה התבנית: "!Hello World" מוערכת לתוצאה, שבמקרה שלנו זו אותה מחרוזת כמו התבנית עצמה.

מעתה ואילך נשתמש בסימון <= כדי לציין הערכה.

E => v

- מייצג שהתבנית E מוערכת לתוצאה v. לדוגמא,

(begin

(display "Hello, World!")

(newline))

<= - מוערך לכלום או ל-void, אך יש לו תופעת לוואי והיא הכתיבה לאמצעי הפלט הסטנדרטי של !Hello, World.

מצד שני, "!Hello World" <= "!Hello World" (הביטוי "!Hello World" מוערך לאותו ביטוי ממש).

בכל מקרה אנו עדיין נמצאים ב-listener, על מנת לצאת על המשתמש להקיש:

(exit)

זה יחזיר אותנו חזרה לשורת הפקודה של מערכת ההפעלה (שהיא, סוג מסוים של listener בעצמה).
ה-listener נוח לבדיקת אינטראקטיביות של תוכניות וקטעי תוכנית, אך זה לא תמיד הכרחי.
המשתמש יכול לדבוק בדרך המסורתית של יצירת תוכניות בשלמותן, ולתת ל-Scheme להריץ אותן ללא
"listening" בצורה מפורשת. לדוגמא המשתמש ב-MzScheme יכול להקליד ב-prompt של מערכת ההפעלה:

mzscheme -r hello.scm

וזה יוצר את ההפניה מבלי לערב את המשתמש עם ה-listener. לאחר ההפניה mzscheme יחזיר את המשתמש שוב ל-prompt של מערכת ההפעלה. למעשה זה כמו לכתוב:

echo Hello, World!

המשתמש יכול לכתוב את הפקודה hello.scm בדומה לפקודה במערכת ההפעלה (shell or או batch file) אך נצטרך להמתין עד לפרק 16 לצורך העניין.

נשלח ב-27/7/2011 16:54

פרק 2 - תבניות נתונים

תבניות נתונים הן אוסף של ערכים קשורים. אוספים צריכים להיות מפורקים לגורמים, וכן הם לעתים בעלי היררכיה מסוימת. ל-Scheme יש קבוצה עשירה של תבניות נתונים: חלקן פשוטות (לא ניתנות לחלוקה) וחלקן מורכבות יותר. תבניות נתונים אלו מורכבות מסוגים אחרים של נתונים.

2.1 הנתונים הפשוטים:

הנתונים הפשוטים מכילים את הנתונים הבאים: symbols ,characters ,booleans ומספרים.

2.1.1 בוליאניים:

ה-booleans בשפה Scheme הם: f# - מייצג שקר ו-t# - מייצג אמת. ב-Scheme ישנו פרדיקט הנקרא
?boolean, אשר בודק אם הארגומנט הוא boolean.
לדוגמא,

(boolean? #t) => #t

(boolean? "Hello, World!") => #f

הפרוצדורה not מחזירה ההפך מהארגומנט עליו היא מופעלת, בתנאי שהוא boolean. לדוגמא,

(not #f) => #t

(not #t) => #f

(not "Hello, World!") => #f

הביטוי האחרון מדגים את הנוחות של Scheme: במקרה ודרוש Scheme ,boolean תתייחס לכל משתנה שהוא לא f#, כאל ערך אמת.

2.1.2 מספרים:

המספרים ב-Scheme יכולים להיות מספרים שלמים (42), רציונלים (22/7), ממשים (3.1416) או מרוכבים
(2+3i). מספר שלם הוא בפרט רציונלי שהוא בפרט מספר ממשי שהוא בפרט מספר מרוכב והוא בפרט מספר. ישנם פרדיקטים הבודקים את הסוגים השונים של המספרים:

(number? 42) => #t

(number? #t) => #f

(complex? 2+3i) => #t

(real? 2+3i) => #f

(real? 3.1416) => #t

(real? 42) => #t

(rational? 3.1416) => #f

(rational? 22/7) => #t

(integer? 22/7) => #f

(integer? 42) => #t

המספרים השלמים ב-Scheme לא מוכרחים להיות מיוצגים כמספרים דצימליים (בסיס 10). הם יכולים להיות מיוצגים כמספרים בינארים, אך צריך להוסיף קידומת b#. לדוגמא, b1100 #, מייצג את המספר שנים עשר. הקידומת של מספר אוקטלי היא o# ושל מספרים הקסאדצימליים הקידומת היא x#. (הקידומת של מספרים דצימלים היא d#).
ניתן לבדוק שוויון בין מספרים ע"י הפרדיקט ?eqv.

(eqv? 42 42) => #t

(eqv? 42 #f) => #f

(eqv? 42 42.0) => #f

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

(= 42 42) => #t

(= 42 #f) -->ERROR!!!

(= 42 42.0) => #t

ניתן לעשות השוואות אחרות:

(< 3 2) => #f

(>= 4.5 3) => #t

לפרוצדורות האריתמטיות +,-,*,/ יש התנהגות צפויה:

(+ 1 2 3) => 6

(- 5.3 2) => 3.3

(- 5 2 1) => 2

(* 1 2 3) => 6

(/ 6 3) => 2

(/ 22 7) => 22/7

לארגומנט יחיד, - ו-/ נקבל את המספר הנגדי לחיבור ואת ההפכי לכפל בהתאמה:

(- 4) => -4

(/ 4) => 1/4

הפרוצדורות max ו-min מחזירות את המקסימום והמינימום בהתאם למספרים שסופקו להם. ניתן לספק לפרוצדורות אלו מספר בלתי מוגבל של ארגומנטים.

(max 1 3 4 2 3) => 4

(min 1 3 4 2 3) => 1

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

2.1.3 characters:

ה-char ב-Scheme מיוצג ע"י הקידומת #\ .לכן c#\ מייצג את ה-c char. ישנם characters לא גרפיים ולהם יש שמות תיאוריים לדוגמא, newline\# ו-tab\#. ה-char המציין רווח יכול להיות מיוצג כך #\, או בצורה יותר קריאה space#\.
הפרדיקט הבוליאני של ה-char הוא ?char.

(char? #\c) => #t

(char? 1) => #f

(char? #\;) => #t

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

(char=? #\a #\a) => #t

(char<? #\a #\b) => #t

(char>=? #\a #\b) => #f

כדי לבצע השוואות בין תווי אותיות קטנות וגדולות נשתמש בפרדיקט char-ci במקום char:

(char-ci=? #\a #\A) => #t

(char-ci #t

פרוצדורות ההמרה בין אותיות קטנות וגדולות הן char-downcase ו-char-upercase :

(char-downcase #\A) => #\a

(char-upcase #\a) => #\A

2.1.4 symbols

תבניות הנתונים שראינו לעיל מוערכות להיות עצמן. כלומר, אם ניתן אחת מתבניות אלו ל-listener, התוצאה המוערכת שתוחזר ע"י ה-listener תהיה אותה התבנית בעצמה. לדוגמא:

#t => #t

42 => 42

#\c => #\c

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

על מנת לציין שמדובר בסמל על המשתמש לציין זאת ע"י quote:

(quote xyz)

=> xyz

מכיוון שסגנון זה נפוץ מאוד בשפה יצרו לכך קיצור. כלומר הביטוי שיופיע להלן:

שקול לביטוי:

(quote E)

ה-symbols ב-Scheme הם רצף של תווים. אך ישנה מגבלה על שמות ה-symbols, אסור לבלבל אותם עם שאר סוגי המשתנים תווים, בוליאנים, מספרים או נתונים מורכבים.
כלומר:

this-is-a-symbol, i18n, <=> ,$, ! ,# ,*

הם SYMBOLS אך 16, i (מס' מרוכב), "t, "this-is-a-string# ו-(barf) (רשימה) לא.

הפרדיקט המיועד לבדיקת סמלים הוא :?symbol.

(symbol? 'xyz) => #t

(symbol? 42) => #f

ב-Scheme אין הבדל בין אות גדולה לאות קטנה ב-symbols, לכן הסמל Calorie זהה לסמל calorie:

(eqv? 'Calorie calorie')

=> #t

ניתן להשתמש בסמל xyz כמשתנה גלובלי ע"י שימוש בתבנית define:

(define xyz 9)

כתיבה זו מציינת שהמשתנה xyz מכיל את הערך 9. אם נספק נתון זה ל-listener התוצאה תהיה הערך של xyz:

xyz

=> 9

נתן להשתמש בתבנית !set על מנת לשנות את הערך שמכיל המשתנה הנ"ל :

(set! xyz #\c)

וכעת

xyz

=> #\c

2.2 סוגי נתונים מורכבים

הנתונים המורכבים הם ע"י צרוף נתונים אחרים בדרכים שונות והגיוניות.

2.2.1 מחרוזות

מחרוזת היא רצף של תווים (לא לבלבל עם symbols שהם נתונים פשוטים שמוערכים לעצמם).
המשתמש יכול לציין מחרוזות ע"י צרוף התווים ע"י גרשיים.
המחרוזות מוערכות לעצמן:

"Hello, World!"

=> "Hello, World!"

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

(string #\h #\e #\l #\l #\o)

=> "hello"

כעת נגדיר את המשתנה הכללי greeting:

(define greeting "Hello; Hello!")

יש לשים לב שהנקודה ופסיק (;) בתוך המחרוזת לא מציינים הערה.

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

(string-ref greeting 0)

=> #\H

הפרוצדורה !string-set מחליפה את התו במקום האינדקס בתו אחר:

(string-set! greeting 1 #\a)

greeting

=> "Hallo; Hello!"

המחרוזות יכולות להיווצר ע"י צרוף מחרוזות שונות ע"י הפרדיקט string-append:

(string-append "E "

"Pluribus "

"Unum")

=> "E Pluribus Unum"

ניתן ליצור מחרוזת באורך ספציפי ולמלא אותו בעזרת !string-set.

(define a-3-char-long-string (make-string 3))

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

2.2.2 וקטורים

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

להלן דרך ליצור וקטור המכיל חמישה מספרים שלמים:

(vector 0 1 2 3 4)

=> #(0 1 2 3 4)

Scheme מייצגת וקטור ע"י #, המלווה בתוכן הוקטור ומוקף בסוגריים.
בהקבלה ל-make-string הפרוצדורה make-vector יוצרת וקטור באורך ספציפי :

(define v (make-vector 5))

הפרוצדורות vector-ref ו-!vector-set יכולות לגשת ולשנות את האלמנטים הוקטור. הפרדיקט המשמש לבדיקת וקטור הוא: ?vector.

2.2.3 רשימות ו-dotted pairs

dotted pair הוא תבנית מורכבת המצרפת שני ערכים שרירותיים לזוג סדור. האלמנט הראשון בזוג נקרא car, האלמנט השני נקרא cdr ופרוצדורת השילוב ביניהם נקראת cons.

(cons 1 #t)

=> (1 . #t)

dotted pairs אינם מוערכים להיות עצמם לכן כדי להתייחס אליהם כאל נתונים (כלומר, לא לפרש אותם באמצעות הקריאה ל-cons) בפירוש חייבים לשים לפניהם גרש בודד.

'(1 . #t) => (1 . #t)

(1 . #t) -->ERROR!!!

פרוצדורות העזר הן car ו-cdr:

(define x (cons 1 #t))

(car x)=> 1

(cdr x)=> #t

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

(set-car! x 2)

(set-cdr! x #f)

=> (2 . #f)

זוגות יכולים להכיל זוגות אחרים. לדוגמא:

(define y (cons (cons 1 2) 3))

=> ((1 . 2) . 3)

ה-car של ה-car של הרשימה הוא 1. ה-cdr של ה-car הרשימה הוא 2. כלומר:

(car (car y))

=> 1

(cdr (car y))

=> 2

Scheme מספקת קיצורים לפרוצדורות car ו-cdr מורכבות יותר. כלומר, caar הוא קיצור ל-car של car וכן cdar הוא קיצור ל-cdr של car וכו'.

(caar y)

=> 1

(cdar y)

=> 2

c...r - קיצור לארבעה דרוגים קיימים. הביטויים cdar ,cdadar, cdaddr תקינים. נשתמש בקיצור זה כדי להימנע מטעויות.

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

(cons 1 (cons 2 (cons 3 (cons 4 5))))

=> (1 2 3 4 . 5)

כלומר, (1234.5) הוא קיצור ל-

(1.(2.(3.(4.5)))).

ה-cdr האחרון של הביטוי הוא 5.

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

'() => ()

הקיצור של הזוג מהתבנית:

(1 . (2 . (3 . (4 . ()))))

הוא: (4 3 2 1).
זוג מקונן מיוחד זה נקרא רשימה .אורך רשימה ספציפית זו הוא ארבע. ניתן ליצור אותה ע"י:

(cons 1 (cons 2 (cons 3 (cons 4 '()))))

אך Scheme מספקת פרוצדורה הנקראת list שיוצרת רשימות בצורה נוחה יותר. list יכולה לקבל מספר כלשהו של ארגומנטים וליצור מהם רשימה.

(list 1 2 3 4)

=> (1 2 3 4)

למעשה אם אנו יודעים מהם האלמנטים של הרשימה, נוכל לשים גרש בודד כדי לפרש רשימה זו:

'(1 2 3 4)

=> (1 2 3 4)

ניתן לגשת לאברי הרשימה ע"י אינדקס:

(define y (list 1 2 3 4))

(list-ref y 0) => 1

(list-ref y 3) => 4

(list-tail y 1) => (2 3 4)

(list-tail y 3) => (4)

list- tail - מחזירה את הזנב של הרשימה החל מאינדקס נתון. הפרדיקטים ?pair, ?list ו-?null בודקים האם הארגומנט הוא זוג, רשימה או רשימה ריקה בהתאמה:

(pair? '(1 . 2)) => #t

(pair? '(1 2)) => #t (pair? '()) => #f

(list? '()) => #t

(null? '()) => #t

(list? '(1 2)) => #t

(list? '(1 . 2)) => #f

(null? '(1 2)) => #f

(null? '(1 . 2)) => #f

2.2.4 המרות בין תבניות נתונים:

ל-Scheme ישנן פרוצדורות המשמשות להמרה בין סוגי נתונים. אנו כבר יודעים כיצד להמיר בין תווים ע"י הפרוצדורות char-downcase ו-char-upcase. ניתן להמיר תווים למספרים שלמים ע"י הפרוצדורה: char->integer וניתן להמיר מספרים שלמים לתווים ע"י הפרוצדורה:
integer->char (המספר השלם המתקבל מההמרה הוא בד"כ הקוד ה-ascii של התו).

(char->integer #\d) => 100

(integer->char 50) => #\2

ניתן להמיר מחרוזת לרשימת תווים מתאימה.

(string->list "hello") => (#\h #\e #\l #\l #\o)

שאר ההמרות הן מהסגנון של: list->string, vector->list ,ו-list->vector.
ניתן להמיר מספרים למחרוזות:

(number->string 16) => "16"

ניתן להמיר מחרוזות למספרים. אם המחרוזת לא מתאימה לאף מספר יוחזר f#.

(string->number "16")

=>16

(string->number "Am I a hot number?")

=> #f

במידה ונוסיף איבר שני לפרוצדורה string->number היא תתייחס אליו כאל הבסיס שבו המספר יהיה מיוצג.

(string->number "16" 8) => 14

התוצאה אכן נכונה כי 16 בבסיס 8 הוא המספר 14.

ניתן להמיר סמלים למחרוזות ולהפך:

(symbol->string 'symbol)

=>"symbol"

(string->symbol "string")

=> string

2.3 תבניות נתונים נוספות:

Scheme מכילה תבניות נוספות של נתונים ,לדוגמא פרוצדורות .ראינו לא מעט פרוצדורות כמו cons ,+ ,display. למעשה אלו הם משתנים המכילים את ערכי הפרוצדורה אשר אינם ברורים כמו מספרים תווים וכו'.

cons

=> <procedure>

הפרוצדורות שראינו עד כה הינן פרימיטיביות שמשתנים גלובליים מכילים אותם. משתמשים יכולים ליצור ערכי פרוצדורה נוספים.
סוג נוסף של נתון הוא port. port הוא צינור שדרכו ניתן לנהל את הפלט והקלט. Ports בד"כ קשורים לקבצים ול-consoles.
בתוכנית הראשונה שלנו "!Hello World", הארגומנט השני של הפרוצדורה display לא מפורש. ברירת המחדל לאמצעי הפלט הוא ה-standard output. אנו יכולים לקבל את אמצעי הפלט הנוכחי ע"י הקריאה לפרוצדורה (current-output-port). אנו יכולים להיות מפורשים יותר כך:

(display "Hello, World!" (current-output-port))

S-expressions 2.4:

כל סוגי הנתונים שדנו בהם יכולים להיכלל למושג אחד הנקרא: s-expression (ה-s - מיצג symbolic). לכן

42,

#\c,

(1.2),

#(a b c ),

"hello",

(quote xyz),

(string->number "16") ו-

(begin( display "Hello ,World!") (newline))

הם s-expression.

נשלח ב-27/7/2011 16:56

פרק 3 - תבניות

לכן התו c#\ הוא תוכנית או תבנית. אנו נשתמש במושג תבנית ולא תוכנית, כדי שנוכל להבדיל גם בין קטעי תוכניות.
Scheme מעריכה את התו c#\ לערך c#\, מכיוון שהוא, מוערך עצמית.

לא כל ה-s-expression הם מוערכים עצמית. לדוגמא הסמל xyz s-expression מוערך לערך המוכל במשתנה xyz וכן הרשימה s-expression

(string -> number "16")

מוערכת למספר 16.
לא כל ה-s-expression הם תוכניות הגיוניות. אם נקליד ל-listener את הביטוי (1.2) ה-listener של Scheme יחשוב שזו טעות.
Scheme מעריכה תבנית של רשימה ע"י כך שהיא בוחנת את האיבר הראשון של התבנית. אם הוא מוערך לפרוצדורה אזי שאר האברים מוערכים לארגומנטים של הפרוצדורה והיא מופעלת עליהם.

אם ראש התבנית הוא תבנית מיוחדת הערכה מתקדמת באופן ייחודי על התבנית.
חלק מהתבניות המיוחדות כבר ראינו לדוגמא :begin , define ו-!set.
begin גורמת לשאר התת תבניות להיות מוערכות לפי הסדר והתוצאה של כל התבנית היא
התוצאה של התת תבנית האחרונה. define מאתחלת לראשונה את המשתנה ו-!set משנה את הקישורים של המשתנה.

3.1 פרוצדורות

הכרנו לא מעט פרוצדורות פרימיטיביות לדוגמא, string->list, cons ודומיהן.
משתמשים יכולים ליצור פרוצדורות משלהם ע"י שימוש בפרוצדורה מיוחדת lambda.
הדוגמא הבאה מגדירה פרוצדורה המוסיפה 2 לארגומנטים שלה:

(lambda (x) (+ x 2))

התת תבנית, (x), היא רשימה של פרמטרים. יתר תתי התבניות מהווים את גוף הפרוצדורה. ניתן לקרוא לפרוצדורה הנ"ל ע"י ארגומנט כפי שקוראים לפרוצדורות פרימיטיביות אחרות.

((lambda (x) (+ x 2)) 5)

=> 7

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

(define add2

(lambda (x) (+ x 2)))

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

(add2 4) => 6

(add2 9) => 11

3.1.1 הפרמטרים של הפרוצדורות

הפרמטרים של הפרוצדורה lambda נמצאים בתת התבנית הראשונה (התבנית שבאה מיד לאחר המילה lambda) .
הפרוצדורה add2 היא פרוצדורה בעלת ארגומנט יחיד וכמוכן רשימת הארגומנטים (x) היא יחידה. הסמל x מתנהג כמשתנה המחזיק את ערך הפרוצדורה. כל הופעה של x בגוף הפרוצדורה, מתייחסת לארגומנט הפרוצדורה. x הוא משתנה מקומי בפרוצדורה.
אנו יכולים להשתמש ברשימות בעלות שני אלמנטים לפרוצדורות בעלות שני ארגומנטים ובאופן כללי n רשימות בעלות n אלמנטים לפרוצדורות בעלות n ארגומנטים.
הדוגמא הבאה היא פרוצדורה בעלת 2 ארגומנטים המחשבת שטח של מלבן. שני הארגומנטים הם האורך והרוחב של המלבן.

(define area

(lambda (length breadth)

(* length breadth)))

יש לשים לב כי הפרוצדורה area מכפילה את הארגומנטים שלה כפי שעושה הפונקציה *.
יכולנו לכתוב בפשטות:

(define area *)

3.1.2 מספר משתנה של ארגומנטים

ישנם פרוצדורות אשר ניתן לקרוא להן מספר פעמים ובכל קריאה עם מספר שונה של ארגומנטים. כדי לבצע זאת רשימת הפרמטרים מוחלפת ע"י סמל יחיד .סמל זה מתנהג כמשתנה הקשור לרשימת ארגומנטים שהפרוצדורה קוראת להם.
באופן כללי רשימת הפרמטרים של lambda הם מהצורה: (x...), סמל או dotted-pair מהצורה של (x....z). במקרה של ה-dotted-pair כל המשתנים לפני הנקודה קשורים לארגומנטים המתאימים בקריאה לפרוצדורה, וארגומנט יחיד לאחר הנקודה שקולט את שאר הארגומנטים כרשימה אחת.

3.2 הפרוצדורה apply

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

(define x '(1 2 3))

(apply + x)

=> 6

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

לדוגמא

(apply + 1 2 3 x)

=> 12

3.3 עריכה ברצף

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

(define display3

(lambda (arg1 arg2 arg3)

(begin

(display arg1)

(display " ")

(display arg2)

(display " ")

(display arg3)

(newline))))

בשפה Scheme ,בגוף ה-lambda מופיע begin במרומז לכן ה-begin בפרוצדורה display3 לא נחוץ, אך הוא לא מזיק.
נכתוב את הפרוצדורה בצורה פשוטה יותר:

(define display3

(lambda (arg1 arg2 arg3)

(display arg1)

(display " ")

(display arg2)

(display " ")

(display arg3)

(newline)))

נשלח ב-27/7/2011 16:58

פרק 4 - משפטי בקרה

כמו בכל השפות גם ל- scheme יש משפטי תנאי. התבנית הבסיסית היא:

(if test - expression

than - expression

else - expression)

אם ה-test-expression הוא אמת (ערך השונה מ-f#) אז יוערך הביטוי then-expression אחרת יוערך הביטוי else-expression.

(define p 90)

(if (> p 70)

'safe

'unsafe)

=> safe

(if (< p 90)

'low-pressure) ;no ''else'' branch

=> low-pressure

ל-Scheme יש תבניות נוספות של משפטי תנאי. הם יוגדרו כמאקרו (פרק 8), המורחב לביטוי תנאי.

when 4.1 ו-unless

when ו-unless נוחים לשימוש במשפטי בקרה כאשר יש רק הסתעפות אחת (כלומר יש הסתעפות ל-"then" או "else") בתבנית הבסיסית .

(when (< (pressure tube) 60)

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube))

בהנחה ש-pressure tube < 60 אזי יתבצע

(attach floor-pump tube) ו-(depress) floor-pump 5

(attach ו-depress הן פרוצדורות מתאימות) .

כעת נתבונן באותה דוגמא אך נשתמש ב-if במקום when:

(if (< (pressure tube) 60)

(begin

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube)))

יש לשים לב כי בשימוש ב-when לא היה צורך להשתמש ב-begin ואילו ב-if יש צורך להשתמש בו.
unless מתנהג באופן דומה כמתואר בדוגמא הבאה:

(unless (>= (pressure tube) 60)

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube))

לא בכל השפות Scheme קיימים when ו-unless לעתים נצטרך להגדירם כפי שנלמד בפרק 8.

4.2 Cond

התבנית של cond נוחה לשימוש כאשר משתמשים במשפטי בקרה בצורה מקוננת

(if (char <? c #\c) -1

(if (char=? c #\c) 0

1))

הקוד הנ"ל ע"י שימוש ב-cond:

(cond ((char<? c #\c) -1)

((char=? c #\c) 0)

(else 1))

ה-cond משמש למשפטי תנאי מסועפים. כאשר לכל close יש ביטוי הנבדק וביטוי הצריך להתבצע. הביטוי הראשון שמצליח, מפעיל את הביטוי השייך אליו. ה-else המסיים נבחר כאשר אף אחד מהביטויים הקודמים לא הצליח.
בפעולות ה-cond יש begin במרומז ולכן אין צורך לכתוב זאת במפורש.

4.3 Case

מצב מיוחד ל-cond היכול להיות מתומצת לביטוי case. זה אפשרי כאשר כל הביטויים הנבדקים שייכים לאותו ביטוי כלומר:

(case c

((#\a) 1)

((#\b) 2)

((#\c) 3)

(else 4))

=> 3

ה-close שראשו מכיל את הערך של c יבחר.

and' 4.4' ו-'or'

Scheme מספקת תבניות מיוחדות עבור ביטויים בוליאניים 'and' ו-'or'.
התבנית המיוחדת 'and' מחזירה אמת אם כל תת התבניות שלה הן אמת. הערך המוחזר הוא סיכום של כל התת תבניות. אם אחת מהתת תבניות היא שקר אזי הערך המוחזר הוא שקר (f#).

לדוגמא:

(and 1 2) => 2

(and #f 1) => #f

התבנית המיוחדת 'or' מחזירה ערך אמת אם לפחות אחד מערכי הביטויים הוא אמת. אם כל ערכי הביטויים הם שקר 'or' תחזיר שקר (#f).

לדוגמא:

(or 1 2) => 1

(or #f 1) => 1

'and' ו-'or' מעריכים את התת תבניות שלהם משמאל לימין. אם התוצאה נקבעה כבר Scheme תתעלם משאר הביטויים.

(and 1 #f expression-guaranteed-to-cause-error)

=> #f

(or 1 #f expression-guaranteed-to-cause-error)

=> 1

נשלח ב-27/7/2011 17:00

פרק 5 - משתנים לקסיקלים

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

לדוגמא,

(define add2 (lambda (x) (+ x 2)))

(define x 9)

x => 9

(add2 3) => 5

(add2 x) => 11

x => 9

בדוגמא שלנו x הוא משתנה כללי וכן ישנו משתנה מקומי x, האחרון הוצג לראשונה ע"י הפרוצדורה add2. המשתנה הגלובלי ערכו תמיד 9 .המשתנה המקומי x ניקשר לערך 3 בקריאה הראשונה של add2 ובקריאה השניה הוא ניקשר למשתנה הגלובלי x שערכו 9.
התבנית !set משנה הערך של המשתנה הגלובלי x ע"י:

(set! x 20)

!set שנתה את ערכו של x ל-20 מכיוון שהוא בטווח ההכרה של !set אך אם !set היתה בתוך גוף הפרוצדורה add2, היא הייתה משנה את ה-x המקומי.

(lambda (x)

(define add2

(set! x (+ x 2))

x))

בדוגמא הזו !set מוסיפה 2 למשנה המקומי x ומחזירה את הערך. (למעשה הפרוצדורה הזו לא שונה מהפרוצדורה add2 הקודמת.) אנו יכולים לקרוא ל-add2 על המשתנה הגלובלי x:

(add2 x) => 22

(המשתנה הגלובלי x הוא כעת 20 ולא 9!!! )

הפרוצדורה !set שנמצאת בתוך add2 משפיעה רק על המשתנה המקומי ש add2 משתמשת בו. המשתנה הגלובלי x לא מושפע מהפרוצדורה !set.

x => 20

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

(define counter 0)

(define bump-counter

(lambda ()

(set! counter (+ counter 1))

counter))

הפרוצדורה bump-counter נקראת thunk. הפונקציה יכולה לשנות רק משתנה גלובלי ולא מקומי, במקרה שלנו היא מקדמת את ה- counter ב-1.
נתבונן בכמה דוגמאות:

(bump-counter) => 1

(bump-counter) => 2

(bump-counter) => 3

5.1 'let' ו-'*let'

משתנים מקומיים ניתנים להצגה מבלי ליצור פרוצדורה. התבנית של let מאפשרת להציג רשימה של משתנים מקומיים, כלומר:

(let ((x 1)

(y 2)

(z 3))

(list x y z))

=> (1 2 3)

כמו ב-lambda בגוף ה-let המשתנה המקומי מאפיל על המשתנה הגלובלי.
בדוגמא שלנו האיתחולים של x ל-1, y ל-2 ו-z ל-3 לא נחשבים לגוף הפרוצדורה. לכן התייחסות ל-x באיתחול תתייחס למשתנה הגלובלי ולא למקומי.

(let ((x 1)

(y x))

(+ x y))

=> 21

זאת מכיוון ש-x מאותחל ב-1 ו-y מאותחל ל-x הגלובלי (שהוא 20).
לעתים יותר נוח לאתחל את המשתנים ברצף, כך שהאתחול של המשתנה האחרון תתרחש בטוח ההכרה של שאר המשתנים הקודמים התבנית *let עושה זאת:

(let* ((x 1)

(y x))

(+ x y))

=> 2

האתחול של x ו-y מתייחסים ל-x המקומי. הדוגמא הקודמת היא למעשה קיצור של התוכנית הנ"ל:

(let ((x 1))

(let ((y x))

(+ x y)))

=> 2

הערכים שקשורים למשתנים יכולים להיות פרוצדורות. לדוגמא,

(let ((cons (lambda (x y) (+ x y))))

(cons 1 2))

=> 3

בגוף הפרוצדורה let, cons מוסיפה לארגומנטים שלה. מחוץ לפרוצדורה cons ממשיכה לייצר dotted - pairs.

5.2 fluid – let

משתנה מילולי מוכר בכל טווח ההכרה שלו בתנאי שמשתנה אחר לא מאפיל עליו. לעתים זה מועיל להציב במשתנה המילולי ערך מסוים באופן זמני ,לשם כך נשתמש בתבנית *fluid-let

(fluid-let ((counter 99))

(display (bump-counter)) (newline)

(display (bump-counter)) (newline))

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

100

101

102

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

counter => 3

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

(let ((counter 99))

(display (bump-counter)) (newline)

(display (bump-counter)) (newline))

בתוכנית זו החלפנו את fluid-let ב-let ותוצאת הריצה היא:

כלומר, המשתנה הגלובלי counter שאותחל ב-3 מעודכן בכל קריאה ל-bump-counter.
המשתנה counter השני שאותחל ל - 99 ,לא מושפע מהקריאות ל- bump-counter, למרות שהקריאות הן בטווח ההכרה של המשתנה המקומי ,הגוף של bump-counter לא נמצא בטווח זה .הפרוצדורה מתייחסת ל-counter הגלובלי שערכו הסופי הוא 6.

counter => 6

fluid-let - היא תבנית מיוחדת במינה. ניתן לעיין בפרק 8.3 בהגדרה שלה.

נשלח ב-27/7/2011 17:03

פרק 6 - רקורסיה

גוף הפרוצדורה יכול להכיל קריאות לפרוצדורות אחרות בין היתר לעצמה:

(define factorial (lambda (n)

(if (= n 0) 1

(* n (factorial (- n 1))))))

הפרוצדורה הרקורסיבית מחשבת עצרת של מספר (!). אם המספר הוא 0 - התשובה שתתקבל תהיה 1. לגבי כל מספר אחר n - הפרוצדורה משתמשת בעצמה לחשב עצרת של n-1, מכפילה את תוצאת הביניים ב-n, ומחזירה את המכפלה.

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

(define is-even?

(lambda (n)

(if (= n 0) #t

(is-odd? (- n 1)))))

(define is-odd?

(lambda (n)

(if (= n 0) #f

(is-even? (- n 1))))

6.1 letrec

אם נרצה את הפרוצדורות לעיל כמשתנים מקומיים, נוכל לנסות להשתמש בצורת ה-let :

(let ((local-even? (lambda (n)

(if (= n 0) #t

(local-odd? (- n 1)))))

(local-odd? (lambda (n)

(if (= n 0) #f

(local-even? (- n 1))))))

(list (local-even? 23) (local-odd? 23)))

כאן, הדבר לא יעבוד לגמרי כיוון שהבדיקות ?local-even ו-?local-odd בשלב האתחול לא מתייחסת למשתנים עצמם.
גם אם נשנה את let ל-*let עדיין זה לא יעבוד, היות וכל עוד ?local-even שבתוך גוף ?local-odd מתייחסת לערך הנכון של הפרוצדורה ?local-odd שבתוך גוף ?local-even עדיין מכוונת על מקום אחר.

כדי לפתור בעיה מסוג זה, Scheme מספקת את הצורה letrec:

(letrec ((local-even? (lambda (n)

(if (= n 0) #t

(local-odd? (- n 1)))))

(local-odd? (lambda (n)

(if (= n 0) #f

(local-even? (- n 1))))))

(list (local-even? 23) (local-odd? 23)))

המשתנים המוצגים ע"י letrec גלויים לא רק בתוך גוף ה-letrec, אלא גם במשך האתחולים כולם. letrec היא כאמור המתאימה ביותר עבור הגדרות רקורסיביות ופרוצדורות רקורסיביות מקומיות הדדיות.

6.2 'Named let'

פרוצדורה רקורסיבית המוגדרת באמצעות שימוש ב-letrec יכולה לתאר לולאות.
נניח כי אנו רוצים להציג ספירה לאחור החל מ-10.

(letrec ((countdown (lambda (i)

(if (= i 0) 'liftoff

(begin

(display i)

(newline)

(countdown (- i 1)))))))

(countdown 10))

הפונקציה תוציא כפלט בחלון ה-console את המספרים מ-10 ועד 1 ותחזיר את התוצאה liftoff.
Scheme מציעה מגוון רחב של פונקציות let הנקראות: 'named let' כדי לכתוב סוג כזה של לולאות בצורה מתומצתת יותר:

(let countdown ((i 10))

(if (= i 0) 'liftoff

(begin

(display i)

(newline)

(countdown (- i 1)))))

שים לב להופעת המשתנה המזהה את הלולאה מיד לאחר ה-let.
תכנית זו שקולה לתכנית הכתובה עם letrec. ניתן להתייחס ל-'named let' כאל macro (ראה פירוט נוסף בפרק 8) המרחיב את צורת ה-letrec.

6.3 איטרציות

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

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

Scheme עושה זאת בעזרת תהליך הנקרא 'tail-call elimination' .אם תתבונן היטב בפרוצדורת countdown, תבחין כי כאשר מתבצעת קריאה רקורסיבית בגוף הפרוצדורה, זוהי קריאת זנב או במילים אחרות - זהו הדבר האחרון שנעשה. כל קריאה של countdown - או שהקריאה אינה לפרוצדורה עצמה, או שזו הפעולה האחרונה ממש שנעשית.
עבור מימוש Scheme , הדבר יוצר רקורסיה שאינה נבדלת מאיטרציה. אז המשך להשתמש ברקורסיה לכתוב לולאות! אל תדאג- הדבר בטוח!

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

(define list-position<

(lambda (o l)

(let loop ((i 0) (l l))

(if (null? l) #f

(if (eqv? (car l) o) i

(loop (+ i 1) (cdr l)))))))

הפרוצדורה list-position מוצאת את האינדקס של המופע הראשון של אובייקט o ברשימה l. אם האובייקט לא נמצא ברשימה, הפרוצדורה תחזיר f#.

להלן פרוצדורת רקורסית זנב נוספת, אשר הופכת את הרשימה in place, כלומר, משנה את תוכן הרשימה הקיימת מבלי להזדקק להקצאות חדשות.

(define reverse!

(lambda (s)

(let loop ((s s) (r '()))

(if (null? s) r

(let ((d (cdr s)))

(set-cdr! s r)

(loop d s))))))

(reverse היא פרוצדורה שימושית מספיק כדי להימצא בניבי Scheme רבים, בדוגמאות ועוד).

6.4 מיפוי פרוצדורה לרוחב רשימה

ישנו סוג מיוחד של איטרציה המשלב חזרה על אותה פעולה עבור כל אלמנט ברשימה.
Scheme מציעה שתי פרוצדורות לצורך העניין: map ו-for-each .

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

לדוגמא:

(map add2 '(1 2 3))

=> (3 4 5)

פרוצדורת for-each גם כן מחילה פרוצדורה נתונה על כל אלמנט ברשימה, רק שהיא מחזירה void. יישום הפרוצדורה נעשה באופן "טהור" עבור כל תופעת לוואי היכולה להיגרם.
לדוגמא:

(for-each display

(list "one " "two " "buckle my shoe"))

כאן תופעת הלוואי היא הצגת המחרוזות (לפי סדר הופעתן) על מסך ה-console.

הפרוצדורות המופעלות ע"י map ו-for-each לא צריכות להיות פרוצדורות של ארגומנט אחד.
לדוגמא, בהינתן פרוצדורה עם n ארגומנטים - map תיקח n רשימות ותחיל את הפרוצדורה על כל סדרה של n ארגומנטים נבחרים לרוחב הרשימות. לדוגמא:

(map cons '(1 2 3) '(10 20 30))

=> ((1 . 10) (2 . 20) (3 . 30))

(map + '(1 2 3) '(10 20 30))

=> (11 22 33)

נשלח ב-27/7/2011 17:05

פרק 7 - קלט/ פלט

ל-Scheme פרוצדורות קלט/ פלט המאפשרות לקרוא מ-port המשמש לקלט או לכתוב ל-port המשמש לפלט.
ports יכולים להיות מקושרים ל-console לקבצים או למחרוזות.

7.1 קריאה

פרוצדורות הקריאה ב-Scheme מקבלות ארגומנט port קלט אופציונלי. אם ה- port אינו מצוין בפירוש - מניחים שהכוונה היא ל-port הקלט הנוכחי (בד"כ ה-console).
קריאה יכולה להיות על בסיס תו, שורה או ביטוי. בכל פעם שמתבצעת קריאה, מצב ה-port משתנה כך שבקריאה הבאה ייקרא חומר עוקב לחומר שכבר נקרא. אם ל-port אין יותר חומר לקרוא, פרוצדורת הקריאה מחזירה נתון מסוים הנקרא סוף-הקובץ (end-of-file) או אובייקט eof. נתון זה הוא הערך היחיד המספק את פרדיקט ?eof-object.

הפרוצדורה read-char קוראת את התו הבא מה-port.
read-line קוראת את השורה הבאה ומחזירה אותה כמחרוזת. (ירידת השורה האחרונה אינה נכללת).
הפרוצדורה read קוראת את הביטוי הבא.

7.2 כתיבה

פרוצדורות הכתיבה ב-Scheme מקבלות את האובייקט שאמור להיכתב ואת ארגומנט port הפלט האופציונלי. אם ה-port אינו מצוין במפורש - מניחים שהכוונה ל-port הפלט הנוכחי. (בד"כ ה-console).
כתיבה יכולה להיעשות על בסיס תו או ביטוי.
הפרוצדורה write-char כותבת את התו הנתון (ללא #/) ל-port.
הפרוצדורות write ו-display כותבות את הביטוי הנתון ל-port בהבדל אחד:
write מנסה להשתמש במבנה מנגנון קריאה בעוד ש-display אינה עושה זאת.
לדוגמא, write משתמשת במרכאות כפולות עבור מחרוזות ובתחביר ה-#/ עבור תווים. display אינה עושה זאת.

7.3 File ports

פרוצדורות קלט/ פלט ב- scheme לא נזקקות לארגומנט ה- port אם אותו port הוא אמצעי הקלט/הפלט הסטנדרטי. בכל מקרה, אם צריכים portים אלו במפורש - הפרוצדורות ללא ארגומנטים current-input-port ו-current-output-port מספקות אותם. לפיכך, בשתי השורות הבאות קורה אותו הדבר בדיוק.

(display 9)

(display 9 (current-output-port))

Port מקושר עם קובץ באמצעות פתיחת הקובץ. הפרוצדורה open-input-file מקבלת ארגומנט שם קובץ ומחזירה port קלט חדש המקושר איתו. הפרוצדורה open-output-file מקבלת ארגומנט שם קובץ ומחזירה port פלט חדש המקושר איתו.
זו נחשבת טעות לפתוח קובץ קלט שאינו קיים או לפתוח קובץ פלט שכבר קיים.
אחרי שביצענו קלט/פלט על ה-port, עלינו לסגור אותו בעזרת close-input-port או
close-output-port.
בדוגמא הבאה, הנח כי הקובץ hello.txt מכיל את המילה הבודדת hello.

(define i (open-input-file "hello.txt"))

(read-char i)

=> #\h

(define j (read i))

=> ello

הנח כי הקובץ greeting.txt אינו קיים לפני שהתכניות הבאות מוזנות ל-listener.

(define o (open-output-file "greeting.txt"))

(display "hello" o)

(write-char #\space o)

(display 'world o)

(newline o)

(close-output-port o)

הקובץ greeting.txt יכיל כעת את השורה:

hello world

7.3.1 פתיחה וסגירה אוטומטית של file ports

Scheme מספקת את הפרוצדורות call-with-input-file ו call-with-output-file השומרות על פתיחת ה-port וסגירתו לאחר שסיימת לעבוד איתו.
הפרוצדורה call-with-input-file מקבלת ארגומנט שם קובץ ופרוצדורה. הפרוצדורה מתייחסת ל-port קלט הנפתח בקובץ. כשהפרוצדורה מסיימת, תוצאותיה מוחזרות לאחר וידוא שה- port אכן סגור.

(call-with-input-file "hello.txt"

(lambda (i)

(let* ((a (read-char i))

(b (read-char i))

(c (read-char i)))

(list a b c))))

=> (#\h #\e #\l)

הפרוצדורה call-with-output-file מעניקה את השימושים האנלוגיים עבור קובץ פלט.

7.4 String ports

לעיתים נוח לקשר ports עם מחרוזות. לפיכך, הפרוצדורה open-input-string נועדה לקשר port עם מחרוזת נתונה. פרוצדורות קריאה ב-port זה יקראו את המחרוזת:

(define i (open-input-string "hello world"))

(read-char i)

=> #\h

(read i)

=> ello

(read i)

=> world

הפרוצדורה open-output-string יוצרת port פלט שלבסוף ינוצל ליצירת מחרוזת:

(define o (open-output-string))

(write 'hello o)

(write-char #\, o)

(display " " o)

(display "world" o)

כעת תוכל להשתמש בפרוצדורה get-output-string כדי לקבל את המחרוזת שהצטברה ב-string port בשם o:

(get-output-string o)

=> "hello, world"

String ports לא חייבים להסגר במפורש.

7.5 טעינת קבצים

קודם ראינו את הפרוצדורה load הטוענת קבצים המכילים קוד Scheme. טעינת קובץ מבוססת על הערכה סדרתית של כל תבנית Scheme בקובץ. ארגומנט ה-pathname הניתן ל-load מוערך ביחס לקרבתו לספריית הפעולה הנוכחית של Scheme, שהיא בד"כ הספרייה שבה הקריאה לריצה נעשתה.

קבצים יכולים לטעון קבצים אחרים. הדבר שימושי בעיקר בתכניות גדולות המשתרעות על פני מספר רב של קבצים. למרבה הצער, ללא שימוש ב-pathnames מלאים, ארגומנט הקובץ של load יהיה תלוי בספריית Scheme הנוכחית.
אספקת pathnames מלאים אינה תמיד נוחה , כי היינו מעונינים לנוע על קבצי התכנית כיחידה (שימור ה-pathnames היחסיים שלהם), שתתכן להרבה מכונות שונות.

MzScheme מספקת את פרוצדורת load-relative שעוזרת במידה רבה בייצוב הקבצים לצורך הטענתם. load-relative, כמו load, מקבלת את ארגומנט pathname. כשמתרחשת קריאת load-relative בקובץ foo.scm, מסלול הארגומנטים שלה מחושב מהספרייה של הקובץ הקורא foo.scm .בייחוד, pathname זה מחושב באופן בלתי תלוי בספריית Scheme הנוכחית, ובכך מאפשר פיתוח נוח של תכנית רבת קבצים.

נשלח ב-27/7/2011 17:08

פרק 8 - Macros

משתמשים יכולים ליצור תבניות משלהם ע"י הגדרת macros. כאשר Scheme נתקלת בביטוי macro, היא פונה לטרנספורמטור של ה-macro של התת תבניות ומעריכה את התוצאה של ההמרה.

ה-Macro מציין את קטע הקוד שלו. סוג זה של המרה שימושי לקיצור תבנית טקסטואלית מורכבת.
Macro - מוגדר ע"י שימוש בתבנית define-macro .
לדוגמא, אם ב-Scheme שלך חסרה הפרוצדורה when, ניתן להגדיר אותה כ-macro.

(define-macro when

(lambda (test . branch)

(list 'if test

(cons 'begin branch))))

ההגדרה הזו של when, תמיר ביטוי של when לביטוי if מקביל.

דוגמא לשימוש ב-when:

(when (< (pressure tube) 60)

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube))

בדוגמא זו ביטוי ה-when יומר לביטוי אחר, התוצאה של יישום הטרנספורמטור של when על ביטויי תת התבניות של ה-when:

(apply

(lambda (test . branch)

(list 'if test

(cons 'begin branch)))

'((< (pressure tube) 60)

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube)))

ההמרה מפיקה את הרשימה:

(if (< (pressure tube) 60)

(begin

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube)))

Scheme תעריך את הביטוי כפי שהעריכה את שאר הביטויים.

הנה דוגמא נוספת להגדרת macro של unless:

(define-macro unless

(lambda (test . branch)

(list 'if (list 'not test)

(cons 'begin branch))))

ניתן להשתמש ב-when בהגדרה של unless:

(define-macro unless

(lambda (test . branch)

(cons 'when

(cons (list 'not test) branch))))

ההרחבות של ה-macro יכולות להתייחס ל-macros אחרים.

8.1 ההרחבות ל-template

הטרנספורמטור של ה-macro לוקח כמה s-expression ומפיק מהם s-expression יחיד שניתן יהיה להשתמש בו כתבנית. בד"כ הפלט הוא רשימה.
בדוגמא שלנו הפלט הוא רשימה הנוצרת ע"י שימוש ב:

(list 'if test

(cons 'begin branch))

ה-test מקושר לתת תבנית הראשונה של ה-macro, כלומר:

(< (pressure tube) 60)

ה-branch קשור ליתר התת תבניות של ה-macro, כלומר:

((open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube))

רשימות הפלט יכולות להיות מעט מסובכות. macro - יותר מסובך יכול להוביל למבנה יותר משוכלל של רשימת הפלט. במקרים אלו יותר קל לייצג את פלט ה-macro כ-template, שיכיל את הארגומנטים של ה-macro במקומות הנכונים.
Scheme מספקת את התחביר לציין template (ע"י גרש).

לכן נוח יותר לייצג את הביטוי:

(list 'IF test

(cons 'BEGIN branch))

כך:

'(IF ,test

(BEGIN ,@branch))

כעת נכתוב מחדש את הגדרת ה-macro של when:

(define-macro when

(lambda (test . branch)

'(IF ,test

(BEGIN ,@branch))))

יש לשים לב שהפורמט של ה-template בניגוד למבני הרשימה הקודמים נותן אינדיקציה על התבנית של רשימת הפלט. הגרש ( ' ) מציג מבנה של template לרשימה.
האלמנטים ב-template מופיעים אחד אחד מלבד אלו שלפניהם יש פסיק (',') או ('@,'). על מנת להמחיש זאת רשמנו את האלמנטים שמופיעים באותיות גדולות.
הפסיק ו ה-('@,') משמשים להכנסת ארגומנטים ל-template. הפסיק מכניס את תוצאת הערכה לביטוי הבא. ה-('@,') מכניס את התוצאה לביטוי הבא לאחר שאיחה אותה, כלומר, הוא מסיר לקבוצה הקיצונית ביותר את הסוגריים.
(מכאן נובע שהביטוי שמגיע לפני ('@,') חייב להיות רשימה).
בדוגמא שלנו לאחר נתינת הערכים ש-test ו-branch קשורים אליהם, קל לראות שה-template יורחב לביטוי הנ"ל:

(IF (< (pressure tube) 60)

(BEGIN

(open-valve tube)

(attach floor-pump tube)

(depress floor-pump 5)

(detach floor-pump tube)

(close-valve tube)))

8.2 הימנעות מלכידת משתנים ב-macro

הגדרת my-or, שהיא תבנית בעלת שני ארגומנטים:

(define-macro my-or

(lambda (x y)

'(if ,x ,x ,y)))

my-or מקבלת שני ארגומנטים ומחזירה את הערך של הארגומנט הראשון שהוא אמת. (אם אין כאלו היא תחזיר f#). למעשה הביטוי השני יחושב רק אם הראשון הוא שקר.

לדוגמא:

(my-or 1 2)

=> 1

(my-or #f 2)

=> 2

אך יש בעיה ב-my-or כפי שהיא כתובה כעת. היא מעריכה את הארגומנט הראשון פעמיים אם הוא אמת: פעם אחת בבדיקת ה-if ופעם נוספת ב-than. תופעה זו יכולה לגרום להתנהגות לא רצויה אם הארגומנט השני מכיל הדפסה למסך לדוגמא.

(my-or

(begin

(display "doing first argument")

(newline)

#t)

קטע קוד זה מדפיס פעמיים "doing first argument". ניתן להימנע מכך ע"י אחסון תוצאת בדיקת ה-if במשתנה מקומי כלומר כך:

(define-macro my-or

(lambda (x y)

'(let ((temp ,x))

(if temp temp ,y))))

קוד זה כמעט טוב, רק שהשתמשנו באותו שם משתנה temp.
אם נריץ זאת נקבל:

(define temp 3)

(my-or #f temp)

=> #f

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

(define-macro my-or

(lambda (x y)

'(let ((+temp ,x))

(if +temp +temp ,y))))

קטע קוד זה יעבוד מכיוון שלא ישתמשו במשתנה temp+ בקוד מחוץ ל-macro.
יש דרך יותר אמינה להשיג שמות משתנים ייחודים ע"י שימוש בפרוצדורה ב-gensym.
הגדרה יותר בטוחה ל-my-or ע"י שימוש gensym:

(define-macro my-or

(lambda (x y)

(let ((temp (gensym)))

'(let ((,temp ,x))

(if ,temp ,temp ,y)))))

בהגדרות ה-macro באתר זה לא נשתמש ב-gensym על מנת להיות יותר תמציתיים.
נשתמש ב-+ כקידומת למשתנים ונשאיר לקורא להפוך אותם ע"י שימוש ב-gensym.

8.3 fluid-let

הגדרה נוספת ל-macro היותר מסובך fluid-let (פרק 5.2). fluid-let מציין באופן זמני קישורים לקבוצה של משתנים לקסיקלים.
לדוגמא ביטוי זה של fluid-let:

(fluid-let ((x 9) (y (+ y 1)))

(+ x y))

ואנו רוצים שהוא יורחב ל:

(let ((OLD-X x) (OLD-Y y))

(set! x 9)

(set! y (+ y 1))

(let ((RESULT (begin (+ x y))))

(set! x OLD-X)

(set! y OLD-Y)

RESULT))

בדוגמא זו אנו רוצים ש-OLD-Y ,OLD-X ו-RESULT יהיו סמלים שלא ילכדו משתנים אחרים בתבנית ה-fluid-let.
בדוגמא הבאה נכתוב את הקטע מחדש בעזרת ה-macro fluid-let אשר מיישמת את מבוקשנו:

(define-macro fluid-let

(lambda (xexe . body)

(let ((xx (map car xexe))

(ee (map cadr xexe))

(old-xx (map (lambda (ig) (gensym)) xexe))

(result (gensym)))

'(let ,(map (lambda (old-x x) '(,old-x ,x))

old-xx xx)

,@(map (lambda (x e)

'(set! ,x ,e))

xx ee)

(let ((,result (begin ,@body)))

,@(map (lambda (x old-x)

'(set! ,x ,old-x))

xx old-xx)

,result)))))

הארגומנטים ב-macro הם: xexe - המייצג רשימה של זוגות משתנים או ביטויים המוצגים ע"י fluid-let ו-body - המייצג רשימה של ביטויים בגוף הפרוצדורה fluid-let.
בדוגמא שלנו

((x 9) (y(+y 1 )))

מייצג את הארגומנט xexe , ו-(( x y +)) מייצג את הארגומנט body.

גוף ה-macro מציג קבוצת משתנים מקומיים :
xx - מייצג רשימת משתנים שחולצו מזוגות המשתנים או הביטויים.
ee - מייצג את הרשימה המתאימה של הביטויים.
old-xx - מייצג רשימה של משתנים מזהים חדשים עבור כל משתנה הנמצא ב-xx.
הם משמשים לאחסון הערכים הנכנסים למשתנים הנמצאים ב-xx, לכן ניתן לחזור לערכים המקוריים של המשתנים לאחר שגוף ה-fluid-let הוערך.
result - הנו משתנה מזהה חדש המשמש לאחסון הערך של גוף הפרוצדורה fluid-let.
בדוגמא שלנו xx - הוא הרשימה ( x y ) ו-ee - הוא הרשימה (y 1 (+9)). בהתאם ליישום הפרוצדורות gensym במערכת המשתמש, יתכן ו-old-xx יהיה הרשימה (GEN-63 GEN-64) ו-result יהיה GEN-65.

רשימת הפלט נוצרת ע"י ה-macro כפי שיתואר בדוגמא להלן ומתאים לדרישותינו:

(let ((GEN-63 x) (GEN-64 y))

(set! x 9)

(set! y (+ y 1))

(let ((GEN-65 (begin (+ x y))))

(set! x GEN-63)

(set! y GEN-64)

GEN-65))

נשלח ב-27/7/2011 17:11

פרק 9 - מבנים

נתונים שבאופן טבעי מקובצים יחדיו נקראים מבנים. ניתן להשתמש בסוגי נתונים מורכבים לייצג מבנים כמו וקטורים רשימות וכו'.
לדוגמא אנו עוסקים בנתונים הקשורים לעץ. האלמנטים של הנתונים או השדות יכולים להיות: גובה, הקף, גיל, צורת העלה וצבע העלה. סה"כ יש לנו 5 שדות.
נתונים אלו יכולים להיות מיוצגים ע"י וקטור בעל 5 אלמנטים. ניתן יהיה לגשת לשדות ע"י הפרוצדורה vector-ref וכן ניתן יהיה לשנות את ערכם ע"י הפרוצדורה !vector-set. בדרך זו אנו מעמיסים על עצמנו ליזכור איזה אינדקס שייך לכל שדה. וכן יכולות להיווצר טעויות במיוחד כאשר מוסיפים שדות.

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

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

(defstruct tree height girth age leaf-shape leaf-color)

מבנה זה מספק פרוצדורה בונה הנקראת make-tree.
פרוצדורה זו יכולה לגשת לכל אחד מהשדות הנקרא tree.girth ,tree.height וכו'.
פרוצדורה היכולה לשנות את ערכי השדות נקראת set!tree.girth, set!tree.height וכו'.

נשתמש ב-constructor כך:

(define coconut

(make-tree 'height 30

'leaf-shape 'frond

'age 5))

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

(tree.height coconut) => 30

(tree.leaf-shape coconut) => frond

(tree.girth coconut) => <undefined>

הפרוצדורה tree.grith מחזירה ערך לא מוגדר, מכיוון שלא נתנו ערך ל-girth ב-coconut .

את הפרוצדורות שמשנות ערכים מפעילים כך:

(set!tree.height coconut 40)

(set!tree.girth coconut 10)

אם נרצה לגשת לשדות ע"י הפרוצדורות המתאימות נקבל:

(tree.height coconut) => 40

(tree.girth coconut) => 10

9.1 אתחולי ברירת המחדל

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

לדוגמא:

(defstruct tree height girth age

(leaf-shape 'frond)

(leaf-color 'green))

(define palm (make-tree 'height 60))

(tree.height palm)

=> 60<

(tree.leaf-shape palm)

=> frond

(define plantain

(make-tree 'height 7

'leaf-shape 'sheet))

(tree.height plantain)

=> 7

(tree.leaf-shape plantain)

=> sheet

(tree.leaf-color plantain)

=> green

9.2 הגדרת ה-'defstruct'

ההגדרות של defstruct macro הן:

(define-macro defstruct

(lambda (s . ff)

(let ((s-s (symbol->string s)) (n (length ff)))

(let* ((n+1 (+ n 1))

(vv (make-vector n+1)))

(let loop ((i 1) (ff ff))

(if (<= i n)

(let ((f (car ff)))

(vector-set! vv i

(if (pair? f) (cadr f) '(if #f #f)))

(loop (+ i 1) (cdr ff)))))

(let ((ff (map (lambda (f) (if (pair? f) (car f) f))

ff)))

'(begin

(define ,(string->symbol

(string-append "make-" s-s))

(lambda fvfv

(let ((st (make-vector ,n+1)) (ff ',ff))

(vector-set! st 0 ',s)

,@(let loop ((i 1) (r '()))

(if (>= i n+1) r

(loop (+ i 1)

(cons '(vector-set! st ,i

,(vector-ref vv i))

r))))

(let loop ((fvfv fvfv))

(if (not (null? fvfv))

(begin

(vector-set! st

(+ (list-position (car fvfv) ff)

(cadr fvfv))

(loop (cddr fvfv)))))

st)))

,@(let loop ((i 1) (procs '()))

(if (>= i n+1) procs

(loop (+ i 1)

(let ((f (symbol->string

(list-ref ff (- i 1)))))

(cons

'(define ,(string->symbol

(string-append

s-s "." f))

(lambda (x) (vector-ref x ,i)))

(cons

'(define ,(string->symbol

(string-append

"set!" s-s "." f))

(lambda (x v)

(vector-set! x ,i v)))

procs))))))

(define ,(string->symbol (string-append s-s "?"))

(lambda (x)

(and (vector? x)

(eqv? (vector-ref x 0) ',s))))))))))

נשלח ב-27/7/2011 17:12

פרק 10 - Alists and tables

רשימות מקושרות או כפי שהן מכונות - alists, הן צורות של רשימות ב-Scheme במבנה מיוחד. כל אלמנט ברשימה נחשב כרכיב 'cons', ה-'car' נקרא המפתח וה-'cdr' הוא ערך המשורשר עם המפתח הנ"ל.

לדוגמא:

((a . 1) (b . 2) (c . 3))

פרוצדורה הנקראת (assv k al) מוצאת את כל רכיבי ה-cons המקושרים עם מפתח k ברשימה המקושרת al. מפתחות הרשימות המקושרות השונות משווים עם ה-k הנתון באמצעות פרדיקט ההשוואה ?eqv. באופן כללי, בכל זאת נרצה פרדיקט אחר להשוואת מפתחות.
לדוגמא, אם המפתחות הם מחרוזות מסוג case-insensitive, הפרדיקט ?eqv אינו יעיל כ"כ.
כעת נרצה להגדיר מבנה הנקרא table שהוא רשימה מקושרת משופרת, המאפשר למשתמש להגדיר פרדיקטים על המפתחות שלו. השדות שלו הם: equ ו-alist.

(defstruct table (equ eqv?) (alist '()))

(פרדיקט ברירת המחדל הוא eqv? באשר לרשימה מקושרת רגילה כאשר הרשימה מאותחלת להיות ריקה).
נשתמש בפרוצדורה table-get כדי לקבל את הערך (בניגוד ל-cons cell) המשורשר עם מפתח נתון. table-get מקבלת table ומפתח כארגומנטים וערך ברירת מחדל אופציונלי שיוחזר במקרה שהמפתח לא נמצא ב-table.

(define table-get

(lambda (tbl k . d)

(let ((c (lassoc k (table.alist tbl) (table.equ tbl))))

(cond (c (cdr c))

((pair? d) (car d))))))

הפרוצדורה lassoc שהשתמשנו בה ב-table-get מוגדרת להלן:

(define lassoc

(lambda (k al equ?)

(let loop ((al al))

(if (null? al) #f

(let ((c (car al)))

(if (equ? (car c) k) c

(loop (cdr al))))))))

הפרוצדורה !table-put משמשת לעדכון ערך המפתח ב-table נתון:

(define table-put!

(lambda (tbl k v)

(let ((al (table.alist tbl)))

(let ((c (lassoc k al (table.equ tbl))))

(if c (set-cdr! c v)

(set!table.alist tbl (cons (cons k v) al)))))))

הפרוצדורה table-for-each קוראת לפרוצדורה נתונה עבור כל זוג מפתח/ערך ב-table:

(define table-for-each

(lambda (tbl p)

(for-each

(lambda (c)

(p (car c) (cdr c)))

(table.alist tbl))))

נשלח ב-27/7/2011 17:13

פרק 11 - ממשק המערכת

תוכניות יעילות ב-Scheme צריכות לאפשר שימוש בפקודות המפעילות את מערכת ההפעלה.

11.1 חיפוש ומחיקת קבצים

הפרוצדורה ?file-exists בודקת האם הארגומנט שסופק לה הוא שם של קובץ.
delete-file - פרוצדורה זו מוחקת את הקובץ שסופק לה בתור ארגומנט.
פרוצדורות אלו אינן סטנדרטיות בשפה אך זמינות ברוב היישומים.
הן פועלות על קבצים ולא על ספריות.

file-or-directory-modify-seconds מחזירה את הזמן שבו הקובץ או הספרייה שונו. הזמן מוערך בשניות מ-12 בצוהריים עפ"י שעון גרינוויץ' ב-1 לינואר 1970.

לדוגמא,

(file-or-directory-modify-seconds "hello.scm")

=> 893189629

בהנחה שהקובץ hello.scm שונה בסביבות 21/4/98.

11.2 פקודות הקוראות למערכת ההפעלה

הפרוצדורה system מריצה את הארגומנט שספקנו לה כמו פקודה למערכת ההפעלה. היא מחזירה true אם הפקודה הצליחה ואת ה-exit status 0 ומחזירה false אם הפקודה נכשלה והחזירה exit status שונה מ-0. הפלט של הפקודה יופיע ב-standard output.

(system "ls")

;lists current directory

(define fname "spot")

(system (string-append "test -f " fname))

;tests if file 'spot' exists

(system (string-append "rm -f " fname))

;removes 'spot'

(system "ls")

;lists current directory

(define fname "spot")

(system (string-append "test -f " fname))

;tests if file 'spot' exists

(system (string-append "rm -f " fname))

;removes 'spot'

הדוגמא לעיל זהה לדוגמא הזו:

(file-exists? fname)

(delete-file fname)

11.3 משתני סביבה

הפרוצדורה getenv מחזירה את המסלול של משתנה הסביבה:

(getenv "HOME")

=> "/home/dorai"

(getenv "SHELL")

=> "/bin/bash"

נשלח ב-27/7/2011 17:16

פרק 12 - מחלקות ואובייקטים

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

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

12.1 מערכת אובייקטים פשוטה

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

יעיל להגדיר בהתחלה מחלקות ע"י שימוש במבנה הנקרא standard-class. מבנה זה מכיל שדות עבור התכונות, מחלקות העל והמתודות. שני השדות הראשונים ייקראו slots ו-superclass בהתאמה.
נשתמש בשני שדות עבור המתודות: שדה ה-method names - יחזיק את רשימת המתודות של המחלקה ואילו שדה ה-method-vector יחזיק את וקטור הערכים של מתודות המחלקה.

להלן הגדרה של standard-class:

(defstruct standard-class

slots superclass method-names method-vector)

אנו יכולים להשתמש ב-make-standard-class שזו פרוצדורת יצירת standard-class כדי ליצור מחלקה חדשה.
לדוגמא:

(define trivial-bike-class

(make-standard-class

'superclass #t

'slots '(frame parts size)

'method-names '()

'method-vector #()))

למחלקות מורכבות יותר יש מחלקות-על שאינן טריוויאליות ומתודות שיידרשו מס' רב של איתחולים סטנדרטיים שנרצה להסתיר במהלך תהליך יצירת המחלקה. לצורך כך נגדיר macro הנקרא: create-class שייבצע את הקריאה המתאימה ל-make-standard-class.

(define-macro create-class

(lambda (superclass slots . methods)

'(create-class-proc

,superclass

(list ,@(map (lambda (slot) '',slot) slots))

(list ,@(map (lambda (method) '',(car method)) methods))

(vector ,@(map (lambda (method) ',(cadr method)) methods)))))

נדחה את הגדרת פרוצדורת create-class-proc לשלב מאוחר יותר.

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

(define make-instance

(lambda (class . slot-value-twosomes)

;Find 'n', the number of slots in 'class'.

;Create an instance vector of length 'n + 1',

;because we need one extra element in the instance

;to contain the class.

(let* ((slotlist (standard-class.slots class))

(n (length slotlist))

(instance (make-vector (+ n 1))))

(vector-set! instance 0 class)

;Fill each of the slots in the instance

;with the value as specified in the call to

;'make-instance'.

(let loop ((slot-value-twosomes slot-value-twosomes))

(if (null? slot-value-twosomes) instance

(let ((k (list-position (car slot-value-twosomes)

slotlist)))

(vector-set! instance (+ k 1)

(cadr slot-value-twosomes))

(loop (cddr slot-value-twosomes))))))))

להלן דוגמא לקביעת מופע למחלקה:

(define my-bike

(make-instance trivial-bike-class

'frame 'cromoly

'size '18.5

'parts 'alivio))

זה קושר את my-bike למופע:

#(<trivial-bike-class> cromoly 18.5 alivio)

כאשר <trivial-bike-class> הוא נתון ב-Scheme (וקטור נוסף) שהוא הערך של trivial-bike-class, כפי שמוגדר לעיל.

הפרוצדורה class-of מחזירה את המחלקה של המופע:

(define class-of

(lambda (instance)

(vector-ref instance 0)))

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

(define class-of

(lambda (x)

(if (vector? x)

(let ((n (vector-length x)))

(if (>= n 1)

(let ((c (vector-ref x 0)))

(if (standard-class? c) c #t))

#t))

#t)))

המחלקה של אובייקט Scheme שלא נוצר בעזרת standard-class תהיה t#, מחלקת האפס.
הפרוצדורות slot-value ו-set!slot-value ניגשות ומשנות את הערכים של מופע מחלקה:

(define slot-value

(lambda (instance slot)

(let* ((class (class-of instance))

(slot-index

(list-position slot (standard-class.slots class))))

(vector-ref instance (+ slot-index 1)))))

(define set!slot-value

(lambda (instance slot new-val)

(let* ((class (class-of instance))

(slot-index

(list-position slot (standard-class.slots class))))

(vector-set! instance (+ slot-index 1) new-val))))

כעת אנו יכולים לטפל בהגדרת create-class-proc. פרוצדורה זו לוקחת מחלקת-על, רשימת תכונות, רשימת שמות המתודות ווקטור מתודות ומבצעת את הקריאה המתאימה ל-make-standard-class. החלק המטעה היחיד הוא הערך הניתן לשדות התכונות. לא רק הארגומנטים של התכונות מסופקים ע"י create-class גם התכונות של מחלקת העל.
בנוסף עלינו לוודא שאין תכונות כפולות.

(define create-class-proc

(lambda (superclass slots method-names method-vector)

(make-standard-class

'superclass superclass

'slots (let ((superclass-slots

(if (not (eqv? superclass #t))

(standard-class.slots superclass)

'())))

(if (null? superclass-slots) slots

(delete-duplicates

(append slots superclass-slots))))

'method-names method-names

'method-vector method-vector)))

הפרוצדורה delete-duplicates המופעלת על רשימה s, מחזירה רשימה חדשה שמכילה רק את המופע האחרון של כל אלמנט ב-s.

(define delete-duplicates

(lambda (s)

(if (null? s) s

(let ((a (car s)) (d (cdr s)))

(if (memv a d) (delete-duplicates d)

(cons a (delete-duplicates d)))))))

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

(define send

(lambda (method instance . args)

(let ((proc

(let loop ((class (class-of instance)))

(if (eqv? class #t) (error 'send)

(let ((k (list-position

method

(standard-class.method-names class))))

(if k

(vector-ref (standard-class.method-vector class) k)

(loop (standard-class.superclass class))))))))

(apply proc instance args))))

כעת נוכל להגדיר מחלקות "מעניינות" הרבה יותר:

(define bike-class

(create-class

(frame size parts chain tires)

(check-fit (lambda (me inseam)

(let ((bike-size (slot-value me 'size))

(ideal-size (* inseam 3/5)))

(let ((diff (- bike-size ideal-size)))

(cond ((<= -1 diff 1) 'perfect-fit)

((<= -2 diff 2) 'fits-well)

((< diff -2) 'too-small)

((> diff 2) 'too-big))))))))

כאן, מחלקת bike-class מכילה מתודה בשם check-fit, המקבלת כארגומנטים את האופניים ואת מידות נעלי בעליהם ומדווחת על התאמת האופניים לאדם.
נגדיר מחדש את my-bike:

(define my-bike

(make-instance bike-class

'frame 'titanium ; I wish

'size 21

'parts 'ultegra

'chain 'sachs

'tires 'continental))

כדי לבדוק אם האופניים יתאימו לבעל מידת נעליים 32:

(send 'check-fit my-bike 32)

ניצור תת מחלקה ל-bike-class.

(define mtn-bike-class

(create-class

bike-class

(suspension)

(check-fit (lambda (me inseam)

(let ((bike-size (slot-value me 'size))

(ideal-size (- (* inseam 3/5) 2)))

(let ((diff (- bike-size ideal-size)))

(cond ((<= -2 diff 2) 'perfect-fit)

((<= -4 diff 4) 'fits-well)

((< diff -4) 'too-small)

((> diff 4) 'too-big))))))))

מחלקת mtn-bike-class מוסיפה תכונה הנקראת suspension ומשתמשת בהגדרות השונות במקצת עבור המתודה check-fit.

12.2 מחלקות הן מופע בעצמן

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

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

(define standard-class

(vector 'value-of-standard-class-goes-here

(list 'slots

'superclass

'method-names

'method-vector)

'(make-instance)

(vector make-instance)))

יש שים לב כי הוקטור של standard-class מלא באופן חלקי בלבד:
הסימון value-of-standard-class-goes-here מתפקד כממלא מקום. כעת, כשהגדרנו את ערך standard-class, נוכל להשתמש בכך כדי להגדיר את המחלקות שלו, שהן בעצם הוא עצמו.
(vector-set! standard-class 0 standard-class)

יש שים לב כי לא נוכל לסמוך יותר על הפרוצדורות המבוססות על מבנה ה-class.

עלינו כל הקריאות מהצורה:

(standard-class? x)

(standard-class.slots c)

(standard-class.superclass c)

(standard-class.method-names c)

(standard-class.method-vector c)

(make-standard-class ...)

בצורה הבאה:

(and (vector? x) (eqv? (vector-ref x 0) standard-class))

(vector-ref c 1)

(vector-ref c 2)

(vector-ref c 3)

(vector-ref c 4)

(send 'make-instance standard-class ...)

12.3 ירושה מרובה

קל לשנות את מערכת האובייקטים כך שתאפשר למחלקות לרשת מיותר ממחלקה אחת. נגדיר מחדש את standard-class כך שתהיה בה תכונה הנקראת class-precedence-list במקום superclass. ה-class-precedence-list של מחלקה מסוימת היא רשימה של כל מחלקות העל, לא רק מחלקת העל הישירה המצוינת במהלך יצירת המחלקה בעזרת create-class. השם מרמז כי מחלקות העל מסודרות בסדר מיוחד, כך שלמחלקות-על שנמצאות בתחילת הרשימה יש עדיפות על אלו שנמצאות בסוף הרשימה.

(define standard-class

(vector 'value-of-standard-class-goes-here

(list 'slots 'class-precedence-list 'method-names

'method-vector)

'()

'(make-instance)

(vector make-instance)))

לא רק רשימת התכונות השתנתה כדי לכלול את התכונה החדשה, אלא גם תכונת ה-superclass תהיה עכשיו () במקום t#. זאת כיוון שה-class-precedence-list של ה-standard-class חייב להיות רשימה.
לכאורה היינו יכולים לציין זאת כ-(t#), אך אנו לא מזכירים את מחלקת האפס כיוון שהיא נמצאת בכל class-precedence-list של כל מחלקה. על המקרו create-class להשתנות כדי לקבל רשימה של מחלקות-על ישירות במקום מחלקת-על בודדת:

define-macro create-class

(lambda (direct-superclasses slots . methods)

'(create-class-proc

(list ,@(map (lambda (su) ',su) direct-superclasses))

(list ,@(map (lambda (slot) '',slot) slots))

(list ,@(map (lambda (method) '',(car method)) methods))

(vector ,@(map (lambda (method) ',(cadr method)) methods))

)))

על ה-create-class-proc לחשב את ה- class-precedence-list ממחלקות העל הישירות ואת רשימת התכונות מה-class-precedence-list.

(define create-class-proc

(lambda (direct-superclasses slots method-names method-vector)

(let ((class-precedence-list

(delete-duplicates

(append-map

(lambda (c) (vector-ref c 2))

direct-superclasses))))

(send 'make-instance standard-class

'class-precedence-list class-precedence-list

'slots

(delete-duplicates

(append slots (append-map

(lambda (c) (vector-ref c 1))

class-precedence-list)))

'method-names method-names

'method-vector method-vector))))

הפרוצדורה append-map היא שילוב של append ושל map:

(define append-map

(lambda (f s)

(let loop ((s s))

(if (null? s) '()

(append (f (car s))

(loop (cdr s)))))))

על הפרוצדורה send לבדוק באמצעות ה- class-precedence-list משמאל לימין כאשר היא מחפשת מתודה כלשהי.

(define send

(lambda (method-name instance . args)

(let ((proc

(let ((class (class-of instance)))

(if (eqv? class #t) (error 'send)

(let loop ((class class)

(superclasses (vector-ref class 2)))

(let ((k (list-position

method-name

(vector-ref class 3))))

(cond (k (vector-ref

(vector-ref class 4) k))

((null? superclasses) (error 'send))

(else (loop (car superclasses)

(cdr superclasses))))

))))))

(apply proc instance args))))

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

נשלח ב-27/7/2011 17:21

פרק 13 - Jumps

אחד היתרונות של Scheme הוא התמיכה ב-jumps או בקרה לא מקומית. Scheme מאפשרת לקפוץ למקומות שרירותיים בתוכנית. זה בניגוד לתבניות המוגבלות האחרות .
האופרטור הלא מקומי של Scheme הוא הפרוצדורה call-with-current-continuation.
אנו נראה כיצד ניתן להשתמש באופרטור הנ"ל .

13.1 call-with-current-continuation

האופרטור הנ"ל קורא לארגומנטים שלו, שהם פרוצדורות בעלות משתנה אחד, עם הערך "current continuation". זה מסביר את השם של הפרוצדורה. הקיצור של הפרוצדורה הוא call/cc.

ה-current continuation בכל שלב בריצת התוכנית הוא קיצור של שאר התוכנית .

לדוגמא,

(+ 1 (call/cc

(lambda (k)

(+ 2 (k 3)))))

שאר התוכנית מהקריאה ל- call/cc היא תוכנית עם "חור" (המיוצג ע"י [ ]):

(1+ [])

במילים אחרות ההמשך הוא תוכנית אשר תוסיף 1 כאשר צריך למלא את ה"חור".

הארגומנט של call/cc שמגיע עמו הוא הפרוצדורה :

(lambda (k)

(+ 2 (k 3)))

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

לדוגמא,
(1+ [])

התוכנית שתרוץ היא:

(3 1+)
הפרוצדורה תחזיר 4.

לסיכום:

(+ 1 (call/cc

(lambda (k)

(+ 2 (k 3)))))

=> 4

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

נתבונן בדוגמא הבאה:

(define r #f)

(+ 1 (call/cc

(lambda (k)

(set! r k)

(+ 2 (k 3)))))

=> 4

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

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

(r 5)=> 6

יש לשים לב ש-r יעזוב את ההמשך שלו, לדוגמא:

(+ 3 (r 5))

=> 6

ההמשכים שמסופקים ע"י call/cc הן abortive continuations.

13.2 Escaping continuations

Escaping continuations הם השימוש הפשוט ביותר של call/cc.
הם מאוד שימושיים בתכנות פרוצדורות או לולאות יציאה. הפרוצדורה list-product לדוגמא לוקחת רשימת מספרים ומכפילה ביניהם.

ההגדרה הפרוצדורה הזו:

define list-product

(lambda (s)

(let recur ((s s))

(if (null? s) 1

(* (car s) (recur (cdr s)))))))

ישנה בעיה עם פתרון זה .אם אחד מהאלמנטים הוא 0 ,ויש הרבה אלמנטים אחרי 0 ברשימה אזי התשובה היא forgone conclusion, וכן הקוד יבצע קריאות רקורסיביות לשווא עד אשר נגיע לפתרון. כאן השימוש ב-escape continuation באים לידי ביטוי:

(define list-product

(lambda (s)

(call/cc (lambda (exit)

(let recur ((s s))

(if (null? s) 1

(if (= (car s) 0) (exit 0)

(* (car s) (recur (cdr s))))))))))

אם האלמנט 0 נמצא, exit נקראת עם 0 ע"י התחמקות מקריאות נוספות של recure.

13.3 Tree matching

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

same-fringe? '(1 (2 3)) '((1 2) 3))

=> #t

(same-fringe? '(1 2 3) '(1 (3 2)))

=> #f

השיטה היא לשטח את העצים ולראות האם התוצאות שוות.

(define same-fringe?

(lambda (tree1 tree2)

(let loop ((ftree1 (flatten tree1))

(ftree2 (flatten tree2)))

(cond ((and (null? ftree1) (null? ftree2)) #t)

((or (null? ftree1) (null? ftree2)) #f)

((eqv? (car ftree1) (car ftree2))

(loop (cdr ftree1) (cdr ftree2))) (else #f)))))

(define flatten

(lambda (tree)

(cond ((null? tree) '())

((pair? (car tree))

(append (flatten (car tree))

(flatten (cdr tree))))

(else (cons (car tree) (flatten (cdr tree)))))))

הפרוצדורה משטיחה את העצים עד שהיא מוצאת אלמנטים לא תואמים. בנוסף האלגוריתמים הטובים ביותר ידרשו שימוש ב-cons כמספר העלים סה"כ .

אנו יכולים להשתמש ב-call/cc לפתור את הבעיה הזו ללא שימוש ב-cons. כל עץ ממופה ל-generator, פרוצדורה המייצרת את העלים של העץ משמאל לימין.

לדוגמא,

(define tree->generator

(lambda (tree)

(let ((caller '*))

(letrec

((generate-leaves

(lambda ()

(let loop ((tree tree))

(cond ((null? tree) 'skip)

((pair? tree)

(loop (car tree))

(loop (cdr tree)))

(else

(call/cc

(lambda (rest-of-tree)

(set! generate-leaves

(lambda ()

(rest-of-tree 'resume)))

(caller tree))))))

(caller '()))))

(lambda ()

(call/cc

(lambda (k)

(set! caller k)

(generate-leaves))))))))

ה-generator נוצר ע"י tree->generator, הוא ישמור את ההמשך של הקריאה ב-caller, כדי שהוא ידע את מי לשלוח לעלה כאשר הוא מוצא אותו לאחר מכן, הוא קורא לפרוצדורה פנימית הנקראת generate-leaves אשר מריצה לולאה שעוברת על העץ משמאל לימין .כאשר הלולאה נתקלת בעלה היא תשתמש ב-caller להחזיר את העלה כתוצאת ה-generator, אך הוא יזכור לשמור את שאר הלולאה במשתנה generated-leaves. בפעם הבאה שנקרא ל-generator, הלולאה תחודש ותחפש אחר העלה הבא.

יש לשים לב שהדבר האחרון ש-generate-leaves עושה הוא להחזיר רשימה ריקה ל-caller לאחר שהלולאה סיימה.
ניתן לומר של-generator אין יותר עלים, מכיוון שרשימה ריקה היא לא ערך מוגדר של עלה .

הפרוצדורה ?same-fringe ממפה את הארגומנטים שלה ל-generator וקוראת לשני ה-generators לסירוגין. היא מודיעה על כשלון כאשר נמצאים עלים לא תואמים.

(define same-fringe?

(lambda (tree1 tree2)

(let ((gen1 (tree->generator tree1))

(gen2 (tree->generator tree2)))

(let loop ()

(let ((leaf1 (gen1))

(leaf2 (gen2)))

(if (eqv? leaf1 leaf2)

(if (null? leaf1) #t (loop))

#f))))))

קל לראות שעוברים על העצים פעם אחת לכל היותר, ובמקרה של אי התאמה המעבר מגיע לאי ההתאמה השמאלית הקיצונית ביותר וכן לא משתמשים ב-cons.

13.4 Coroutines

ה-generators שהשתמשנו בהם לעיל הם הכללה מעניינת של רעיון הפרוצדורה.
בכל פעם שה-generator נקרא הוא מחדש את חישובו, וכאשר יש לו תוצאה הוא מחזיר אותה
ל-caller שלו לאחר שהוא שמר את ההמשך במשתנה פנימי.
אנו יכולים להכליל את ה-generators כך שהם יוכלו לחדש אחד את השני ע"י כך שהם ישלחו תוצאות אחד לשני. פרוצדורות אלו נקראות: coroutines .

ה-coroutine תהיה פרוצדורה עם ארגומנט יחיד והגוף שלה מכיל קריאות ל-resume.
Resume היא פרוצדורה בעלת שני ארגומנטים המשתמשת ב-coroutine כדי לחדש coroutine אחרת ועם ערך למסירה.

ל-Coroutine (נניח נקרא לה A) יש משתנה פנימי הנקרא local-control-state המאחסן בכל נקודה את החישוב שנותר של ה-coroutine.
בהתחלה זה כל החישוב של הפרוצדורה. כאשר יש קריאה ל-resume כלומר קוראים ל-coroutine B, ה-coroutine העכשווית תעדכן את הערך של local-control-state שלה לשארית של עצמה, תעצור עצמה ותקפוץ ל-coroutine B.
כאשר coroutine A תחודש בשלב מסוים החישוב שלה ימשיך לפי ההמשך המאוחסן במשתנה המקומי שלה local-control-state.

(define-macro coroutine

(lambda (x . body)

'(letrec ((local-control-state

(lambda (,x) ,@body))

(resume

(lambda (c v)

(call/cc

(lambda (k)

(set! local-control-state k)

(c v))))))

(lambda (v)

(local-control-state v)))))

13.4.1 Tree matching עם Coroutines

Tree-matching הוא שימוש פשוט של coroutines. תהליך ההתאמה הוא ע"י coroutine אשר תלויה בעוד שתי coroutine נוספות המספקות את העלים של העצים המתאימים .

(define make-matcher-coroutine

(lambda (tree-cor-1 tree-cor-2)

(coroutine dont-need-an-init-arg

(let loop ()

(let ((leaf1 (resume tree-cor-1 'get-a-leaf))

(leaf2 (resume tree-cor-2 'get-a-leaf)))

(if (eqv? leaf1 leaf2)

(if (null? leaf1) #t (loop))

#f))))))

ה-coroutines של ה-leaf-generator זוכרות למי לשלוח את העלים שלהן:

(define make-leaf-gen-coroutine

(lambda (tree matcher-cor)

(coroutine dont-need-an-init-arg

(let loop ((tree tree))

(cond ((null? tree) 'skip)

((pair? tree)

(loop (car tree))

(loop (cdr tree)))

(else

(resume matcher-cor tree))))

(resume matcher-cor '()))))

הפרוצדורה same-fringe? יכולה כמעט להיכתב כך:

(define same-fringe?

(lambda (tree1 tree2)

(letrec ((tree-cor-1

(make-leaf-gen-coroutine

tree1

matcher-cor))

(tree-cor-2

(make-leaf-gen-coroutine

tree2

matcher-cor))

(matcher-cor

(make-matcher-coroutine

tree-cor-1

tree-cor-2)))

(matcher-cor 'start-ball-rolling))))

אך ה-letrec של Scheme יכול להפריד התייחסויות רקורסיביות בתוך המשתנים שהוא מציג רק אם ההתייחסויות של המשתנים הללו כרוכות בתוך lambda, לכן נכתוב:

(define same-fringe?

(lambda (tree1 tree2)

(letrec ((tree-cor-1

(make-leaf-gen-coroutine

tree1

(lambda (v) (matcher-cor v))))

(tree-cor-2

(make-leaf-gen-coroutine

tree2

(lambda (v) (matcher-cor v))))

(matcher-cor

(make-matcher-coroutine

(lambda (v) (tree-cor-1 v))

(lambda (v) (tree-cor-2 v)))))

(matcher-cor 'start-ball-rolling))))

יש לשים לב ש-call/cc לא נקראת בצורה ישירה. המשך ההפעלה מטופל ע"י ה-coroutine.

call/cc אם ב-Scheme שלך אין את הקיצור הנ"ל ניתן להוסיף לתוכנית:

(define call/cc call -with-current-continuation ).

נשלח ב-27/7/2011 17:26

פרק 14 - אי-דטרמיניסטיות

האופרטור האי-דטרמיניסטי של מכקרת'י amb הוא ותיק כמו lisp בעצמה, למרות שהוא אינו מוצג בה. amb מקבל אפס או יותר ביטויים, מבצע מעין בחירה אי-דטרמיניסטית ביניהם ומעדיף את הבחירות שייגרמו לתכנית להצליח באופן משמעותי. כאן נחקור שיבוץ של amb ב-Scheme שמבצע ברירה לעומק (dfs) של הבחירות אי-דטרמיניסטיות השונות, ומשתמש באופרטור הבקרה call/cc לבצע נסיגה (backtracking) עבור בחירה חלופית. התוצאה שתתקבל היא אסטרטגית נסיגה אלגנטית שתשמש לחקירת מרחבי בעיה בצורה ישירה ב-Scheme ללא צורך בעזרי שפה מורחבת. השילובים הנזכרים באסטרטגיות הממשיכות נועדו לממש Prolog - סוג של תכנות לוגי, אך מדובר בדבר פשוט יותר כיוון שהאופרטור המסופק הדומה מאד לאופרטור בוליאני ב-Scheme, אינו דורש הקשר מיוחד לשימושו ואינו מסתמך על תשתית לשונית כמו משתנים לוגיים ויוניפיקציות.

14.1 תיאור של 'amb'

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

(amb 1 2)
יוערך להיות 1 או 2.
amb שנקראת ללא ביטויים אינה מחזירה ערך ונחשב כי נכשלה (fail). לפיכך,

(amb)

-->ERROR!!! amb tree exhausted

(נדון בניסוחי הודעות השגיאה מאוחר יותר).

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

((amb 1 (amb)
ו-(amb (amb) 1)
שניהם מחזירים 1.

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

(amb #t #f)

יחזיר או t# או f#, אך בתכנית-

(if (amb #t #f)

(amb))

ביטוי ה-amb הראשון חייב להחזיר t#. אם הוא יחזיר f#, ה-else יהיה זה שיבחר, מה שיגרום לתכנית כולה להיכשל.

14.2 מימוש 'amb' ב-Scheme

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

(define amb-fail '*)

(define initialize-amb-fail

(lambda ()

(set! amb-fail

(lambda ()

(error "amb tree exhausted")))))

(initialize-amb-fail)

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

(define-macro amb

(lambda alts...

'(let ((+prev-amb-fail amb-fail))

(call/cc

(lambda (+sk)

,@(map (lambda (alt)

'(call/cc

(lambda (+fk)

(set! amb-fail

(lambda ()

(set! amb-fail +prev-amb-fail)

(+fk 'fail)))

(+sk ,alt))))

alts...)

(+prev-amb-fail))))))

קריאה ל-amb ראשית תאכסן ב-prev-amb-fail+ את ערך amb-fail הנוכחי בזמן הכניסה. זאת כיוון שמשתנה ה-amb-fail מאותחל להימשכויות כשלונות שונים כמו מס' האלטרנטיבות השונות שאנו מנסים. אז אנו "לוכדים" את כניסת ה-amb sk+, כך שכאשר ערך אחת האלטרנטיבות יהיה אי-כישלון, נוכל לצאת בקלות מ-amb.
מנסים כל אחת מאלטרנטיבות alt באופן סדרתי.
ראשית, אנו "לוכדים" את ההימשכות העכשווית fk+, "מכסים" אותה בפרוצדורה וטוענים amb-fail לפרוצדורה זו. האלטרנטיבה אז מוערכת כ-(sk alt+). אם alt מצליחה - ערכה יוזן ל-sk+, שייצא מייד מקריאת ה-amb. אם alt ייכשל, תתבצע קריאה ל-amb-fail. התפקיד הראשון של amb-fail הוא לטעון מחדש את amb-fail לערך שהיה לו בזמן הכניסה. אז נעשית פנייה אל הימשכות הכישלון fk+, שגורמת לאלטרנטיבה הבאה, אם קיימת, להיות מנוסה.
אם כל האלטרנטיבות נכשלות מתבצעת קריאה ל-amb-fail שבכניסת ה-amb, שאוכסן ב-prev-amb-fail+.

14.3 שימושי amb ב-Scheme

כדי לבחור מספר בין 1 ל-10 היינו יכולים לומר

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

כדי להיות בטוחים, כתכנית, יוחזר לנו הערך 1, אך באופן עקרוני יכולנו לקבל את כל אחד מהמספרים המוזכרים.
הפרוצדורה number-between היא דרך מופשטת יותר לייצר מספרים ממס' נתון lo ועד מס' נתון hi (כולל קצוות):

(define number-between

(lambda (lo hi)

(let loop ((i lo))

(if (> i hi) (amb)

(amb i (loop (+ i 1)))))))

כך, הקריאה (number-between 1 6 ) תחזיר בהתחלה 1 .כשזה ייכשל, תתבצע לולאה וייוצר 2. כשזה ייכשל נקבל 3, 4 וכו' עד 6. אחרי 6, קריאה ללולאה עם ערך 7, שהוא גדול מ-6, תקרא ל-(amb), שייגרום לכישלון סופי. (זכור כי (amb) בעצמה נותנת ערך כישלון). בנקודה זו, התכנית המכילה את הקריאה ל-(number-between 1 6 ) תבצע נסיגה לקריאת ה-amb הקודמת כרונולוגית, ותנסה לספק את הקריאה באופן אחר.

הכישלון המובטח של (amb) יכול לשמש לתכנית assertions.

(define assert

(lambda (pred)

(if (not pred) (amb))))

הקריאה (assert pred) עומדת על כך ש-pred יהיה בעל ערך אמת. אחרת, נקודת ההחלטה הנוכחית של amb - תיכשל.
להלן פרוצדורה המשתמשת ב-assert המייצרת ראשוני קטן או שווה לארגומנט שלה hi:

(define gen-prime

(lambda (hi)

(let ((i (number-between 2 hi)))

(assert (prime? i))

i)))

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

(amb)

=> 3

זה מותיר אחריו המשך כשלון נוסף, שיכול להיקרא שוב עבור פתרון נוסף:

(amb)

=> 5

הבעיה בשיטה זו היא שתכנית בהתחלה נקראת מה-prompt של Scheme, ופתרונות מוצלחים מושגים גם ע"י קריאה ל-amb ב-prompt של Scheme.
למעשה, אנו משתמשים בתכניות שונות (א"א לצפות כמה!), כדי להעביר מידע מתכנית קודמת לבא. במקום זאת, היינו מעונינים לקבל פתרונות אלו כערך המוחזר של תבנית כלשהי שנוכל לקרוא לה מכל הקשר בו אנו נמצאים. כדי לבצע זאת, הגדרנו את המקרו bag-of, שיחזיר את מופעי ההצלחות של הארגומנט הניתן לו. (אם הארגומנט אף פעם לא מצליח, bag-of יחזיר רשימה ריקה). לפיכך, נוכל לומר כי

(bag-of

(gen-prime 20))

יחזיר

(2 3 5 7 11 13 17 19)

מקרו ה-bag-of מוגדר בצורה הבאה:

(define-macro bag-of

(lambda (e)

'(let ((+prev-amb-fail amb-fail)

(+results '()))

(if (call/cc

(lambda (+k)

(set! amb-fail (lambda () (+k #f)))

(let ((+v ,e))

(set! +results (cons +v +results))

(+k #t))))

(amb-fail))

(set! amb-fail +prev-amb-fail)

(reverse! +results))))

ראשית, bag-of שומר את הכניסה שלו amb-fail. הוא מגדיר מחדש את amb-fail להמשך מקומי k+ הנוצר בעזרת בדיקת if. בתוך הבדיקה, הארגומנט e של bag-of מוערך. אם e מצליח - תוצאתו נאספת לרשימה הנקראת results+, וההמשך המקומי נקרא עם הערך t#. זה גורם למשפט ה-if להצליח, תוך כדי ש-e מנסה שנית בנקודת הנסיגה הבאה. כך מושגות תוצאות נוספות עבור e בדרך זו, וכולן נאספות לתוך results+. לבסוף, כש-e נכשל, תתבצע קריאה ל-amb-fail הבסיסי, שזו בעצם קריאה פשוטה להמשך המקומי עם הערך f#. זה דוחף את השליטה אחרי ה-if. נחזיר את amb-fail לערך שהיה לו קודם הכניסה, ונחזיר את results+. (ה-!reverse הוא פשוט כדי להפיק את התוצאות באותו סדר בו הן יוצרו).

14.4 בעיות לוגיות

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

14.4.1 בעיית קלוטן (kalotan)

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

קבע מהו המין של ההורים ושל קיבי.

הפתרון כולל הצגת קבוצת משתנים, השמת ערכי החלטות בתוכם ומניית המצבים שייתכנו כסדרה של ביטויי assert.
המשתנים: parent1 ,parent2 ו-kibi הם מין ההורים (לפי סדר הופעתם) ומינו של קיבי. kibi-self-desc הוא המין שקיבי טוען שהוא משתייך אליו (בקלוטנית).
?kibi-lied הוא משתנה בוליאני שאומר אם טענת קיבי לגבי מינו היתה שקר.

(define solve-kalotan-puzzle

(lambda ()

(let ((parent1 (amb 'm 'f))

(parent2 (amb 'm 'f))

(kibi (amb 'm 'f))

(kibi-self-desc (amb 'm 'f))

(kibi-lied? (amb #t #f)))

(assert

(distinct? (list parent1 parent2)))

(assert

(if (eqv? kibi 'm)

(not kibi-lied?)))

(assert

(if kibi-lied?

(xor

(and (eqv? kibi-self-desc 'm)

(eqv? kibi 'f))

(and (eqv? kibi-self-desc 'f)

(eqv? kibi 'm)))))

(assert

(if (not kibi-lied?)

(xor

(and (eqv? kibi-self-desc 'm)

(eqv? kibi 'm))

(and (eqv? kibi-self-desc 'f)

(eqv? kibi 'f)))))

(assert

(if (eqv? parent1 'm)

(and

(eqv? kibi-self-desc 'm)

(xor

(and (eqv? kibi 'f)

(eqv? kibi-lied? #f))

(and (eqv? kibi 'm)

(eqv? kibi-lied? #t))))))

(assert

(if (eqv? parent1 'f)

(and

(eqv? kibi 'f)

(eqv? kibi-lied? #t))))

(list parent1 parent2 kibi))))

הערה לגבי פרוצדורות העזר: הפרוצדורה ?distinct מחזירה אמת אם כל האלמנטים ברשימת הארגומנטים שלה נבדלים, ושקר אחרת. הפרוצדורה xor מחזירה אמת אם רק אחד משני הארגומנטים שלה ערכו אמת ,ושקר אחרת.
הקלדת (solve-kalotan-puzzle) אכן תפתור את הבעייה.

14.4.2 צביעת מפה

במשך זמן מה היה ידוע הדבר (למרות שרק הוכח לאחרונה), שארבעה צבעים מספיקים לצבוע מפה יבשתית - כלומר, לצבוע את המדינות כך שנוכל להבחין בין שתי מדינות שכנות. הקצאת הצבעים ,למעשה, היא עדיין משימה לא קלה והתכנית הבאה מראה איך תכנות אי-דטרמיניסטי יכול לעזור.
התכנית הבאה פותרת את בעיית צביעת מפה של אירופה המערבית. הבעיה והפתרון ב-prolog מוצגים ב-The art of prolog .(מאלף יהיה להשוות את פתרונינו עם הפתרון בספר).
הפרוצדורה choose-color מחזירה באופן אי-דטרמיניסטי אחד מארבעה צבעים:

(define choose-color

(lambda ()

(amb 'red 'yellow 'blue 'white)))

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

(list 'belgium b (list f h l g ))

כיוון שלפי הצהרות בעיה זו - השכנות של בלגיה הן צרפת (f), הולנד (h), לוקסמבורג (l), וגרמניה (g).
ברגע שיצרנו רשימות לכל מדינה, אנו מבטאים את התנאי (היחיד!) שעליהן לקיים, דהיינו, שלשום מדינה לא יהיה צבע כמו שכנותיה. במילים אחרות, עבור כל מדינה, אסור לאלמנט השני להיות חבר ברשימה של האלמנט השלישי.

(define color-europe

(lambda ()

;choose colors for each country

(let ((p (choose-color)) ;Portugal

(e (choose-color)) ;Spain

(f (choose-color)) ;France

(b (choose-color)) ;Belgium

(h (choose-color)) ;Holland

(g (choose-color)) ;Germany

(l (choose-color)) ;Luxemb

(i (choose-color)) ;Italy

(s (choose-color)) ;Switz

(a (choose-color)) ;Austria

)

;construct the adjacency list for

;each country: the 1st element is

;the name of the country; the 2nd

;element is its color; the 3rd

;element is the list of its

;neighbors' colors

(let ((portugal

(list 'portugal p

(list e)))

(spain

(list 'spain e

(list f p)))

(france

(list 'france f

(list e i s b g l)))

(belgium

(list 'belgium b

(list f h l g)))

(holland

(list 'holland h

(list b g)))

(germany

(list 'germany g

(list f a s h b l)))

(luxembourg

(list 'luxembourg l

(list f b g)))

(italy

(list 'italy i

(list f a s)))

(switzerland

(list 'switzerland s

(list f i a g)))

(austria

(list 'austria a

(list i s g))))

(let ((countries

(list portugal spain

france belgium

holland germany

luxembourg

italy switzerland

austria)))

;the color of a country

;should not be the color of

;any of its neighbors

(for-each

(lambda (c)

(assert

(not (memq (cadr c)

(caddr c)))))

countries)

;output the color

;assignment

(for-each

(lambda (c)

(display (car c))

(display " ")

(display (cadr c))

(newline))

countries))))))

נשלח ב-27/7/2011 17:29

פרק 15 - מנועים

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

שלושת הארגומנטים שעמם קוראים למנוע הם:

מספר של יחידות זמן או ticks.
פרוצדורה שמצליחה.
פרוצדורה שנכשלת.

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

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

(define printn-engine

   (make-engine

           (lambda ()

               (let loop ((i 0))

                    (display i)

                    (display " ")

                    (loop (+ i 1))))))

כעת, נקרא לפרוצדורה printn-engine:

(define *more* #f)

(printn-engine 50 list (lambda (ne) (set! *more* ne)))

=> 0 1 2 3 4 5 6 7 8 9

כלומר הלולאה מדפיסה מספר מוגדר (במקרה שלנו 9) ואח"כ נכשלת בגלל פסיקת השעון. אך הפרוצדורה שנכשלת קובעת משתנה גלובלי הנקרא *more* למנוע שנכשל, שאתו אנו יכולים לחדש את הלולאה שהמנוע הקודם השאיר:

(*more* 50 list (lambda (ne) (set! *more* ne)))

=> 10 11 12 13 14 15 16 17 18 19

כעת אנו נבנה את המנוע בעזרת call/cc כדי ללכוד את החישוב של המנוע הכושל.
בהתחלה נבנה מנועים שטוחים או מנועים שהחישוב שלהם לא כולל ריצה של מנועים אחרים. אח"כ נכליל את הקוד למנועים מקוננים אשר יכולים לקרוא למנועים אחרים. אבל בכל המקרים נצטרך שעון.

15.1 השעון

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

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

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

השעון מאפשר את הפעולות הבאות:

(clock 'set-handler h) - מעדכנת את מטפל הפסיקות ל-h.
(clock 'set n) - מאתחלת את יחידות הזמן שנותרו ל-n ומחזירה את הערך הקודם.

הטווח של מספר חידות הזמן במספרים שלמים לא שליליים ובאטומים נקרא *infinity*. שעון עם אינסוף יחידות זמן לא יכול להסתיים ולכן לא נקרא למטפל הפסיקות. שעון זה נחשב כבר ל"מופסק" תנועה. כדי להפסיק שעון צריך לקבוע את יחידות הזמן שלו ל-*infinity*.

מטפל השעון נקבע ל-thunk לדוגמא,

(clock 'set-handler

 (lambda ()

    (error "Say goodnight, cat!")))

(clock 'set 9)

זה יגרום לטעות לאחר 9 יחידות זמן והמסר שיוצג ע"י הסיגנל יהיה : "!Say goodnight, cat".

15.2 מנועים שטוחים

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

(define *engine-escape* #f)

(define *engine-entrance* #f)

(clock 'set-handler

    (lambda ()

         (call/cc *engine-escape*)))

כעת נסתכל בקוד של המנוע עצמו. כמו שנאמר make-engine לוקח thunk ומחזיר מנוע מתאים:

(define make-engine

  (lambda (th)

    (lambda (ticks success failure)

      (let* ((ticks-left 0)

             (engine-succeeded? #f)

             (result

              (call/cc

               (lambda (k)

                 (set! *engine-escape* k)

                 (let ((result

                        (call/cc

                         (lambda (k)

                           (set! *engine-entrance* k)

                           (clock 'set ticks)

                           (let ((v (th)))

                             (*engine-entrance* v))))))

                   (set! ticks-left (clock 'set *infinity*))

                   (set! engine-succeeded? #t)

                   result)))))

        (if engine-succeeded?

            (success result ticks-left)

            (failure

             (make-engine

              (lambda ()

                (result 'resume)))))))))

בהתחלה נכיר את המשתנים ticks-left ו-?engine-succeeded. המשתנה הראשון יחזיק את יחידות הזמן שנשארו כדי שהמנוע יסיים בזמן. המשתנה השני הוא הדגל שיסמן אם המנוע הצליח .

לאחר מכן אנו נריץ את המנוע בתוך שתי קריאות מקוננות של call/cc. הקריאה הראשונה של call/cc לוכדת את ההמשך שישתמשו בו ע"י המנוע שנכשל כדי לנטוש את החישוב של המנוע.
ההמשך מאוחסן במשתנה הגלובלי *engine-escape*. הקריאה השניה של ה-call/cc לוכדת את ההמשך הפנימי שישתמשו בו ע"י הערך המוחזר של ה-th thunk אם הוא רץ לקראת סיום. ההמשך הזה מאוחסן במשתנה הגלובלי *engine-entrance*.

בהמשך הקוד אנו רואים שאחרי לכידת ההמשכים *engine-escape* ו-*engine-entrance*, אנו קובעים את יחידות הזמן של השעון לזמן מוגבל ומריצים את ה-th thunk. אם ה-th מצליח הערך שלו v ישלח להמשך *engine-entrance*. לאחר שהשעון פסק, מבררים מהו הזמן שנותר, והדגל ?engine-succeeded נקבע ל-true.
כעת אנו עוברים על פני ההמשך *engine-escape* ומריצים את המשגר הסופי של הקוד, מכיוון שאנו יודעים שהמנוע הצליח אנו מיישמים את הפרוצדורה שמצליחה ויחידות הזמן נשארות.

אם ה-th thunk לא מסתיים, תתרחש פסיקה. זה יקרא למטפל הפסיקות אשר לוכד את ההמשך העכשווי של ה-thunk ושולח אותו להמשך *engine-escape*. זה מניח את ה-thunk שנכשל במשתנה חיצוני result. כעת אנו נמצאים בחלק הסופי של המשגר. מכיוון ש-?engine-succeeded עדיין false אנו מיישמים את הפרוצדורה שנכשלת למנוע חדש שנעשה מחוץ ל-result.

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

15.3 מנועים מקוננים

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

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

אנו צריכים לבצע fluid-let על המשתנים הגלובליים *engine-escape* ו-*engine-entrance* מכיוון שכל מנוע זקוק לזוג ההמשכים הללו. כאשר מנוע מסתיים (בכישלון או בהצלחה) ה-fluid-let יבטיח שהמנוע הבא ישתלט.

בשילוב כל הנאמר למעלה, הקוד למנועים מקוננים הוא :

(define make-engine

 (lambda (th)

    (lambda (ticks s f)

      (let* ((parent-ticks

              (clock 'set *infinity*))

             ;A child can't have more ticks than its parent's

             ;remaining ticks

             (child-available-ticks

              (clock-min parent-ticks ticks))

             ;A child's ticks must be counted against the parent

             ;too

             (parent-ticks-left

              (clock-minus parent-ticks child-available-ticks))

             ;If child was promised more ticks than parent could

             ;afford, remember how much it was short-changed by

             (child-ticks-left

              (clock-minus ticks child-available-ticks))

             ;Used below to store ticks left in clock

             ;if child completes in time

             (ticks-left 0)

             (engine-succeeded? #f)

             (result

              (fluid-let ((*engine-escape* #f)

                          (*engine-entrance* #f))

                (call/cc

                 (lambda (k)

                   (set! *engine-escape* k)

                   (let ((result

                          (call/cc

                           (lambda (k)

                             (set! *engine-entrance* k)

                             (clock 'set child-available-ticks)

                             (let ((v (th)))

                               (*engine-entrance* v))))))

                     (set! ticks-left

                       (let ((n (clock 'set *infinity*)))

                         (if (eqv? n *infinity*) 0 n)))

                     (set! engine-succeeded? #t)

                     result))))))

        ;Parent can reclaim ticks that child didn't need

        (set! parent-ticks-left

          (clock-plus parent-ticks-left ticks-left))

        ;This is the true ticks that child has left --

        ;we include the ticks it was short-changed by

        (set! ticks-left

          (clock-plus child-ticks-left ticks-left))

        ;Restart parent with its remaining ticks

        (clock 'set parent-ticks-left)

        ;The rest is now parent computation

        (cond

         ;Child finished in time -- celebrate its success

         (engine-succeeded? (s result ticks-left))

         ;Child failed because it ran out of promised time --

         ;call failure procedure

         ((= ticks-left 0)

          (f (make-engine (lambda () (result 'resume)))))

         ;Child failed because parent didn't have enough time,

         ;ie, parent failed too. If so, when parent is

         ;resumed, its first order of duty is to resume the

         ;child with its fair amount of ticks

         (else

          ((make-engine (lambda () (result 'resume)))

           ticks-left s f)))))))

יש לשים לב שהשתמשנו באופרטורים clock-minus ,clock-min ו-clock-plus במקום min, - ו-+. זאת מכיוון שהערכים שהשעון השתמש בהם כללו את *infinity* בנוסף למספרים השלמים. חלק מהניבים של Scheme מספקים את הערך *infinity* ואז ניתן להשתמש באופרטורים האריתמטיים הרגילים. במידה ולא זה יהיה תרגיל נחמד להגדיר את האופרטורים המשוכללים הנ"ל .

לדוגמא - ב-Guile ניתן להגדיר:

((define *infinity* (/ 1 0).

בית >

פורומים >

אינטרנט ומחשבים >

למתכנתים שבינינו >

שפת SCHEME

מנהל לחץ כאן לנעילת האשכול

1 2

סך הכל 2 דפים.

שאלות ותשובות ·תנאי שימוש והצהרת פרטיות ·נגישות ·פרסמו אצלנו

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