Scheme修行　第17章　我変わる、ゆえに我あり！

計算の結果を保存しておいたり、途中の状況を保存しておく手法を習います。

ノート：

deep

最初のdeepの定義は特にメモは保存しないその場限りの定義。

関数deepは

引数mに適用する
mが0であれば、アトムpizzaである
mが0でなければ、(deep (sub1 m))をリストの先頭要素としたリストである

> (deep 5)
(((((pizza)))))
>

次に、計算結果を残す版。

deepMを定義する時点で、リストRsとリストNsを定義。またdeepと同じ内容の内部関数Dを定義。
findを使って既にNs/Rsに答えが含まれているか調べる
含まれていない場合、内部関数Dを使って答えを出し、Rs、Nsにそれぞれ保存して結果とする
含まれている場合、検索結果を結果とする

この関数ではNs/Rsに見つからなかった時に、既にNs/Rsに存在している答えを参照せずに答えを作成してしまう。再帰の途中の結果は一切保存されない。
この定義をdeepM1として動作確認をする。

> (deepM1 5)
(((((pizza)))))
>

内部関数Dで再帰する際にDではなくdeepMを呼ぶ様にする。sub1する毎にdeepMを適用するので、その都度検索し、結果を保存する。一度mでdeepMを呼ぶと1〜mの全ての結果がNs/Rsに保存される。
この定義をdeepM2として動作確認をする。

> (deepM2 5)
(((((pizza)))))
>

Dを定義する際にDの中身からDを参照しないのでletrecである必要がなくなる。

> (deepM3 5)
(((((pizza)))))
>

letを二重にする意味は無いので一つのletでNs、Rs、Dを定義する。

> (deepM4 5)
(((((pizza)))))
>

ここでDは一回しか参照されないので、参照している箇所に展開する事が出来る。

> (deepM5 5)
(((((pizza)))))
>

lambdaで関数を定義して直ちに引数に適用するのは、letで仮引数に実引数を割り当てて、関数の定義そのものをその場で評価してその結果を割り当てるのと等価なので、mにnを割り当て、resultに(if …)以下の関数定義を適用した結果を割り当てる。

> (deepM6 5)
(((((pizza)))))
>

mと言う元仮引数はdeepMの仮引数nと等価、再帰適用する度にその値は変わるが、一回の適用では変わらず常にnと同じなので存在する意味は無い。全てのmはnに置き換えられる。

> (deepM7 5)
(((((pizza)))))
>

counter

さて、本題はここから。

ガウスは1〜100までの数の合計を101×50に置き換えた人物だそう。ここの例では1001×500。

deepRは単にdeepの結果をNs/Rsに記録するだけの関数。
consCを使ったdeepの定義をdeep2として動作を確認。

> (deep2 5)
(((((pizza)))))
>

ただし、このままではNの値を知る手段が無い。

新しいconsCの定義。
大域変数counterを定義。
consCの定義のlambdaの前で、大域変数counterに単にNの値を返す関数を割り当てる。大域的に参照出来るcounterを参照するとその時点でのNが返る。counterはNへのアクセサーとなる。読み出すだけで変更する事は出来ない。

DrRacketでは(define counter)と言う表記は許されず何らかの値を設定する必要がある。

新しいconsCをconsC2とし、consC2を使うdeepをdeep3として定義して動作を確認する。

> (counter)
0
> (deep3 5)
(((((pizza)))))
> (counter)
5
> (deep3 7)
(((((((pizza)))))))
> (counter)
12
>

supercounter

supercounterは1000から0までの数を引数に与えられた関数を適用する関数。さらに最後にcounterの値を返す。
関数の定義を加えてから走らせるとNは0に戻ってしまうので、もう一度(deep 5)、(deep 7)を適用してからsupercounterを適用する。

> (counter)
0
> (deep3 5)
(((((pizza)))))
> (counter)
5
> (deep3 7)
(((((((pizza)))))))
> (counter)
12
> (supercounter deep3)
500512
>

set-counter

ゲッターとしてのアクセサーとしてcounterを定義した様に、セッターを定義する。ゲッターを持ったconsCをconsC3として、consC3を使ったdeepをdeep4として定義し動作確認をする。

> (counter)
0
> (deep4 5)
(((((pizza)))))
> (deep4 7)
(((((((pizza)))))))
> (counter)
12
> (set-counter 0)
> (counter)
0
> (supercounter deep4)
500500
>

consC3を使うdeepMをdeepM8として定義し、動作を確認する。

> (counter)
0
> (supercounter deep4)
500500
> (deepM8 5)
(((((pizza)))))
> (counter)
500505
> (set-counter 0)
> (counter)
0
> (deepM8 5)
(((((pizza)))))
> (counter)
0
> (deepM8 7)
(((((((pizza)))))))
> (counter)
2
>

本と異なる結果になるのは、(set-counter 0)でNは0にリセットされるのに対してNsとRsは(deepM8 5)の結果を保存しているため。(deepM8 5)では新たにconsCが適用される事は無いのでNは0のまま。(deepM8 7)を評価した時に追加で二回consCが適用されるだけ。

本と合わせる為にもう一度全ての定義を評価し直す。

> (counter)
0
> (deepM8 5)
(((((pizza)))))
> (counter)
5
> (deepM8 7)
(((((((pizza)))))))
> (counter)
7
> (supercounter deepM8)
1000
>

Alan J.PerlisはACMに寄稿した記事"Epigrams on Programming"に「55. A LISP programmer knows the value of everything, but the cost of nothing.」と記している。
http://web.archive.org/web/19990117034445/http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html

著者はLISPerもやれば出来ると言いたかったのか？

rember1*C

rember1*のconsを全てconsCに書き換えて、consの回数を数える。

> (counter)
0
> (let ((a 'noodle)
        (l '((food) more (food))))
    (rember1*C a l))
((food) more (food))
> (counter)
0
>

consCは一回も適用していない。

new-lに割り当てる為に(R '( (food) more (food)) oh)が評価される。
new-carに割り当てる為に(R '(food) oh)が評価される。
1. 最初のアトムfoodに辿り着きconsCを適用する手前まで行くが、引数の(R '() oh)を先に評価する。
2. 引数が空リストなのでohが適用される。
new-carに'noが割り当てられる。
'noはアトムなので、consCを適用する手前まで行くが、引数の(R '(more (food)) oh)を先に評価する。
アトムmoreに辿り着き、再びconsCを適用する手前まで行くが、引数の(R '( (food)) oh)を先に評価する。
new-carに割り当てる為に(R '(food) oh)が評価される。
1. アトムfoodに辿り着き、consCを適用する手前まで行くが、引数の(R '() oh)を先に評価する。
  1. 引数lが空リストなので、ohが適用される。
new-carに'noが割り当てられる。
'noはアトムなので、consCを適用する手前まで行くが、引数の(R '() oh)を先に評価する。
1. 引数lが空リストなので、ohが適用される。
hew-lに'noが割り当てられる
'noはアトムなのでそのまま引数のl、すなわち( (food) more (food))を値とする。

５回consCを適用する手前まで行くが、その引数を評価する段階でohが適用され、consCはその度にスキップされる。

一方letccを使わない場合、返り値のリストは全てconsCを使って組み立てる事になる。

> (counter)
0
> (let ((f 'food) (m 'more))
    (consC3 (consC3 f (quote ()))
            (consC3 m
                    (consC3 (consC3 f (quote ()))
                            (quote ())))))
((food) more (food))
> (counter)
5
> (set-counter 0)
> (counter)
0
> (let ((a 'noodle)
        (l '((food) more (food))))
    (rember1*C2 a l))
((food) more (food))
> (counter)
5
>

プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート