🐠

【継続】Scheme (Gauche) でコルーチンを実装してみる

に公開
scheme
gauche
tech

はじめに

プログラミングの概念の一つに「継続」というものがある．これは抽象的には計算の残りの部分を表す概念で，具体的には関数や手続きとして表現可能なものである．自分もそうであったが，まったく知らない人にとっては「継続」を用いると何ができて何が嬉しいのかわからないことも多いと思う．そこで，自分の理解のためにも継続を用いることで実現できることや長所，短所について整理しようと思う．

まず，何ができるかというところであるが教科書的な説明だと以下のような機能が実現可能とされている．

  • 大域脱出break
  • コルーチン
  • 例外処理機構

さて，上に連ねた機能は基本的に言語処理系が提供する機能であってプログラマが自前で用意するものではないことに気が付く．つまり，継続が使えると，処理系に依存する機能を自分で実装してしまえるということだ．

継続を理解すれば上にあげた機能を自分で実装できるようになる．Schemeを勉強する人は自前でコルーチンを実装するのが定番という噂なので自分も挑戦してみる．ルートとしては，Schemeの基本的な事柄や関数や無名関数に触れたあと，継続を理解したらようやくコルーチンの実装に入れるといった感じだ．

手続きとラムダ

手続きを定義する

Schemeにおける手続きの定義は以下のとおり．手続き名および引数を示した後，後に手続き本体が続き，最後のS式が手続きの戻り値となる．

(define (手続き名) 手続き本体...)
(define (手続き名 引数...) 手続き本体...)
手続きの例1
;; Hello と出力するだけの手続き
(define (print-hello)
  (print "Hello!"))
手続きの例2
;; 階乗を計算する手続き
(define (factorial n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))
実行例
(factorial 3)
6
(factorial 5)
120

ちなみにGauche本（オライリーから出版されているプログラミングGaucheのこと）では一般的に関数とも呼ばれるものを「手続き」と呼んでおり，本全体にわたって手続きで統一されているように見受けられる．「手続き」という用語で統一されているのはSchemeの仕様（R5RS）に倣っているためと思われる[1]．一説によれば手続きと呼ぶか関数を呼ぶかは，戻り値を返すかどうかで区別されるらしい．Schemeは継続渡しスタイルだからreturnによる制御構造がないということになる．値を返すという考えが弱いとなると，必然的に呼び方も「手続き」になるということが想像できる．

ラムダ

名前のない手続きは次のようにして作成することができる．

(lambda (引数リスト) 手続き...)

実際に名前のないて続いを作成する例を示す．

ラムダの例1
gosh$ ((lambda (x y) (+ x y)) 3 4)
7

ラムダを用いて手続きを定義することもできる．先ほど示した手続きの定義は今から示す（冗長な）手続き定義の糖衣構文となっている．

ラムダによる手続きの定義
(define factorial
  (lambda (n)
    (if (= n 0)
      1
      (* n (factorial (- n 1))))))

(factorial 5)
120

高階手続き

Scheme風に言えば高階手続きだが単語としては高階関数の方が聞き馴染みがある．呼び方はともかく，手続きを受け取る手続きのことを高階手続きと呼ぶ．

以下はとても単純な高階関数の例．printを渡して手続きを実行しているので，「やっほー」という文字列が出力される．

(define (high-order-proc proc)
    (proc "やっほー"))

(high-order-proc print)
;; やっほー

Gauche本に掲載されている例はもう少し複雑だった．リストの要素のうち条件を満たすものだけを抽出し，処理にかけることができる．以下の例ではeven?を用いて偶数のみを足し合わせている．

偶数のみを足し合わせる高階手続き
(define (find-fold pred? proc seed lis)
  (cond ((null? lis) seed)
        ((pred? (car lis))
          (let ((seed2 (proc (car lis) seed)))
            (find-fold pred? proc seed2 (cdr lis))))
        (else (find-fold pred? proc seed (cdr lis)))))

(print (find-fold even? (lambda (elm seed) (+ elm seed))
  0 '(1 2 3 4 5 6 7 8 9 10)))

継続渡しスタイル

Gauche本では継続の説明に「仕事の流れ」を例え話に用いていた．従来のcall/return方式を仕事の流れに例えるならば，仕事を依頼されたら成果物を依頼者に返すというスタイルということになるだろう．一方，依頼を受けて仕事をした後，残りの作業を依頼者に返すのではなく次の作業者に渡すというスタイルもある．ある企業が下請け企業に仕事を依頼し，その下請け企業がさらに下請け企業に仕事を流すというどこかで見たようなやり方である（闇の世界）．継続渡しスタイルは後者となる．

例え話は置いておいて，実際にプログラムでどう表現するのかを考えてみる．例えば，以下の階乗の計算を行う手続きは，その内部でfactを呼び出しその結果をnにかけている．これは，従来のcall/return方式と言える．

(define (fact n)
  (if (= n 0)
    1
    (* n (fact (- n 1)))))

これを，継続渡しスタイルで書くということはどういうことだろうか．少なくとも，factの結果を利用して掛け算はできないはず．仕事の例で例えたように，nをかけるという操作は残りの作業ということになり，次の作業者に依頼しなければならないからだ．

実は，「残りの作業を次の人に依頼する」という処理はラムダ式を用いると実現できる．残りの作業に必要なパラメタはラムダ式の引数で受け取り，依頼先で発生した成果をラムダ式に適用する．だから，上の階乗の計算の再帰呼出しの部分は以下のようになるはずだ．___になっている部分は今は考えないようにする．

...
  (fact (- n 1) (lambda (f) (* n ___)))

変わった点はfactに引数が増えた点である．再帰呼び出しfactの後に行う手続き（継続）がラムダ式となっている．そのラムダ式の内部でnをかけるという処理が行われる．ラムダ式の実行のタイミングは呼び出し先に委ねられる．

さらに，外側にあった掛け算がなくなったことによりこの再帰呼び出しは末尾呼び出しになった．これにより末尾最適化の恩恵を受けることもできる．実は末尾呼び出しになるというのは継続の本質的な性質で，どんなプログラムも継続渡しスタイルで書くと関数呼び出しは末尾呼び出しとなる．以下は 「Practical Scheme なんでも継続」からの引用である．引用元で述べられているように関数からの returnという概念がなくなってしまうのが継続である．

継続渡し形式では、関数からのreturnという概念が無くなる。 呼び出し元が指定した継続contを結果の値を引数として呼び出すことが、 returnと等価になるわけだ(*2)。 関数側から見ると、contは呼んだっきり 戻って来ない手続きに見える (あるいは、関数としては contに結果を渡した時点で使命を終えているので、 contが戻って来ようが来まいが関係無いとも言える)。 この操作を最初の節の関数呼び出しの記述と比べてみよう。 「callとは、継続を伴って関数を呼び出すこと。returnとは、渡された継続へと 制御を移すこと」。 これを文字通り実装しているのが継続渡し形式というわけだ。
出典: https://practical-scheme.net/docs/cont-j.html

さて，先ほどfactを呼び出す際に第2引数を渡すことにした．したがって，factの定義も書き換えておく必要がある．___にしている部分はもうちょっと考える必要があるけど今は一旦おいておく．注目するのはfactの第2引数にcntが与えられるということだ．これは呼び出し元が指定する継続となっている．実体は手続き，すなわちラムダとなっているはず．cntに適切なパラメタを与えて呼び出すことで依頼主の残りの仕事を再開できる．

factを2引数の手続きに書き換える
(define (fact n cnt)
  (if (= n 0)
    (___)
    (fact (- n 1) (lambda (f) (___)))))

最後に今まで放置していた___の部分を埋めたいわけだが，ここは発想のコツが必要であると思う．もちろん自然に書ける人もいるだろうし，それは素晴らしいのだが自分の場合はそうは行かなかった．再帰プログラムを初めて書く時のように，コツを会得するまではなかなか自然に書けるものではないと思う．特にスタック型のcall/return方式に慣れきっていると余計難しいのではないだろうか．

以下に注意すべきことを箇条書きでまとめた．この思考に辿り着けたらあとはパズルのようにプログラムを組み立てる．

  • cntは継続である
  • n = 0のとき継続には1を渡す必要がある．なぜならこのときのcntはn = 1で作られた継続．n = 1のときパラメタfとして0の階乗が求められているが0の階乗は1であるからだ．
  • n != 0のとき，継続にはn * fを渡す．fはn-1までの階乗であるためn * fはnの階乗となる．継続にnの階乗を渡して残りの仕事を進めるといった具合だ．

こうして組み上がったプログラムを以下に示す．

継続で書いた階乗のプログラム
(define (fact n cnt)
  (if (= n 0)
    (cnt 1)
    (fact (- n 1) (lambda (f) (cnt (* n f))))
    ))

(fact 7 (lambda (x) (print x)))

細かい部分ではあるが階乗の呼び出し部分(fact 7 ...)にも継続が渡されている．継続渡しスタイルでは戻り値を使わないのだった．だから(print (fact 7))みたいな書き方はしない．これは階乗の計算の結果を待ってそれを出力するというコードになる．ではどうするかというと出力の処理を継続としてfactに渡すようにする．見てもらうとわかるように上のプログラムでもそうなっている．

少々長かったが継続渡しスタイルでプログラムを書いてみることに挑戦した．自分もまだまだ自然に継続渡しスタイルでの書き方が出てくるようにはならない．どうしてもcall/return方式に引っ張られるところがある．

次の節は少し話題を変えてマクロを扱ってみたい．というのも，コルーチンを実装するにあたり構文拡張が必要になってくるからだ．（必須というわけではないのだがマクロにすると便利）

構文拡張（マクロ）

Schemeでプログラムを書く際は他のプログラミング言語と比べて構文を意識することは少ない．なぜならすべてリストで済むから，リストの構文を覚えてさえいれば問題ないからだ．ではSchemeで言う構文とは何かというと，リストの評価手順のことである．

Schemeの構文が指すレイヤについて

なんというか，一般的な意味での構文とSchemeでの構文はレイヤが違う気がする．一般的には構文というと構文解析のレイヤで用いる言葉だけど，Schemeでの構文はもうしこす上のレイヤで使っているんじゃないかな．だってS式の構文解析は終わってるはずだから

次のようなリストを考える．これは一部のパターンを除いて基本的には手続き呼び出しとなる．まずXとYとZを評価する．評価の順序は不定である．次にYとZの評価結果をXに引数として与えるというのが手続き呼び出しの評価手順である．

(X Y Z)

多くの場合，リストは手続き呼び出しとなるため上の手順で評価されるのだが，一部そうでない例外もいる．Schemeの規格R5RSではdefine，set!，lambda，if，quoteが構文として定義されていて，これらのシンボルがリストの先頭要素にあった場合は「構文」として認識されそれぞれの評価ルールに従って評価される．

さて，Schemeの構文が上に述べた5つのみかというとそうではない．上の5つの構文を使ってScheme自身が構文を拡張することができる．これはSchemeの強みの一つでもある．拡張された構文も標準ライブラリとして提供されているので特に追加の操作なく使うことができる．拡張構文の例としては，let，begin，cond，case，and，orなどがある．これらの拡張構文を先に述べた5つの原始的な構文に変換するマクロもR5RSで示されている[2]．

前置きが長くなったが要はマクロを使えば独自の構文を作れるということである．Schemeではマクロの定義方法がいくつか用意されているらしい．普通に結構複雑でちゃんと理解しようとすると長くなりそうな...

パターンマッチによるマクロ

whenとunlessを追加してみる．whenは条件を満たしときのみ後続の処理を実行する構文で，unlessはその逆となる．構文を定義するときはdefine-syntaxから始まるリストを書く．<name>がキーワードとなり，リストの先頭に現れた際にパターンマッチが行われる．そして，パターンにマッチすればテンプレートに置き換えられるという仕組みになっている．パターンはsyntax-rulesによって加えていくことができる．

define-syntaxとsyntax-rulesによるマクロ定義
(define-syntax <name>
    (syntax-rules (<literal> ...)
        (<pattern> <template>)
        ...))

では実際にwhenとunlessのマクロを記述してみる．whenとunlessの違いはnotがあるかないかぐらいなのでほぼ同じコードとなっている．expr ...というのはexprの0個以上の繰り返しとなる．<literal>の部分は今は空のリストになっている．<literal>にはパターン中で予約語として扱いたい識別子を記述する．

when式のマクロ定義
(define-syntax when
    (syntax-rules ()
        ((when test expr ...) (if test (begin expr ...))))
unless式のマクロ定義
(define-syntax unless
    (syntax-rules ()
        ((unless test expr ...) (if (not test) (begin expr ...)))))

<literal>の部分に識別子を追加するとifを以下のようなif-then-elseの形式に上書きすることができる[3]．

if-then-elseのマクロ定義
(define-syntax if+
  (syntax-rules (then else)
    ((if+ test then expr1 else expr2) (if test expr1 expr2))))

(if+ #t then (print "yes") else (print "no"))
(if+ #f then (print "yes") else (print "no"))

コルーチン

call/cc

コルーチンの話をする前にまずcall/ccの話をしておく．どんなプログラムもある時点に注目すれば，それ以降の処理は継続とみなすことができる．call/return方式でプログラムを書いていると継続が明示的に現れることがないだけで継続は存在する．そのような継続を明示的に扱えるように取り出すのがcall/ccだ．そして取り出した継続を引数の1引数の手続きに渡す．

通常の再帰で書いた階乗
(define (fact n)
  (if (= n 0)
    1
    (* n (fact (- n 1)))))

(print (fact 7))
call/ccを用いた階乗
(define (fact/cc n)
  (call/cc (lambda (k) ; 継続を取り出す
    (if (= n 0)
      (k 1)
      (k (* n (fact/cc (- n 1)))) ;
    ))))

(print (fact/cc 7))

break と next

call/ccを使うと制御を途中で奪い取ることができる．find-foldの例でbreakとnextを実現する例を示す．

元のプログラム
(define (process elt seed) (cons elt seed))
(print (find-fold odd? process '() '(1 2 3 4 5 6 7 9 10)))

まず外側のcall/ccでfind-foldの継続を取り出している．継続breakを呼び出すと，そのタイミングでfind-foldが終わったあとの処理へジャンプできる．次に内側のcall/ccではprocessの継続を取り出している．この継続はfind-foldのループ内部から取り出されたものであるため，これを呼び出すと処理がループの中へ戻る．breakで一度ループの外へ飛んだあと再びループの中へ戻れるようにグローバル変数nextに戻るための手続きを保存してある．

breakとnextを実装
(define next #f)
(call/cc (lambda (break)
  (find-fold odd?
    (lambda (elt seed)
      (call/cc (lambda (cnt)
          (set! next (lambda () (cnt (process elt seed))))
          (break #f))))
    '() '(1 2 3 4 5 6 7 8 9 10))))

ようやくコルーチン

ここまで，マクロによる構文拡張，call/ccによる継続の取り出し，breakとnextによる処理の中断と再開を扱ってきた．これらを組み合わせると複数の処理が同時に動いているような状態を作ることが可能となる．より具体的には，各処理の継続をキューに登録しておきyieldが呼ばれたらキューから継続を一つ取り出し再開するだけである．

次のコードではコルーチンを作成する構文を追加している．このマクロは展開されると，外側が(define (<routine-name> yield) ...)という手続き定義となる．手続きの本体ではすぐにcall/ccが呼ばれており，ルーチンの後の継続を補足してreturnと名付けている．したがって，returnを呼び出せばルーチンを中断するようになっている．

コルーチンを作成する構文をマクロで追加
;; キューを使用する
(use util.queue)

;; タスクキューを作成する
(define tasks (make-queue))

;; コルーチン作成構文
(define-syntax coroutine
  (syntax-rules ()
    ((_ (routine-name yield) body ...)
      (define (routine-name)
        (call/cc (lambda (return)
          (define (yield)
            (call/cc (lambda (cnt)
              (enqueue! tasks cnt)
              (return))))
            body ...))
        ((dequeue! tasks))))))

次に内部でyieldの定義が書かれている．パターンの部分に登場するyieldの正体を定義している．引数にあえてyieldを与えているのはシンボル名のリネームを防ぐためであったり，yield以外のキーワードを指定できたりするためだろう．仮に引数にyieldを置かなかった場合，マクロ定義におけるyieldは変数名の衝突を防ぐために自動的にリネームされてしまい参照することができなくなる．

yieldの定義
(define (yield)
  (call/cc (lambda (cnt)
    (enqueue! tasks cnt)
    (return))))

yieldは呼び出されるとその時点での継続を補足し，それを継続キューtasksに追加する．そして，returnを呼び出されることによってルーチンの外へと処理が移動する．マクロ定義ではさらにbody ...が続き本命の処理が展開される．

最後の((dequeue! tasks))はcall/ccの後にあり，ルーチンからみたときの継続にあたる．よくみると丸カッコが2重になっており，キューから取り出した手続きをその場で実行するというコードになっている．いずれかのルーチンでyieldが呼ばれたらキューから取り出した手続きが走り出すというわけである．

最後にコルーチンのコードをすべて載せておく．

coroutine.scm
(use util.queue)

;; タスクキュー
(define tasks (make-queue))

;; コルーチン作成構文
(define-syntax coroutine
  (syntax-rules ()
    ((_ (routine-name yield) body ...)
      (define (routine-name)
        (call/cc (lambda (return)
          (define (yield)
            (call/cc (lambda (cnt)
              (enqueue! tasks cnt)
              (return))))
            body ...))
        ((dequeue! tasks))
          ))))

;; タスクキューの初期化
(define (coroutine-init! . rs)
  (set! tasks (make-queue))
  (for-each (lambda (r)
    (enqueue! tasks r))
    rs))

(coroutine (three yield)
  (let lp ()
    (print "one")
    (sys-sleep 1)
    (yield)
    (print "two")
    (sys-sleep 1)
    (yield)
    (print "three")
    (sys-sleep 1)
    (yield)
    (lp)
  ))

(coroutine (five yield)
  (let lp ()
    (print "いち")
    (yield)
    (print "にい")
    (yield)
    (print "さん")
    (yield)
    (print "しい")
    (yield)
    (print "ご")
    (yield)
    (lp)
))

(coroutine-init! three)
(five)
脚注

  1. https://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3AProcedure ↩︎

  2. https://conservatory.scheme.org/schemers/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%_sec_7.3 ↩︎

  3. https://practical-scheme.net/gauche/man/gauche-refj/Wei-Sheng-De-makuro.html ↩︎

Discussion