読者です 読者をやめる 読者になる 読者になる

やろーじだい

ブログです

まとめること・書くことによって得たこと

以前ブログでまとめることについて書いた。今回はネットに公開する形ではなかったが、ある程度継続することができていたので現状についてとまとめたい。

長くなった上に対象はよくわからないので暇な方向けです。

近況

四ヶ月ほど前から、先月末が締切である学会へ提出する論文の作成とその研究を進めていた。この中で、少なくとも二週間に一回、基本的には週に一回の間隔で教授との一対一のミーティングを行うことを決めこれを継続することができた。これによって得られたことをまとめる。

 それとは別に、一昨年の末から行っていた思考を記録するメモ帳が一冊埋まったのでこれについても書きたい。

まとめる

まとめるというのは、その時までに自分の学んだこと・調べたことなどについてを他人が読んで (見て) 理解できる形にするための文章化・図化などを指すようにした。ただし、他人が理解できる、ということを意識することが重要で、実際に読んでもらうことは必須ではない。もちろん読んでもらった方が本当に他人が理解できているのかを確認できるのでそういう機会はあった方がより良いと思う。

 やっていたことは、教授とのミーティングにあたって毎週ミーティング前日までに行ったことをまとめるということをしており、これをニヶ月ほど繰り返した。内容は以下のようなものであった。

  • 前回までの簡単なまとめ
  • それからの実験の要約と結果 (結果は表やグラフなどでかならず可視化するようにした)
  • 何がわかったか/わからなかったか

初めの内はミーティング前日ギリギリまで研究をして、最後にまとめの資料を作成するというやり方をしていた。しかし、明らかに必要な情報を落とすなどしてうまくまとめられなかったので、やっていることを逐次記録するようにし、ミーティングではその記録を少し修正したものを使うようにした。

 以前の問題として研究のスピードが本当に遅いということがあった。研究をする・プレゼンを作る・研究用のプログラミングをする・論文を読む・書く、あらゆるひとつひとつのことに異様に時間がかかっていた。しかし、ミーティングを行うための発表資料を作るようになってからは、今現在、論文を完成させるという目標のために足りないものは何なのか、その足りないものができると次は何ができるのかを自覚しやすくなった。まだまだスピードは改善されていないが、明かにひとつひとつの作業から受ける負担は減っているように思う。

 何故そのようなことになったかは、次のメモ書きの内容も大きく関係しているので最後にまとめる。

書く

自分の思考をメモするということを一昨年前から始めていた。きっかけは読書のメモを取るために枠線などが無いメモ帳を購入したことだった。

 そのメモ帳には本当にあらゆることを記録しており、例えば読書感想・その日のTODO・ある人への感情・思いつきや日記など、このメモを人に読まれることがあれば自殺を考えるレベルであらゆることを思ったままに書いている。

 このメモによって得られることの重要な点が二つあり、ひとつはその思ったことをそのままに書くことによって残る記録そのものである。今現在書いているようなブログの記事は、インターネットに公開するという目的で書かれているので、自覚・無自覚に関わらず様々なバイアスを受けている。良く見られるように書こうとしたり、文脈が無しでは意味不明なことを取り除いたりしている。一方メモの記録は誰かに見られることを前提としていない完全なまでに自分の思考であるので、今のブログの記事などとは全く異なるものになっている。

 通常、誰かに見せるためではない自分のためだけの文章を書く機会というのは、日記などの習慣が無ければあまり無いかと思う。自分の考えを記録するためだけに書かれた文章は、それを書いた時の自分の状態や気分などの空気も記録されており、後々読み返すと書かれていること以上に様々なことを振り返ることができておもしろい。

 また、もうひとつの点として、最後に更に詳しく考察するが、自分は同じことを何度も何度も考えてしまう癖のようなものがあることに気がつくことができたということだった。メモをしながら考えるようにしてから、結論まで考えることがしやくすなった。悩むことと思考するということの違いがわからなかったが、結論を導けるかどうかというのがありそうだなと思った。

 同じことを何度も考えていることも、結論に辿りつけていないということについても長い間無自覚であったが、これを自覚することができた理由について考えた。

流れ続ける思考

上の二つから気が付いたことは、思考というのは、常に流動するものであるということだった。イメージとしては、何かある一つのことを考えているとしてもその対象が頭の中を占めているというよりは、何度も何度も考え中に表れ続けているという感じである。ひとつのことを考えている時はとても小さな輪の形で考えがループしている。

 私は日常の中でこの状態に陥ることがとても多かった。この考えのループというのは自分の人生の中での問題の多くを表していたので非常に衝撃的な発見だった。

 これは何かを考えるとき全般に言えることで、それにはもちろんプログラミングという行いも含まれている。プログラミングをする時に頭の中でだけ考えていると、同じ事を何度も何度も繰り返し考えてしまいなかなか前に進めないということが起きる。これを打開する方法は非常に明確で、すでに考えたことは脳の中ではないどこかに固定する必要があるということだった。プログラミングでは、ある目的の関数の部品となる関数を書くことで、自分はその関数化されたものを使って次の段階について考えることに集中できるようになる。

 それはプログラミング以外でも同じことで、何か考えにふけっているとき、それは同じことを何度も繰返し考えている状態で思考が閉じていることが多く、問題が解決することが非常に難しい状態になっている。しかし、その自分が考えている内容を少しづつ何かに落としこむことによって、私はそれを使用してて次のことを考えることができるようになる。一般的に言われているような、文章を書くと思考がまとまるということの理由は、このようなものであるのだろうと思う。

 思考を外部に固定せずに自分の中でだけやろうとすると、多くのことについて覚えておく必要があり、結論に到達することがとても難しい。加えて、一度最初の前提に立ち返ってみるということも非常に難しくなり、そもそもの前提が間違えていた場合それに気が付くことも難しくなる。それに比べて文章化をしながらの思考は、それをしない時に比べて思考の足場が存在しているので段違いに次に進みやすく、かつ戻りやすい。もちろんその進む方向が本当に正しい方向であるかはわからず、これは別な問題ではあるが、少なくともどこかには辿り付くことがしやすくなる。結論が出さえすれば、記録に残されている前提と結論を元手に、それが今求めている結論としてふさわしいのかどうかを考えることもしやすい。

 この思考の固定の必要性にはもちろん個人差があると思われる。その個人差の要因はわからないが、現在では思考をメモすることができない状態でも、同じことを考えているループに入ると「今同じことを考え続けている」ということに気が付けるようになってきた。メモ帳などを自転車の補助輪のように考えて、思考を外部に固定することなくうまく考えを進めていく能力が後天的に向上することに期待している。ひとまずはこのメモをすることを継続していきたい。

 今でこそ文章を書く人ならば自覚していることなんだろうなと思えることだが、上記のことから明らかなように文章というのは既に考え抜かれたものからなる集合体ではなく、思考の流れの記録になっている。文章を書くことによって思考を記録し、その記録から次の思考が産まれる。その思考は文章となりまた次の思考の土台になる。文章とはこの繰り返しの記録ということになる。

この記事を読み返してみると、多くはこれを書く以前には明確に考えていなかったものによってできていることに驚く。すごい。

「つくって学ぶプログラミング言語 - Ruby による Scheme 処理系の実装 」を途中まで読んだ

きちんと Lispインタプリタの実装したことがなかったのでここを参考にしながら 2 ヶ月程前に Common Lisp で 3 章 (再帰) まで実装していた。いつ再開するかわからないので今日の記事で宣言した通りとりあえずまとめておく。
 自分のプログラムはここで公開しているが、自作のライブラリ と CL21 を使っているので導入しなければ動かない。
 Ruby を使っても良かったのだが、ただ写すだけになってしまいそうだったのと、

本書で出てくるプログラムをコピー&ペーストしていけば、実行できるようになっています。動作することを確認するくらいには役立つでしょう。ただし、本当に理解したいのであれば、なるべく自分で プログラミングしてみてください。それもプログラムを見て理解した後は、そのプログラムを見ずに。 どこが理解できないでるかが明確になるかと思います。
はじめに P-ii

ということから、別な言語を使った方がこれを実践しやすいと思ったため。

第1章 プログラムと評価

1章終了段階でのコードは ここ で確認できる。
 この本では Ruby で配列として扱えるという理由で [:+, 1, 2] というような構文を採用していたので自分は (:+ 1 2) という様にした。関数と変数は共にシンボルとして扱うようにした。また命名規則に関しても基本的に Common Lisp でよく見る形式にした。例えば述語は Ruby の場合 immediate_val? となるものを immediate-val-p のようにハイフン区切りで p を付けるといった様に。
 環境は

(defparameter *primitive-fun-env*
  #H(:+ '(:prim +)
     :- '(:prim -)
     :* '(:prim *)))

のように Hash-tabel を利用した。

第2章 関数適用の評価

eval_let の実装にあたって

(defun let-to-parameters-args-body (exp)
  `(,(map #'first (second exp))
    ,(map #'second (second exp))
    ,(third exp)))

(defun eval-let (exp env)
  (destructuring-bind (parameters args body) (let-to-parameters-args-body exp)
    (let ((new-exp (append `((:lambda ,parameters ,body)) args)))
      (_eval new-exp env))))

というようにバッククオート構文を使用しているのだが、

(defun let-to-parameters-args-body (exp)
  (list (map #'first (second exp))
        (map #'second (second exp))
        (third exp)))

の方が読みやすい気がした。
 let? のような関数の実装が雑で不安だったので

(defun letp (exp)
  (and
   (eq :let (first exp))
   (listp (second exp))
   (third exp)))

のようにした。
 ここを読むと、クロージャとは何なのかが明確になるので、その辺りが曖昧な人は読む価値があると思った。

第3章 再帰

再帰関数の実装に興味があったのでこの章は楽しかった。実装にあたって苦労したのだが、最も苦労した理由がテストのミスであり辛かった。テストのミスというのはどうすれば防ぐことができるのだろう。
 ここでは Ruby に慣れていなかったのと、環境を用意せずに読んでいた (実際に実行して試さなかった) ため eval_retrec など少し読むのに苦労した。もう少し関数を分けて処理に名前を付けて欲しいと思った。
 またここまでで唯一の破壊的処理を行う set_extend_env! が実装されているが、何故ここで副作用を使うようにしたのかの説明が無かった。単純に考えれば環境 (Hash-tabel) の更新なので Copy を作るのは重い処理だからかと思ったが、 extend_env では Hash.new を使って新しい環境を作成しているのだが違いは何なのだろう。

追記:

 このツイートへのリプライで破壊的更新をしている理由について教えて頂いた。
 コピーをするとクロージャの持つ環境が更新できず :dummy にアクセスしてしまうので、ここでは破壊的処理を行って更新しなければならなかった (extend_env では既に環境内にある closure の持つ環境を変更することができない)。

まとめるということについて

まとめるということについて

自分はこれまで興味を持って取り組んだことの状況が、終わったかそうでないかの2パターンに頭の中で振り分けてしまっていた。これでは本は読み終わらなければ、延々に興味の対象として胸の中に居続けることになるし、勉強についてはどこまで行っても終わりがない。この状態は良くないのでひとつひとつにしっかり集中して取り組まなければと思いながらも、簡単に興味が分散する性格をしているので全くうまくいかず気が付けば大学院1年の冬にさしかかろうとしている。
 常々、自分に足りないものは「まとめる」ということだという思いがあった。しかし、これまで私はまとめるという行いが長い時間をかけてやってきたものの集大成である様なイメージを持っていた。そのためなかなかその「まとめる」という段階にまで到達するほどのものができず、自分でも長い時間何をやっていたのか説明ができない状態が続いていた。
 つい昨日、自分がやったところまでを「とりあえずまとめる」ということを意識すれば一度その興味のあることについて区切りをつけることができるのではないかと気がついた。それによって、自分が現在までおこなっていたことが明確になる。また他に興味が湧いたとしても、その段階で手をつけていたものをとにかくまとめることで、そこまでのことに区切りを付け、次のところに心おきなく進むことができそうだ。今までは「そういうえばこれについて勉強している途中だった」ということを考えなが別なことをやっていることがあり、非常に気分が悪かった。この「次に行く前にそこまでのことを、どんなに浅い段階でもいいのでまとめる」ことを徹底することができれば、ここまで挙げてきた問題を改善することができそうだと思う。
 自分は大抵の場合、こういった「これをやります宣言」をしたものを全く実行できていないという典型的なダメ人間であるのだが、今回に関してはこの宣言を行うと同時に、この思いつきについてブログにまとめるということができているので今までよりはましだろうということにしたい。

Aizu SICP 第5回

2016/7/11 追記: 数式のサイズを見易いように修正

今日は参加できる人が少なめだったので練習問題 1.9 ~ 1.13 を解く時間にしてみたが、参加者全員で頭をひねって解く時間はなかなか良かったのでこの形式でまたやりたい。

今回の内容

注意: 以下では私達の練習問題の解答を載せています。まだ問題を解いていない人は一度取り組んでみてください。すでに解き終わっている人で何か解答におかしいところを見つけた人は教えてください。

練習問題 1.9

 実際に動かすために incdec を以下の様に実装した。

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

また、+ で実装すると Scheme 上で実装されている + を上書きしてしまい面倒なのでそれぞれの関数を plus1plus2 とした。

(define (plus1 a b)
  (if (= a 0)
      b
      (inc (plus1 (dec a) b))))

(define (plus2 a b)
  (if (= a 0)
      b
      (plus2 (dec a) (inc b))))

plus1 は「a plus1 b は a = 0 の時 b であり、それ以外の場合、a から 1 引いたものに b を plus1 した結果に更に 1 足したものに等しい」 であり plus2 は「a plus2 b は a = 0 の時 b であり、それ以外の場合、a から 1 引いたものに、b に 1 を加えた結果を plus2 したものに等しい」という意味を持つ。この時、 plus1 では明らかに inc による遅延演算の連鎖がおこるため再帰プロセスであり、 plus2 では毎回の演算が独立しているため反復プロセスであることがわかる。以下に (+ 4 5)plus1plus2 それぞれを適応した展開の流れを記述する。

;; plus1
(plus1 4 5)
;; ↓
(inc (plus1 3 5))
;; ↓
(inc (inc (plus1 2 5)))
;; ↓
(inc (inc (inc (plus1 1 5))))
;; ↓
(inc (inc (inc (inc (plus1 0 5)))))
;; ↓
(inc (inc (inc (inc 5))))
;; ↓
(inc (inc (inc 6)))
;; ↓
(inc (inc 7))
;; ↓
(inc 8)
;; ↓
9

;; plus2
(plus2 4 5)
;; ↓
(plus2 3 6)
;; ↓
(plus2 2 7)
;; ↓
(plus2 1 8)
;; ↓
(plus2 0 9)
;; ↓
9

練習問題 1.10

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

以下は何も考えず実行した結果を貼った。

(A 1 10)
;;=> 1024
(A 2 4)
;;=> 65536
(A 3 3)
65536

以下は数学的定義を与える問題について。

f

(define (f n) (A 0 n))

これは A の定義から、 n = 0 の時 (f n) は 0, それ以外の場合は全て cond 式の第2式に入るため (* 2 n) が実行される。よって

{ \displaystyle
f(n) = 2n
}

g

(define (g n) (A 1 n))

n = 0, 1, 2, 3 の場合を展開すると、

(A 1 0)
;; ↓
0
;; ↓
(A 1 1)
;; ↓ (A の定義より)
2
(A 1 2)
;; ↓
(A 0 (A 1 1))
;; ↓
(A 0 2)
;; ↓ (f の定義より)
4 
(A 1 3)
;; ↓
(A 0 (A 1 2))
;; ↓
(A 0 (A 0 (A 1 1))
;; ↓ 
(A 0 (A 0 2))
;; ↓ (f の定義より)
8

一般化すると、

(A 1 n)
;; ↓
(A 0 (A 1 (- n 1)))
;; ↓
(A 0 (A 0 (A 1 (- n 2))))
...
;; ↓
(A 0 (A 0 (A 0 ... (A 1 1))))

このように n-1 の数だけ 2 に  f(n) が適応される。(ただし n = 0 の場合は A の定義より 0 になる。また 0 未満の場合は未定義 (無限ループ)) よって、

f:id:lhcpr:20160710204153p:plain:w200

h

(define (h n) (A 2 n))

n = 0, 1, 2, 3 の場合を展開すると、

(A 2 0)
;; ↓
0
(A 2 1)
;; ↓
2
(A 2 2)
;; ↓
(A 1 (A 2 1))
;; ↓
(A 1 2)
;; ↓ (g の定義より)
4
(A 2 3)
;; ↓
(A 1 (A 2 2))
;; ↓ (上の定義より)
(A 1 4)
;; ↓
16

という様に、

(h n)
;; ↓
(A 2 n)
;; ↓
(A 1 (A 2 (- n 1)))
;; ↓
(A 1 (h (- n 1)))

というような漸化式の形をしている。例えば n = 3 の場合は  { 2^{2^{2^{1}}} } という様に展開される。数式として表わすと、

f:id:lhcpr:20160710214755p:plain:w250

練習問題 1.11

再帰プロセスは数式をそのままプログラムにできる。反復プロセスは P40 フィボナッチの関数とほぼ同様にできる。

(define (f n)
  (f-rec 2 1 0 n))

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

同様な形の漸化式の場合、項の数がいくつ増えてもその分だけ引数の数を増やしていけば同様に反復プロセスに落とすことができることがわかる。

練習問題 1.12

いまいち問題の意味がわからなかったが、多分こういう意味だろうということで実装した。

(define (pascal-triangle row col)
  (cond ((= col 1) 1)
        ((= row col) 1)
        (else (+ (pascal-triangle (- row 1) col)
                 (pascal-triangle (- row 1) (- col 1))))))

練習問題 1.13

kとk-1のふたつを仮定する数学的帰納法を用いた。参考

n = 0 の場合

f:id:lhcpr:20160710231335p:plain:w300

n = 1 の場合

f:id:lhcpr:20160710231233p:plain:w350

次に n = k, n = k - 1 の時に問題の式が成り立つと仮定すると、(k と書くべきところを n と書いてしまいました。許してください。)

f:id:lhcpr:20160710232506p:plain:w500

ここで

f:id:lhcpr:20160710234337p:plain:w330

f:id:lhcpr:20160710234447p:plain:w330

であり

f:id:lhcpr:20160710233502p:plain:w300

f:id:lhcpr:20160710233701p:plain:w300

であるので、

f:id:lhcpr:20160710234844p:plain:w500

よって全ての整数 n  {\geq} 0 について

f:id:lhcpr:20160710235026p:plain:w150

が成り立つ。

Aizu SICP 第四回

2016/6/11 に Aizu SICP 第四回を行った。途中の練習問題は一旦飛ばした。

タイムテーブル

  • 19:10 ~ 19:30: 読書 p38「1.2.2 木の再帰」~ p42 練習問題1.11前まで
  • 19:30 ~ 20:00: 質疑
  • 20:05 ~ 20:20: 読書 p43「1.2.3 増加オーダー」 ~ p47 「1.2.4 指数計算」練習問題前まで
  • 20:20 ~ 20:50: 質疑

今回の内容

1.2.2 木の再帰

より正確には、Fib(n) は  {\Phi^{n} / \sqrt{5}} に最も近い整数になります (練習問題 1.13参照)。 {\Phi} は次の値です。
{ \displaystyle \Phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180}
 {\Phi}黄金比 (golden ratio) で、次の等式を満します。
 {\Phi^{2} = \Phi + 1}
そのため、このプロセスのステップ数は、入力に対して指数的に増加します。
p38~39

最後の「そのため」は、

より正確には、Fib(n) は  {\Phi^{n} / \sqrt{5}} に最も近い整数になります。
P38

にかかる。
 両替の問題は読書会中に各自紙に書くことによって理解を試みた。数学的な話題になってくると紙とペンが欲しくなるので準備が必要だった。
 この章の中で

count-change は、fib の一つ目の実装同様、冗長な木の再帰のプロセスを生成します (292 の計算にはかなりの時間がかかるでしょう)。
P42

という話があったが、現在の性能では数ミリ秒であり、この本がかなり前にかかれた本であることを再確認した。

1.2.3 再帰オーダー

任意の十分に大きな  {n} に対して、 {n} と独立な正の定数  {k_1} {k_2} が存在し、 {k_1f(n) \leq R(n) \leq k_2f(n)} を満たすとき、 {R(n)} は増加オーダーが  {\Theta(f(n))} であると言い、 {R(n) = \Theta(f(n))} (シータ f(n) と読む) と書きます。(別な言い方をすると、大きな  {n}に対して、 {R(n)} の値は  {k_1f(n)} {k_2f(n)} で挟まれるということです。)
P44

という定義から、  {\Theta(n)} {O(n)} {\Omega(n)} を満すものとしての  {\Theta(n)} であると考えてよさそう。

1.2.4 指数計算

 ここの主題とは無関係だが、

ここで、ある整数が偶数かどうかをテストする述語は、基本手続きの remainder (割り算の余り) を使って次のように定義します。
P46

ということから Scheme の言語仕様には、even? は含まれていないようだ (Racket 上では実装されている)。こういったことがこれから先頻繁に表れると考えられるので注意する。基本的に Racket 上で実装されているならば、実装の方法を確認した上で既に実装されているものを利用して問題無いと思う。

質疑応答など

「木の再帰プロセス」と「再帰プロセス」は別な概念か

 あえて「木の」と表記していたのが気になったとういことだったが、「木の再帰プロセス  {\in} 再帰プロセス」という考えで問題は無いか。

両替アルゴリズムの他のより良いものは何があるか

一方で、答えを計算するためのよりよいアルゴリズムをどう設計するかというのは自明ではありません。この問題は、読者への宿題とします。
P42

読書会中にはメモ化の他には、何かしら反復プロセスで実装するというアバウトな考えしか浮かばなかった。

 その後、木の下から集めていくことをイメージして1時間くらい考えてみたがわからなかった。

 {\Theta} は空間や計算量共に使えるものか

 P43 で定義された  {R(n)} のように様々なものを表すことができると考えられる。

ビックオー  {O} について

注:ビッグオーをビッグシータの意味で使うことも多いので注意が必要です。
http://mathtrain.jp/landausymbol

ということが URL のページで書いてあったが、実際に  {O} {\Theta} の意味で使っているところを目撃した記憶がない。

Aizu-SICP 第三回

2016/5/22 に Aizu-SICP 第三回 (SICP読む会) を行った。時間が空いたこともあり、復習に時間を使わせて頂いた。

タイムテーブル

  • 19:00 ~ 19:40: これまでの簡単な復習と練習問題の確認
  • 19:40 ~ 19:55: 読書 p32~p36 「1.2 手続きとそれが生成するプロセス」~「1.2.1 線形再帰と反復」練習問題前まで
  • 19:55 ~ 20:25: 質疑

今回の内容

1.2 手続きとそれが生成するプロセス

 手続きは、計算プロセスの局所展開 (local evolution) のためのパターンです。それは、プロセスの各段階が、どのように前の段階の上に構築されるかを記述するものです。プロセスの局所展開は手続きによって記述されるものですが、できればプロセスの全体的なふるまい、別の言い方をするとグローバル (global) なふるまいについても何か言えるようになりたいところです。これは、一般的にはとても難しいことです。しかし、プロセスの展開のよくあるパターンについての説明を試みるぐらいはできるでしょう。 P32

今一理解できないが、あるプロセス (関数) がどのような形 (一般的に見たふるまい) を持っているかを明かにしたいと理解した。例として以下の章では、再帰関数を二つの形に分けたり、計算時間などを計算することにより、そのプロセスのふるまいを一般的に説明することを試みている。

1.2.1 線形再帰と反復

 ここでは様々な概念に対して名前を付けている。概念としては知っていても何と呼ぶかが明確でないものが多かったが、名前が付くことで話をすることがしやすくなった。例として以下に挙げる。

遅延演算の連鎖

 P33 図 1.3 のような再帰関数において、展開後に行われる演算の連鎖こと。 (図 1.3 における *)

再帰プロセス

 遅延演算が行われる再帰関数の性質。また例による n! の計算は記録するための情報量や計算ステップ数が n に対して線形に増加するため、線形再帰プロセスと呼ばれる。

反復プロセス

 図 1.4 のように、関数の結果を引数として変数に保存することにより遅延演算が行われない再帰関数の性質。毎回の再帰が独立して計算を反復しており、またステップ数は n に対して線形に増加するため線形反復プロセスと呼ばれる。再帰プロセスと反復プロセスについては今まで、末尾再帰最適化できない方・できる方のように呼んでいた。
 反復プロセスが末尾再帰最適化できることの理由として、本文中の

反復プロセスの場合、プログラムの変数はどの時点でもプロセスの状態を完全に記述しています。 P35

というのが重要な点だとわかった。

状態変数

 反復プロセスにおいて、関数の状態 (繰返しの数やそれまでの反復の結果) を保存しておくための変数。関数 fact-iter における productcountermax-countを指す。

再帰プロセスと再帰手続きの違い

 再帰プロセスは上記のような、再帰関数ふるまいを一般化した場合のひとつを指しているが、再帰手続きとは自分自身を参照しているような関数 (手続き) を指す。今回の例では図 1.3・図 1.4 の関数は共に再帰手続きであるが、再帰プロセスであるのは図 1.4 のみである。

Aizu-SIPC 第二回

2015/12/20 に Aizu-SICP 第二回 (SICP読む会) を行った。 更新したつもりが下書きにしたまま半年放置されていた。

タイムテーブル

  • 19:00 ~ 19:15: 前回課題とした練習問題 1.2 ~ 1.5 の答え合わせ
  • 19:15 ~ 19:45: 読書 P22~26 「1.1.7 ニュートン法による平方根
  • 19:45 ~ 20:20: 質疑
  • 20:20 ~ 20:35: 読書 P27~P31 「1.1.8 ブラックボックス抽象化としての手続き」

今回の内容

1.1.6 条件式と述語

練習問題 1.2

(define 1-2 (/ (+ 4 5 (- 2
                         (- 3
                            (+ 6
                               (/ 4 5)))))
               (* (- 2 7)
                  (- 6 2)
                  3)))

練習問題 1.3

(define (1-3 a b c)
  (cond ((<= a b c) (sum-of-squares b c))
        ((<= b a c) (sum-of-squares a c))
        (else (sum-of-squares a b))))

練習問題 1.4

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

定義後

> (a-plus-abs-b (+ 3 1) (- 1 -5))

と実行した場合の評価の流れを以下に記述する

(a-plus-abs-b (+ 3 1) (- 1 -5))
; ↓
((if (> (- 1 -5) 0) + -) (+ 3 1) (- 1 -5))
; ↓
((if (> 6 0) + -) (+ 3 1) (- 1 -5))
; ↓
((if #t + -) (+ 3 1) (- 1 -5))
; ↓
(+ (+ 3 1) (- 1 -5))
; ↓
(+ 4 6)
; ↓
10

練習問題 1.5

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

適用順序評価の場合は

(test 0 (p))

を実行した時に引数である 0 と (p) が評価される。その時 p の評価を得るために関数 p の定義から (p) を評価する必要があり、評価が無限に続いてしまう。一方、正規順序評価の場合は test の引数を評価せず、 また if は第一引数が真の場合は第二引数のみを評価するので

(test 0 (p))
; ↓
(if (= 0 0) 0 (p))
; ↓
(if #t 0 (p))
; ↓
0

となり評価が終了する。

1.1.7 例: ニュートン法による平方根

 再帰を利用した繰返し処理の具体例であり、初めての例としては少々複雑に感じた。ひとつひとつの関数が何をするものなのか、じっくり見る必要あり。ぱっと見ただけですぐに理解できなければ具体的な値を入れて自分で展開していく。

練習問題 1.6

 練習問題 1.5 に似た原理の問題である。 if 式の特殊形式であり、評価規則が通常と違う (全ての引数を評価しない) ことによって再帰関数 sqrt-iter は成りたっている

練習問題 1.7

 小さい値の場合、今回の good-enough? 内では誤差の大きさを比較するための定数として 0.001 が使われているが、これに近い小さな値の平方根は、その平方根の値に対して誤差の割合がかなり大きくなり、さらに小さい値 (平方根が 0.001) に対しては全く求まらない。大きい値を使用すると good-enough? 内で二乗した時に桁溢れが起る(?) 前回の guess と新しい guess を比較する形で誤差を推定すれば例題の good-enough? よりは良い精度になると考えられる。 (実際に試していない)

練習問題 1.8

(define (cube x)
  (* x x x))

(define (1-8-improve guess x)
    (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (1-8-good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))

(define (1-8-sqrt-iter guess x)
  (if (1-8-good-enough? guess x)
      guess
      (1-8-sqrt-iter (1-8-improve guess x) x)))

(define (1-8-cube-root x)
  (1-8-sqrt-iter 1.0 x))

1.1.8 ブラックボックス抽象化としての手続き

関数一つ一つが持つモジュールとしての役割

 関数は何かしらひとつの仕事をし、複数の関数によって作られた関数はまた何かひとつの仕事をする。 Lisp でユーザーが作成した関数と、処理系に提供されている関数の差は無い。

束縛と代入の違いについての重要性

 ある変数と値の関係は、全てのスコープごとに独立している。現在のスコープにある変数と値の関係が定義されていなければ (自由変数)、ひとつ外のスコープを見に行く。あるスコープで使われている変数と同じ名前の変数がそのスコープの内側で使われており、値が別に束縛されたとしても、外側のスコープでは影響が無い。

ブロック構造

 P31 の例のような自由変数を使用する書き方は関数ひとつひとつが独立していないため読み辛く感じる。

質疑まとめ

関数の末尾の ? について

 Lisp で述語 (#t, #f を返す関数) を定義する際の慣例。

正の実数の平方根は必ず存在するのか

 http://d.hatena.ne.jp/takemita/20100114/p3

+とgood-enough?で、再定義した際の挙動が違うのはなぜ?

という質問が出て、読書会中はたしかにそうだなと思ったのだが、今試してみたところ普通に束縛され、自分で定義した関数との違いは無いようだった。

> (define + -)
> (define (test x y) (+ x y))
> (test 3 3)
0

読書会中は REPL でいろいろ実験を行っており、環境がかなり荒されていたのでその辺りが原因だったかもしれない。

scheme にループはあるか?

 繰り返しのための構文 do もあるが、一般に Scheme では繰り返しのために再帰を使用する。

scheme の引数の評価順序は?

Common Lispでは,関数の引数は左から右の順に評価される. Schemeでは評価順は意図的に未定義とされた. (それを忘れた人間は慌てふためいて実装者の笑いものになる.) http://www.asahi-net.or.jp/~kc7k-nd/onlispjhtml/continuations.html

レキシカルスコープの定義がよくわからない

このような定義のネストはブロック構造 (block structure) と呼ばれます。これは、基本的には最も単純な名前パッケージング問題の正しい解決方法です。しかし、ここにはもっといいアイデアが隠れています。補助手続きの定義を内部化することに加えて、それらを単純にすることもできます。x は sqrt に束縛されているので、sqrt の内部で定義された good-enough?, improve, sqrt-iterは x のスコープ内にあります。つまり、x をこれらの手続きに明示的に渡す必要はないということです。そうする代わりに、次に示すように内部定義では x を自由変数にします。そうすると、x の値は、それを囲む手続きである sqrt の引数から取ってくることができます。このような規定は レキシカルスコーピング (lexical scoping) と呼ばれます。27
27: レキシカルスコーピングにおいては、手続きの自由変数はその手続きを包む手続き定義の束縛を参照すると規定します。つまり、手続きが定義された環境での探索が行われるということです。
P.31

P.28の「手続きを使う人が、それがどうやって実装されているかについての知識を求められるべきではありません。」とは?

 関数を作成する側が注意するべき項目であり、「手続きを作る人は、手続きを使う人に、手続きの内部の知識を持つことを要求してはいけない」というような意味と読書会中に理解した。 これによると dynamic scope は完全に否定されていることになる?