2009/10/19

継続渡しスタイルCPS

WS0815

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))))

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

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

 

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

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

 

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

 

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

 

JS

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

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

 

C#

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));
        }
    }
}

The Little Schemer

The Little Schemer

posted with amazlet at 09.03.30

Daniel P. Friedman Matthias Felleisen
Mit Pr
売り上げランキング: 16078

おすすめ度の平均: 5.0

5 小さなScheme処理系で学ぶ数学基礎理論
5 Schemeが好きになります
5 英語であるのが苦痛にならない楽しさ
5 面白いスタイル

Amazon.co.jp で詳細を見る

The Seasoned Schemer

The Seasoned Schemer

posted with amazlet at 09.03.30

Daniel P. Friedman Matthias Felleisen
Mit Pr
売り上げランキング: 18883

おすすめ度の平均: 5.0

5 Little Schemer とセットで

Amazon.co.jp で詳細を見る

0 件のコメント:

コメントを投稿