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

やろーじだい

ブログです

Aizu-SIPC 第二回

2015/12/20 に Aizu-SICP 第二回 (SICP読む会) を行った。 更新したつもりが下書きにしたまま半年放置されていた。

タイムテーブル

  • 19:00 ~ 19:15: 前回課題とした練習問題 1.2 ~ 1.5 の答え合わせ
  • 19:15 ~ 19:45: 読書 P22~26 「1.1.7 ニュートン法による平方根
  • 19:45 ~ 20:20: 質疑
  • 20:20 ~ 20:35: 読書 P27~P31 「1.1.8 ブラックボックス抽象化としての手続き」

今回の内容

1.1.6 条件式と述語

練習問題 1.2

(define 1-2 (/ (+ 4 5 (- 2
                         (- 3
                            (+ 6
                               (/ 4 5)))))
               (* (- 2 7)
                  (- 6 2)
                  3)))

練習問題 1.3

(define (1-3 a b c)
  (cond ((<= a b c) (sum-of-squares b c))
        ((<= b a c) (sum-of-squares a c))
        (else (sum-of-squares a b))))

練習問題 1.4

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

定義後

> (a-plus-abs-b (+ 3 1) (- 1 -5))

と実行した場合の評価の流れを以下に記述する

(a-plus-abs-b (+ 3 1) (- 1 -5))
; ↓
((if (> (- 1 -5) 0) + -) (+ 3 1) (- 1 -5))
; ↓
((if (> 6 0) + -) (+ 3 1) (- 1 -5))
; ↓
((if #t + -) (+ 3 1) (- 1 -5))
; ↓
(+ (+ 3 1) (- 1 -5))
; ↓
(+ 4 6)
; ↓
10

練習問題 1.5

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

適用順序評価の場合は

(test 0 (p))

を実行した時に引数である 0 と (p) が評価される。その時 p の評価を得るために関数 p の定義から (p) を評価する必要があり、評価が無限に続いてしまう。一方、正規順序評価の場合は test の引数を評価せず、 また if は第一引数が真の場合は第二引数のみを評価するので

(test 0 (p))
; ↓
(if (= 0 0) 0 (p))
; ↓
(if #t 0 (p))
; ↓
0

となり評価が終了する。

1.1.7 例: ニュートン法による平方根

 再帰を利用した繰返し処理の具体例であり、初めての例としては少々複雑に感じた。ひとつひとつの関数が何をするものなのか、じっくり見る必要あり。ぱっと見ただけですぐに理解できなければ具体的な値を入れて自分で展開していく。

練習問題 1.6

 練習問題 1.5 に似た原理の問題である。 if 式の特殊形式であり、評価規則が通常と違う (全ての引数を評価しない) ことによって再帰関数 sqrt-iter は成りたっている

練習問題 1.7

 小さい値の場合、今回の good-enough? 内では誤差の大きさを比較するための定数として 0.001 が使われているが、これに近い小さな値の平方根は、その平方根の値に対して誤差の割合がかなり大きくなり、さらに小さい値 (平方根が 0.001) に対しては全く求まらない。大きい値を使用すると good-enough? 内で二乗した時に桁溢れが起る(?) 前回の guess と新しい guess を比較する形で誤差を推定すれば例題の good-enough? よりは良い精度になると考えられる。 (実際に試していない)

練習問題 1.8

(define (cube x)
  (* x x x))

(define (1-8-improve guess x)
    (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (1-8-good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))

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

(define (1-8-cube-root x)
  (1-8-sqrt-iter 1.0 x))

1.1.8 ブラックボックス抽象化としての手続き

関数一つ一つが持つモジュールとしての役割

 関数は何かしらひとつの仕事をし、複数の関数によって作られた関数はまた何かひとつの仕事をする。 Lisp でユーザーが作成した関数と、処理系に提供されている関数の差は無い。

束縛と代入の違いについての重要性

 ある変数と値の関係は、全てのスコープごとに独立している。現在のスコープにある変数と値の関係が定義されていなければ (自由変数)、ひとつ外のスコープを見に行く。あるスコープで使われている変数と同じ名前の変数がそのスコープの内側で使われており、値が別に束縛されたとしても、外側のスコープでは影響が無い。

ブロック構造

 P31 の例のような自由変数を使用する書き方は関数ひとつひとつが独立していないため読み辛く感じる。

質疑まとめ

関数の末尾の ? について

 Lisp で述語 (#t, #f を返す関数) を定義する際の慣例。

正の実数の平方根は必ず存在するのか

 http://d.hatena.ne.jp/takemita/20100114/p3

+とgood-enough?で、再定義した際の挙動が違うのはなぜ?

という質問が出て、読書会中はたしかにそうだなと思ったのだが、今試してみたところ普通に束縛され、自分で定義した関数との違いは無いようだった。

> (define + -)
> (define (test x y) (+ x y))
> (test 3 3)
0

読書会中は REPL でいろいろ実験を行っており、環境がかなり荒されていたのでその辺りが原因だったかもしれない。

scheme にループはあるか?

 繰り返しのための構文 do もあるが、一般に Scheme では繰り返しのために再帰を使用する。

scheme の引数の評価順序は?

Common Lispでは,関数の引数は左から右の順に評価される. Schemeでは評価順は意図的に未定義とされた. (それを忘れた人間は慌てふためいて実装者の笑いものになる.) http://www.asahi-net.or.jp/~kc7k-nd/onlispjhtml/continuations.html

レキシカルスコープの定義がよくわからない

このような定義のネストはブロック構造 (block structure) と呼ばれます。これは、基本的には最も単純な名前パッケージング問題の正しい解決方法です。しかし、ここにはもっといいアイデアが隠れています。補助手続きの定義を内部化することに加えて、それらを単純にすることもできます。x は sqrt に束縛されているので、sqrt の内部で定義された good-enough?, improve, sqrt-iterは x のスコープ内にあります。つまり、x をこれらの手続きに明示的に渡す必要はないということです。そうする代わりに、次に示すように内部定義では x を自由変数にします。そうすると、x の値は、それを囲む手続きである sqrt の引数から取ってくることができます。このような規定は レキシカルスコーピング (lexical scoping) と呼ばれます。27
27: レキシカルスコーピングにおいては、手続きの自由変数はその手続きを包む手続き定義の束縛を参照すると規定します。つまり、手続きが定義された環境での探索が行われるということです。
P.31

P.28の「手続きを使う人が、それがどうやって実装されているかについての知識を求められるべきではありません。」とは?

 関数を作成する側が注意するべき項目であり、「手続きを作る人は、手続きを使う人に、手続きの内部の知識を持つことを要求してはいけない」というような意味と読書会中に理解した。 これによると dynamic scope は完全に否定されていることになる?