אתר ללימוד מקיף> פרק 13 - Jumps

פרק 13 - Jumps

הנושאים בפרק זה:
13.1.     call-with-current-continuation
13.2.     Escaping continuations
13.3.     Tree matching
13.4.     Coroutines
            13.4.1. Tree matching עם Coroutines

אחד היתרונות של 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 ).