何だかんだモロモロ終って今日から通常営業に戻ります。数日休んだだけでタスクが山盛り積もってて、これを崩すだけでかなーり大変そうなんですが(汗

問題解答

問1.12
再帰ということで、効率を考えなければさくっと書ける。

(define (pascalTriangle i j)
  (cond ((= j 0) 1)
        ((= i j) 1)
        ((< i j) 0)
        (else (+ (pascalTriangle (- i 1) (- j 1)) (pascalTriangle (- i 1) j)))))

問1.13
問題だけだとどこから手をつけたら。。。という感じだったものの、ヒントをそのまま実装したら確認できた。

(define (fib n)
  (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib (- n 1))
                  (fib (- n 2))))))

(define (phi i)
  (define (phi-iter count)
    (if (= count 1)
        (/ (+ 1 (sqrt 5)) 2)
        (* (/ (+ 1 (sqrt 5)) 2) (phi-iter (- count 1)))))

  (phi-iter i))

(define (psi i)
  (define (psi-iter count)
    (if (= count 1)
        (/ (- 1 (sqrt 5)) 2)
        (* (/ (- 1 (sqrt 5)) 2) (psi-iter (- count 1)))))

  (psi-iter i))

(define (checkFib n)
  (- (/ (- (phi n) (psi n)) (sqrt 5)) (fib n)))

というか、、、、SICP、問題が多いな(汗。問題をマメにやってるとなかなか進まない。そんなものなんだろうか?

本文

1.2.3 増加の程度
一般的には計算量 O が注目されがちな、オーダーの話。ここでは計算量に限らずメモリの使用量や一般的なリソースの消費の度合いを示す概念として説明されている。

今日はここまで。一日一ページづつしか進められていないのがまどろっこしい気はするものの、やり続けることに価値があるということで亀の歩みで続けるようにする。

本文

反復アルゴリズムに慣れるために両替が例に上がっている。ただ、ここで書かれている日本語がよくわからない(汗。
しかたないので原文もあわせて読みつつ何を言っているのか解釈(実際には不安に思ったところに曖昧さはなかった)。

註33の内容を試しにやってみる。両替を cc 、d を使用する硬貨とすると

(cc d 10)
(cc 1 10) + (cc 5 5)
(cc 1 9) + (cc 5 5) → (cc 1 n) は (cc 1 0) になり、条件より 1 に置きかわる
1 + (cc 5 5)
1 + (cc 1 5) + (cc 5 0) → (cc 1 5) は先の計算の途中にも出て、1 に置きかわる。また、(cc 5 0) は条件より 1
1 + 1+ 1 = 3

という感じ。硬貨の額面金額を取得するために配列が使えないと、それだけで問題が難しくなるような気がする。

問題解答

問題1.11
再帰は簡単。

(define (f n)
	(if (< n 3) n (+ (f (- n 1)) (f (- n 2)) (f (- n 3)))))

反復でやっぱりハマるものの、うっすらといつも使っているループとの対応が取れてきた気がする。
自分の解答は以下の通り。

(define (f n)
    (define (f-iter i v0 v1 v2)
        (cond ((< n 3) n)
                 ((= i (- n 3)) (+ v0 v1 v2))
                 (else (f-iter (+ i 1) v1 v2 ))))
    (f-iter 0 0 1 2))

。。。と思って回答を見たら全然違う(そもそも問題を間違えていた)

(define (fi n)
    (f-iter 2 1 0 n))

(define (f-iter a b c n)
    (cond ((= n 0) c)
            ((= n 1) b)
            ((= n 2) a)
            (else (f-iter (+ a b b c c c) a b (- n 1)))))

ループだとカウントアップしていくのに、反復だとカウントダウンしていく感覚が何だかなじめない。
ただ、確かに数学的にはこっちの方がそれっぽい気はする。
頭の中に値が変化するモデルが組み立てられれば、反復の方が簡潔かつ柔軟に記述できそうな気はする。

問題解答

問題1.9

前者は (+ a b) が (inc (+ (a-1) b)) と展開できるので、a が 0 になるまで繰り返し展開された後で集約されていきます。そのため再帰的。後者は (+ a b) が (+ (a-1) (b+1)) と置き換えられ、a が 0 になるまで繰り返し置き換えられるので反復的。

問題1.10
(A 1 10) は手で何とか展開できたものの、 (A 2 4) は大変すぎるので実行して動作確認しました。
回答っぽいのには辿り着いたけど、2^..^n の計算の仕方が。。。。 f の時って 2n なので、その時でも一般化された (A m n) って成り立つのかがわからない。ざっくりした流れはつかめたので置いておくことにします。

本文

1.1.2 木構造再帰
再帰版の fib は一瞬で書けたものの、反復版でつまづく(というか、今もモヤッとしている)。反復の書き方がどうも慣れない。
明日、反復の復習をします。

問題解答

問1.6

昨日わからなかった問1.6を考えるところから再開。いろいろ考えたもののわからないので、ギブアップして回答を参考にすることにしました。

述語(good-enough? guess x)が真になっても, new-ifは代替部
(sqrt-iter (impreve guess x) x)
を評価しようとするので, 停止しない.

これを読んで納得。

(new-if good-enough? guess sqrt-iter)

ということになるので、 new-if が評価される前に good-enough? と sqrt-iter 両方が評価されてしまうのか。蓋を開けてみれば何てことはなかったです。

問1.7

計算精度の問題。値が小さいときは許容値が相対的に大きくなりすぎて十分計算がされなくなってしまって、値が大きい時は大きな数値間の差を取ることで有効桁数が落ちて許容値以下にならなくなってしまうため、無限ループになってしまう。

プログラムの改良は一応自前でできたものの、解答と照らし合わせると全く知らない記法がされていて目が点。
これは追々やるだろうし、今のところはこんな感じなのねということで写経しながら流れを掴むだけにとどめておきます。

環境構築

そろそろコードをコンソールで打つ(そして無限ループに入って死ぬw)のも辛いので、今日は Gauche+Meadow で動作確認できるように環境構築をすることにしました。

環境構築は”Meadow + Gauche セットアップメモ“を参考。。。というか、そのまま実行。M-x run-scheme で gosh プロンプトが出るところまですんなり行きました。

もうちょっと詳しい使い方も知りたかったので、ひげぽんさんの”関数型言語の勉強にSICPを読もう – (4) 1章 – 小休止 Schemeの環境整備“も参考にいろいろお試し。

.scm は自動で Sceme モードと紐づいているようなので、ファイルを編集し始めた時点でモードが切り替わります。
操作として覚えないといけないのは

• M-x run-scheme　で gauch インタプリタ起動
• ウィンドウを分割して、一方にソースコード、一方で gauche インタプリタを起動した状態で式の末尾で C-x C-eするとその式を実行

さしあたってこの二つくらい。最初勘違いしていたのが、C-x C-e するとファイル全体が評価されるのかと思っていた点。これは式だけなので気をつける必要があります。ファイル全体を評価する方法も知りたかったですがすぐに見つからず。Meadow を使ってるのに Lisp 周りは全然使ってないのがバレバレですね orz→問1.7の回答を見たら、そもそも一つの式にまとめてしまっているのでファイル全体を評価するという必要がないのかも?うーん。。。それだけじゃ足りないような気もするんですが。

何だかんだ作業していたら夜中になってしまって SICP を読む時間がほとんど取れず。
作業の進捗も大事だけど、うまいこと切り替えないと時間の捻出ができなくなってしまうので、今後対策を考えていかないと。

今回は Newton 法の解説を読みつつコードを写経して動作確認と、問1.6に着手。

問1.6は実際に動かしてプログラムが返ってこなくなることは確認できたものの、なぜそうなるか説明ができないところでタイムアウト。明日また考える。

今日は新幹線の中で読んだ内容のおさらいとして 1-12P を、メモをとりながら読み込み。内容はプログラムの基礎や Lisp の文法、Lisp インタプリタ内での式の評価順序について。

演習問題を確かめようと実行すると無限ループになって帰ってこなくなるような罠が潜んでたり、さっそく Lisp の面白い書き方例が出てきたり。

(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))

なんてのは、実行して理解したら”おおっ!!”という感じがする。

ずっと昔から読もう読もうと思いつつほったらかしにしていた SICP を今年は読んでみることにしてみました。
#正月、帰省帰りの新幹線内でたまたま読み始めたってのがきっかけなんですが

1.1.6 まで読んだ感じだと、まあ一人で読むこともできそうだなーって感触はあるものの、多分一人で読んだら体力切れで途中で挫折するなーって感じもしているのでちょっと計画を立てつつ完走できるようにしたいなとおもっています。

計算機プログラムの構造と解釈[第2版]は書籍も出ていますが、Web でも公開されています。Web 版は書籍で載っていない問題の解答もあるのでとても助かります。

そんなこんなで動作確認をするために Scheme を実行するための環境構築をしなければいけないんですが、Scheme って言っても結構いろいろあるものなんですね。どれにするかなーとググっていたら正にこの正月から SICP を読み始めたという同志(こっちが勝手に言ってるだけw)を発見。

SICP を読むために Emacs で Scheme 環境を構築

環境構築の内容がものすごく詳細に書かれていて参考になりそうなのでこちらを参考にさせていただきつつ、処理系も Gauche を使うことに。 Gauche は SICP で使われているものとは細かいところで違いがあるようなので、 “SICPを読むためにやっておくと便利かもしれないこと” あたりに目を通しておくといいかも?

ひとまずコードを実行して動作確認をしたいだけなら Gauche を起動すればできるので今日のところはこれで確認するとして、ボチボチ Emacs の連携とかの環境を整えつつ本を読み進めていこうかとおもっています。