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

SICP 孤読書会 - 1.1 プログラムの要素(1.1.6 〜 1.1.8)

1.1.6 条件式と述語

特殊形式

  • cond
  • if
  • and
  • or

の説明。


問題 1.1 〜 1.5

SICP/ch1 at master · snufkon/SICP · GitHub

に解答。

問題1.4 は cond を使った方がよかったかも。


たびたび使う関数は、

SICP/lib at master · snufkon/SICP · GitHub

に分けておき load して使えるようにしておく。

解答は

Structure and Interpretation of Computer Programs

で確認してますが、間違っていたら教えていただけると助かります。


1.1.7 Newton 法による平方根

数学の関数と計算機の手続きの間には、重要な違いがある。

  • 手続きは実効的でなければいけない。

平方根の関数は

√x = y >=0 かつ y^2 = x であるような y

と定義できる。

これは正当な数学の関数を述べているが、手続きを述べてはいない。

この定義は与えられた数の平方根をどう見つけたらよいかについて殆ど何もいっていない。

関数と手続きの対照は、

  • 関数: もののあり様の記述、平叙文的記述
  • 手続き: ことのなし方の記述、命令文的記述

計算機科学では命令文的(どうする)記述に関心を持つ。


問題 1.6 〜 1.8

SICP/ch1 at master · snufkon/SICP · GitHub

に解答。

問題1.7

1.1.7 の sqrt だと小さい数を利用した場合は

|guess^2 - x| < 0.001

で x が無視されて右辺(0.001)の値に応じた誤差が発生する。

大きい数を利用した場合、

|guess^2 - x| < 0.001

の左辺が0.001以下にならなくなり計算が終わらなくなる。

って感じですかね。たぶん。

0.001の値を小さくすると

  • 小さい数での誤差は減少するけど、大きい値が計算できなくなる。

0.001の値を大きくすると

  • 大きい値の計算はできるようになるけど、小さい数での誤差は増加する。

ってところでしょうか。


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

手続きは、他の手続きを定義する時に部品として使え、まとまった仕事が出来ることが重要。

局所名

手続きの仮パラメタは、手続き定義中でどんな名前を持っていても構わない。

そういう名前を束縛変数(bound variable)という。

手続き定義は仮パラメタを束縛する(bind)という。

変数が束縛されていなければ、自由(free)という。

名前が束縛されている式の範囲を有効範囲(scope)という。

手続き定義の中では、その手続の仮パラメタとして宣言された束縛変数の有効はその手続本体となる。

内部定義とブロック構造

定義(define)は入れ子にして記述することができる。

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

定義の入れ子をブロック構造(block struture)という。

この定義はもっと簡単に記述することができる。

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

内部定義で束縛していた仮パラメタxを取り除いた。

x は内部定義の中で自由変数となる。

自由変数は外側の定義の束縛を指すようになる。(この場合はsqrtのx)

この規則を静的有効範囲(lexical scoping)という。


SICP 孤読書会のメインページはこちら