第十五章 引擎 ============== 引擎表示服從時間搶占的運算過程。換句話說，一個引擎下面的運算過程是普通的程序作為定時器可搶占的進程。 一個引擎用三個參數來調用： 1. 分配時間片（運行時間單元）的數目 2. 成功過程 3. 失敗過程 如果引擎的計算在分配的時間片內完成了，那么就把計算的結果作為參數來調用成功過程，如果沒有計算完成，那么把未計算完的部分作為參數來調用失敗過程。 比如，考慮一個引擎，其下的運算是一個循環，該循環打印非負整數的序列。該引擎用下面的`make-engine`過程（后面會定義該過程）創建，`make-engine`接受一個程序（即該引擎下面的計算過程）為參數，并返回對應的引擎。 ```scheme (define printn-engine (make-engine (lambda () (let loop ((i 0)) (display i) (display " ") (loop (+ i 1)))))) ``` 下面調用`pritn-engine`： ```scheme (define *more* #f) (printn-engine 50 list (lambda (ne) (set! *more* ne))) => 0 1 2 3 4 5 6 7 8 9 ``` 也就是循環打印到某個特定的數（這里是`9`）然后就失敗(fail)了，因為時鐘中斷了。然而，我們定義的失敗過程把fail掉的引擎賦值給了全局變量`*more*`。這樣我們就可以從上個引擎中斷的地方恢復： ```scheme (*more* 50 list (lambda (ne) (set! *more* ne))) => 10 11 12 13 14 15 16 17 18 19 ``` 我們現在來構建引擎，使用`call/cc`來捕獲一個失敗引擎未完成的計算。首先我們會構造一個flat引擎，也就是說該引擎的計算中不能運行其他引擎。稍后我們會讓代碼更通用，實現nestable引擎，這樣的引擎可以調用其他引擎。但是不管那種引擎，我們都需要一個定時的東西，時鐘（clock）。 ## 15.1 時鐘 我們的引擎假設有一個全局的時鐘或可中斷的定時器來記錄程序運行的時間片。我們假設下面的時鐘接口——你通常應該很容易把Scheme提供的時鐘接口（如果有的話）打包成下面這種類型。（附錄D用Scheme的Guile方言定義了一個時鐘） 我們的`clock`過程的內部狀態包括以下兩項： 1. 剩余的時間片的數目，以及 2. 一個中斷處理器(handler)，當時鐘的時間片用完了的時候被調用。 `clock`允許下面的操作： 1. `(clock 'set?handler h)`設置中斷處理器為`h`。 2. `(clock 'set n)`把時鐘的剩余時間片重置為`n`，返回之前的值。 `n`的取值范圍是所有非負整數以及一個叫`*infinity*`的原子。一個時鐘如果有`*infinity*`的時間片永遠不會終止，所以也用不著設置中斷處理器。這樣的時鐘總是“靜止的”或“停止的”（定時器的工作就是：減到0并中斷，而這樣的時鐘永遠不會減到0并中斷，所以處于“非工作”狀態）。讓一個時鐘停止只要把時間片設為`*infinity*`即可。 時鐘的處理器被設置為一個程序，比如： ```scheme (clock 'set-handler (lambda () (error "Say goodnight, cat!"))) (clock 'set 9) ``` 這樣`9`個時間片過去后會產生一個錯誤，并且顯示的錯誤信息是`"Say goodnight, cat!"` ## 15.2 flat引擎 我們將首先設置時鐘的中斷處理器。注意這個處理器只有在“工作”狀態的時鐘用完時間片后才會被調用。這只有引擎計算失敗時才發生，因為只有引擎設置時鐘。 處理器捕獲當前的續延，也就是當前失敗引擎的剩余計算部分。這個續延被保存到全局的`*engine-escape*`變量中。該變量存放當前引擎的續延。因此時鐘處理器捕獲失敗引擎的剩余部分并把它發送到引擎代碼的出口。這樣所需的失敗處理才能執行。 ```scheme (define *engine-escape* #f) (define *engine-entrance* #f) (clock 'set-handler (lambda () (call/cc *engine-escape*))) ``` 讓我們來看一下引擎代碼的內部。如上所述，`make-engine`接受一個程序并為之構造一個引擎： ```scheme (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`的返回值使用，如果`th`完成了的話。這個續延保存在全局的`*engine-entrance*`變量中。 查看上面的代碼，我們能發現在捕獲續延`*engine-escape*`和`*engine-entrance*`后，我們設置時鐘的時間片為允許允許的時間并運行`th`。如果`th`成功了，其返回值`v`被發送到續延`*engine-escape*`，然后時鐘就停止了，剩下的時間片的數量就確定了，并且標記`engine-succeeded?`被設置為真。我們現在略過(?)`*engine-escape*`續延，并執行最后一段選擇語句：由于我們知道引擎成功了，我們以執行結果和剩余的時間片為參數調用`success`過程。 如果程序`th`沒能在制定時間完成，就會被中斷。這會調用時鐘的中斷處理器，來捕獲當前失敗程序的續延，并把它傳給`*engine-escape*`變量。這樣就把`result`變量設置為失敗任務的續延，我們現在執行最后一個`if`語句，由于`engine-succeeded?`是`false`，我們以`result`構造一個新引擎并作為參數調用`failure`過程。 注意當一個失敗的引擎被移除時，it will traverse the control path charted by the first run of the original engine.盡管如此，因為我們總是顯式的使用保存在`*engine-entrance*`和`*engine-escape*`變量中的續延，而且我們總是在開啟引擎計算前重新設置它們，我們能保證跳轉總是會到當前執行的引擎代碼。 ## 15.3 交疊(nestable)的引擎 為了讓上面的代碼更通用化，適應交疊的引擎，我們需要引入一些時間片管理的機制，來為交疊運行的所有引擎管理正確的時間片。 為了跑一個新引擎（子引擎），我們需要停止當前引擎（父引擎）。然后需要給子引擎分配適當的時間。這可不是直接在程序代碼里設置那樣，因為給子引擎分配比父引擎剩下的時間片更多的時間片是不對的。在子引擎跑完后我們還得更新父引擎剩余的時間片。如果子引擎在給定時間內跑完，所有它剩下的時間片都還給父引擎。如果子引擎要求的時間片被拒絕（因為父引擎的剩余時間片都無法滿足），那么如果子引擎失敗了，父引擎也會失敗，但是必須記得在重啟父引擎時也重啟子引擎，其時間片仍然是之前需要的那些。 我們需要用`fluid-let`來聲明全局的`*engine-escape*`和`*engine-entrance*`變量，因為每個引擎都必須有它自己的這兩個做控制用的續延。當引擎退出時（不論是成功還是失敗），`fluid-let`會保證其外層引擎會接管這個控制(sentinel)。 考慮到以上這些，可交疊引擎的代碼應該像下面這樣： ```scheme (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-min`，`clock-minus`和`clock-plus`替代了`min`，`-`和`+`。這是因為時鐘算術的值除了整數之外還包含`*infinity*`。有些Scheme的方言在它們的算術運算中提供了`*infinity*`的值——如果這樣的話，你就可以用這些通用的算術運算符了。如果沒有的話，定義這幾個增強運算符也是很簡單的事情。 -------------------------- 1. 在Guile中，你可以`(define *infinity* (/ 1 0))`。