処理を保存してみる

C#

前回の続き。今回は「内部イテレータを外部イテレータに手動で変換してみる実験 - terazzoの日記」の、「継続渡し形式を中断可能にする」の部分。
前回はFactとFiboをCPS変換してFactCpsとFiboCpsに書き換えてみたけど、CPS変換前後で再帰関数であることは変わってない。再帰関数は実行すると結果まで一気に計算していく。例えば、FactCpsは

FactCps(10, n => Console.WriteLine("10! = " + n));

を実行すれば、引数で与えられた継続

n => Console.WriteLine("10! = " + n)

までが一気に実行される。

今回は、それをちょっと変更して、

という感じで、再帰関数を呼び出しても、一気に計算が進まないようにしてやる。もはや再帰関数と呼んでいいのか分からんけど。

あと、JavaからC#への移植にあたって、

  • クロージャのように使われているJavaの無名クラスのインスタンスは、C#のラムダ式で置き換えられる（多分）
  • Javaで使われている無名クラスが、フィールドを持つ場合や複数のメソッドを持つ場合、C#ラムダ式では模倣できない（多分）
  • C#ではJavaのような無名クラスの使い方ができない（多分）

なので、ResultHandlerIterable、ResultHandlerIterableTopを実装する無名クラスに相当するものをあらかじめ定義した（以下のContinuationHolderクラスとContinuationHolderTopクラスを参照）。CpsWrapperを実装する無名クラスはフィールドを持たず、メソッドが1個しかないのでActionで置き換えた。クラスやインターフェースの名前は適当に変更した。

ということでソースコード。

まずは、ResultHandlerIterableに相当するIContinuationHolderと、ResultHandlerIterableを実装する無名クラスに相当するContinuationHolder。

interface IContinuationHolder
{
  // 継続を実行
  void Call(int result);
  // 次の処理を保存
  void SetNext(Action thunk);
}

class ContinuationHolder : IContinuationHolder
{
  Action<int> _call;
  IContinuationHolder _contHolder;

  public ContinuationHolder(Action<int> call, IContinuationHolder contHolder)
  {
    _call = call;
    _contHolder = contHolder;
  }

  public void Call(int result)
  {
    _call(result);
  }

  public void SetNext(Action thunk)
  {
    // 次の処理を保存。
    // 最終的にはIContinuationHolderTopのSetNextにたどりつく。
    _contHolder.SetNext(thunk);
  }
}

次に、ResultHandlerIterableTopに相当するIContinuationHolderTopと、ResultHandlerIterableTopを実装する無名クラスに相当するContinuationHolderTopクラス。

interface IContinuationHolderTop : IContinuationHolder
{
  Action GetNext();
}

class ContinuationHolderTop : IContinuationHolderTop
{
  Action<int> _call;

  // 次の処理の正体
  Action _thunk;

  public ContinuationHolderTop(Action<int> call)
  {
    _call = call;
  }

  public void Call(int result)
  {
    _call(result);
  }

  public void SetNext(Action thunk)
  {
    _thunk = thunk;
  }

  public Action GetNext()
  {
    return _thunk;
  }
}

thunkを取り出して実行するメソッド

static void Run(IContinuationHolderTop resultHandler)
{
  Action thunk = null;
  while (null != (thunk = resultHandler.GetNext()))
  {
    thunk();
  }
}

以上を踏まえて...

factCps()を中断可能に変更

static void RunFactCpsIterable()
{
  IContinuationHolderTop contHolder =
    new ContinuationHolderTop(n => Console.WriteLine("10! = " + n));
  FactCpsIterable(10, contHolder);
  Run(contHolder);
}

static void FactCpsIterable(int n, IContinuationHolder contHolder)
{
  if (n == 0)
  {
    contHolder.SetNext(null);
    contHolder.Call(1);
  }
  else
  {
    Action<int> cont = result => contHolder.Call(n * result);
    Action thunk =
      () => FactCpsIterable(n - 1, new ContinuationHolder(cont, contHolder));
    contHolder.SetNext(thunk);
  }
}

fiboCps()を中断可能に変更

static void RunFiboCpsIterable()
{
  IContinuationHolderTop contHolder =
    new ContinuationHolderTop(n => Console.WriteLine("10th Fibonacci number = " + n));
  FiboCpsIterable(10, contHolder);
  Run(contHolder);
}

static void FiboCpsIterable(int n, IContinuationHolder contHolder)
{
  if (n == 1 || n == 2)
  {
    contHolder.SetNext(null);
    contHolder.Call(1);
  }
  else
  {
    Action thunk =
      () => FiboCpsIterable(n - 1,
          new ContinuationHolder(
            a => FiboCpsIterable(n - 2,
              new ContinuationHolder(
                b => contHolder.Call(a + b),
                contHolder)),
            contHolder));
    contHolder.SetNext(thunk);
  }
}

実際にやってみた

http://ideone.com/08dTZ
正直、再帰呼び出しを１ステップずつやってなにが嬉しいのかよくわからない。これがどうやってイテレータの話につながるのか想像できないな...。
つづく。