SICP読書会 #3

いつもどおり千代田区立図書館で19:00から22:00まで。今日はP14からP20まで進みました。前回のすすみがイマイチだったので、今回はまずまずといったところ。

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

著:エイブルソン,ハロルド, 著:サスマン,ジュリー, 著:サスマン,ジェラルド・ジェイ, 原著:Abelson,Harold, 原著:Sussman,Julie, 原著:Sussman,Gerald Jay, 翻訳:英一, 和田

¥5,586 （2024/11/14 21:49時点 | Amazon調べ）

Amazon

楽天市場

ポチップ

参加者は随時募集中です。

■ 1.1.8 ブラックボックス抽象としての手続き
「束縛する(bind)」という言葉が出てきました。「手続き定義は仮パラメタを束縛する」のように使用するとのことですが、要するに「関数の仮引数は、その関数内だけで有効である」ということですね。このあたりは、普通にプログラムをしている人ならば、あまり悩むことなく理解できるのではと思いました。

もうひとつ、Scheme的な記述としてブロック構造(block structure)という書き方が出てきました。先の平方根を求めるプログラムは、以下のように手続きsqrtの定義の中に書くことができるそうです。

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

さらに、手続きgood-enough?, improve, sqrt-iterは、手続きsqrtの仮引数xの有効範囲内にあるので、各手続きの中のxは省略できます。なので、上記の手続きは以下のように書くことができます。

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

ふむ。なるほど。

id:daisunが、このあたりをお得意のJavaScriptで説明してくれたのでわかりやすかったです。

■ 1.2 手続きとその生成するプロセス
要するに、プロセスが取る振る舞いを視覚化しましょう、といってます。次以降の節への導入。

■ 1.2.1 線形再帰と反復
おもしろかった！nの階乗を計算する手続きfactorialを、再帰的プロセスと反復的プロセスで記述して、プロセスの視覚化をします。

再帰的プロセスは、こんな感じ。

(define (factorial n)
  (if (= n 1)
    1
  (* n factorial (- n 1))))

でた！再帰！

次に、反復的プロセスはこんな感じ。

(define (factorial n)
  (fact-iter 1 1 n))
　
(define (fact-iter product counter max-count)
  (if (> counter max-count)
    product
    (fact-iter (* counter product)
      (+ counter 1)
  max-count)))

C言語とかで普通にプログラムを書くと、こっちのほうになりますね。1からnになるまで1ずつカウントアップしてかけ算をおこなう。nになったら終わりってやつ。

再帰的プロセスのほうは遅延演算(deferred operations)をおこなうので、まず、計算する式をすべて展開して、すべて展開し終わったら、一気に計算する。なので、置き換えモデルによって記述すると、いったん膨張してから収縮するようなプロセスを取る。

対して反復的プロセスのほうは、毎回計算がおこなわれるので膨張や収縮はない。

ここでのポイントは、「プロセス」が膨張・収縮する話をしているのであって、「メモリ」の話をしているのではないということ。

最後のほうに、ループ構造は末尾再帰で置き換えられるとか書いてあったが、いまのところ意味不明。5章で検討するとか書いてるので飛ばした。

■ 問題 1.9
ホワイトボードに、みんなで置き換えモデルで計算の様子を描いてみた。どう見ても反復的プロセスのほうが効率がよさそう。ここまで再帰再帰いってきたのに、ちょっとマイナスイメージ。

■ 問題 1.10
宿敵 Ackermann関数。みんなでウンウン悩んだ。まず何をしたいかが不明。hattorix0先生が(A 2 4) を気合いで書いてたｗ 途中でタイムアップになって終了。次回までにリベンジを誓いました。電車の中とかでやろう…。

■ 次回
7/15(火) 19:00~21:00(予定)

SICP eXtreme Readingの会