銀色うつ時間

思い出すたび何か胸につっかえてるだけ

SICP（計算機プログラムの構造と解釈）1.1

SICP

はじめに

『計算機プログラムの構造と解釈』を読む。動機は以下。

  • いわゆる情報系の勉強をしていないので、基礎を身につけたい
  • Lispインタープリタを実装してみたい
  • ストリーム、遅延評価、末尾再帰最適化、構文・字句解析器など、なんとなくしか知らないものを理解したい
  • すごいエンジニアがみんな読んでる

年単位でかかるかもしれないが、それでも終わらない可能性・挫折する可能性があるので、練習問題は無理に全部やらない。

資料

mobiをkindleに送ってkindleから読んでいる。

html版

計算機プログラムの構造と解釈 第二版

訳にかなり癖があるので、意味を掴みにくい場合は、原著を確認するとよいかもしれない。また、コード集はこちらにしかないので、適宜見るとよい。

Welcome to the SICP Web Site

HTML版は、スタイルが適用されていないので、読みにくい。epub化を考えたけど、自分がやる前に既にepubおよびmobiで公開してくれている方がいたので、ありがたく使わせていただく。

github.com

環境

環境はOSXにLisp/Scheme派生の言語Racketをバイナリからインストールして使っている。DrRacketというIDEが同梱されているので、そちらを利用するか、/Applications/Racket\ v6.2/binにPATHを通せば$ racketで対話型コンソールを起動できる。

racket-lang.org

Emacsの使用経験がないため、エディタは検討中。vimでやるか、これを期にemacsを覚えるか。。。

本文

1.1.7

平方根について。数学的な関数とコンピュータの記述について。 数学では平叙文的（何であるか）記述をするのに対して、コンピュータは命令文的（どうするか）記述をする。どう計算するかというアプローチに対して、通常は次々と近似をとるニュートン法を用いる。

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

> (sqrt 2)
1.4142156862745097
> (sqrt 3)
1.7321428571428572
1.1.8

手続きを抽象化してブロック構造をとる方法、パラメータのスコープについて。外の入れ子にある束縛されたパラメータを内部で利用する（レキシカルスコープ）。

(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))

問題

EXSERCISE 1.3

三つの数を引数としてとり , 大きい二つの数の二乗の和を返す手続き

> (define (square a) (* a a))
EXERCISE 1.4

schemeの評価モデルは、演算子が合成式である組み合わせでも使える

> (define (a-plus-b a b)
  ((if (> b 0) + -) a b))
> (define (sum a b) (+ a b))
> (define (larger-square-sum a b c)
    (cond ((and (< a b) (< a c)) (sum (square b) (square c)))
          ((and (< b a) (< b c)) (sum (square a) (square c)))
          (else (sum (square a) (square b)))))
> (larger-square-sum 3 4 5)
41
EXERCISE 1.5

作用的順序の評価と正規順序の評価について

EXSERCISE 1.6

特殊形式として定義されているifを通常の手続きとして再実装して、1.1.7における平方根の手続きを行った場合、どうなるか。

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

> (define (sqrt-iter guess x)
    (new-if (good-enough? guess x)
            guess
            (sqrt-iter (improve guess x)
                       x)))

結果、無限ループする。これは、Schemeにおける通常の手続きが作用的順序で行われることに起因する。作用的順序での評価は、以下の通り。

  1. 組み合わせの部分式を評価する
  2. 最左部分式の値である手続き（演算子）を残りの部分式の値である引数に作用させる

つまり、一般的なSchemeの評価規則で定義されたnew-ifの場合だと、先に部分式が評価されるため、

(good-enough? guess x)

が真であったとしても

(sqrt-iter (improve guess x)
           x

が評価されるため、無限ループする

EXERCISE 1.7

曖昧。 平方根の手続きにおいて、入力が非常に小さい値もしくは大きい値にテストすっとが失敗する。大きい値の場合は、浮動小数点の比較における誤差によるところ。桁数の増大によって仮数が計算機に無視されるため、無限ループする。値が小さい場合、予測値が基準値より下回ると真を返すため、値にかなりのずれがあっても再帰が終了してしまう。改良版未着手。

EXERCISE 1.8

未着手。立方根の問題。ニュートン法の実装を改良する。