Engine in Scheme

Engine(引擎)是支持时间抢占 的高级抽象过程, 它可被用于模拟多任务处理、实现操作系统内核和非确定性计算。

(make-engine thunk)

通过传递一个无参数的thunk(形实转换程序)给make-engine来创建一个engine。thunk的body是会被engine执行的计算,engine本身是带3个参数的过程:

  • ticks: 一个正整数,指定提供给engine的执行时间片(原文用的是fuel这个单词,意思是燃料,正对应这engine的本意,十分贴切)的数量,engine将会执行到时间片用完或者计算完成为止;
  • complete: 一个或多个参数的函数,用于指定计算完成后的操作。它的参数是剩余的时间片数量和计算产生的值;
  • expire: 一个参数的函数,该函数指定如果在计算完成之前时间片用完了该怎么办。它的参数是一个能从中断点继续进行计算的新引擎。

将引擎应用于其参数时,它将开启一个时长为ticks的计时器,如果引擎计算在计时器执行之前完成,系统将调用complete,并将剩余的ticks和计算产生的值传递给它;

另一方面,如果计时器在引擎计算完成之前耗尽了,则系统会从中断计算的continuation中创建一个新引擎,并使该引擎过期。complete和expire会被新引擎继续使用。If, on the other hand, the timer goes off before the engine computation completes, the system creates a new engine from the continuation of the in- terrupted computation and passes this engine to expire. complete and expire are invoked in the continuation of the engine invocation.


看看具体的例子:

(define eng
  (make-engine
    (lambda () 3)))

(eng
	10  ;; ticks
	(lambda (ticks value) value)  ;; complete
	(lambda (x) x)  ;; expire
)  3

通常将列表作为完整过程传递给引擎,使引擎完成时返回一个列表,该列表的第一个元素是剩余的ticks,另一个元素是计算返回的值,这通常很有用。

(define eng
  (make-engine
    (lambda () 3)))

(eng 10 list
	(lambda (x) x))  (9 3)

在上面的示例中,计算值为3,还剩下9个时间片,即,需要一单位的时间片来计算出3。


再看一个复杂点的例子: 先定义一个计算裴波那切值的函数

(define fibonacci
  (lambda (n)
    (let fib ([i n])
      (cond
        [(= i 0) 0]
        [(= i 1) 1]
        [else (+ (fib (- i 1))
                 (fib (- i 2)))]))))

创建engine

(define eng
  (make-engine
    (lambda ()
      (fibonacci 10))))
(eng 50 list
	(lambda (new-eng)
	(set! eng new-eng) "expired"))  "expired"
(eng 50 list
	(lambda (new-eng)
	(set! eng new-eng) "expired"))  "expired"
(eng 50 list
	(lambda (new-eng)
	(set! eng new-eng) "expired"))  "expired"
(eng 50 list
	(lambda (new-eng)
	(set! eng new-eng) "expired"))  (21 55)

每次时间片(燃料)用完时,到期程序都会将eng分配给新引擎。整个计算需要4个blocks,每个block包含50个ticks。最后50个燃料中,有21个都用掉了。因此,使用的燃料总量为179个。

我们还可以统计一下消耗的ticks数量

(define mileage
  (lambda (thunk)
    (let loop ([eng (make-engine thunk)] [total-ticks 0])
      (eng 50
           (lambda (ticks . values)
             (+ total-ticks (- 50 ticks)))
           (lambda (new-eng)
             (loop new-eng
      (+ total-ticks 50)))))))
(mileage (lambda () (fibonacci 10)))  179

再看看一个例子——round-robin:

(define round-robin
  (lambda (engs)
    (if (null? engs)
        '()
        ((car engs)
			1 ;;ticks
			(lambda (ticks value) (cons value (round-robin (cdr engs)))) ;;complete
			(lambda (eng) ;;expire
				(round-robin
					(append (cdr engs) (list eng))))))))


(round-robin
  (map (lambda (x)
         (make-engine
           (lambda () (fibonacci x))))
  '(4 5 2 8 3 7 6 2)))  (1 1 2 3 5 8 13 21)

这段代码需要费些思量,首先map函数创建了8个engine, 然后代入round-robin函数,该函数依次执行各个engine,但是每个engine分配的时间片只有1,对于参数’(4 5 2 8 3 7 6 2),数字越小,越先执行完成,所以越早执行complete函数,最终结果就是排好顺序的了,很棒的程序!