Rubyの継続(continuation)

前置き

Hal Fulton著の"The Ruby Way"に、Rubyの「継続(continuation)」という機能を使ったフィボナッチ数生成器の例が載っていたので、解読してみたいと思います。ただし、フィボナッチよりは役に立つ生成器を目指します。

本文

生成器

サザエさんの予告編をアナウンスするのは、サザエさんとタマを除く磯野家のメンバーと決まっています。これを生成する生成器NextWeekSazaeを書いてみましょう。

使い方は、こんな感じ。準備はnew()するだけで、あとはnext()するたびに、新しい予告担当者を生成します。

nws = NextWeekSazae.new

week1 = nws.next  #=> 'Katsuo'
week2 = nws.next  #=> 'Masuo'
week3 = nws.next  #=> 'Fune'

他の生成器にも再利用したいので、NextWeekSazaeクラスは、抽象クラスGeneratorから派生するような設計にしたいです。NextWeekSazaeクラスは、できるだけ生成処理に専念したいですね。

class NextWeekSazae < Generator
  def generating_loop
    loop do
      generate 'Tarao'
      generate 'Wakame'
      generate 'Katsuo'
      generate 'Masuo'
      generate 'Fune'
      generate 'Namihei'
#     generate 'Ikura'
    end
  end
end

ここで、親子の責任分担は以下のようになっています。

  • 子は、generating_loop()を定義し、その中でひたすら生成する
  • 生成した値は、Generator#generate()で親に通知する
  • 親は、generating_loop()をコールバックする
  • next()も親が定義し、子から通知された値を返す

子クラスに、生成処理以外の余計なコードが一切無いのがポイントです。生成値をどこに貯めるのかとか、どこまでnext()で返したかとか、そんなことは関知しません。ちなみにフィボナッチなら、こんな感じです。

class Fib < Generator
  def generating_loop
    generate 1
    a, b = 1, 1
    loop do
      generate b
      a, b = b, a + b
    end
  end
end

サザエさんにしろ、フィボナッチにしろ、生成処理が無限ループになっているので、最初に示したクライアント側のコード(newして、nextを連打する)と両立するには、一見、マルチスレッドが必要な気がします。そして、スレッド同期もケアしないと、next()呼び出しが生成ループを追い越しかねない……。ところが、継続(continuation)を使うと、そんな心配は不要です。

継続(continuation)

継続は、Kernel#callcc()とContinuation#call()で実現されています。それぞれ、C言語のsetjmp()とlongjmp()に相当します。

callcc()はブロックを引数に取り、AとBの2つの経路に分岐します(setjmpやforkと同じイメージ)。経路Aは初回呼び出し時に通る経路で、Continuationオブジェクトを生成し、ブロックを実行して、callcc()から抜けます。もう一方の経路Bは、何もせずにcallcc()から抜ける経路です。初回呼び出し時に生成されたContinuationに対してcall()が呼ばれたときに、経路Bを通ります。

callcc()の戻り値は、経路Aを通った場合はブロックの最後の値です。経路Bの場合は、callの引数がcallcc()の戻り値になります。

2つの経路

Generatorクラスの実装

require 'continuation'

class Generator
  def initialize
    do_generation
  end
  
  def next
    callcc { |cont|           # [1]
      @main = cont
      @gen.call               # [X]
    }
  end
  
  private
  
  def generate(value)
    callcc { |cont|           # [2]
      @gen = cont
      @main.call value        # [Y]
    }
  end
  
  def do_generation
    callcc { |cont|           # [3]
      @gen = cont
      return                  # [Z]
    }
    generating_loop
  end
  
end

Ruby 1.9では継続機能の削除が検討されたようです。結局は残ったようですが、1.9では、明示的にrequireしないと使えません。

Generatorクラスは、@mainと@genの2つのContinuationオブジェクトを持ちます。マルチスレッドモデルに例えるなら、@mainはメインスレッド(つまりクライアント側のスレッド)へ制御を移すためのもので、@genは生成ループのスレッドへ制御を移すためのものです。この比喩では、Continuationオブジェクトはスレッドコンテキストに相当します。

nextとgenerateはソックリですね。クライアントがnextしたときは、メイン用のContinuationオブジェクトを生成([1]の経路A)して@mainへ退避し、@genへジャンプ([X])します。これに対し、生成ループがgenerateしたときは、生成器用のContinuationオブジェクトを生成([2]の経路A)して@genへ退避し、@mainへジャンプ([Y])します。つまり、nextとgenerateが呼ばれるたびにコンテキストが切り替わるわけです。

[X]で@genへジャンプすると、@genが指すContinuationオブジェクトを生成した[2]の経路Bへ入りcallccから抜け、generateからも抜けて、生成ループへ戻ります。一方、[Y]で@mainへジャンプするときは、引数にvalueを指定しています。すると、@mainが指すContinuationオブジェクトを生成した[1]の経路に入りcallccから抜け、nextからも抜けて、メインへ戻ります。このとき、callccの戻り値(及びnextの戻り値)はvalueになります。

ここで、ニワトリと卵の話しをしましょう。nextとgenerateはどっちが先でしょうか。実はnextが先です。初めてnextが呼ばれるとき、まだgenerateは呼ばれてません。そのままでは、@genはnilです。なので、誰かが@genを初期化しておく必要があります。これがdo_generationの役割です。

do_generationはinitializeから呼ばれ、生成器用のContinuationオブジェクトを生成([3]の経路A)して@genに退避し、メソッドからreturn([Z])します。この時点では、generating_loopには到達しません。do_generationからreturnした後は、initializeから抜け、newからも抜けて、メインへ戻ります。

その後、最初のnextが呼ばれると、[X]で@genへジャンプし、[3]の経路Bへ入りcallccから抜け、generating_loopへ入り、最初のgenerateが呼ばれます。あとはgenerateとnextのピンポンが繰り返される、というわけです。

生成の流れ

Last modified:2012/06/08 22:35:11
Keyword(s):
References:[言語Tips]
This page is frozen.