vallog: Scheme 紙面プログラミング

紙面で Scheme プログラミングしてみました。
帰ってから、実際に動かしたコードは下の方に掲載しました。

なぜこんなことをしたのか

手元にノートしかない状態に長時間置かれたためです。結構、オススメかもしれません。

なぜ Y Combinator なのか

他に適当なネタが思いつきませんでした。すぐ書けるようなものだと、暇つぶしになりませんし・・・。

Y Combinator については、以下の記事を見たときの衝撃からか、何かと気になる存在です。

Y コンビネータって何？ - IT戦記

The Little Schemer, 4th Edition 含め、何度も書いているので、どういうものか理解できている（つもり）です。

vallog: Y Combinator

いつも Web 上の解説を読んだり、The Little Schemer, 4th Edition のやり方を真似てやっていました。
しかし、どれもしっくりこないので、自力で、自分の頭で考えてやってみました。

やってみてどうだったか

紙でいけます。さすが黒板言語。意外と楽しめます。紙面でやるネタが他にも欲しくなりました。
括弧の対応がすごく難しいですね。しばらくすると慣れてきます。

lambda は ^ （カレット）で書きました。lambda は紙に書くには長すぎました。

結果

階乗から Y Combinator を取り出せ（導き出せ）ました。

目的は、「再帰」の部分と「階乗」の部分を分離すること、と考えて良いのかもしれません。
分離した「再帰」に「階乗」の部分を引数で渡せるようにする、とも言えると思います。
もしくは、「再帰」を一般化するとか「抽象化する」でも良いのかもしれません。

本当の目的はよくわかりません。たぶんλ計算の本を読むと分かるのだと思います。

これができたからといって、特にお得なことはありません。知りません。ですが、頭の体操としては非常におもしろいです。私は好きです。

コード

ではまず、普通の階乗を定義します。

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

	(f 5)

view raw y00.scm hosted with ❤ by GitHub

意外とここが一番難しいかもしれません。階乗の定義から手続き名を取り去ります。つまり define を使わないわけですが、名前が無いと再帰できませんよね。
名前を付けるには引数にしてしまえば良い、ということです。ある意味ここが分かれば、もうできたも同然です。ここが頭の中で動かなければ、これ以降が厳しいかもしれません。自分を呼び出す自分に自分を渡す、みたいな。

	;; 1
	((lambda (f)
	(f f))
	(lambda (f)
	(lambda (n)
	(if (zero? n) 1
	(* n ((f f)(- n 1)))))))

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

view raw y01.scm hosted with ❤ by GitHub

次に、(f f) の部分を f と書けるようにしたいと思います。ここでは、引数を一つ取る無名関数で包んでしまえば良いです。すると、それを丸ごと外から渡すことができるようになります。(f f) → (lambda (x)((f f) x)) 。

	;; 2
	((lambda (f)
	(f f))
	(lambda (f)
	(lambda (n)
	(if (zero? n) 1
	(* n ((lambda (x)
	((f f) x))(- n 1)))))))

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

view raw y02.scm hosted with ❤ by GitHub

2 で包んだ (lambda (x)((f f) x)) を外から渡せるようにしたいと思います。(lambda (f)(lambda (n) ... の関数をさらに無名関数で包んで、その中で引数に (lambda (x)((f f) x)) を渡してあげれば良いですね。f のままでも良いのですが、紛らわしいので f を g にしました。これで内側の f には (lambda (x)((g g) x)) が入るようになります。

	;; 3
	((lambda (f)
	(f f))
	(lambda (g)
	((lambda (f)
	(lambda (n)
	(if (zero? n) 1
	(* n (f (- n 1))))))
	(lambda (x)
	((g g) x)))))


	;; test
	(((lambda (f)
	(f f))
	(lambda (g)
	((lambda (f)
	(lambda (n)
	(if (zero? n) 1
	(* n (f (- n 1))))))
	(lambda (x)
	((g g) x))))) 5)

view raw y03.scm hosted with ❤ by GitHub

そうすると、内側の (lambda (f) ... がそのまま「階乗」の部分です。これを分離するのが目的ですから、一番外側で外部から引数として受け取るようにしてあげれば良いです。良い名前が思い浮かばなかったので、concrete の c にしました。できあがり。

	;; 4
	((lambda (c)
	((lambda (f)
	(f f))
	(lambda (g)
	(c (lambda (x)
	((g g) x))))))
	(lambda (f)
	(lambda (n)
	(if (zero? n) 1
	(* n (f (- n 1)))))))

	;; test
	(((lambda (c)
	((lambda (f)
	(f f))
	(lambda (g)
	(c (lambda (x)
	((g g) x))))))
	(lambda (f)
	(lambda (n)
	(if (zero? n) 1
	(* n (f (- n 1))))))) 5)

view raw y04.scm hosted with ❤ by GitHub

単一引数しか受け取れないのもアレなので、可変長引数に対応してみようとしました。たぶん、できたのではないかと思います。apply してあげれば良いです。テストでアキュムレータを第二引数に取る階乗を渡してみましたが、動いているようですね。

	;; 5
	((lambda (c)
	((lambda (f)
	(f f))
	(lambda (g)
	(c (lambda x
	(apply (g g) x))))))
	(lambda (f)
	(lambda (n acc)
	(if (zero? n) acc
	(f (- n 1)(* n acc))))))


	;; test
	(((lambda (c)
	((lambda (f)
	(f f))
	(lambda (g)
	(c (lambda x
	(apply (g g) x))))))
	(lambda (f)
	(lambda (n acc)
	(if (zero? n) acc
	(f (- n 1)(* n acc)))))) 5 1)

view raw y05.scm hosted with ❤ by GitHub

これで「再帰」と「階乗」が分離できました。この「再帰」の部分が Y Combinator ということで良いと思います。

あとは、名前を付けるなりして動かしてみます。

	(define Y
	(lambda (c)
	((lambda (f)
	(f f))
	(lambda (g)
	(c (lambda x
	(apply (g g) x)))))))

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

	((Y fact-acc) 10 1)
	; -> 3628800

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

	((Y fact) 15)
	; -> 1307674368000