vallog: 継続渡しスタイルCPS

2009/10/19

継続渡しスタイルCPS

1年くらいSchemeやってて継続（渡し、呼び出し）についても何度か読んだり書いたりしてるはずなのに未だに「どんなんだっけ？」となってしまう私です。

「なんでも継続」とか読んで少しだけ書いてみた。

普通の階乗

;; factorial
(define fact
(lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

継続渡し階乗（Continuation Passing Style -> CPS）

(define fact/cps
(lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/cps (- n 1)(lambda (x)
                           (cont (* n x)))))))

やっぱりイメージが沸かないので展開してみた

(fact/cps 5 (lambda (x) x))

(fact/cps (- 5 1)
(lambda (x)((lambda (x) x)(* 5 x))))

(fact/cps (- (- 5 1) 1)
(lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))))

(fact/cps (- (- (- 5 1) 1) 1)
(lambda (x)((lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))) (* 3 x))))

(fact/cps (- (- (- (- 5 1) 1) 1) 1)
(lambda (x)((lambda (x)((lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))))

(fact/cps (- (- (- (- (- 5 1) 1) 1) 1) 1)
(lambda (x)((lambda (x)((lambda (x)((lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))) (* 1 x))))

ということですか。わかりました。わかりません。毎度理解できたつもりですが、数日すると忘れるんだろうな。ということはつまりわかってないのな。

実行時のキャプチャーとか言いますよね、わかります。わかりません。セーブポイントみたいなもんだということですね？現在の環境ごとクロージャにぶち込んでほいほい渡していって必要になってから使うし使わなくても良いし、と。

scheme の「継続」の超てきとうな説明

超てきとうとは書いてありますがわかりややすかったです。「なんでも継続」の最初の方もわかりやすかった。

The Little Schemer のrember&coのところをもっかいやってみよう。というか丸ごと読み直そう。んでThe Seasoned Schemerもちゃんと読もう。

なんかピンとこないんですよね・・・。

あ、ついでにJavaScriptとC#も。改めて書く必要もなく同じコードなんですけどね。なんとなく。C#は気分でgoto使ってみた。

function factCps (n, cont)
{
return n === 0
? cont(1)
: factCps (n - 1, function(x){ return cont(n * x);});
};

factCps(5, function(x){ return x;});

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics;

namespace SampleCallPassingStyle
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Trace.Listeners.Add(new ConsoleTraceListener());
            Trace.WriteLine("Continuation Passing Style Factorial Start");

restart:

            try
            {
                FactCps(decimal.Parse(Console.ReadLine()), 0, i => { Console.WriteLine(i); return i; });
                goto restart;
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
                goto restart;
            }
        }

        public static decimal FactCps(decimal n, decimal nest, Func<decimal, decimal> cps)
        {
            return n == 0
                ? cps(1)
                : FactCps(n - 1, ++nest, i => { Console.WriteLine("i = {0}, n = {1}, cont({0} * {1}), nest = {2}", i, n, nest); return cps(i * n); });

            //return n == 0
            //    ? cps(1)
            //    : FactCps(n - 1, ++nest, i => cps(i * n));
        }
    }
}