SICP読書会 #3

計算機プログラムの構造と解釈いつもどおり千代田区立図書館で19:00から22:00まで。今日はP14からP20まで進みました。前回のすすみがイマイチだったので、今回はまずまずといったところ。

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

■ 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) を気合いで書いてたw 途中でタイムアップになって終了。次回までにリベンジを誓いました。電車の中とかでやろう…。

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

SICP eXtreme Readingの会

気に入ったらシェアお願いします!

この記事を書いた人

こんにちは!カノといいます👓
インターネットやテクノロジー、ビジネスモデルや歴史(世界史・日本史)、美術などが好きです。メガネのせいか真面目っぽく見えるらしいですが、基本的には昔からいい加減な性格です。
このブログは昔からずっと個人的な日記みたいな感じで書いてきていて、基本的には個人的なログになりますが、興味のあるところだけ読んでいただけるとうれしいです。コメントやTwitterのフォローなどは大歓迎です。

コメント

コメント一覧 (1件)

  • [SICP][JavaScript]Re: 第3回 SICP読書会

    カノログ 第3回 SICP読書会 http://kanolog.jp/2008/07/3-sicp-ee80.html id:kanouk課長がこの前の読書会のことを書いていたので、 読書会ではこの辺を大雑把に説明してたので 手続きsqrtにあわせてJavaScriptで書き直してみた。 ここはxを各functionに引数として渡していた…

コメントする

目次