エンジン[cite{engine}]は時分割プリエンプションに従う計算を 表現するものです。別の言葉でいうと、エンジンを構成する計算 は時分割プリエンプションが可能なプロセスとして走る通常の サンクです。
エンジンは次の 3 つの引数とともに呼ばれます。(1) 時分割の単位数あるいは クロック数、(2) 成功手続き、(3) 失敗手続き。 エンジンの計算が割り当てられたクロック数 以内で終了すれば、 成功手続きが、計算結果と残りのクロック数に適用されます。 エンジンの計算が割り当てられたクロック数以内に終了しなかった 場合には、失敗手続きが、エンジンの計算の未終了部分を表現 する新しいエンジンに適用されます。
例として、一連の非負の整数を印字するループの計算を構成するエンジン
を考えてみましょう。あとですぐに定義する 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 を使って、失敗するエンジンの未終了計算を
捕捉することでエンジンを構築しましょう。まず、フラットな
エンジン、あるいは、その計算が他のエンジンを走らせることが
ないようなエンジンを作ります。そのあとで、このコードを
一般化して、もっと一般的に入れ子可能なエンジン、あるいは、
ネスタを作ります。これは他のエンジンを呼ぶことができるものです。
しかし、いずれの場合にもタイマ機構あるいはクロックというものが
必要です。
ここでのエンジンは、プログラム実行の時刻経過を刻む、グローバルクロック あるいは割り込み可能なタイマがあることを仮定しています。ここでは、以下 のようなクロックインタフェースがあることを仮定しましょう。 もし、お使いの Scheme が何らかのアラーム機構を提供していれば、 以下のようなタイプのクロックを間に合わせにつくるのは容易いことです。 (付録 D では Scheme の Guile [cite{guile}] 方言用のクロックを 定義しています。)
ここでの clock 手続きの初期状態はふたつの項目から構成されます。
(1) 残りのクロック数
(2) クロック数を使い果したときに呼び出される割り込みハンドラ
clock は以下のオペレーションを可能にします。
(1) (clock 'set-handler h) は割り込みハンドラを h に設定する。
(2) (clock 'set n) はクロックに残りのクロック数を n に設定し、
以前の値を返す。
クロック数のとりうる範囲は非負整数と *infinity* とよばれるアトム
です。*infinity*クロック数をもつクロックはクロック数を使い果す
ことはなく割り込みハンドラをセットすることはありません。このような
クロックは静止あるいは「すでに止っている」といいます。
クロックを止めるには、そのクロック数を *infinity* にセットします。
クロックハンドラはサンクにセットされています。たとえば、
(clock 'set-handler (lambda () (error "Say goodnight, cat!"))) (clock 'set 9)
これは 9 クロック経過後エラーシグナルをあげます。そして そのシグナルにより、「Say goodnight, cat!」というメッセージが 表示されます。
まず最初にクロックに割り込みハンドラをセットします。 このハンドラは、非静止クロックがクロック数を使い果したときにのみ 呼び出されることに注意してください。割り込みハンドラの呼び出しは エンジンの計算が失敗する直前で、クロック数が設定された エンジンに対してのみにしか起りません。
このハンドラは、現在の継続を捕捉します。つまり、現時点で
エンジンを失敗させる残りの計算です。この継続はグローバル
変数 *engine-escape* に格納されている別の継続に送られます。
*engine-escape* 変数は、現在のエンジンの脱出継続を格納しています。
したがって、このクロックハンドラは失敗エンジンの残りを捕捉し、
それをそのエンジンのコードの脱出ポイントに送ります。そうすると
必須の失敗アクションに到達できます。
(define *engine-escape* #f) (define *engine-entrance* #f) (clock 'set-handler (lambda () (call/cc *engine-escape*)))
さて、いよいよ、エンジンのコードの内部に踏み込んでみていきましょう。
以前言いましたように、make-engine はサンクをとり、それから
エンジンを構築します。
(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 の返り値によって
使われるものです。この継続はグローバル変数 *engine-entrance* に
格納されます。
このコードを実行していくと、継続を *engine-escape* と
*engine-entrance* に捕捉したあとで、クロックのクロック数を
このエンジンに割り当てた時間分にセットして、サンク th を
走らせます。th が成功すれば、その値 v が継続
*engine-entrance* に送られ、クロックが停止したのち、
残りのクロック数を確認し、フラグ eingine-succeeded? を
真にセットします。ここで、渡された*engine-escape* 継続に
行きます。そして、コード中の最終のディスパッチャを走らせます。
すでに、エンジンが成功しているのが判っているので、
success 手続きを結果に適用し、クロック数を残します。
サンク th が時間どおり終了しなかったとしても、
割り込みを受けます。この割り込みはクロック割り込みハンドラを
起動し、これが動作中で今失敗したサンクの現在の継続を捕捉し、
それを、継続 *engine-escape* に送ります。これにより、
失敗したサンク継続が、外側の変数 result に置かれます。
そうすると、このとき、コード中の最終ディスパッチャの中に
いることになります。engine-succeeded? はまだ偽ですから、
failure 手続きを result から作られた新しいエンジンに
適用します。
失敗したエンジンが取り除かれるときに、元のエンジンの最初の
駆動によって引かれた制御パスを辿るということに注意してください。
それにもかかわらず、グローバル変数 *engine-entrance* および
*engine-escape* に格納された継続を明示的に使用し、
エンジン継続を実行するまえに常にそれらを新しく設定しているので、
ジャンプはつねに現在実行中のコードにもどると仮定しています。
上のコードを一般化して入れ子可能なエンジンにするには、 入れ子で動作している、すべてのエンジンに正しい数の クロック数を割り当てるクロック数管理を組み込む 必要があります。
新しいエンジン(子エンジン)を走らせるには現時点でのエンジン (親エンジン)を停止させる必要があります。そして、適切な数の クロック数を子エンジンに割り振る必要があります。これは プログラムの教科書にはるようなクロック数の割り当てとは 同じにはなりません。それは、親エンジンが残しているクロック数 よりも多いクロック数を消費する子エンジンに対しては、 不平等になるからです。子エンジンが完了したあと、 親エンジンのクロック数を更新しなければなりません。子エンジンが 時間内に終了したら、残りのクロック数は親に戻されます。 親エンジンに余裕がなく、子エンジンにクロック数を渡せない場合には 子エンジンは失敗し、親エンジンも失敗します。しかし、親エンジンが 再スタートしたときには、約束のクロック数を持って子エンジンを 再スタートすることを覚えていなければなりません。
また、グローバル変数 *engine-escape* と *engine-entrance*
に fluid-let を使う必要があります。それは入れ子になったそれぞれの
エンジンはそれぞれの番兵継続の対を持っていなければならないからです。
エンジンが存在する場合(それが、成功エンジンであろうと、失敗エンジンで
あろうと)、fluid-let は必ず、次の取り囲むエンジンの番兵が引き継げ
るようにします。
これらを全部組み合わせると、入れ子可能なエンジンのコードは 以下のようになります。
(define make-engine (lambda (th) (lambda (ticks s f) (let* ((parent-ticks (clock 'set *infinity*)) ;子エンジンは親エンジンの残りのクロック数を超える ;クロック数をもつことはできない (child-available-ticks (clock-min parent-ticks ticks)) ;子エンジンのクロック数カウントは親エンジンについても ;カウントされる (parent-ticks-left (clock-minus parent-ticks child-available-ticks)) ;子エンジンへの割り当て予定のクロック数が親エンジンの 残りクロック数より大きいときには、足りない数を記憶する (child-ticks-left (clock-minus ticks child-available-ticks)) ;子エンジンが時間内で完了したら、以下をつかってクロックに ;その残りのクロック数を格納する (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)))))) ;親エンジンは子エンジンで必要なかったクロック数の返還要求ができる (set! parent-ticks-left (clock-plus parent-ticks-left ticks-left)) ;これは、子エンジンが残した本当のクロック数で ;これは short-changed の分も勘定にいれてある (set! ticks-left (clock-plus child-ticks-left ticks-left)) ;のこりのクロック数をもって、親エンジンを再スタートする (clock 'set parent-ticks-left) ;この時点でのこりは、親エンジンの計算である (cond ;子エンジンが時間内に終了した -- 成功したお祝いをする (engine-succeeded? (s result ticks-left)) ;子エンジンが割り当て予定の時間を使い果し失敗した -- ;失敗手続きを呼ぶ ((= ticks-left 0) (f (make-engine (lambda () (result 'resume))))) ;親エンジンが十分な時間を持っていなかったために子エンジンが失敗 ;それで、親エンジンも失敗した ;そうなら、親エンジンが再起動したとき最初にすべきことは ;子エンジンを同じクロック数で再起動すること (else ((make-engine (lambda () (result 'resume))) ticks-left s f)))))))
算術演算子として min、-、+ の代りに qclock-min、
clock-minus、clock-plus を使っていることに注意してください。
これは、クロック数演算で使われている値には、整数以外に、
*infinity* が含まれているからです。いくつかの Scheme 方言
算術演算に *infinity* が含まれています1。その場合は
通常の算術演算子を使うことができます。さもなければ、拡張演算子を
定義することは簡単な練習問題としておきます。
1 たとえば、Guile では
(define *infinity* (/ 1 0)) とすることができます