SICP六日目 〜問題1.9
三日で一問ぐらいのペースですが、本当に三日間一日一回は問題を眺めて、ぼんやり答えを予測してそれからまとめて書いています。一度に解こうとしてはいけません。眠くなります。暇なときに頭の隅で考えるぐらいがちょうどいいです。放射氏は多分正面から構えるとだめなやつコレ。
ブラックボックス抽象としての手続き
このへんです。
レキシカルスコープはC系とかの変数のスコープやnamespaceで考えるよりは、javascriptのアレかー、って考えたほうが理解が早いですよね。そのまんまですよね。
var test = (function () { var local_value; //いろいろやってるところ }());
こんな感じ。
- 束縛変数(bound variable)
- 束縛する(bind)
このあたりは他の本でも出てくる言葉なのでよくよく覚えておく。bindという英単語だとイメージをつかみやすいのに、束縛と言われるとえーっとなる謎。bindは数字を変数にベタッとはりつけてる絵が浮かぶんですが、束縛は普通に亀甲縛りしてる絵ですな。
線形再帰と反復
このへんです。
脳内でシミュレーションして脳がイーッってなるのが再帰で、イーッってならないのが反復だ! と感覚的には分かるんですが(脳内スタックメモリが少ない人になら分かっていただけると思います)、言葉で説明するとなると難しいですね。
関数に代入した変数が確定するまで待たなければいけないのが再帰で、代入した時点で確定しているのが反復、とか。とにかくふわっと覚える。ふわっと。
問題1.9
問題をよく読む。
これはincとdecを実装して動かしてしまうと、「はたしてincで使った+は自分で実装した関数なのかそうじゃないのか。そうだとしてその部分も答えに含める必要があるのか」とか余計なことを考えそうなので、実際の動作確認はしないで答えることにします。あくまでもincとdecは「問題で定義されているそのままの動作とする」ということで。
置き換えモデル - 一つ目
対象はこれですね。
(define (+ a b) (if (= a 0) b (inc (+ (dec a) b))))
脳がイーッってなったから再帰だ。
置き換えモデルで書くと、
(+ 4 5) (inc (+ 3 5)) (inc (+ inc((+ 2 5)) 5)) (inc (+ inc((+ inc((+ 1 5)) 5) 5))) (inc (+ inc((+ inc((+ inc(+ 0 5) 5)) 5) 5))) (inc (+ inc((+ inc((+ inc(5) 5)) 5) 5))) (inc (+ inc((+ inc(6) 5) 5))) (inc (+ inc(7 5))) (inc 8) (9)
はい再帰的でした。置き換えモデルは自分で書いてみると結構めんどくさいことを学習した。
置き換えモデル - 二つ目
対象はこれ。
(define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))
イーッってしないから反復。
置き換えモデルで書くと、
(+ 4 5) (+ 3 6) (+ 2 7) (+ 1 8) (+ 0 9) (9)
反復でした。
しかし毎度毎度問題が本当によくできているなあと思います。最低限で伝えるべき全てを伝えている。
他の方々が書いたSICPのブログをあちこち見てみました
…皆様一章は一瞬で通過しておられました。
フフッ、自分の理解の遅さを客観的に把握するとめげるのでもう見ません。