月: 2015年3月

SICP

SICP を読んでみる #39 MIT OCW 3A/第二章 p.54

MIT OCW

Lecture 3A | MIT 6.001
本日の MIT ビデオは 2A の後半。

  • cons/car/cdr を使用してリストを作成する方法
  • 上記の糖衣構文、 list
  • map

list や map は本ではまだ出てきていないのでここで初お目見え。
やってることはわかるけど、list すらプリミティブなデータ型として用意しないとは、、、、どんだけミニマム主義なんだ(汗

問題解答

問2.13
うーんという感じだったのでカンニング。何のことはない、手を動かすだけの問題だった。

m0↓ = c0 – (c0*p0), m0↑ = c0 + (c0*p0)
m1↓ = c1 – (c1*p1), m1↑ = c1 + (c1*p1)

m0*m1 の結果を v とすると、m0,m1 ともに正なので

v↓ = (c0 – (c0*p0))(c1 – (c1*p1))
v↑ = (c0 + (c0*p0))(c1 + (c1*p1))

v↓ = c0*c1 – c0(c1*p1) – c1(c0*p0) + (c0*p0)(c1*p1)
= c0*c1 – c0(c1*p1) – c1(c0*p0) + c0*c1*p0*p1

p0,p1 が小さいのでこの二つを掛けた値はゼロとみなす。

= c0*c1 – c0(c1*p1) – c1(c0*p0)
= c0c1(1-(p1+p0))

よって、誤差は p1+p0 になる。v↑も同様な手順で計算できる。

問題2.14
2.13 で求めた式を使って二つの式を計算してみると、同じになる。あれ?
これは、区間を意識する必要がありそう。。。。。と思って手計算してみたけど埒があかないのでカンニング。

どうやら、代数的に等価なのにプログラムに落とし込むと結果が異なるということがあるらしい。
この一連の問題はちょっと手に負えなさそう。ただ、扱う問題によってはここら辺はかなり大事な内容な気がするので、きちんと時間をかけて手を動かして理解した方がよさそう。

問題2.15,2.16
区間を使った計算の総まとめ的な問題。これまでの、区間の積和演算の知識を使うと直感的にも演算によって導き出される区間が変わりそうな気はする。
この欠点のない区間算術演算パッケージは、できなさそうな気がするんだけどできちゃうんだろうなというのが最初の印象。
ちょっと調べると、本に書いてある通りこれは相当難しい問題らしい。例えばここでは幾つかの議論へのリンクが貼られている。

抵抗値の計算の時、誤差ってどのように扱うって習ったのかな。。。?そういえば記憶が曖昧な気がする。計算時にはそもそも誤差はないものとして扱うことしかしてこなかったかも。

ということで、消化不良ながらも区間つきの値の演算についての項目は終了。一見単純そうなのに、実はかなり難しい問題の典型的な例だったみたい。

SICP

SICP を読んでみる #38 MIT OCW 2B/第二章 pp.53-54

MIT OCW

Lecture 2B | MIT 6.001
本日の MIT ビデオは 2B の後半。

・抽象化レイヤ
・pair の pair を用いて、任意の大きさのデータブロックを定義できる
・cons/car/cdr を自前で用意
 ・データ的なものを関数を用いて表現する

問題解答

問2.11


(define (mul-interval x y)
	(cond ((< 0 (lower-bound x)) (make-interval (* (lower-bound x) (lower-bound y))
                                              (* (upper-bound x) (upper-bound y)))
         ((= (lower-bound x) 0) (make-interval 0
                                               (* (upper-bound x) (upper-bound y))))
         ((< (lower-bound x) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               (* (upper-bound x) (upper-bound y))))
         ((= (upper-bound x) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               0))
         ((< (upper-bound x) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               (* (upper-bound x) (lower-bound y))))
         ((= (lower-bound y) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               0))
         ((< (lower-bound y) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               (* (upper-bound x) (lower-bound y))))
         ((= (lower-bound y) 0) (make-interval 0
                                               (* (lower-bound x) (lower-bound y))))
         ((= (lower-bound y) 0) (make-interval (* (upper-bound x) (lower-bound y))
                                               (* (lower-bound x) (upper-bound y)))))))

9 つに場合分けすることはできたけれども、いずれかの値が 0 でない場合は常に二回乗算がおこなわれるような。。。?
→問題は"二回以上"だけど、正しくは"二回より多く"。また、場合分けの仕方がダメだった。
また、x と y の区間が被らない前提で考えてしまった。

本来なら xy それぞれについて

  • 完全に負
  • ゼロをまたぐ
  • 完全に正

の、3×3通りについて考えないといけなかった。

問2.12

(define (make-center-percent v percent)
  (make-interval (* v (- 1.0 (/ percent 100.0)))
                 (* v (+ 1.0 (/ percent 100.0)))))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (percent i)
    (* (/ (width i) (center i)) 100))

P54 は丸々問題なので時間がかかる。

それにしても、WordPress でタグを打ちながら記事を書くのがいい加減辛い、、、、
テーマも適当だし、いい加減もっと手軽なものに移行したい。

SICP

SICP を読んでみる #37 MIT OCW 2B/第二章 p.53

MIT OCW

Lecture 2B | MIT 6.001
本日の MIT ビデオは 2B の前半。 pair を使って有理数を定義したり、演算をしたり。

pair
car
cdr
抽象レイヤ
約分のタイミングを例に、システムのデザインの話

問題解答

問2.9
区間を値 v と w で表して、それを演算するという話。
区間 x1 と x2 があって、その差の区間は

下限 : (v2-w2) – (v1+w1)
上限 : (v2+w2) – (v1-w1)
上限-下限 : ((v2+w2) – (v1-w1)) – ((v2-w2) – (v1+w1))
= v2-v1-v2+v1 +w2+w1+w2+w1
= 2(w1+w2)

同様に和の区間は

下限 : (v2-w2) + (v1-w1)
上限 : (v2+w2) + (v1+w1)
上限-下限 : ((v2+w2) + (v1+w1)) – ((v2-w2) + (v1-w1))
= v2+v1-v2-v1+w2+w1+w2+w1
= 2(w1+w2)

よって、両者とも区間の幅の関数になる。

乗算は
値1 : (v1+w1) * (v2+w2) = (v1v2+v1w2+v2w1+w1w2)
値2 : (v1-w1) * (v2+w2) = (v1v2+v1w2-v2w1-w1w2)
値3 : (v1+w1) * (v2-w2) = (v1v2-v1w2+v2w1-w1w2)
値4 : (v1-w1) * (v2-w2) = (v1v2-v1w2-v2w1+w1w2)

値をどれか取って確かめる。

差 : 値4-値1:
(v1v2-v1w2-v2w1+w1w2) – (v1v2+v1w2+v2w1+w1w2)
= (-v1w2-v2w1) – (v1w2+v2w1)
= -2(v1w2+v2w1)

和 : 値4+値1:
(v1v2-v1w2-v2w1+w1w2) + (v1v2+v1w2+v2w1+w1w2)
= 2(v1v2+w1w2)

いずれも v1,v2 が残ってしまう

問2.10
ゼロ除算の問題?

(define (div-interval x y)
  (if (or (= (upper-bound y) 0) (= (lower-bound y) 0))
      (display "error")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))
SICP

SICP を読んでみる #36 MIT OCW 2/第二章 pp.52-53

今日も MIT OCW の視聴から。

MIT OCW

Lecture 2A | MIT 6.001
∑計算
高階関数
Fixed-point
average-damp
Newton法

質疑応答もあわせてλ式と普通の関数との書き換えとか、教科書であまり触れられていない内容が解説されていて復習にちょうどいい。

本文

2.1.4 拡張問題:区間算術演算
区間を持った値の扱いについて。

問題解答

問2.7

(define (lower-bound x)
  (car x))

(define (upper-bound x)
  (cdr x))

(define v (make-interval 1 2))
(upper-bound v)
(lower-bound v)

問2.8

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                         (- (upper-bound x) (lower-bound y))))

ここらへんはさすがに簡単。

ビデオの視聴が一時間かかるから、本をやる時間が結構削られる。ビデオの内容が本でやってる内容に追いつくまではこんなペースになるのかな。

SICP

SICP を読んでみる #35 MIT OCW 1B

Church 数について何とか片がついたので引き続き本を進めます。その前に昨日から始めた MIT の授業視聴。1A1B あたりはまだまだ基礎の部分なので大丈夫な感じ。それでも、本だけだと取りこぼしてしまう内容を拾えたりして教えてくれる人の存在って重要だよなーとシミジミ思います。

MIT のコースを見てて地味に嬉しいのが、20-30 分くらいで内容が区切られてて一旦小休止が入るところです。このタイミングが結構絶妙で、集中力が切れるなーっていうくらいで休憩になるのでいい感じでリフレッシュして改めて講義に集中できるんですね。これは集中力の続かない私にも嬉しいです。

ビデオは 1B。繰り返し、再帰、計算量、フィボナッチ数列、ハノイの塔。
繰り返し版のフィボナッチ数列は省いていた。

午前中に別作業をしてしまったために SICP 本文はお休み。

SICP

SICP を読んでみる #34 第二章 p.52

今日から復習も兼ねて MIT の SICP コースのムービーもみてみることにしました。
とりあえずは一日一本、学習がおわっているところまでみてみるつもりです。

ムービーをみた感じ、授業では SICP の中の細かいところまでは突っ込んでいない感じです。自分が理解する範囲も SICP で言及されている内容が最大で、そこから外れている部分は目を瞑るっていう感じがいいのかも。問2.6 であれば SICP で提示されている add-1 の導出まで手をつけるのはやりすぎたかなという感じ。

問題解答

問2.6
今日こそは片をつけたい Curch 数。

SUCC の求め方についてはひとまず横に置いておいて、問題に集中する。

・(zero と add-1 を使わずに)one と two を直接定義せよ.

(define zero (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x))))))

・(add-1 の繰り返し作用させず)加算手続き + を直接定義せよ.

結局わからなかったので先人の知恵を拝借しつつ回答。

a+b
((two inc) ((three inc) 0))

three を計算した結果に two 追加して演算する : (f f) (f f f)

a*b
((two (three inc)) 0)

(three inc) という関数を用いて two という演算をする : (f f f) (f f f)

b^a
(((two three) inc) 0)

three という関数を用いて two という演算をする : ((f f f) (f f f))

言語化するともやっとする。ちゃんと理解できていないんだろうなぁ。

(define (sum a b)
  (lambda (f) (lambda (x) (a f) ((b f) x))))

(((sum two three) inc) 0)

(define (pow a b)
  (lambda (f) (lambda (x) (((b a) f) x))))

(((pow two three) inc) 0)

(define (mult a b)
  (lambda (f) (lambda (x) ((a (b f)) x))))

(((mult two three) inc) 0)

とりあえず課題はおわり。ただ、全く消化しきれている気がしない。
λ計算と展開あたりがかなりダメな予感。

SICP

SICP を読んでみる #33 第二章 p.52

問題解答

引き続き Church 数と格闘。今日は加算手続き + の定義。

加算手続き (+ a b) は “a に対して手続きを b 回繰り返す手続き”。

普通に書くとこうなる

(define (add a b)
  (define (add-iter f n)
    (if (= n 0)
        ((lambda (x) (x))
        ((lambda (x) (f (add-iter (a b f (- n 1)))))))))

  (add-iter f b))

ここで、置き替えないといけないのは if, True, False

404 Blog Not Found の記事を見ていたので、うろ覚えなのをしっかり理解する。

まずは記事中の記法の確認。

0 := λ f x . x
1 := λ f x . f x
2 := λ f x . f f x
(define zefo (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

λ式の展開が怪しいので手を動かしてみる

(define zefo (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x) (f x))
(define two (lambda (f) (lambda (x) (f (f x)))))

(define (inc n)
  (+ n 1))
(define (to-s z)
  ((z inc) 0))

(to-s zero)
(to-s (lambda (f) (lambda (x) x))) ;;zero を展開
(((z inc) 0) (lambda (f) (lambda (x) x))) ;;to-s を展開
(((lambda (f) (lambda (x) x)) inc) 0) ;;z に代入
(
 ((lambda (f) (lambda (x) x)) inc)
0) ;;ブロックをわかりやすくした
((lambda (x) x) 0) ;;f に代入
0 ;;x に代入

(to-s one)
(to-s (lambda (f) (lambda (x) (f x))))
(((z inc) 0) (lambda (f) (lambda (x) (f x))))
(((lambda (f) (lambda (x) (f x))) inc) 0)
((lambda (x) (inc x)) 0)
(inc 0)
((lambda (n) (+ n 1)) 0)
(+ 0 1)
1

(to-s two)
(to-s (lambda (f) (lambda (x) (f (f x)))))
(((z inc) 0) (lambda (f) (lambda (x) (f (f x)))))
(((lambda (f) (lambda (x) (f (f x)))) inc) 0)
((lambda (x) (inc (inc x))) 0)
(inc (inc 0))
((lambda (n) (+ n 1)) ((lambda (n) (+ n 1)) 0))
((lambda (n) (+ n 1)) (+ 0 1))
((lambda (n) (+ n 1)) 1)
(+ 1 1)
2

うーん。まあ慣れてきた。。。かな?

記事中の SUCC の復習。

SUCC := λ n f x . f(n f x)
2 := (λn f x . f(n f x)) 1
2 := λ f x . f(1 f x)
2 := λ f x . f(f x)

試しに 3 もやってみる。。。と思ったらうまくいかない。
ラムダ計算でよく出てくる謎の記法、これは何だ?

Wikipedia に載っていた
“BNFで書かれた以下の文脈自由文法によって定義される。”

OK.もう一回やってみる。

3 := (λn f x . f(n f x)) 2
3 := λf x . f(2 f x)
3 := λf x . f(λ a b . a(a b) f x)
3 := λf x . f(f(f x))


4 := (λn f x . f(n f x)) 3
4 := λf x . f(3 f x)
4 := λf x . f(λa b . a(a(a b)) f x)
4 := λf x . f(f(f(f x)))

カッコの扱いにちょっと慣れてきた。あと、lambda ではなくて λ と書けるのがありがたい。

SUCC の求め方も謎だったけど、思考を追った記事発見。これも手を動かして理解する。

ONE : λ f x.f x
SUCC : λ n f x.f n

(SUCC ONE) とした結果、TWO が得られれば OK.

(SUCC ONE)
(SUCC λ f x.f x)
(λ n f x.f n λ f x.f x)
λ f x.f λ a b.a b

“ここでα変換したλa.λb.a bを数ではなく、ひとつの函数*2として捉えると、どうやったら(f x)になるのかが見えてきます。”

見えてこないよ!! λ f x を展開するのか?

(a b) f x ;; λ a b.a b を二つの引数を取る関数とみなす
(f x)

ONE に ONE を作用させたい場合、こうなるらしい。謎。

SUCC : λ n f x.f (n f x)
(SUCC ONE)
(λ n f x.f (n f x) ONE)
(λ n f x.f (n f x) λ f x.f x)
λ f x.f (λ a b.a b f x)
λ f x.f (f x)

結論。理解できなかった。。。orz
泥沼化してるし、どこまで攻めるべきか。ちょっと考える必要がありそう。

そもそも SICP の先生を探したほうがいいのかも。

SICP

SICP を読んでみる #32 第二章 p.52

問題解答

問2.6
前回から引き続き、Church 数について。SICPを読む(39) 問題 2.6 Church数selflearnウィキの内容が、思考の流れも含めてわかりやすいっぽいのでこれをそのままおっかけながら理解していく。

処理を言葉にしてみる
※一通りやってみた感じ、言葉で表現するのは意味がなさそう

(define zero (lambda (f) (lambda (x) x)))

(f を引数に取り、(x を引数に取りそのまま返す手続) を返す手続き) を返す

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(n という手続を引数に取り、
(f を引数に取り、(x を引数に取り、
(f を n で評価した結果を用いて x を評価した結果) を f で評価する手続) を返す手続)
を返す手続き)

うむ。わからん。

zero : (lambda(x) x) なので、何もしない → 加算を行う上ではゼロと等価

((zero zero) 100)

これは 100 を返す。

add-1 の使い方がわからない。

(define inc (lambda (x) (+ x 1)))
(((add-1 zero) inc) 0)

らしいけど、いきなり inc とか定義してしまっていいものなのか?

Chrch 数の定義に戻って考えてみる。Church 数は“ある数は、ある関数fを何回 x に適用するか、という定義にしてしまうのである。”
とのこと。

これを念頭に最初に戻る。

(define zero (lambda (f) (lambda (x) x)))

zero は f を適用しない。これは判りやすい。

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

n に zero を代入して one を作ってみれば理解できそう。

(add-1 zero)

(add-1 (λ (g) (λ (z) z)))
※zero の引数を z と表記、f も g に置き換え

((λ (f) (λ (x) (f ((n f) x)))) [(λ (g) (λ (z) z))])
※zero をわかりやすいように [] で括った

(
 (λ (f) (λ (x) (f ((n f) x)))) [(λ (g) (λ (z) z))]
)

(
 (λ (x) (f (([(λ (g) (λ (z) z))] f) x)))
)

(
 (λ (x) (f (
             ([(λ (g) (λ (z) z))] f)
             x)))
)

((f (z x)))

式を展開していて感じたけど、lambda 式の展開が自分の中で曖昧。
簡単な式でおさらいしてみる。

((lambda (x) (+ x 1)) 0)

(define (add x) (+ x 1))
(add 0)

と等価。

((λ(x) (+ x 1)) 0)

を展開する。

(+ 0 1)

これだと直感的にできてしまう。エセマシン語で処理をもっと細かくしてみる

; ((λ(x) (+ x 1)) 0)
; (λ(x) (+ x 1)) : operator
; 0 : operand
push 0
call (λ(x) (+ x 1)) ; "x を引数にとって (+ x 1) を処理するための手続き"
  x = pop()

  ; + : operator
  ; x, 1 : operand
  push 1
  push x
  call +
    v2 = pop()
    v1 = pop()
    push (v1+v2)
  ret = pop()
  push ret

(+ 0 1) はカッコを含めて演算結果の 1 に置き替えられる。
((λ(x) (+ x 1)) 0) はカッコを含めて手続きの (+ 0 1) に置き替えられる。

同様な考え方で zero を展開してみる。

(define zero (lambda (f) (lambda (x) x)))

((zero g) 0)
(((lambda (f) (lambda (x) x)) g) 0)

(
 ((lambda (f) (lambda (x) x)) g)
 0)

(
 (lambda (x) x)
 0)

0

できてる気はするけど、何だか怪しい。置き替えモデルの復習が必要っぽい。

1.1.5 手続き作用の置き換えモデル を参考におさらい。

(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
(f 5)

(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

これはすんなりできる。OK。

もう一回。

(define zero (λ(f) (λ(x) x)))
((zero g) 0)

(((λ(f) (λ(x) x)) g) 0)

; 処理するブロックをわかりやすくする
(
 ((λ(f) (λ(x) x)) g)
0)

; 置き替え
(
 (λ(x) x)
0)

; こういうこと
((λ(x) x) 0)

; 置き替え
0

結果は同じだけど前より処理がハッキリしている感じがする。
この勢いで (add-1 zero) もやってみる。

(define zero (λ(f) (λ(x) x)))
(define (add-1 n)
  (λ(f) (λ(x) (f ((n f) x)))))

(add-1 zero)

(add-1 [(λ(g) (λ(z) z))])

((λ(f) (λ(x) (f ((n f) x)))) [(λ(g) (λ(z) z))])

(λ(f) (λ(x) (f (([(λ(g) (λ(z) z))] f) x))))

((n f) x) この部分、n に代入された zero は f に関わらず x をそのまま返すので

(λ(f) (λ(x) (f x)))

つまり、x に対して f を一度演算する手続を返す。

うーん。何か怪しげ。

展開はちょっと置いておいて、Church 数の定義に則って zero, one, two を定義してみる。

(define zero (lambda (f) (lambda(x) x)))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

((zero inc) 0)
((one inc) 0)
((two inc) 0)

zero, one, two という手続きと、0,1,2 という値は直接関係なくて、それらを繋ぐ(写像する)関数として inc を使っているという理解でいいのか。

(define (mult x) (* x x))

((zero mult) 2)
((one mult) 2)
((two mult) 2)

これなら 2^n になる。

また、先ほど展開した

(λ(f) (λ(x) (f x)))

(define one (lambda (f) (lambda (x) (f x))))

を見比べると全く同じなことがわかる。

加算手続きを定義するには繰り返しを定義する必要がありそう。時間オーバーなので次回はここから。

処理の置き替えは、もうちょっと手を動かして慣れた方がよさそう。