星田さんの記事に対するコメント。
結論から言うと、
まあ片っ端からCPSで動くのを書いていけば近いうちに心底理解出来る・・かな？
その通り。片っ端から書いていけばいい。
ただ、まぁ確かにコツはあるんだ。
と言うんでテクニック的な話。
実はここ数日、継続渡しの学習をしてます。フィボナッチのCPS版・・うーん？これはいきなり複雑すぎるので基本から行こうｗ
最初の例はフィボナッチ数列のあまりにも「教科書的な」再帰のコードだ。
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
僕ならこうやってCPSへと持っていく。
1. 大元の関数の引数を増やす。
つまりこうだよね。
(define (fib n k) ; ここに引数kを付け足す
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
2. ベースケースでkが結果を受け取るようにする。
つまりこうだ。
(define (fib n k)
(if (< n 2)
(k n) ;; 引数kが結果を受け取るようにする
(+ (fib (- n 1)) (fib (- n 2)))))
3. 再帰の一番内側を「末尾再帰なので」引っ張り出す。
次はこうしちゃう。
(define (fib n k)
(if (< n 2)
(k n)
(fib (- n 2) ;; 再帰の一番奥の部分
(+ (fib (- n 1)) )))
何も考えずに、再帰の「一番奥にある」ブツを機械的に引っ張り出しちまう。
4. (lambda(u)... で残りと繋ぐ
ここも機械的に(lambda (u) ... と置く。
(define (fib n k)
(if (< n 2)
(k n)
(fib (- n 2) (lambda (u) ; 機械的に(lambda (u) を打ち込む
(+ (fib (- n 1)) )))
5. 3. と同様に + の内側にある再帰関数を外側へ引っ張り出す。
つまりこうだ。
(define (fib n k)
(if (< n 2)
(k n)
(fib (- n 2) (lambda (u)
(fib (- n 1) ; 内側にある再帰関数を外側へ出す
(+ ) )))
6. 4.と同様に(lambda (v) ... で機械的に繋ぐ
つまりこういうこった。
(define (fib n k)
(if (< n 2)
(k n)
(fib (- n 2) (lambda (u)
(fib (- n 1) (lambda (v) ; 機械的に(lambda (v) を打ち込む
(+ ) )))
7. fib (- n 2) と言う情報はuに渡され、fib (- n 1) と言う情報はv に渡されている
これは言い換えると
- u = fib (- n 2)
- v = fib (- n 1)
と言う事だ。元々のフィボナッチ数列が
(+ (fib (- n 1)) (fib (- n 2)))
である以上、等価性から
(+ u v)
が結果になる事が分かる。
そしてこれをkに受け渡せば良い。従って
(define (fib n k)
(if (< n 2)
(k n)
(fib (- n 2) (lambda (u)
(fib (- n 1) (lambda (v)
(k (+ u v))))))))
が嫌でもCPSスタイルとなる。
なんでAddのCPS版はLambdaがいらないのか？
平たく言うと、それは再帰関数じゃないから。
四則演算他、単純な基礎関数は全部そうなる。
詳しくはまたもやSchemeとActor理論を参照の事。
ちなみに、add-cpsを使うとフィボナッチのCPSは、
(define (add-cps x y cont)
(cont (+ x y)))(define (fib n k)
(if (< n 2)
(k n)
(fib (- n 2) (lambda (u)
(fib (- n 1) (lambda (v)
(add-cps u v k)))))))
となって、基本関数も全部CPSにすると、
(define (add-cps x y cont)
(cont (+ x y)))
(define (<-cps x y cont)
(cont (< x y)))
(define (sub-cps x y cont)
(cont (- x y)))
(define (fib n k)
(<-cps n 2
(lambda (u)
(if u
(k n)
(sub-cps n 2 (lambda (v)
(fib v (lambda (w)
(sub-cps n 1 (lambda (x)
(fib x (lambda (y)
(add-cps w y k)))))))))))))
となる・・・・・・まぁ、ちとやり過ぎかも(笑)。
結局色々と書いてみないと理解できないので、手当たり次第にCPS方式に直してみる
例えばpowも再帰で直球勝負で書くと
(define (pow x n)
(if (zero? n)
1
(* x (pow x (- n 1)))))
となるだろう(注: どんな数の0乗も1になる、ということに留意・※1)。
1. 大元の関数の引数にcontを付け足す
こういう事だ。
(define (pow x n cont) ; 引数にcontを増やす
(if (zero? n)
1
(* x (pow x (- n 1)))))
2. ベースケースの返り値をcontに受け渡す
こういう事。
(define (pow x n cont)
(if (zero? n)
(cont 1) ; 返り値をこう改造する
(* x (pow x (- n 1)))))
3. 再帰部分を括りだす
こういう事だ。
(define (pow x n cont)
(if (zero? n)
(cont 1)
(pow x (- n 1) ; 再帰部分を括りだす
(* x ))))
4. 機械的に(lambda (u) ... を付け足す
こういう事。
(define (pow x n cont)
(if (zero? n)
(cont 1)
(pow x (- n 1) (lambda (u) ; lambda (u) を機械的に挿入する
(* x ))))
5. uにはpow x (- n 1)の情報が詰まってる
ということは暫定的には
- u = pow x (- n 1)
だと言う事。と言う事は
- (* x (pow x (- n 1))) = (* x u)
なんで、これをcontへ受け渡せば良い。
従って、
(define (pow x n cont)
(if (zero? n)
(cont 1)
(pow x (- n 1) (lambda (u)
(cont (* x u))))))
となる。
また、
(define (zero?-cps n cont)
(cont (zero? n)))
(define (mul-cps x y cont)
(cont (* x y)))
を設定すると、
(define (pow x n cont)
(zero?-cps n
(lambda (u)
(if u
(cont 1)
(sub-cps n 1 (lambda (v)
(pow x v
(lambda (w)
(mul-cps x w cont)))))))))
とこれも大げさにする事が出来る。
オシマイ。
※1: どんな数でも0乗は1になる、ってのはエラい人がうんうんうなって計算して発見したわけじゃあない。単に人がそう決めただけ、だ。理由はその方が便利だから。
ここで衝撃の事実を話すと、数学は自然科学の王者、と思われてるが、実の事を言うと、数学自体は自然科学でもなんでもなくって、実態は人工科学と言って良い。人がルールを決めてそのルールに則った時何が発見されるのか、と言うゲームなんだ。だから基礎としては「何故?」は来ない。D&Dのルールブックを買って、そのルールに対して「何故?」は生じないだろう。「そういうゲームだからだ」としか言いようがない。「決められたモノ」には従うしかないんだ。数学とはそういうものだ。
数学教育に於いて、実はこの「本質的には人工科学だ」と言う事は、ある種意図的に教えない事になっている(笑)。だから何らかの基礎的な事を「理解出来ない」と「頭が悪い」と思い込むが、実際は例えば野球のルールブックを覚える気があるのかないのか、程度の話でしかないんだ(笑)。根本的なトコでは頭の良さは全く関係がない。
つまり「人が決めた事を延々と学ぶ」と言う意味に於いては「数学なんて役に立たない」と言うのは、D&Dのルールブックを覚えたからと言って社会生活に役立たない、と言う事と意味的には全く同じで「その通り」なんだ。しかも数学は「何も規定しない」。数学そのものを学んでも役に立たない、ってのはその通りだ。
例えば「長さを測る」「お金を数える」「面積を計算する」と言うのは数学そのものではない。xメーターyセンチ、と数学で言う「長さ」は直接は関係ねぇんだ実は(笑)。xメーターyセンチに数学で言う「長さ」を適用しようと「我々が決めて」、そこで初めて「現実的な意味が生じる」と言うのがホントのトコで、つまり、この範囲は数学そのものじゃなくって「応用数学」なんだ。
このように、小学生レベルから「数学の抽象概念」を現実に適用すると・・・と言うような教授法を行えば、すんげぇややこしい話になるし、厨二病こじらせてる年代だと色々と抽象的な事を教えても反発するか、逆に抽象的な世界に入り込み過ぎて帰ってこれなかったりするんで(笑)、要するにこの辺の話は「流して」、大学の数学科で数学専攻の人間が初めてそこで学ぶような話だったりする(笑)。
いずれにせよ、「数学は実生活に役立たない」と言うのは実は○だ。役立つ/役立たないと言うのは純数学の話じゃなくって「応用数学」の範疇の話であり、かつ応用数学そのものはやっぱり純数学ではないのである。
