Scheme/継続の種類と利用例

Introduction

このセクションでは、継続を用いたプログラムを実際に動かしてみる。教科書の例題を解くためだけでなく、制御処理の仕組みを継続を活用して作ったり、既存のライブラリの動作をカスタマイズすることで実用的なプログラミングに応用できるようになることを目指す。また、処理系における実装の方法についても触れ、継続呼び出しのパフォーマンスについても考察する予定。

call/cc

導入

call/ccは、(call/cc proc) 式を評価した後すべき計算を、継続オブジェクトとして proc に渡す手続きである。

この継続オブジェクトは、C言語で考えると (call/cc proc) を評価した後の処理へgotoするマクロ、もしくは (call/cc proc) を評価したときに setjmp() によってマークした地点に longjmp() によって移動する関数に似ている。しかし、call/ccで渡される継続オブジェクトには、式の評価がどの関数から呼ばれたのかが記録されていて、proc が呼び出した関数からはもちろん、外側の動的スコープからでも呼び出せる点で、より強力である。

なお、R5RSではcall-with-current-continuationという手続き名で仕様が決められているが、ほとんどの処理系で略称のcall/ccを使える。

ループ脱出

まずは一番簡単な例から紹介する。C 言語のbreak文やreturn文のように、行うべき続きの処理をスキップして、call/ccの外側まで移動することができる。

(call/cc (lambda (break)
  (let loop ()
    (display (* 2
      (let ((x (read)))
        (if (number? x) x (break "input error!")))))
     (newline)
     (loop))))

ループ

call/ccでの継続を呼び出すことで、行うべき続きの処理を以前の状態に巻き戻すことができる。

以下は人工的な例に感じられるかもしれないが、継続呼び出しによる巻き戻しを用いてループを行っている。

(let ((x (call/cc (lambda (c) (cons c 4)))))
  (cond
; 継続呼び出しを行わなければ、値を返してプログラムは終了する。
    ((= (cdr x) 0) #t) 
; x を表示した後、(car x)に保存されている継続を呼び出す。
    (else (display x) (newline) ((car x) (cons (car x) (- (cdr x) 1))))))

出力は、以下のようになる。

(#<continuation> . 4)
(#<continuation> . 3)
(#<continuation> . 2)
(#<continuation> . 1)

コルーチン・マイクロスレッド・ジェネレータ

ここまでの例で、継続の呼び出しはgoto文の実行と同じようなものだという感覚が分かったと思う。ここではより複雑な例として、コルーチン・マイクロスレッド・ジェネレータを取り上げる。これらは処理の途中で継続を保存して、必要な時に継続を呼び出して再開する仕組みを持っている。

ジェネレータは「中断可能な関数」のようなものである。ジェネレータの内部でyieldが呼び出されると処理が一旦中断し値が返されるが、その後ジェネレータをもう一度呼び出すことでyieldした位置から処理を再開することができる。これをcall/ccを使って実装してみる。今回は動作確認のため、ジェネレータでハノイの塔の円盤を中断/再開しつつ移動してみることにする。

(define yield #f)

;ジェネレータの実装
(define (make-generator thunk)
  (define state (cons thunk '()))
  (define (run-generator)
    (set! state (call/cc (lambda (return)
      (set! yield (lambda (x) (call/cc (lambda (c) (return (cons c x))))))
      (apply (car state) (cdr state))
      (return (cons values '(#f))))))
    (apply values (cdr state)))
  run-generator)

;ハノイの塔の円盤を、fromからtoへn個動かす。
;towersは塔のリストで、塔は上から順に並べた円盤のリストである。
(define (hanoi n from to tmp towers)
  (if (= n 0)
      towers
      (let* ((t1 (hanoi (- n 1) from tmp to towers));まずn-1個の円盤をfromからtmpに動かす。
             (t2 (yield (move t1 from to))))        ;n個目の円盤をfromからtoへ動かし、一旦中断する。
            (hanoi (- n 1) tmp to from t2))))       ;その後、n-1個の円盤をtmpからtoへ動かす。

;ハノイの塔の一番上の円盤をfromからtoに移動する。
(define (move lis from to)
  (define (moved-tower lis from to index)
    (cond
      ((= index from) (cdr  (list-ref lis from)))
      ((= index to)   (cons (car (list-ref lis from)) (list-ref lis to)))
      (else (list-ref lis index))))
  (let loop ((n 0))
    (if (= n (length lis)) '()
      (cons (moved-tower lis from to n) (loop (+ n 1))))))

(define hanoi-generator (make-generator (lambda () (hanoi 5 0 1 2 '((0 1 2 3 4) () ())))))

このジェネレータは以下のように呼び出すことができる。

> (hanoi-generator)
((1 2 3 4) (0) ())
> (hanoi-generator)
((2 3 4) (0) (1))
> (hanoi-generator)
((2 3 4) () (0 1))
> (hanoi-generator)
((3 4) (2) (0 1))
> (hanoi-generator)
((0 3 4) (2) (1))

...

> (hanoi-generator)
(() (0 1 2 3 4) ())
> (hanoi-generator)
#f
> (hanoi-generator)
#f

...

このジェネレータを呼び出すと、

呼び出し元に戻る継続をreturnに束縛する。
計算の続き（継続）と返り値をstateに保存し、returnによってジェネレータの呼び出し元に戻るような関数をyieldに保存する。
stateに保存されていた計算の続きを計算する。
計算が終了したら、返り値#fをreturnする。続きの計算はなくなったので、恒等関数valuesを代わりにセットしておく。

という処理が行われる。保存されている「計算の続き」にはジェネレータ内部 (thunk) でなされる計算だけでなく、以前ジェネレータを呼び出した呼び出し元の情報までもが保存されているが、実際にはその継続が呼ばれる前にreturnしてしまうので、その情報は使われることはない。

外部イテレータとは、Pythonのイテレータやfor文、JavaのIterator.next()メソッドのように、手続きを呼び出すごとに次々とデータを探索する手続きやオブジェクトである。このようなものをジェネレータを用いて書くことができる。（書きかけ）

マイクロスレッド、もしくはファイバーは、軽量なスレッドの実装である。一定時間が経過すれば自動的に次のスレッドに切り替わる普通のプリエンプィブなスレッドと異なり、処理があらかじめプログラムに記述された中断点に達した時に初めて次のマイクロスレッドが呼び出されるようになっている。マイクロスレッドはユーザ空間に実装されたスレッドであり、クロックによるハードウェア割り込みも使われないのでスレッド切り替えのオーバヘッドが少なく、1ステップが非常に短い処理を短時間のうちに多数こなすことができる。Schemeにおいてはネイティブスレッドの代替としてマルチタスクの簡易な実装として紹介されていることも多いが、ゲームでオブジェクトを多数移動させるなどの切り替えの多い処理をおこなうときに、真価を発揮する。

マイクロスレッドの実装は停止/再開可能な手続きという点ではジェネレータと違いはなく、同じように実装できる。加えて、スレッドをラウンドロビンで実行するための簡易的なスケジューラを書く。

(define yield #f)
(define running-threads '())

;ジェネレータから名前を変えただけ。
(define (make-microthread thunk)
  (define state (cons thunk '()))
  (define (run-microthread)
    (set! state (call/cc (lambda (return)
      (set! yield (lambda x (call/cc (lambda (c) (return (cons c x))))))
      (apply (car state) (cdr state))
      (return (cons values '(#f))))))
    (apply values (cdr state)))
  run-microthread)

;スケジュールに追加する。
(define (start-microthread proc)
  (set! running-threads (cons proc running-threads)))

;running-threadsを順番に呼び出すだけの手続き。
(define (microthread-main-loop)
  (let loop ()
    (for-each (lambda (x) (x)) running-threads))
    (loop)))

以下のように使用される。

（書きかけ）

複数の通常スレッドの内部にそれぞれ多数のマイクロスレッドを所属させることもできる。この手法はマルチコアCPUを有効に活用するために必須である。以下ではsrfi-18のスレッドがネイティブスレッドで実装されている処理系(Gaucheなど)を対象に、次のようなコードを書いてみる。

（書きかけ）

バックトラッキング

バックトラッキングは非決定性オートマトンを実行する手法の一つである。バックトラッキングを使って、n-Queen問題や数独などの論理パズルを解くプログラムや、文字列を正規表現にマッチするプログラムを書くことができる。バックトラッキングのアルゴリズムは、以下のようになる。

（状態遷移図を書く）

次に行うべき処理(オートマトンの状態の遷移先)が複数ある場合、分岐点を一旦保存した後、とりあえず一つの分岐先を選んで次のステップの処理を実行する。
その分岐先で解が見つかった場合、その結果を出力し、プログラムは終了する。
分岐先で解が見つからなかった場合は、保存されていた分岐点へ戻り、他の選択肢が試される。

「分岐点を保存」という文句を読んで、ここにはcall/ccでの継続取り出しが使えそうだと直感したなら、継続の意味や応用の方法はもう分かってきているのだと思う。実際、call/ccを用いることで、普通のSchemeプログラムとバックトラッキングを融合させ、解の探索プログラムを簡潔に表現することができる。

(define (fail) #f)
(define (amb-proc . x)
  (define former-fail fail)
  (if (null? x)
    (fail)
    (call/cc (lambda (return) ; 分岐点
      (set! fail (lambda () ; 選ばなかった選択肢を保存
        (set! fail former-fail)
        (return (apply amb-proc (cdr x)))))
      (return ((car x))))))) ; 一つの選択肢を返す

実用的には、amb マクロを実装すると、遅延評価のために(lambda () ...)を書く必要がなく便利である。

(define-syntax amb
  (syntax-rules ()
    ((_) (amb-proc))
    ((_ value ...) (amb-proc (lambda () value) ...))))

使用例:

(display
  (let ((i (amb 1 2 3)) (j (amb 3 4 5)))
    (if (= (* i i) j) (cons i j) (amb))))
; => (2 . 4)

これを使って、数独を解くプログラムを作る。

初めに、問題の表し方を決める。?は空欄を表す。

  (define problem '(
    (5 3 ? ? 7 ? ? ? ?)       
    (6 ? ? 1 9 5 ? ? ?)
    (? 9 8 ? ? ? ? 6 ?)
    (8 ? ? ? 6 ? ? ? 3)
    (4 ? ? 8 ? 3 ? ? 1)
    (7 ? ? ? 2 ? ? ? 6)
    (? 6 ? ? ? ? 2 8 ?)
    (? ? ? 4 1 9 ? ? 5)
    (? ? ? ? 8 ? ? 7 9)))

(問題はcommons:File:Sudoku-by-L2G-20050714.svgより)

次に、与えられたパターンが数独のルール（行、列、3x3ブロックの中ではすべて異なる）を満たしているかどうか判別する関数を書く。

; srfi-1 を使います
(require 'srfi-1)

; リスト中の数字(1～9)が全て異なれば #t を返す
(define (unique x)
  (define check (make-vector 10 #t))
  (define (loop x)
    (if (null? x) #t
      (cond
        ((eq? (car x) '?)
          (loop (cdr x)))
        ((vector-ref check (car x))
          (vector-set! check (car x) #f)
          (loop (cdr x)))
        (else #f))))
  (loop x))

; (group n (1 2 3 ... )) => ((1 2 ... n) (n+1 n+2 ... 2n) ...)
(define (group count lis)
  (if (null? lis) '()
    (cons (take lis count)
          (group count (drop lis count)))))

 ; matrix が数独のルールを満たしていれば #t を返す 
(define (sudoku-check matrix)
  (and
 ; 行のチェック
       (every unique matrix)
 ; 列のチェック
       (every
         (lambda (x)
           (unique (map (lambda (row) (list-ref row x)) matrix)))
         (iota 9))
 ; 3x3 ブロックのチェック
       (every
         (lambda (three-rows)
           (every
             (lambda (x) (unique
                 (append-map
                   (lambda (row) (list-ref row x))
                   (map (lambda (row) (group 3 row)) three-rows))))
             (iota 3)))
         (group 3 matrix))))

最後に、

空いている空欄を一つ選んで、数字に置き換える
数独のルールに合致しているかどうか確認する

を繰り返すプログラムを書く。

空きマスを置き換える数を(amb 1 2 ... 9)にしているので、一旦1を埋めて次にすすみ、その後どのようにマスを埋めて行っても数独のルールを満たすパターンを見つけられなかった場合は、2を選んで次に進む、という動作をする。

call/ccは環境(set!での値の変更)を元に戻さないので、再帰呼び出しによるループを使う必要がある。これは少々不便な点である。

 ; ?のマスを一つ置き換える
(define (replace-matrix proc subst matrix)
  (define replaced #f)
  (map
    (lambda (row)
      (map
        (lambda (cell)
          (cond
            ((and (not replaced) (proc cell)) (set! replaced #t) subst)
            (else cell)))
        row))
    matrix))

(define (solve problem)
  (let loop ((answer problem))
    (if (sudoku-check answer) ; 数字が重複していないかどうか
      (if
        ; ? が残っているかどうか 
        (any (lambda (row)
            (any (lambda (x) (eq? x '?)) row))
          answer)
        ; ? を (amb 1 2 ...) に置き換え、loopに戻る。
        (loop (replace-matrix (lambda (x) (eq? '? x)) (amb 1 2 3 4 5 6 7 8 9) answer))
        ; 答えを返す
        answer)
      ; 失敗
      (amb)))

 ; 問題を解いて表示する
(for-each
  (lambda (x) (display x) (newline))
  (solve problem)))

(注・比較的速い実装を使った場合でも、実行には数十秒程度かかることがあります）

例外処理

ループ脱出の応用で、例外の発生と例外処理の仕組みを書くことができる。

(define raise-error #f)

(define (may-throw-error)
  (let ([num (read)])
     (if (not (number? num)) (raise-error "**input error** : Not a number!"))
     ; 掛け算した結果を表示
     (display (* 2 num))
     (newline)))

(define (run-with-exception)
  (call/cc (lambda (return)
    (let 
       ([e (call/cc (lambda (on-error)
             (set! raise-error on-error)
             (return (may-throw-error))))])
       ; 例外の補促
       (display "Error: ")
       (display e)
       (newline)
       ; やり直し
       (run-with-exception)))))

この例では、raise-errorが呼ばれた段階で制御が例外の捕捉へと移るので、数値以外の入力に対しては掛け算は行われず、全体の処理がやり直される。

dynamic-wind

dynamic-wind は、継続の呼び出しにより制御が「飛んで」移動した場合でも、スコープに突入・脱出する時に決められた操作を実行させるための手続きである。 ^[1]

前項の例外処理では、例外を起こすコードは一つであったが、現実には何層もネストして try-catch を書く場合がある。また、例外処理とその他の目的での継続を併用することもある。実用的なプログラムでは、コルーチンの再開などによって try が再開されその後エラーが発生した場合でも、対応する catch が呼ばれるべきである。dynamic-wind を使えば、どのようにして try スコープに突入したとしても、必ず catch を呼ぶエラーハンドラを事前に設定することができる。

実用的な例外処理システムとして、srfi-34 (日本語訳) の例外処理がある。参照実装としてcall/ccとdynamic-windを使ったプログラムが掲載されている。

実装例

スタックを用いている処理系^[2]では、call/ccの捕まえた継続が外部から呼び出された時に、その時点での変数の値 (引数の束縛) や呼び出し元の情報を復元するために、call/ccはコールスタックをまるごとヒープにコピーする。これへのポインタが継続オブジェクトとして手続きに渡される。このコピーは時間のかかる処理なので、コピーをしないで済むのならば避けたい。break・return・continueの代用として使う場合など、捕まえた継続が外部からは呼ばれないことが分かっている場合、C言語のsetjmp・longjmpのようにスタックポインタのみを用いる方法に最適化することができる。

プログラムをCPS変換してからコンパイルする処理系 (たとえばChicken Scheme) では、call/ccは単にcall/ccの呼び出しを表す関数と、現在のスタックポインタを継続オブジェクトとして渡せば十分である。この実装はcall/ccの呼び出しや継続オブジェクトの呼び出しが高速である一方で、継続オブジェクトが生きている段階でスタックを使い切ってしまうと、ガーベッジコレクタが継続が参照しているスタック変数をすべてコピーしなくてはならない。

call/ccの副作用

call/ccで取り出された継続を適用することは、副作用のある操作であると考えられている。 ^[3] たとえば、以下のコードはそのことを示している。

; 一つ目の(call/cc values)の返す継続と、二つ目の(call/cc values)の
; 返す継続は同じでない。参照透過でない。
(cons (call/cc values) (call/cc values))

; そもそも、副作用がないプログラムの実行結果から、関数の引数の
; 評価順を外部から判定することはできないはず。
(call/cc (lambda (c) (cons (c 1) (c 2)))

set!構文とは異なり、環境を書きかえない「継続の適用」に副作用があることは、直観的でないと感じるかもしれない。実際、call/cc以外に副作用のないプログラムは、単純にCPS変換するだけで副作用のないプログラムになる。しかし、（最適化の対象として）副作用がないというためには、環境を書きかえないことだけでは不十分であり、プログラム全体の評価ツリーを書き換えないことが必要である。

もっといえば、ある「括弧」（動的スコープ）を評価することによって、その「括弧」の外側にある式にまで、どのように評価されるかを決定・変更する作用が「副作用」ということになる。逆に、「括弧」を値に置き換えるだけで式全体の評価値が計算できるなら、それは副作用がないといえる。

継続の適用は、外側の動的スコープにある「続きの計算」の評価を省略し、その継続が取り出された (call/cc (lambda (c) ... )) という外側の「括弧」の評価値を決定するという点で、副作用を持っている。この性質によって、継続呼び出しのあるプログラムには、評価順序の入れ替え、メモ化など「副作用のないプログラムのためのプログラム変換（最適化）」を利用することができない。

部分継続では、shiftの取り出す継続の範囲はresetまでに限られているので、部分継続の適用によって「副作用を及ぼせる範囲」はresetの内側に限られる。したがって、部分継続以外には副作用のないプログラムは、reset呼びだしの外側では、部分継続の適用も含めてメモ化を適用できるなど副作用のないプログラムと同様に扱うことができる。

shift / reset

shift / reset は部分継続（partial continuation, 限定継続 delemited continuation）を使うための構文である。 call/ccにより渡される継続と異なり、続きの計算全てを表す継続ではなく、resetのある途中位置までの継続を表し、終わりまで達したならば継続の呼び出し元へ返る。呼び出し元へ返るという点では部分継続は普通の関数と同じように扱うことができる。

部分継続を用いた対話型プログラム

実装例

call/ccを用いる方法と、処理系に組み込む方法がある。call/ccを用いる方法は移植性が高いものの、一般にパフォーマンスはとても悪い。

control / prompt

bshift / breset

gshift / greset

脚注

^ 動的環境と限定継続をもつプログラム言語の意味論と実装 (田中陽・亀山幸義, 2007 p.14 4.3章 call/cc と dynamic-wind の意味論) が分かりやすい。厳密には、dynamic-windの実現のために継続を適用する動作そのものが少し拡張されている。
^ 3impでいうところのスタックベースの実装
^ [1]

このページ「Scheme/継続の種類と利用例」は、まだ書きかけです。加筆・訂正など、協力いただける皆様の編集を心からお待ちしております。また、ご意見などがありましたら、お気軽にトークページへどうぞ。

[1] 動的環境と限定継続をもつプログラム言語の意味論と実装 (田中陽・亀山幸義, 2007 p.14 4.3章 call/cc と dynamic-wind の意味論) が分かりやすい。厳密には、dynamic-windの実現のために継続を適用する動作そのものが少し拡張されている。

[2] 3impでいうところのスタックベースの実装

[3] [1]

[1]

[2]

[3]