SICPの1章を高速で読んだ

SICP

付箋があるところだけかいつまんで記録。演習は全スキップだが、どうしても必要になったらやるかもしれない。今のところ、10~15時間くらいで78ページ読めているので、600ページ読むためには、100時間くらいかければよい(算数合ってる？)。100時間だから、週に10時間とれるとして、2ヶ月ちょいくらい。今後難しくなってくるだろうし、もうちょっとペースを上げたいなぁ。
せっかくだから原著で読んでいるけど、今のところ英語はあまり苦になってない(まだ最初の方だから、知ってる内容も多い)。訳本の日本語が突拍子もないらしいので、たまに分からないところは調べて読むようにすれば、誤解がないしいいかなぁと思って原著にしている。読む速度も、日本語よりは少し遅いけど、これも英語思考の訓練だと思って頑張ることにする。

1. Building Abstractions with Procedures

  • Scheme入門？
  • 計算の手続きとは何か
  • normal-order evaluationとapplicative-order evaluation
    • フツーの順番で評価するやり方と、遅延評価？
  • functionとprocedureの違い
    • functionは関数=写像、なので、外部仕様（＝結果）がきちんと記述されていればよい("declarative knowledge")。一方で、procedureは手続なので、過程(個々の命令)が記述されていなければならない("imparative knowledge")。
  • \sqrt{x}の漸化式というか特性方程式は\alpha = \frac{\alpha + \frac{x}{\alpha}}{2}
    • よく見たらaverage dumpingじゃん！(後述)
  • a bound value, whose scope is within the ...
  • lexical scoping
  • linear recursive process vs linear iterative process
    • 末尾再起(tail recursion)を使って処理をiterativeにしよう！
    • じゃないと、呼び出しのスタックがlinearに増えるので、処理数と記憶領域の両方がnに比例してしまう。
    • この後の演習で、「君の書いたプログラムがrecursive processなら、iterative processに書き換えよう」続出
  • tree recursionというのもある
    • linearどころかexponentialにrecursiveだけど処理の記述がとてもシンプルになる
  • Order of growth (1.2.3)
    • 計算量の分かりやすい定義
    • k_1 f(n) < R(n) < k_2 f(n)となるf(n)で、\Theta \( f(n) \)
  • ユークリッドの互除法を復習（すっかり忘れてた）
    • a>bとしてGCD( a, b )=GCD(b, a%b)
    • Lameの定理(証明付き)
      • m>nのとき、GCD(m,n)を求めるのにkステップかかるとき、n>Fib(k) なんだと。
      • つまり、互除法は最低でもlog(n)程度かかる
  • フェルマーの小定理
  • higher-order procedures
  • procedureをprocedureの引数にすることによって記述能力が格段に向上
  • ある関数のsummationを求めるときなど
  • シンプソン公式で積分を求めたり、普通に刻んで積分を求めたりできる
  • filter, accumlateなどの概念もExerciseで。
  • 待望のlambda登場
  • fixed-point search: finding fixed points of functions
    • 固有値を求めるって感じかしら。
  • average dumping
    • x' = x - f(x)が収束しないならxとf(x)の平均をx'にしてしまおう
  • （°°;）p73

Experienced programmers know how to choose procedural formulations that are particularly perspicuous, and where useful elements of the process are exposed as separate entities that can be reused in other applications.

  • ニュートン法
    • 懐かしいなぁ…今ではすっかりご無沙汰。
  • Abstractions and first-class procedures
  • "rights and priveledges" of first-class elements:
    • 変数として命名可能
    • 引数としてprocedureに渡すことができる
    • procedureの結果として受け取ることができる
    • データ構造として扱える
  • 高階関数の扱いから、fixed-point search辺りの解説がこの章のキモで、それまでのはフリとかScheme入門だと思う。
  • おわり。

Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)

Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)