vallog: 2008/12

2008/12/31

【scheme】1.2.1＠SICP　再帰と反復と遅延演算

大晦日なのに、またまた階乗計算ですが。線形再帰と反復。お陰で遅延評価（遅延演算）がわかったー！計算式の評価の前に式展開が先に行われるということなんだねと思う。以下、SICPよりほぼ写経ですが・・・。一般的な階乗計算関数

;;factorial ;;n! = n * (n - 1) * (n - 2)....3 * 2 * 1
(define factorial
(lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))
(factorial 5);;=> 120

上記関数の実行イメージ

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factoriall 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

こっちの発想はなかった。 1*2*3・・・とやっていって、かける数がパラメータで与えられた回数に達するまで続ける方法。

;;n! = 1 * 2 * 3....
(define factorial2
(lambda (n)
    (define iter
      (lambda (product counter)
        (if (> counter n)
          product
          (iter (* counter product) (+ counter 1)))))
    (iter 1 1)))

(factorial2 5);;=> 120

実行イメージ

(factorial2 5)
(iter 1 1 5)
(iter 1 2 5)
(iter 2 3 5)
(iter 6 4 5)
(iter 24 5 5)
(iter 120 6 5)
120

【scheme】クロージャ

よく見るクロージャのサンプルをSchemeで書いてみた。初期値を取って、呼ばれるたびにインクリメントした値を返す関数を返す関数。こういうの見るとOOPっているの？ってならないか。

(define counter
(lambda (n)
    (lambda ()
      (set! n (+ n 1)) n)))

(define disp
(lambda (s)
    (display s)
    (newline)))

(let ((c (counter 0)))
(disp (c));;=> 1
(disp (c));;=> 2
(disp (c));;=> 3
(disp (c));;=> 4
(disp (c)));;=> 5

(let ((c2 (counter 10)))
(disp (c2));;=> 11
(disp (c2));;=> 12
(disp (c2));;=> 13
(disp (c2)));;=> 14

【scheme】アキュムレータ、局所変数、破壊的代入

ハッカーと画家コンピュータ時代の創造者たち http://stack.nayutaya.jp/book/4274065979 のP.198のアキュムレータを写経したり。

アキュムレータを生成する関数、すなわち、数nを取り、 「数iを取ってnをiだけ増加させ、その増加した値を返す関数」 を返すような関数だ（「増加させる」に注意。ただ足すだけではない。 アキュムレータ（累積機）だから累積させなければ）。

パラメータ：n 戻り値：パラメータ：i 戻り値：nをi増加させて返すを返す

;;=> accumulator
(define accumulator
(lambda (n)
(lambda (i)
(set! n (+ n i)) n)))

;; local variable
(let ((a (accumulator 0)))
(display (a 1))(newline);;=> 1
(display (a 1))(newline);;=> 2
(display (a 3))(newline);;=> 5
(display (a 0))(newline));;=> 5

クロージャってことでいいよねコレ。ついでに、局所変数についても調べてみた。（let）

Schemeも破壊的代入を行う手続きが書けるんだね。（set!）

なんか違和感あるなー、なんとなく、代入って。まぁ話によると、純粋な関数型言語ってHaskellとConcurrentCleanくらいしかないみたいだしね。（純粋関数型言語＝代入なしってこと？）こういうの（display, newline）が冗長だー。こういうのどう書くかなー。

(let ((a (accumulator 0)))
(display (a 1))(newline);;=> 1
(display (a 1))(newline);;=> 2
(display (a 3))(newline);;=> 5
(display (a 0))(newline));;=> 5

変数も代入もまだSICPに出てこない。 SICPってSchemeの入門書ではなくてプログラミングとかコンピュータ科学とかの入門書のはずだよな。一般的には変数とか代入が最初に解説してありそうなもんだけどねｗ変数や代入より関数定義、再帰、レキシカルスコープが先に出てくるんだもんなーｗ

【Scheme】問題1.6＠SICP

なぜ「if」が特殊形式なのか。「new-if」関数を定義して確かめてみるという問題。実際やってみたけど、ピンとこなかった。（ちゃんとifの動作を思い出してればわかったはず）

;;not special syntax. new-if procidure.
(define new-if
(lambda (predicate then-clause else-clause)
    (cond
      (predicate then-clause)
      (else else-clause))))

(new-if (= 2 3) 0 5);;=> 5
(new-if (= 1 1) 0 5);;=> 0

こないだのsqrt内のgood-enough?で使われているifをnew-ifに置き換えるとエラー。ピンとこなかったのでまんまと解答集を見てみる。

(define square
(lambda (x)
    (* x x)))

(define avarage
(lambda (x y)
    (/ (+ x y) 2)))

;; "if" replaced "new-if"
(define sqrt
(lambda (x)
    (define improve
      (lambda (guess)
        (avarage guess (/ x guess))))
    (define good-enough?
      (lambda (guess)
        (< (abs (- (square guess) x)) 0.001)))
    (define sqrt-iter
      (lambda (guess)
        (new-if (good-enough? guess)
          guess
          (sqrt-iter (improve guess)))))
    (sqrt-iter 1.0)))

(sqrt 9);;=> 3.00009155413138

そうだった。 ifはpredicateが真の場合は2つ目のパラメータを評価しないんだった。 new-ifではnew-ifが評価される前にsqrt-iterが評価されて無限再帰ですね。

【scheme】ブロック内スコープ＠SICP

平方根を求めるsqrt関数先日のもの（【scheme】1.1.7 例：Newton法による平方根＠SICP）

(define avarage
(lambda (x y)
(/ (+ x y) 2)))
(avarage 10 20);;=> 15
(avarage 5.0 8.0);;=> 6.5

(define square
(lambda (x)
(* x x)))
(square 5);;=> 25
(square 12);;=> 144

(define improve
(lambda (guess x)
(avarage guess (/ x guess))))
(improve 10.0 5.0);;=> 5.25
(improve 1.5 2.5);;=> 1.5833333333333335

(define good-enough?
(lambda (guess x)
(< (abs (- (square guess) x)) 0.001)))

(define sqrt-iter
(lambda (guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x))))

(define sqrt
(lambda (x)
(sqrt-iter 1.0 x)))

(sqrt 9);;=> 3.00009155413138
(sqrt (+ 100 37));;=> 11.704699917758145
(sqrt (+ (sqrt 2)(sqrt 3)));;=> 1.7739279023207892
(square (sqrt 1000));;=> 1000.000369924366

各関数をsqrt定義内に納めたもの。

;; local scope difinition
(define sqrt
(lambda (x)
    (define square
      (lambda (x)
        (* x x)))
    (define avarage
      (lambda (x y)
        (/ (+ x y) 2)))
    (define improve
      (lambda (guess x)
        (avarage guess (/ x guess))))
    (define good-enough?
      (lambda (guess x)
        (< (abs (- (square guess) x)) 0.001)))
    (define sqrt-iter
      (lambda (guess x)
        (if (good-enough? guess x)
            guess
            (sqrt-iter (improve guess x) x))))
    (sqrt-iter 1.0 x)))
(sqrt 9);;=> 3.00009155413138

sqrtのパラメータxのブロック内スコープ（レキシカルスコープ）を利用したもの。 xを利用した関数を返すようにすればクロージャできそうでつね。

(define square
(lambda (x)
(* x x)))
(define avarage
(lambda (x y)
(/ (+ x y) 2)))

(define sqrt
(lambda (x)
    (define improve
      (lambda (guess)
        (avarage guess (/ x guess))))
    (define good-enough?
      (lambda (guess)
        (< (abs (- (square guess) x)) 0.001)))
    (define sqrt-iter
      (lambda (guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess)))))
    (sqrt-iter 1.0)))
(sqrt 9);;=> 3.00009155413138

2008/12/30

【scheme】スコープ＠ブロック（？）

ブロック内スコープとレキシカルスコープか。

(define x
(lambda ()
    (define y "Hello world")
    (define z
      (lambda ()
        (display y)))
    (z)))
(x);;=> Hello world
;;(y);;=> reference to undefined identifier: y
;;(z);;=> reference to undefined identifier: z

【scheme】こないだのlistで書き忘れた

リストの中身を全部出力したかっただけなんだけどな。こんなことになっちゃった。センスなさすぎﾜﾛﾀ系？

;;list
(define x (list 1 2 3))

;;display list
(define disp-list
(lambda (l)
    (if (not (null? l))
      (begin
        (display (car l))
        (newline)
        (disp-list (cdr l))))))

(disp-list x)
;;=> 1
;;=> 2
;;=> 3

2008/12/29

【scheme】listとcarとcdr

(define x (list 1 2 3))
x;;=> (1 2 3)

(car x);;=> 1
(cdr x);;=> (2 3)

(define y '(1 2 3))

y;;=> (1 2 3)
(car y);;=> 1
(cdr y);;=> (2 3)

2008/12/28

【scheme】コラッツcollatz角谷

「schemeでもコラッツの問題を書いてみよう！」と思ったら、こないだ書いててﾜﾛﾀ。消しゴム系ですね、頭ん中。
【Scheme】SchemeでもCollatz http://ameblo.jp/valvallow/entry-10179274699.html
これがこないだの。

(define (collatz n)
  (display n)
  (newline)
  (if (> n 1)
      (if (even? n)
          (collatz (/ n 2))
          (collatz (+ (* n 3) 1)))))

(collatz 5)
;; =>  5
;; =>  16
;; =>  8
;; =>  4
;; =>  2
=> 1
(collatz 30)
;; =>  30
;; =>  15
;; =>  46
;; =>  23
;; =>  70
;; =>  35
;; =>  106
;; =>  53
;; =>  160
;; =>  80
;; =>  40
;; =>  20
;; =>  10
;; =>  5
;; =>  16
;; =>  8
;; =>  4
;; =>  2
;; =>  1

これが今日書いたの。こないだより悪くなってるような気がするな。

;;collatz
(define collatz
  (lambda (seed f)
    (f seed)
    (cond
     ((<= seed 1))
     ((even? seed)
      (collatz (/ seed 2) f))
     ((odd? seed)
      (collatz (+ 1 (* seed 3)) f)))))

(collatz 5 (lambda (s)(display s)(newline))) ;;=> 5 ;;=> 16 ;;=> 8 ;;=> 4 ;;=> 2 ;;=> 1 ;;=> #t

Y-Combinatorで。
【Scheme】Y-Combinator（Yコンビネータ/不動点演算子） http://ameblo.jp/valvallow/entry-10182574504.html

;;collatz with y-combinator

;;Y is y-combinator
(define Y
  (lambda (f)
    ((lambda (h)(h h))
     (lambda (p)
       (f (lambda (n)((p p) n)))))))

;;collatz
(define collatz
  (lambda (f)
    (lambda (seed)
      (display seed)
      (newline)
      (cond
       ((<= seed 1))
       ((even? seed)
        (f (/ seed 2)))
       ((odd? seed)
        (f (+ 1 (* seed 3))))))))

((Y collatz) 5)
;;=> 5
;;=> 16
;;=> 8
;;=> 4
;;=> 2
;;=> 1
;;=> #t

Y-Combinator、複数パラメータに対応したの書いてみたい。ここが参考になりそう。
ボクノス：Yコンビネータを読み解こう http://d.hatena.ne.jp/tanakaBox/20080203/1202023473

【scheme】解答集＠SICP（計算機プログラムの構造と解釈）

こんなページを発見。

訳者直々の解答集ということでいいのかな？

【scheme】1.1.7 例：Newton法による平方根＠SICP

1.1.7 例：Newton法による平方根＠SICPがよくわからなかったのでとりあえず写経してみた。とりあえず、今回みたいな数学的なことはあまり真剣に読み解こうとはせず進めていこう。

全景

(define avarage
(lambda (x y)
    (/ (+ x y) 2)))

(define square
(lambda (x)
    (* x x)))

(define improve
(lambda (guess x)
    (avarage guess (/ x guess))))

(define good-enough?
(lambda (guess x)
    (< (abs (- (square guess) x)) 0.001)))

(define sqrt-iter
(lambda (guess x)
    (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x))))

(define sqrt
(lambda (x)
    (sqrt-iter 1.0 x)))

(sqrt 9);;=> 3.00009155413138
(sqrt (+ 100 37));;=> 11.704699917758145
(sqrt (+ (sqrt 2)(sqrt 3)));;=> 1.7739279023207892
(square (sqrt 1000));;=> 1000.000369924366

最初の手続。これは名前通りパラメータの平均を返す。

(define avarage
(lambda (x y)
(/ (+ x y) 2)))

(avarage 10 20);;=> 15
(avarage 5.0 8.0);;=> 6.5

これも名前の通りパラメータの２乗を返す。

(define square
(lambda (x)
(* x x)))
(square 5);;=> 25
(square 12);;=> 144

これは？？？「improve」を辞書で調べてもｲﾐﾌ。改良？ http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=Improv&dtype=1&dname=1na&stype=0&pagenum=1&index=03652100

(define improve
(lambda (guess x)
(avarage guess (/ x guess))))

(improve 10.0 5.0);;=> 5.25
(improve 1.5 2.5);;=> 1.5833333333333335

これもなんだろうか。精度の基準だろうとは思う。再帰の終了条件。

(define good-enough?
(lambda (guess x)
(< (abs (- (square guess) x)) 0.001)))

処理の本体。再帰してる。

(define sqrt-iter (lambda (guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))))

ラッパー的な、Facade的な、エントランス的な。

(define sqrt
(lambda (x)
(sqrt-iter 1.0 x)))

【Scheme】問題1.5＠SICP

いまいちよくわからない。

正規順序の場合、先にパラメータが展開されようとして無限に再帰し続けることになるってことでFA?

作用順序の場合は、testが展開されてifのところでxが評価されて0だとわかればyは評価されないので0が帰って正常に処理が終了する・・・・ってことでOK？

SICPのP.9に「解釈系が実際に使っている『引数を評価し、作用させる』方法を作用的順序の評価・・・」ってとこみると、作用的順序が採用されてるのかなーと思っていたら、実際に下記のコード実行したら無限ループなんですけど・・・。

ということは正規順序？よくわからない。ヘルプ・・・・。もうちょっとよく読んでみる；；

(define p
(lambda () (p)))

(define test
(lambda (x y)
(if (zero? x) 0 y))

(test 0 (p))

追記：なんか勘違いしてたみたいだ。こういうことか。

正規順序

;;normal order
(test 0 (p))

((if (zero? 0)
0
(p)));;=> 0

作用順序

;;applicative order
(test 0 (p)) (test 0 (labda () (lambda () ((lambda () (lambda () (lambda ....

ということで、実際に採用されてるのが「作用順序」。「演算子より先に非演算子が評価される」ってことでFA。

【Scheme】問題1.4＠SICP

パラメータbが正なら+負なら-のプロシージャを返す。

処理の結果としてプロシージャも返せますよー、ってことが言いたいのかな？問題文ｲﾐﾌ。

(define a-plus-abs-b (lambda (a b)
((if (> b 0) + -) a b)))
(a-plus-abs-b 1 2);;=> 3
(a-plus-abs-b 1 -2);;=> 3

【scheme】schemeのandでSQLのbetween演算子的な

引数の順序が悪いかな。

(define between
(lambda (min n max)
(and (<= min n) (<= n max))))
(between 1 1 1);;=> #t
(between 1 2 3);;=> #t
(between 2 3 2);;=> #f
(between 4 3 2);;=> #f
(between -1 500 6000000);;=> #t

2008/12/26

【C#】メソッドからメソッド自身を呼ぶ時にメソッド名を使わない。

JavaScriptのarguments.calleeみたいなのはC#でどう書くかなーと。
（メソッドが自分自身を呼ぶには、ということ）
C#3.0以降で書いたこれ↓を基に、C#1.1でやってみる（なぜ1.1）。
【C#】Collatz問題（コラッツ予想・角谷の問題）

これは前回のコード。
CollatzはCollatzの呼び出しを行っている。

using System;

namespace Sample_Collatz2
{
    class Program
    {
        static void Main(string[] args)
        {
            decimal seed;
            decimal.TryParse(Console.ReadLine(), out seed);

            Console.WriteLine();
            Collatz(seed, n => Console.WriteLine(n));
            Main(null);
        }

        static void Collatz(decimal n, Action<decimal> a)
        {
            a(n);

            if (1 < n)
            {
                Collatz(n % 2 == 0 ? n / 2 : n * 3 + 1, a);
            }
        }
    }
}

こっちがC#1.1で書き直したもの。

MethodBase.GetCurrentMethod()で帰ってきたMethodInfoクラスをInvokeすると、たぶん目的のことができてる。

using System;
using System.Reflection;

namespace Sample.Callee
{
	class Class1
	{
		[STAThread]
		static void Main(string[] args)
		{
			try
			{
				Console.WriteLine();
				int i = int.Parse(Console.ReadLine());
				Collatz(i, new Action(Display));
			}
			catch (Exception ex)
			{
				Console.WriteLine(ex.Message);
			}
			finally
			{
				//Main(null);
				MethodBase.GetCurrentMethod().Invoke(
					null, new object[]{null});
			}
		}

		static void Display (object o)
		{
			Console.WriteLine(o);
		}

		delegate void Action (object o);

		static void Collatz (int n, Action a)
		{
			a(n);

			if (1 < n)
			{
				//Collatz (n % 2 == 0 ? n / 2 : n * 3 + 1, a);
				MethodBase.GetCurrentMethod().Invoke(
					null, new object[]{n % 2 == 0 ? n / 2 : n * 3 + 1, a});
			}
		}
	}
}

2008/12/24

【Scheme】Y-Combinator（Yコンビネータ/不動点演算子）

【Scheme】Y-Combinator（Yコンビネータ/不動点演算子）
■Y-Combinator
「Y-Combinator」を理解するために書いたコードを元に、思考の過程を書く。
■参考
記事最下に記載。
■材料
再帰を伴う処理を基に書いていく。
通例通り階乗（http://ja.wikipedia.org/wiki/階乗）を求める「fact」関数を例に取る。
■その前に・・・
Y-Combinatorは何がしたいのか？
・無名（匿名）関数で再帰を行いたい。
⇒ 普通は「fact」関数の定義の中で「fact」呼び出しが行われる。
⇒ 「fact」という名前を使わずに再帰したい。
■注
１）、「;」で始まるコメントは出鱈目な英語です。（DrScheme（http://www.db.is.kyushu-u.ac.jp/enshu/）の日本語表示が気持ち悪いから）
２）、「;=>」は実行結果の出力
まずは与えられた数字の階乗を求める関数、「fact」を定義してみる。

;normal fact
(define fact
(lambda (n)
    (if (zero? n)
    1
    (* n (fact (- n 1))))))
(fact 5) ;=> 120

見慣れた感じ。 Schemeやったことなくても読めるはず。

;gate of normal fact
(define fact-maker
(lambda ()
    (lambda (n)
      (if (zero? n)
      1
      (* n (fact (- n 1)))))))
((fact-maker) 5);=> 120

factを直接呼び出したくない。 fact呼び出しをlambdaで包んで、fact-makerという名前をつけてみる。 factの名前を排除したかったが、結局最後のところでfactを呼び出している。 factへの入り口が変わったに過ぎない。

;receive fact
(define fact-maker
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))
((fact-maker fact) 5);=> 120

さっきfactを包むのに使ったlambdaに引数fを追加して呼び出し時にfactを渡してみる。これでfactは処理の「外」に出た。まだ処理の中にfactの残骸が見える。
(if (zero? n)
1
(* n (f (- n 1))))

;maker receive maker
(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1)))))))
((m m) 5);=>120

ここで、fact-makerはfactを置き換えるために作ったことを思い出してみる。 ((fact-maker fact) 5)を((fact-maker fact-maker) 5)としてみる。
ついでに「fact-maker」を「m」に置き換える（見づらかったので）。
fact-makerはfactを置き換えるためのものなので当然正常に動く。ただし、fact-makerはfactを引数に取っていた。置き換えると、fact-makerはfact-makerを引数に取らなければならない。
よって、fact-makerに渡されたfact-makerは引数fに割り当てられることになる。つまり、(f (- n 1))は((f f) (- n 1))となる。 ((fact-maker fact-maker) (- n 1)) ⇒ ((f f) (- n 1))

((m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1))))))) 5);=>120

呼び出しである((m m) 5)の引数であるmを直接mの中身と置き換えてみる。もちろん正常に動く。

(((lambda (f)
(lambda (n)
    (if (zero? n)
      1
      (* n ((f f) (- n 1))))))
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((f f) (- n 1))))))) 5);=>120

((m m) 5)のmを両方ともmの中身で置き換えてみる。かなり冗長だけど、名前を使わずに再帰できてるっぽい。

; (f 5) equals ((lambda (n) (f n)) 5) ; ((lambda (n) ((f f) n)) 5)
(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n ((lambda (n) ((f f) n)) (- n 1)))))))
((m m) 5);=>120

((f f) (- n 1))の(f f)のところがｶｯｺﾜﾙｲ。 (f (- n 1))にしたい。そのためのステップとして、(fact 5)と((lambda (x) (fact x)) 5)は同じなので、(f f)が(lambda (n) ((f f) n))となる。
(【scheme】schemeのlambdaラムダλ（http://ameblo.jp/valvallow/entry-10182420367.html）を見ればわかるように（わかりにくすぎる）)

(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
        1
        (* n (f (- n 1)))))))

(lambda (n) ((f f) n))を「外」に追い出して、fに渡すようにすると、m自体はこうなる。あとは、呼び出し時に(lambda (n) ((f f) n))を渡すようにすればいい。

((m m) 5)

とりあえず、この右側のmを(lambda (n) ((f f) n))に変えることができればOK。

((m
(lambda (n) ((f f) n))) 5);=> error

これは、(lambda (n) ((f f) n))がその場で評価されようとしてしまうから。

;gate of y-combinator
(lambda (p)
(m (lambda (n) ((p p) n))))

(lambda (n) ((f f) n))をmに渡す部分をlambdaにくるみ、fという名前をpに変更。

((m
(lambda (p)
(m (lambda (n) ((p p) n))))) 5);=> 120

今、((m m) 5)の右側のmを置き換えることに成功したのでこういうことになる。正常に動作。

(((lambda (p)
(m (lambda (n) ((p p) n))))
(lambda (p)
(m (lambda (n) ((p p) n))))) 5);=> 120

次に、((m m) 5)の左側のmも同様に置き換える。正常に動作。

;receive m receive 5
(((lambda (f)
((lambda (p)
(m (lambda (n) ((p p) n))))
(lambda (p)
(m (lambda (n) ((p p) n)))))) m) 5)

次に、mを「外」に追い出したいので、mに変わるfを引けるようにする。ここではまだfを引けるようにlambdaでくくりだしただけで、mは置き換えていない。

;replace m to received f ;this is the y-combinator
(lambda (f)
((lambda (p)
(f (lambda (n) ((p p) n))))
(lambda (p)
(f (lambda (n) ((p p) n))))))

mを外から引いたfに置き換えて完了。これがYコンビネータ（不動点演算子）らしい。 factの部分が完全に消えうせた。つまりfactも「再帰」から開放された。

;receive 5 reveive m to execute y-combinator
(((lambda (f)
((lambda (p)
(f (lambda (n) ((p p) n))))
(lambda (p)
(f (lambda (n) ((p p) n)))))) m) 5);=>120

階乗を求めるmとmの引数となる5を渡す。正常に動作する。

;named Y to y-combinator
(define Y
(lambda (f)
    ((lambda (p)
      (f (lambda (n) ((p p) n))))
    (lambda (p)
      (f (lambda (n) ((p p) n)))))))

Yコンビネータに名前をつける。でも冗長さが残っててｶｯｺﾜﾙｲ。（同じ処理が2回書いてある）

((Y m) 5);=>120
((Y m) 10);=>3628800

;twice ;(lambda (p) ; (f (lambda (n) ((p p) n)))) ; to once
(define Y
(lambda (f)
    ((lambda (h)(h h))
      (lambda (p)
        (f (lambda (n)((p p) n)))))))
((Y m) 5);=> 120

冗長な部分を排除したい。重複部分をlambdaでくくりだす。

;fibonacci
(define fib
(lambda (n)
    (if (<= n 2)
      1
      (+ (fib (- n 1))(fib (- n 2))))))
(fib 10);=> 55

フィボナッチ数列を求める普通の関数。今度はフィボナッチ数列のコードで試してみる。

;Y-Combinator fibonacci
(define fib
(lambda (f)
    (lambda (n)
      (if (<= n 2)
        1
        (+ (f (- n 1))(f (- n 2)))))))
((Y fib) 10);=> 55

正常に動作。
【全景】

;normal fact
(define fact
(lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))
(fact 5) ;=> 120
;gate of normal fact
(define fact-maker
(lambda ()
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1)))))))
((fact-maker) 5)
;receive fact
(define fact-maker2
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n (f (- n 1)))))))
((fact-maker2 fact) 5)
;maker receive maker
(define m
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((f f) (- n 1)))))))
((m m) 5)
((m
(lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((f f) (- n 1))))))) 5)
(((lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((f f) (- n 1))))))
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((f f) (- n 1))))))) 5)
; (f 5) equals ((lambda (n) (f n)) 5)
; ((lambda (n) ((f f) n)) 5)
(define m2
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((lambda (n) ((f f) n)) (- n 1)))))))
((m2 m2) 5)
;(lambda (f)
; (f0 (lambda (n) ((f f) n))))
; is one of fact-maker
(define f0
(lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n (f (- n 1)))))))
;gate of y-combinator
(lambda (p)
(f0 (lambda (n) ((p p) n))))
((m
(lambda (p)
    (f0 (lambda (n) ((p p) n))))) 5)
(((lambda (p)
(f0 (lambda (n) ((p p) n))))
(lambda (p)
(f0 (lambda (n) ((p p) n))))) 5)
;receive f0 receive 5
(((lambda (f)
((lambda (p)
     (f0 (lambda (n) ((p p) n))))
   (lambda (p)
     (f0 (lambda (n) ((p p) n)))))) f0) 5)
;replace f0 to received f
;this is the y-combinator
(lambda (f)
((lambda (p)
     (f (lambda (n) ((p p) n))))
   (lambda (p)
     (f (lambda (n) ((p p) n))))))
;receive 5 reveive f0 to execute y-combinator
(((lambda (f)
((lambda (p)
     (f (lambda (n) ((p p) n))))
   (lambda (p)
     (f (lambda (n) ((p p) n)))))) f0) 5)
;named Y to y-combinator
(define Y
(lambda (f)
    ((lambda (p)
       (f (lambda (n) ((p p) n))))
     (lambda (p)
       (f (lambda (n) ((p p) n)))))))
((Y f0) 5)
((Y f0) 10)
;twice
;(lambda (p)
;       (f (lambda (n) ((p p) n))))
; to once
(define Y2
(lambda (f)
    ((lambda (h)(h h))
     (lambda (p)
       (f (lambda (n)((p p) n)))))))
((Y2 f0) 5)
;fibonacci
(define fib
(lambda (n)
    (if (<= n 2)
        1
        (+ (fib (- n 1))(fib (- n 2))))))
(fib 10)
;Y-Combinator fibonacci
(define fib2
(lambda (f)
    (lambda (n)
      (if (<= n 2)
          1
          (+ (f (- n 1))(f (- n 2)))))))
((Y fib2) 10)

【結論】
Yコンビネータはすごい。
何がすごいか、言語化できない。
ということは、まだ理解できていない。ということ。
求め方、組み方はなんとなく理解できた。
他の言語でも組める気はする。
JavaScript、Ruby、C#で試してみたい。
Yコンビネータの何がすごいのか、言語化できるように理解を深めたい。
Schemeの勉強になったし、Y-Combinatorの求め方もわかったし、遅延評価についてはまだイメージがぼやけってるけど、少しだけ想像できるようになってラッキー♪
なにより、すごくおもしろかったｗ
【参考】
[C#]Y Combinatorが凄すぎる！
http://d.hatena.ne.jp/yuji1982/20080124/1201177935
⇒ 発端の記事。
ちょうどyuji1982さんとTwitterなんかで話すようになったころ。
2008年の1月くらいにこの記事見て、yuji1982さんが遠い世界の人だと感じた。
Y コンビネータって何？ - IT戦記
http://d.hatena.ne.jp/amachang/20080124/1201199469
⇒ もう一つの発端。
世間はこれで火がついたっぽい。
yuji1982のブックマーク / Y combinator (11)
http://b.hatena.ne.jp/yuji1982/Y%20combinator/
⇒ 発端となったyuji1982さんのYコンビネータに関するブックマーク。
Y Combinator
http://www.loveruby.net/ja/misc/ycombinator.html
⇒ 今回は主にここを参考にした。
Scheme
Yコンビネータを読み解こう
http://d.hatena.ne.jp/tanakaBox/20080203/1202023473
⇒ 後で知ったページ。ここが一番わかりやすい。
Scheme
Y combinator on Scheme
http://fixedpoint.jp/2007/02/14/y.html
⇒ Scheme
不動点演算子ふたたび
http://d.hatena.ne.jp/sumii/20051203/1133575324
⇒ Scheme
C# 3.0 と不動点演算子
http://d.hatena.ne.jp/NyaRuRu/20070722#1
⇒ C#
以前から思ってたけど、異世界の人。
Yコンビネータができるまで（C#）
http://faroffsea.blogspot.com/2008/09/yc.html
⇒ C#
C#でYコンビネータ
http://blog.inomata.lolipop.jp/?eid=815474
⇒ C#
Recursive lambda expressions
http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx
⇒ C#
不動点オペレータについて
http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/fix.html
⇒ Scheme
ホワット・ア・ワンダフル・ワールド
http://alohakun.blog7.fc2.com/blog-entry-894.html
⇒ 直接は関係ない。
そろそろ分かっておきたいY Combinator
http://d.hatena.ne.jp/authorNari/20081130/1227977113
⇒ Ruby
Yコンビネータメモ
http://d.hatena.ne.jp/gotin/20080127/1201372491
⇒ JavaScript
Yコンビネータ復習
http://faroffsea.blogspot.com/2008/02/y.html
⇒ Common Lisp
MIT（マサチューセッツ工科大学）の盾
http://groups.csail.mit.edu/mac/projects/scheme/
⇒ SICPはここの教科書らしい。

【scheme】schemeのlambdaラムダλ

日本語がｶｵｽだ。
Schemeのlambda

;平方する関数「square」
(define square
(lambda (n)
(* n n)))
(square 5);=> 25

;squareの実行をlambdaで包んで別名をつけてみる
(define f
(lambda (n)
(square n)))
(f 5);=> 5

;squareという名前が付いていた中身をsquareと置き換える
(define f
(lambda (n)
((lambda (n)
(* n n)) n)))
(f 5);=>25

;fという名前が付いていた中身をfと置き換える
((lambda (n)
((lambda (n)
(* n n)) n))
5);=> 25

;無駄なlambdaを排除
((lambda (n)
(* n n)) 5);=> 25

;これと同じ
((lambda (n)
(square n)) 5);=> 25

;これとも同じ
((lambda (n)
(f n)) 5);=> 25

;これとも同じ
(square 5);=> 25

;これとも同じ
(f 5)
(* 5 5)
25

2008/12/17

【C#】キーボードショートカット（ホットキー）割り当て

Windowsアプリケーションでショートカット・キーを割り当てるには？
http://www.atmarkit.co.jp/fdotnet/dotnettips/208winshrtcutkey/winshrtcutkey.html

絶対現場主義Visual C#実践講座―開発の現場から生まれた実践テクニック&TIPS集

【C#】Collatz問題（コラッツ予想・角谷の問題）

以前書いた記事を読んで見たら馬鹿げたコードを書いていて恥ずかしかったので、今ならどうかくか。
ザッとっ書いてみた。

wikipedia：コラッツの問題
 http://ja.wikipedia.org/wiki/コラッツの問題

using System;

namespace Sample_Collatz2
{
    class Program
    {
        static void Main(string[] args)
        {
            decimal seed;
            decimal.TryParse(Console.ReadLine(), out seed);

            Console.WriteLine();
            Collatz(seed, n => Console.WriteLine(n));
            Main(null);
        }

        static void Collatz(decimal n, Action<decimal> a)
        {
            a(n);

            if (1 < n)
            {
                Collatz(n % 2 == 0 ? n / 2 : n * 3 + 1, a);
            }
        }
    }
}

【Scheme】問題1.3＠SICP【Lisp】

問題1.3
3つの数を引数に取りその中の大きいもの二つの平方の和を返す手続きを定義せよ。

:再帰でいってみよー
(define (square x)
(* x x))

(define (sum-of-bigpair a b c)
(if (and (< a b)(< a c))
    ;(+ (* b b)(* c c))
    (+ (square b)(square c))
    (sum-of-bigpair b c a)))

(sum-of-bigpair 1 2 3) ; => 13
(sum-of-bigpair 5 6 2) ; => 61
(sum-of-bigpair -1 -2 -3) ; => 5

絶対もっとスマートな解があるだろ。
でも、ここまでで出てきたのは関数定義と条件分岐だけだし・・・
あー、あとandとorか。（論理和、論理積）
馬鹿正直に書いたらif文で書くことになる＾＾；
（最初、まんまとif文で書いた）
解答を探してみたら、こんなページ発見。
いろんな考え方があるんだねー。考え方がわかりやすく書いてあっておもしろい＞＜

こういう解答をSICPにも載せてくれりゃーいいのに。
SICP練習問題1.1～1.3
http://blog.ajiyoshi.org/Entry/275/

＞全部足してから一番小さいのだけ引く
とか、なるほど。

【Scheme】【Lisp】携帯電話で使えるiアプリすぷ

こ、これは・・・！？

携帯電話で使える iアプリすぷ
http://www.yuasa.kuis.kyoto-u.ac.jp/~yuasa/jakld-i/jakld-jssst.pdf
*注、PDF直リンク

(TUT-)Scheme入門
http://www.yuasa.kuis.kyoto-u.ac.jp/~hiraisi/files/tus-lecture.pptx
*注、pptx直リンク
↑これに載ってた。

[追記]
ケータイで動く i アプリすぷ iαpplisp
http://jp.franz.com/base/seminar/2006-11-22/SeminarNov2006-yuasa.pdf
[追記2]
docomo携帯で下記URLからダウンロード可能！
http://ryujin.kuis.kyoto-u.ac.jp/~yuasa/jakld-i/

試しに、
(define h "hello")
h
ってして、evalってしたら・・・
Debug Windowに "hello"
すげーな！最近は携帯アプリでプログラミングっすか！？

【Scheme】SchemeでもCollatz

wikipedia：コラッツの問題

http://ja.wikipedia.org/wiki/コラッツの問題

ということでSchemeでも今できる範囲で書いてみた。
きっとﾋﾄﾞｲのだろうけど。。

(define (collatz n)
  (display n)
  (newline)
  (if (> n 1)
    (if (even? n)
      (collatz (/ n 2))
      (collatz (+ (* n 3) 1)))))
(collatz 5)
;=> 5
;=> 16
;=> 8
;=> 4
;=> 2
;=> 1