やろーじだい

ブログです

不定期に行うイベントに関する反省点

読書会にあたって、まとめの記事の日にちから分かるように非常に間があいてしまった。このように間が合いてしまった原因のひとつとして以下の画像のような連絡をしたことにあったと考えている。

f:id:lhcpr:20170608152944p:plain

というのも、「ある日以降に追って連絡します」というような曖昧すぎる連絡を行ってしまうことにより、暇になったら連絡しようという風に考えていつのまにか忘れているということが起った。参加者も記憶から薄れていってしまうし、思い出したとしてもその人の中での優先度は下がってしまう。主催者本人としても一度時間が空くとタイミングを見失ってしまい、目先の忙しさに追われて調整ができなくなってしまった。このようなことを二度もやってしまい初回から1年半でたった7回 (つい先月までは4回) しか読書会が行われていなかった。

改善策

改善策として考えたのは単純なことで、次回の設定を曖昧にしないというだけのこと。学年も研究室も違う大学生が常に毎週同じ時間が空いているということは無いので固定することは難しいが、以下の調整さんで行っているように、主催者が空いている時間帯を列挙して参加者全員が参加できる日に行うという風にしている。

前回の調整

この日程の調整を、ある日の読書会が終わった後に速やかに設定するようにした。もし急遽開催が難しくなった場合もすぐさま次の日程の選択肢を提示する。早ければ早いほど参加者も日程の調整がしやすい (優先度を上げてくれる) ので極力早めにやる。これによって前回に自分の体調不良で延期が発生してしまったが、極端に時間が空くことなく問題なく次が開催できた。

杜撰な主催にも愛想を尽かさずに参加してくれている人はたった3人になってしまったが、今後も卒業まで読めるだけ読んでいきたい。

おまけ

会津での生活が辛くなる夏にどこか避暑地でやりたいと思います。(これも早い内設定して連絡します。これはまだ具体的な日程を設定できないので許してください)

Aizu-SICP 第七回

第七回をやりました。

今回の内容

P59 1.3 高階手続きによる抽象の定式化 ~ P65 1.3.2 lambda を使って手続きを構築する 終わりまで

 今回は質疑を含めて読書会中に言及したものを含めて補足のように書いた。

1.3 高階手続きによる抽象の定式化

私達が普段まとめて「関数」と呼ぶところを、この本では、プログラミング的な意味では「手続き」という単語を、数学的な意味では「関数」という単語を使用しているので今後もこれに倣うようにする (以前これについて言及されている部分があったと記憶しているのだが見当たらなかった)。

1.3.1 引数としての手続き

項を計算するのに identity (恒等) 手続きを使うと、sum によって sum-integers を定義できます。
P62

さらっと出ているが、恒等手続きはある値に任意の手続きを適用できるように抽象化を行った際に、「なにも適用しない」ということをするためによく使われる重要なものなので、初めて触れる概念の場合は覚えておきたい。

P63 練習問題 1.29 ~ P65 1.33 まで

ここは一旦飛ばした

1.3.2 lambda を使って手続きを構築する

lambda という名前でなく、make-procedure (手続き作成) のような当たり前の名前をつけたほうが、 Lisp を勉強する人にはわかりやすく、怖そうな感じを与えないですんだかもしれません。
P67 注釈 53

比較的新しいプログラミング言語の場合は functionfn という単語を使う場合が多いのではないかと思ったので、適当に思いついた言語のラムダ式の定義方法を調べてみた。

C++ (構文) 参考

#include <iostream>
#include <string>
using namespace std;
int main(int argc, char const* argv[])
{
        string x = "I am string";
        [&] { cout << x << endl; } (); //参照
        [=] { cout << x << endl; } (); //コピー
        return 0;
}

Erlang (fun) 参考

> F = fun(X) -> X * X end.
#Fun<erl_eval.6.80247286>
> F(100).
10000

Go (func) 参考

func main() {
    fn := func() {
        fmt.Println("hello")
    }
    fn()
}

Haskell (: バックスラッシュ) 参考

inc = \x -> x + 1

main = do
    print $ inc 5

\(バックスラッシュ)をギリシア文字の λ(ラムダ)に見立てています。

OCaml (fun) 参考

# (fun x -> x * x) 5;;
- : int = 25

Python (lambda) 参考

num = (lambda x,y:x + y)(3,4)
print num    # 7

Rust (構文) 参考

// 引数リスト(i32, i32)をとって戻り値i32を返すクロージャ
let add = |x, y| { x - y };
let sub = |x, y| x + y;
println!("{} {}", add(1,2), sub(1,2));

// 引数なし/戻り値()のクロージャを宣言&呼出し(意味はない)
(||{})();

Scala (構文) 参考

(x: Int) => x * x 

lambda という単語を意識して使っているのは一部 (挙げたものの中では HaskellPython) であり、function (ここでの procedure) という単語を中心にするものや、予約語を使わずに構文で表現してしまうものも増えているようだった。事実 lambda という単語からは無名関数を作りだすものとしてのイメージが湧き辛いため今後もこの流れが多そうだ。

let を使って局所変数を作る

P69 の繰り返しになるが、 let がネストした例として更に以下に示す。

(let ([x 1])
  (let ([x 3]
        [y (+ x 3)])
    (+ x y)))
;=> 7

直感的には 9 になるのではないかと考える人もいるかもしれないが以下のように lambda 式で置き替えることができる。

((lambda [x] 
         ((lambda [x y] (+ x y))
          3 
          (+ x 3)))
 1)
;=> 7

したがって内側の lambda 式の引数に含まれる x と仮引数を表す x は無関係になる。そのため、展開前の例の内側の let にある (+ x 3)(+ 1 3) となるので結果は 7 になる。

P70 練習 1.34

(define (f g) (g 2))
(f f)

これの結果はどうなるかという問題で、安易に無限ループするのだろうと考えてしまった。しかし以下のように展開されるので無限ループには入らずエラーで止まる。

まず f というものは (lmabda (g) (g 2)) であると考えられる。

(f f)

((lambda (g) (g 2)) 2)

ここでラムダ式g2 を受けとるが 2 は関数ではないので *** ERROR: invalid application: (2 2) というエラーで停止する。

Aizu-SICP 第六回

再開した。

今回の内容

1.2.6 例:素数判定

読んですぐにわからない内容が多かったので、紙とホワイトボードを駆使して理解を試みた。

 まず素数判定として 1 から √n までの数で割っていく有名な手法についてだが、この時、1 ~ √n まででよいということをすぐに理解できなかったので、これについて考えた。

 注釈44に

もし d が n の約数であれば、n/d も約数になります。しかし、d と n/d の両方とも √n より大きいということはありえません。

とある。言葉としてはこの通りだがすぐにはピンと来なかったので証明を試みた。(参加者が考えたもの)

n = a x b (a,b∈Z, a<=b, a,b>0)
a <= b
a x a <= a x b
a x a <= n
a <= √n

よって n の約数である ab (a,b∈Z, a<=b, a,b>0) がある時、小さい方の約数 a は必ず √n 以下になる。

フェルマーテスト

n が素数で、a が n より小さい任意の正の整数であるとき、a の n 乗は法 n に関して a と合同である。

簡単に言い変えると

n が素数であるならば、任意の整数 a (a < n) を選んだとき、 an と a を n で割ったときの余りは等しくなる。

逆に言えば

任意の整数 a (a < n) を選んだとき、 an と a を n で割ったときの余りが等しいならば、n は素数である。

ただし、次の「確率的手法」で言われている通り、このフェルマーテストが失敗する (a^na が法 n に関して合同ではない) ならば n素数ではないと言い切れるが、逆の場合は n素数である確率が限りなく高いという意味になる (このテストを満しながらも素数ではない値がある<注釈47>)

 以下でフェルマーテストの例を簡単に見てみる

n = 3
a = 2
a^n = 8

a % n   = 2
a^n % n = 2

よって n は素数である (確率が非常に高い)

n   = 4
a   = 2
a^n = 16

a % n   = 2
a^n % n = 0

よって n は素数ではない (確定)

質問・議論

  • Θなどの意味について再確認
  • 素数判定が 1 ~ √n までで良いことの証明 (した)
  • フェルマーの小定理をわかりやすく (した)
  • フェルマーテストが Θ(logn) であることについて (何故か)

P53 には、「ある数値の冪乗の、別のある数値を法とした剰余を求める手続き」のステップ数が指数 (a^nn) に対して対数的に増加する (logn) とある。すなわち Θ(log n) というのはフェルマーテスト一回に必要な計算量であり、このフェルマーテストの精度を高めるために何度かフェルマーテストを行うことは考慮されていない。もし m 回ランダムに a を選択しフェルマーテストを行うならば計算量は Θ(m log n) となると考えられる。

今後について

  • この章の練習問題 (1.21 ~ 1.28) をどの程度やるかを考え中

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

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

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

近況

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

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

まとめる

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

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

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

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

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

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

書く

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

 そのメモ帳には本当にあらゆることを記録しており、例えば読書感想・その日の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

が成り立つ。