やろーじだい

ブログです

継続を用いた割り込み処理の実装 (のための継続の学習)

やりたいこと

 sleep などで入力した値だけ処理を停止させておきながら、キーボードが入力された時にそれを見て、それによって停止を中断したりするような割り込みのような処理をしたい。継続使えそうじゃないかと思ったので gauche で実装を試みた。

読む人の時間を奪わないためにまず結論

 最終的に、継続を使う以前に、sleep している処理と並列してキーボード入力を監視、ある入力を受け取ったら sleep から抜けるという方法はわからなかったが、I/O (今回はキーボード入力) に対してタイムアウトを実装すれば間接的に n 秒 sleep しつつ、入力を待つということが実装できることに気付いた。その点でググったら都合良く gauche を使って実装している例があったので解決した。長時間かかる処理にタイムアウトをつける

 継続についての理解が進んだので良かった。最終的に、最初に引数 n を渡して継続を利用した関数を作りそれを呼び出す度に毎回 1 秒スリープして n 回呼び出したら以降は sleep しないような関数、というものを作成したところで解決策がみつかったので終了した。

 以下は継続を勉強した時のメモになる。

継続

 以前から継続という概念については読んだりしていたが、実際に使用して何かをしたこともなく理解しているのかわからないのでまず継続について学びなおした。

まず適当に検索して見つけたページを読んだ。 なんでも継続

処理をひとつづきのパイプのようなものだと考えて、 どこでも良いがどこかをすぱっと切ってみる。その切り口の下側が上側の継続である(図3)。

概念の説明としてはここが一番しっくりきた。

 [末尾再帰と継続]で使われている木の葉の数を数えるプログラムを見てみる。

(define (leaf-count/cps tree cont)
  (if (pair? tree)
      (leaf-count/cps (car tree)
        (lambda (n)
          (leaf-count/cps (cdr tree)
            (lambda (m) (cont (+ n m))))))
      (cont 1)))

(define tree '((a . b) (c . d) . e))

gosh> (leaf-count/cps tree values)
5

(values は多値を返すための関数)

上のプログラムがパッと見難しいので順を追って評価した。lambda 式内で入れ子に表れる nm については区別のために便宜上 - を付与した。

(leaf-count/cps '((a . b) (c . d) . e) values)

;; ↓

(let ((tree '((a . b) (c . d) . e))
      (cont values))
  (leaf-count/cps (car tree)
                  (lambda (n)
                    (leaf-count/cps (cdr tree)
                                    (lambda (m)
                                      (cont (+ n m)))))))

;; ↓

(leaf-count/cps '(a . b)
                (lambda (n)
                  (leaf-count/cps '((c . d) . e)
                                  (lambda (m)
                                    (values (+ n m))))))

;; ↓

(let ((tree '(a . b))
      (cont (lambda (n)
              (leaf-count/cps '((c . d) . e)
                              (lambda (m)
                                (values (+ n m)))))))
  (leaf-count/cps (car tree)
                  (lambda (n-)
                    (leaf-count/cps (cdr tree)
                                    (lambda (m-)
                                      (cont (+ n- m-)))))))

;; ↓

(leaf-count/cps 'a
                (lambda (n-)
                  (leaf-count/cps 'b
                                  (lambda (m-)
                                    ((lambda (n)
                                       (leaf-count/cps '((c . d) . e)
                                                       (lambda (m)
                                                         (values (+ n m)))))
                                     (+ n- m-))))))

;; ↓

((lambda (n-)
   (leaf-count/cps 'b
                   (lambda (m-)
                     ((lambda (n)
                        (leaf-count/cps '((c . d) . e)
                                        (lambda (m)
                                          (values (+ n m)))))
                      (+ n- m-)))))
 1)

;; ↓

(leaf-count/cps 'b
                (lambda (m-)
                  ((lambda (n)
                     (leaf-count/cps '((c . d) . e)
                                     (lambda (m)
                                       (values (+ n m)))))
                   (+ 1 m-))))

;; ↓

((lambda (m-)
   ((lambda (n)
      (leaf-count/cps '((c . d) . e)
                      (lambda (m)
                        (values (+ n m)))))
    (+ 1 m-)))
 1)

;; ↓

((lambda (n)
   (leaf-count/cps '((c . d) . e)
                   (lambda (m)
                     (values (+ n m)))))
 (+ 1 1))

;; ↓

((lambda (n)
   (leaf-count/cps '((c . d) . e)
                   (lambda (m)
                     (values (+ n m)))))
 2)

;; ↓

(leaf-count/cps '((c . d) . e)
                (lambda (m)
                  (values (+ 2 m))))

というように評価されていく。このように見ていくと、cont にうまいこと以降に行われるべき処理が入っており、関数の呼び出し元に戻ることなく処理が最後まで行われることが伺える。

呼び出し側は、leaf-countの戻り値を受け取って処理を続けるかわりに、 leaf-countを呼び出す時点の継続を関数の形にしてcontとして渡すのだ。

というのはこれを言っているのがわかった。

継続渡し形式では、関数からのreturnという概念が無くなる。呼び出し元が指定した継続contを結果の値を引数として呼び出すことが、returnと等価になるわけだ。

これも上の評価で実際にそうなっているのがよくわかった。


 次に実際に Scheme 上で継続を使って実装する方法を探して、[お手元マルチスレッド]という項で継続を用いたマルチスレッド(もどき)を実装しているのでこれを読んでみた。使いたい人のための継続入門

Schemeにはcall/ccという呪文があって、 大域脱出だの例外機構だのマルチスレッドさえ実装できる。 しかし、call/ccは決して怪しい動作をするものなんかじゃなく、 ある意味、とても普通の関数である。 このことを理解してもらうために、call/ccなどと省略せずに、 call-with-current-continuationという正式名称に注目してみよう。

(fact/cps 10 (lambda (a) (* 2 a)))

fact/cps は上は[なんでも継続]であった reaf-count/cps と同じようなものなので、 (fact 10) を計算のあとの継続として (lambda (a) (* 2 a)) があるものだということになる。これを call/cc を使って書くと以下のようになる。

( 2 (call/cc (lambda (cont) (cont (fact 10)))))
contには(lambda (a) (
2 a))が渡ってくると考えられそうだ。 fooの素に相当する現在の継続の素を改めて書く必要はない。

ただし以下の話が続く。

;; call/ccの継続渡し形式への書き換えを試みてみる
((lambda (cont) (cont (fact 10)))
(lambda (a) ( 2 a)))
しかし、よくよく考えると、(
2 …)式の続きの計算はどうなるんだろう?
厳密に考えると、read-eval-print-loopがあるはずで、 次のread-eval-printが延々待ってるハズである。 これは以降の説明でも重要な点で、無視できないので仕方がない。 PRINT-AND-NEXT-REPLというものを便宜的に持ち込もう。 というわけで、次のようにするとしよう。
;; call/ccの継続渡し形式への書き換えを試みてみる(PRINT-AND-NEXT-REPL導入版)
( 2 ((lambda (cont) (cont (fact 10)))
(lambda (a) (PRINT-AND-NEXT-REPL (
2 a)))))

call/cc式の外側にある2倍を行う処理もそのまま残留している。 もし、
;; 継続渡し形式への変換と混同しちゃった版
((lambda (cont) (cont (fact 10)))
(lambda (a) (PRINT-AND-NEXT-REPL (* 2 a))))
という風な継続渡し形式への変換を予想された方は注意。 call/ccは継続渡し形式に変換する関数ではなく、 あくまで、call/cc式自身の継続(自分の値を待っている計算)を自動的に作り、 それをcall/ccの引数であるprocedureに渡して、 そのprocedureをcallするという関数だ。

見事に勘違いしていた。call/cc は外側の継続を持っているが、call/cc 継続自体の存在が call/cc の外側から無くなるわけではない。


保存した継続kは今までの説明のまま機械的に変換すると、 (lambda (a) (PRINT-AND-NEXT-REPL (+ x a z)))になるはずだが、 これは正確ではなかったということだ。
;; 実は不正確だった継続
(lambda (a) (PRINT-AND-NEXT-REPL (+ x a z)))
正しくは、(今のGaucheでは)継続kは (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))だったのだ。 なぜなら、第二引数であるcall/cc式を評価する前に 第一引数であるxは評価されて1を得ていたからだ。

;; より正確な継続
(lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))
つまり、Gaucheでは左から順に引数を評価するために、

;; 引数の評価順とcall/ccの位置
;; (1) xが評価される
;; (2) call/cc式が評価される
;; (3) zが評価される
;; (4) +が3つの値に適用される

(+ x call/cc式 z)
この式の第二引数のcall/cc式を評価する前に、 すでにxの値が環境から取り出されて1になっており、 call/cc式の継続(続きの計算)には 「環境からxの値を取り出す」という計算は含まれてないのだ。

逆に言えば評価すらも継続の処理一部として考えられるということになる。


もっと細かいことを言えば、 (lambda (a) (PRINT-AND-NEXT-REPL (# 1 a z)))であり、 もし、継続を保存後に(set! + *)とか(set! + max)などとしても、 やはり加算を行なうのである。

Common Lisp ではリストの先頭は関数とみなしてまず引数を評価していたような気がするので確かめたところやはりそうだった。

CL-USER> (undef-func (print 3))

; in: UNDEF-FUNC (PRINT 3)
;     (UNDEF-FUNC (PRINT 3))
;
; caught STYLE-WARNING:
;   undefined function: UNDEF-FUNC
;
; compilation unit finished
;   Undefined function:
;     UNDEF-FUNC
;   caught 1 STYLE-WARNING condition

3 ; Evaluation aborted on #<UNDEFINED-FUNCTION UNDEF-FUNC {1003B1DCB3}>.
CL-USER>

コンパイル時の warning が出ているが、実行時には 3 と表示された後にエラーが出ている。つまり関数の評価の前に引数から評価されている。しかし以下のような話が続いた。

実は今のGaucheでは (lambda (a) (PRINT-AND-NEXT-REPL ((identity +) 1 a x)))なので 破壊後の+の値である#が計算されて(# 1 2 10)から10が返る。 最初の(identity +)が引数の評価より後なのだ。 実は+などの様な組込み関数を使わずにユーザ定義関数を使う場合にも最後に評価される。 というか、むしろ逆で組込み関数の場合に最適化のために 引数が評価されるより前に#に評価済みになっているのだ。

一応試してみる。

(define adding
  (lambda a
    (apply + a)))

gosh> (define k #f)
k
gosh> (define x 1)
x
gosh> (adding x (call/cc (lambda (cont) (set! k cont) 2)) x)
4
gosh> (set! x 10)
10
gosh> (k 2)
13
gosh> (set! adding max)
#<subr (max arg0 :rest args)>
gosh> (k 2)
10

確かに継続 k の実行時に addingmax として振る舞っている。 Common Lisp ではどうなってるのか (組み込み関数とユーザー定義関数を区別しているのか) を調べる手段がわからなかった。


 本題のお手元マルチスレッド (お手軽マルチスレッド?) の部分と部分継続の項の前例をやっていて継続についてある程度理解が進んだ気がした。次に 「sleep 中にキーボード入力で任意のタイミングで sleep を解除する」というものを実装しようとした。

 考えた方法は、継続を利用して呼び出す度に 1 秒 sleep する関数を実装し、それを呼ぶ度にキーボード入力を見る処理を挟むというもの。とりあえず sleep の部分を実装した。

(define cont-sleep #f) ; 継続保存用

(define (sleep/cps n)
  (let ([n-rest n])
    (call/cc (^[cc] (set! cont-sleep cc)))
    (if (not (= n-rest 0))
        (begin
          (sys-sleep 1)
          (set! n-rest (- n-rest 1))
          #t)
        #f)))

gosh> (sleep/cps 3)
#t
gosh> (cont-sleep)
#t
gosh> (cont-sleep)
#t
gosh> (cont-sleep)
#f

期待通りの動作をした。しかし、この間にキーボード入力を見に行くということをするとしても、このキー入力自体にタイムアウトなどがなければ、正しい時間スリープすることができないことに気がついた。ここで read に対してタイムアウトが実装できれば良いということに気付いたので検索したところみつかった。

 長時間かかる処理にタイムアウトをつける。詳細についてこのページで解説されているが、この関数では、継続を脱出のために利用している。

おわり

(16. 継続)http://www.shido.info/lisp/scheme_cc.htmlleaf-generator が全く理解できていない。