読者です 読者をやめる 読者になる 読者になる

(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

SICPを読む_(10)1章_手続きによる抽象の構築(p31-37)

Scheme SICP

間がめちゃくちゃ開いた気がします…。気がついたら脱線しまくりの、私生活ドタバタで全然進んでませんでした。
ということで気を取り直して、またサクサク進みますよ!><

1.3高階手続きによる抽象(p31)

  • プログラムで3乗することはできるが、言語には3乗の概念を表す能力がない。*1
    • 強力のプログラム言語への要請の1つは、パターンに名前を付けて抽象化できること
    • また、その抽象を直接使ってプログラミングができること
  • 手続きはこの能力を提供する

ということで、抽象化はSchemeだと「手続き」として提供されますよっと。*2
しかし、、、

  • パラメタ(引数)は数値でなければならないと制限されると、数値計算でさえも抽象の能力が激しく狭められる
  • 同じプログラムパターンが異った手続きとともに使われる
  • 手続きを引数としてとり、引数を値として返す手続きがあると便利
  • 手続きを扱う手続きを高階手続き(higher-order procedures)という

_人人人人人人人人人人人人人人人人人人_
> 手続きを扱う手続きを高階手続きという <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄

所謂、高階関数っていわれるものですね。
で、高階関数を使うと何が嬉しいのかとかそういうのが、この先書いてあるんだと思ってます。。

1.3.1 引数としての手続き

まずはこの3つ手続きから。

;;aからbまでの整数の和
(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

;;aからbまでの3乗の和
(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

;;級数の項の並びの和
(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

この手続きを見ていると共通の基本パターンを持ってることが分かる、と。
こんな感じですね。<>書きしてるところの穴埋めをすれば、それぞれの手続きと等しくなる。

(define (<name> a b)
  (if (> a b)
      0
      (+ (<term> a)
	 (<name> (<next> a) b))))

この辺だらだらとSICPで書いてあるんですけど、書いてあることまんまですね。
まとめると、数学の級数の総和を例にとって、より高度な抽象手続きを書くことができ再利用しやすくなってるよ、というのを示している感じ。

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
	 (sum term (next a) next b))))

(define (sum-cubes a b)
  (sum
   (lambda (x) (* x x x))
   a
   (lambda (n) (+ n 1))
   b))

(define (sum-integers a b)
  (let ((identity
	 (lambda (x) x))
	(inc
	 (lambda (x) (+ x 1))))
    (sum identity a inc b)))

(define (pi-sum a b)
  (sum
   (lambda (x)
     (/ 1.0 (* x (+ x 2))))
   a
   (lambda (x)
     (+ x 4))
   b))

問題1.29(p33)

シンプソンの公式は知らないけど、とりあえず書けた。*3
比較すると分かるけど、シンプソンは綺麗な数字でるのに、インテグラルは近似値なので精度こそ上がれどシンプソンの方がいい感じです。
シンプソンの公式だと3次式のとき誤差が0になるだけで、どちらも近似法には変わりないとのことでした。。(また何かの時に調べる)

gosh> (simpson cube 0 1 100)
gosh> 1/4
gosh> (integral cube 0 1 0.01)
gosh> 0.24998750000000042
gosh> (simpson cube 0 1 1000)
gosh> 1/4
gosh> (integral cube 0 1 0.001)
gosh> 0.249999875000001

問題1.30(p33)

反復的に書くのはそんなに難しくなかった。
引数aを次へとカウントアップして、引数resultを今回の計算結果と今までの計算結果を合計する感じで書ける。

問題1.31(p34)

sumとproductそんなに違わないです。記号が違うくらいと、(> a b)で返す値が0か1かくらいしか違いがない。
piの近似値はパターン見つけるのに苦労しました。a~bを何処に置くかが最初全然分からなかった…。

問題1.32(p34)

これは問題1.31でそんなに違わないと言っていた、ちょっと違うところを抽象化するだけなので迷いはない。

問題1.33(p34)

適当に解いたけど、だいたいあってるはず。これはちょっと貼っておく。

(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (cond
     ((> a b) result)
     ((filter a) (iter (next a)
		       (combiner (term a)
				 result)))
     (else (iter (next a)
		 result))))
  (iter a null-value))

1.3.2 lambdaを使う手続きの構築(p34~37)

今までの例題解く中でだいぶ好き勝手使ってるので、今更感はある。。。

  • 名前を付けて定義するより、「ほげほげする手続き」とか「ふがふがする手続き」を直接指定できたら便利だよね。
    • だから、lambdaを使おう!!

という話。

(define (name arg) (body))
;;は
(define name (lambda (arg) (body)))
;;の構文糖衣といえる

lambdaは名前が付かないほかは、defineと同様に手続きを作れるよ。

((lambda (x y z) (+ x y (square z))) 1 2 3)
局所変数を作り出すletの使い方

letもちょくちょく使ってたのでかなり今更ではあるんだけど…。

  • letはlambda作用の構文糖衣
  • defineは内部手続きのためだけにして、ちょっとした手続きにはletを積極的に使う
(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ...
      (<varn> <expn>)
  <body>))
;;と
((lambda (<var1> <var2> ... <varn>)
   <body>)
 (<exp1>
  <exp2>
  ...
  <expn>))
;;は等価

問題1.34(p27)

意地悪く、だと問答無用で無限ループだと思います。
以下のとおり。

(define (f g)
  (g 2))

(f f)
;((lambda (g) (g 2)) 2)
;(2 2)

ということで、とりあえずこの辺まで。

*1:Schemeには、かな

*2:他の言語でも名前は違えど関数だったりメソッドだったりとありますね

*3:知らんのに書けんのか!って思ったけど、よくわからないなりになんとかなる