オンラインSICP読書女子会 #14 (2.1.3-2.1.4)
2.1.3 (ex-2.4 .. ex-2.6) まで＞＜。
2.1.3 データとは何か
メッセージパッシングってメソッド呼び出しの別解釈でも聞いたことある！
cons/car/cdr やら + やらの組み込み関数置き換えちゃうと元のが使えなくて困るけれど,
組み込み関数の方を直接呼び出す方法とかないのかな…?
ex-2.4 lambda による cons の実装
; [ex-2.4.scm]
(define (ex-2.4)
(print "(car (cons 10 20))")
(print "; ==> " (car (cons 10 20)))
(print "(cdr (cons 10 20))")
(print "; ==> " (cdr (cons 10 20)))
#t)
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
実行結果:
gosh> (ex-2.4)
(car (cons 10 20))
; ==> 10
(cdr (cons 10 20))
; ==> 20
ex-2.5. 2**a * 3 ** b による cons の実装
なんだかオーダー受けた時に素数を掛けあわせた数だけ覚えておけば, それを素因数分解すれば簡単にオーダーの種類と数に戻せるっていうネタを思い出しました＝ω＝
; [ex-2.5.scm]
(define (ex-2.5)
(print "(car (cons 10 20))")
(print "; ==> " (car (cons 10 20)))
(print "(cdr (cons 10 20))")
(print "; ==> " (cdr (cons 10 20)))
#t)
(define (cons x y)
(* (expt 2 x) (expt 3 y)))
(define (div-times a b)
(define (iter tmp result)
(if
(= (remainder tmp b) 0)
(iter (/ tmp b) (+ result 1))
result))
(iter a 0))
(define (car z)
(div-times z 2))
(define (cdr z)
(div-times z 3))
gosh> (ex-2.5)
(car (cons 10 20))
; ==> 10
(cdr (cons 10 20))
; ==> 20
#t
ex-2.6. church 数
チャーチ数！
lambda のなかに lambda はなかなかうまく把握できない＞＜。
; [ex-2.6.scm]
(define (ex-2.6)
(print "(church-to-integer zero)")
(print ";==> " (church-to-integer zero))
(print "(church-to-integer (add-1 zero))")
(print ";==> " (church-to-integer (add-1 zero)))
(print "(church-to-integer (add-1 (add-1 zero)))")
(print ";==> " (church-to-integer (add-1 (add-1 zero))))
(print "(church-to-integer (add-1 (add-1 (add-1 zero))))")
(print ";==> " (church-to-integer (add-1 (add-1 (add-1 zero)))))
(newline)
(print "(church-to-integer one)")
(print ";==> " (church-to-integer one))
(print "(church-to-integer two)")
(print ";==> " (church-to-integer two))
(newline)
(print "(church-to-integer (add one two))")
(print ";==> " (church-to-integer (add one two)))
(print "(church-to-integer (add (add one two) one))")
(print ";==> " (church-to-integer (add (add one two) one)))
(print "(church-to-integer (add (add one two) two))")
(print ";==> " (church-to-integer (add (add one two) two)))
#t)
(define (church-to-integer cn)
(define (int-inc n)
(+ n 1))
((cn int-inc) 0))
; church-number :: (a -> a) -> (a -> a)
; チャーチ数自体は2つの引数 g と initial-value をとる関数 `g -> initial-value -> a`.
; `g` は任意の変換関数 `a -> a`
; `initial-value` は適当な初期値.
;
; zero :: church-number
(define zero
(lambda (_f) ; church 数自体は lambda.
; チャーチ数の zero とは, initial-value に対して
; g を 0 回適用する手続き.
; つまり zero の本体は, initial-value をそのまま返す手続き.
(lambda (x)
; zero の実体.
x
)
)
)
; zero の次は one …にいくとみせかけて「1を足す処理」の定義.
; これがあれば one = (add-1 zero) で作れるし,
; 任意の自然数も繰り返せばできるから?
;
; add-1 :: church-number -> church-number
(define (add-1 n)
; n :: 1を足す対象の数. これ自体も church-number.
(lambda (f) ; church 数自体はいつでも lambda.
(lambda (x)
; 一行でかくとこれだけ:
; (f ((n f) x))
; もうちょっとばらしてかいてみる:
;
; n に対してf, x を適用することで具象化して得られた結果.
(define n-evaluated ((n f) x))
; さらにもう一回 f を適用した結果が, 「1を足す」処理の実体.
(f n-evaluated)
)
)
)
; one :: church-number
;
; one = (add-1 zero)
; > (add-1 n) = (lambda (f) (lambda (x) (f ((n f) x))))
; (lambda (f) (lambda (x) (f ((zero f) x))))
; > zero = (lambda (_f) (lambda (x) x))
; (lambda (f) (lambda (x) (f (((lambda (_f) (lambda (x) x)) f) x))))
; >> ''''''''''''''''''''''''''''''''
; ; この部分を適用して縮退してみる.
; >> ((lambda (_f) (lambda (x) x)) f)
; >> (lambda (x) x)
; >> ,,,,,,,,,,,,,,
; (lambda (f) (lambda (x) (f ((lambda (x) x) x))))
;
; ; さらに縮退.
; (lambda (f) (lambda (x) (f ((lambda (x) x) x))))
; >> ''''''''''''''''''
; >> ((lambda (x) x) x)
; >> x
; >> ,
; (lambda (f) (lambda (x) (f x)))
; >> '''''
;
(define one
(lambda (f)
(lambda (x)
; church 数での 1 とは, initial-value に一回だけ g を適用するということ.
(f x)
)
)
)
; two :: church-number
;
; two = (add-1 one)
; > (add-1 n) = (lambda (f) (lambda (x) (f ((n f) x))))
; (lambda (f) (lambda (x) (f ((one f) x))))
; > one = (lambda (f) (lambda (x) (f x)))
; (lambda (f) (lambda (x) (f (( (lambda (f) (lambda (x) (f x))) f) x))))
; >> ''''''''''''''''''''''''''''''''''''
; >> ( (lambda (f) (lambda (x) (f x))) f)
; >> (lambda (x) (f x))
; >> ,,,,,,,,,,,,,,,,,,
; (lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
; >> ''''''''''''''''''''''
; >> ((lambda (x) (f x)) x)
; >> (f x)
; >> ,,,,,
; (lambda (f) (lambda (x) (f (f x))))
; >> '''''''''''
;
(define two
(lambda (f)
(lambda (x)
; church 数での 2 とは, initial-value に2回 g を適用するということ.
(f (f x))
)
)
)
; add :: church-number -> church-number -> church-number
; (+) を直接 define で置き換えると, 普通の算術演算ができなくなっちゃうので
; ここでは別の名前で代用しておく.
(define (add a b)
(lambda (f)
(lambda (x)
; まずは a に対してf, x を適用することでその具象化した結果を得る.
(define a-evaluated ((a f) x))
; a から得た結果を元に, そこにさらに b による f の適用を追加した結果を得ると
; それが church 数における加算処理の結果となる.
((b f) a-evaluated)
)
)
)
実行結果:
gosh> (ex-2.6)
(church-to-integer zero)
;==> 0
(church-to-integer (add-1 zero))
;==> 1
(church-to-integer (add-1 (add-1 zero)))
;==> 2
(church-to-integer (add-1 (add-1 (add-1 zero))))
;==> 3
(church-to-integer one)
;==> 1
(church-to-integer two)
;==> 2
(church-to-integer (add one two))
;==> 3
(church-to-integer (add (add one two) one))
;==> 4
(church-to-integer (add (add one two) two))
;==> 5
#t