אתר ללימוד מקיף> פרק 15 - מנועים

פרק 15 - מנועים

הנושאים בפרק זה:
15.1.     השעון
15.2.     מנועים שטוחים
15.3.     מנועים מקוונים

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

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

מספר של יחידות זמן או 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).