処理を保存してみる
前回の続き。今回は「内部イテレータを外部イテレータに手動で変換してみる実験 - terazzoの日記」の、「継続渡し形式を中断可能にする」の部分。
前回はFactとFiboをCPS変換してFactCpsとFiboCpsに書き換えてみたけど、CPS変換前後で再帰関数であることは変わってない。再帰関数は実行すると結果まで一気に計算していく。例えば、FactCpsは
FactCps(10, n => Console.WriteLine("10! = " + n));
を実行すれば、引数で与えられた継続
n => Console.WriteLine("10! = " + n)
までが一気に実行される。
今回は、それをちょっと変更して、
という感じで、再帰関数を呼び出しても、一気に計算が進まないようにしてやる。もはや再帰関数と呼んでいいのか分からんけど。
- クロージャのように使われている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
正直、再帰呼び出しを1ステップずつやってなにが嬉しいのかよくわからない。これがどうやってイテレータの話につながるのか想像できないな...。
つづく。