社内SICP勉強会(第2回)

まだまだSchemeに慣れない。

前回の勉強会で紹介されたtraceのしかた

(use slib)
(require 'trace)
(trace hoge)

とするとhogeの挙動を追いかけてくれる。

範囲

1.1.7(P12)から1.1の終わり(P17)まで

  • 1.1.7 Newton法
  • 1.1.8 ブラックボックス抽象としての手続き
    • プログラム全体は手続きの束
      • その束は問題の部分問題への分割を反映している
      • 手続きをブラックボックスと見なして、手続きがどう計算しているかではなく、どのような値を返すかに着目する。
      • そうすることで、手続きを抽象化(procedural abstraction)して考えることができる。
      • logをとって2倍してexponentialをとったら2乗になる理由は?
    • 局所名
      • 手続きのパラメタ名は手続き本体に対して、局所的でなければならない
      • 束縛変数(bound variable):手続きの仮パラメタには、手続き定義の中で、仮パラメタがどんな名前を持っていても構わないという特別な役目がある名前。
      • 手続き定義は仮パラメタを束縛する(bind)
      • 変数が束縛されていなければ自由である(free)
      • 名前が束縛されている式の範囲を有効範囲(scope)という
    • 内部定義とブロック構造
      • 定義の入れ子をブロック構造(block structure)という
      • 外側の手続きが呼び出された時の引数を、内部定義における自由変数として使うやり方を静的有効範囲(lexical scoping)という

問題1.6

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
     (else else-clause)))

(new-if (= 2 3) 0 5)

(new-if (= 1 1) 0 5)

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
       guess
       (sqrt-iter (improve guess x)
               x)))
  • 何が起きるか?
    • プログラムが終了しなくなる。
  • 理由は?
    • 特殊形式ifは解釈系の評価によらず述語式を最初に評価し、その結果が帰結式と代替式のいずれを評価するのを決める
    • それに対して新たに定義したnew-ifは一般系であるため、作用的順序で評価され、帰結式、代替式の双方が評価される
    • 今回の場合は再帰的にsqrt-iterが呼び出され続けてしまい、値を返すことができず終了しなくなる

問題1.7

  • 非常に小さな数で失敗する例
    • (sqrt 0.000001) = (sqrt 1.0E-6)だと理想的には(sqrt 0.001) = (sqrt 1.0E-3)となってほしいがそうならず終了する。
    • 自分の環境では0.031260655525445276で終了した。
  • 失敗の理由
    • (good-enough? guess x)はabs(guess^2 - x) < thresholdで、xが0.000001の場合、guess^2-0.000001と、guessの二乗が判定基準より小さくなった時点で真になるため、そこで更新がストップしてしまうから。
  • 非常に大きな数で失敗する例
    • 非常に大きな数だとプログラムが終了しなくなってしまう。
  • 失敗の理由
    • 有効数字の範囲内で判定基準を満たさなくなるから。
  • 新しいgood-enough?の実装
(define (new-sqrt-iter last-guess guess x)
  (if (new-good-enough? last-guess guess)
      guess
      (new-sqrt-iter guess (improve guess x) x)))

(define (new-good-enough? last-guess guess)
  (< (abs (- last-guess guess))
     0.001))

(define (sqrt x)
  (new-sqrt-iter 2.0 1.0 x)) 
  • 先ほど失敗した例でうまくいくか
gosh> (sqrt 0.000001)
0.0012961915927068783

gosh> (sqrt 100000000000000)
10000000.0

より小さな数の平方根を求めるためには基準値を小さくする必要がある。

問題1.8

立方根手続きの実装

(define (cube-root-iter guess x)
  (if (good-enough? guess x)
      guess
      (cube-root-iter (improve guess x) x)))

(define (improve guess x)
  (/ (+ (/ x (* guess guess))
     (* 2 guess))
     3))

(define (good-enough? guess x)
  (< (abs (- (* guess guess guess)
          x))
     0.001))

(define (abs x)
  (if (< x 0)
      (- x)
      x))

(define (cube-root x)
  (cube-root-iter 1.0 x))
gosh> (cube-root 8.0)
2.000004911675504

いくつか理解があいまいな部分があるので、もう少し考えたり調べる。