Scheme修行　第18章　我変わる、ゆえに我同じなり！

consセルをクロージャーで実現する話。そう言えばSICPでも同じ事をしていた様な…。

この章を読んで始めて第６章で登場する『影法師（shadow）』の意味が分かりました。影法師とは同じ事を表現する別の実装の事を指している様です。第６章では普通のS式ではない算術式を表すリストの世界を作り、その算術式を計算する演算子も実装しました。また自然数を表現するのに単に数のリテラルではなくリストに含まれる空リストの数で表現する世界、及びその世界で使える幾つかの述語と演算子が紹介されていました。この章ではリストを別の方法で実装しています。

ノート：

kons、kar、kdr

kons、kar、kdrが出発点。

関数konsはクロージャを返す。

そのクロージャには引数のkarとkdrが結び付いている。
そのクロージャは引数selectorに適用する。
引数selectorに適用されると、結び付いているkar、kdrにselectorを適用する。

関数karはkonsが返したもの（ここではクロージャ）に適用する。
（関数carはconsが返したもの（普通はリストあるいはconsセル）に適用する）

引数（クロージャ）をある関数に適用する。
その関数は二つの引数aとdを取り、引数aを関数値とする。

この「ある関数」はkonsの定義のselectorとなる。selectorはkarとkdrに適用されるので、この場合はkonsに渡されたkarが関数値となる。つまり関数karを適用すると関数konsに渡した第１引数のkarが得られる。

関数kdrは同様に関数konsに渡した第２引数のkdrが得られる。

このkonsを使ってlotsを実装する。

> (lots 3)
#<procedure:...er/section18.rkt:3:4>
>

konsが作るのは従来のリストではない為、結果を表示出来ない。

lenkthを実装し動作確認をする。

> (lenkth (lots 3))
3
> (lenkth (lots 5))
5
> (lenkth (lots 15))
15
>

こちらはちゃんと動作している事が確認出来る。

konsCをconsCと同様に以下の様に実装する。

(define kounter (lambda () 0))
(define set-kounter (lambda () 0))
(define konsC
  (let ((N 0))
    (set! kounter (lambda () N))
    (set! set-kounter (lambda (x)
                        (set! N x)))
    (lambda (x y)
      (set! N (add1 N))
      (kons x y))))

add-at-endを実装して動作を確認する。

> (kounter)
0
> (add-at-end (lots 3))
#<procedure:...er/section18.rkt:3:4>
> (kounter)
3
>

bons

bonsはkonsと異なり引数を一つだけ取る。

konsと同じ様にクロージャを返す。
kdr部分はクロージャ毎にローカルに持つ。kdrの初期値は空リスト。
クロージャは三つの引数を取る関数selectorを引数に取る。
1. 一つ目の引数にはkdrを書き換える為の関数
2. 二つ目の引数はbonsに与えられた引数kar
3. 三つ目の引数は現在のkdr

bonsが作るものに対するkarはselectorとして二つ目の引数を返す関数を渡せば良い。
bonsが作るものに対するkdrはselectorとして三つ目の引数を返す関数を渡せば良い。
bonsが作るものに対するset-kdrはselectorとして一つ目の引数である関数を返す関数を渡してその関数を取り出し、それを適用してkdr部分を書き換えれば良い。

bonsは最初のkonsと全く同じものを作る訳ではないので、kons、kar、kdrを再定義する必要がある。

新しいkonsは

kar部分(a)とbonsを使ってまずものを作る
set-kdrでkdr部分を設定する
ものを返す。

set-kdrがものを返す仕様であればletでcを作る必要は無いのだが。

これでadd-at-end-tooが実装出来る。ここでは全てのリストがbonsで作られたリストである必要がある。

リストの末尾に卵を加えるときにkonsをしましたか。
新しい卵のときだけです。

はadd-at-end-tooの中の(kons (quote egg) (quote ()))の部分を指しているのか？　(add-at-end-too dozen)でkonsを使った回数が1回との事なので、どうやらその様。

dozenのなかのkonsはbakers-doesn-tooのなかの最初の12個と同じだということですか。
まったくもってそのとおり！

はadd-at-end-tooはリスト全体を作り替えず、最後のkons（consセル相当）のkdr部分のみを書き換えている。12個目は書き変わって入るが同じオブジェクト（クロージャ）。

dozenのなかのkonsはbakers-doesnの中の最初の12個と同じだということですか。
まったくもって違います！

はadd-at-endを使っているので、全てのkons（consセル相当）は新規に作られている事を意味する。

今度は何回のkonsを使いましたか。
14回です。
13回ではなくて驚きましたか。
はい。

の部分はadd-at-end-tooを使った事で、元のdozenが13個のeggを含むリストに書き替わっているから。

bakers-dozen-againはadd-at-endを使っているために、全て元のdozenとは異なるkonsだし、前回作ったbakers-dozenのkonsとも異なる。

eklist?を実装して動作確認する。

> (eklist? bakers-dozen bakers-dozen-too)
#t
>

ライプニッツの名前が挙がっている。ライプニッツによる同一性の定義を引き合いに出している物と思われる。eklist?の定義からすると二つの物が互いに過不足無く同じ性質を持っている（eq?が#tを返す）と言う事か。

same?

同一性について同じオブジェクト（あるいはセル）であるかと言う定義を導入。Schemeを作ったGerald SussmanとGuy Steele Jrとこの同一性の定義についての関係は不明。

c1とc2それぞれのkdrをt1、t2にそれぞれ退避して、（値をコピーする訳ではない）
c1のkdrを1に、c2のkdrを2に変更する
c1のkdrとc2のkdrを比較する
c1とc2のkdrをそれぞれ元に戻す
比較の結果を返す

c1とc2が同じセルであれば両方ともkdrは2に変わっているので同じと判断される。

> (same? bakers-dozen bakers-dozen-too)
#f
>

本では#tと言う事になっているが、bakers-dozenはdozenをkonsでコピーしている筈なので#fが正しい筈。

> (same? dozen bakers-dozen-too)
#t
>

bakers-dozen-tooはdozenをそのまま利用して最後のセルのkdrのみを書き換えたので#tが正しい。

その後の会話も#tが答えである前提の様な雰囲気なので、bakers-dozenと比較した部分がタイポの様に思われる。

最初のkonsの定義と区別する為に二番目の定義をkons2として

> (same? (kons2 (quote egg) (quote ()))
         (kons2 (quote egg) (quote ())))
#f
>

konsは呼ばれる度に新規のクロージャを作るので、異なるkonsとなる。

(set-kdr (last-kons long) long)はループになったリストを作ってしまうのでlenkthを適用すると帰って来ない。

> (define long (lots2 12))
> (lenkth2 long)
12
> (set-kdr (last-kons long) long)
> (lenkth2 long)

Interactions disabled

(set-kdr (last-kons long) (kdr (kdr long))も最後のkonsの次を３番目のkonsに繋いでしまうため「６の字」状のループを作ってしまい、同じくlenkthを適用すると帰って来ない。

> (define long (lots2 12))
> (lenkth2 long)
12
> (set-kdr (last-kons long) (kdr2 (kdr2 long)))
> (lenkth2 long)

Interactions disabled

finite-lenkth

内部関数Cは二つのポインタを引数に取る。
最初のポインタは再帰の度に一つ進み、二番目のポインタは再帰の度に二つ進む。slとqkはslowとquickか？
Cが再帰を止めるのは
1. pとqが同じセルの時
2. qがリストの末尾から出た時、qは数えるべきセルを指していないので値は０。
3. qがリストの末尾の時、qが指している最後のセルの分を１と数える。
pとqが同じセルを指す事無くqが末尾に到達した場合、qは二つずつ進んでいるので１回の再帰毎に２を足す事になる。
最初にCを呼ぶときにはpのセルは空ではないので最後に１を足す。

ループになっている場合にqが進んで行って既に通過したセルに戻った瞬間にループが検出される訳ではない。pとqは異なるスピードで走査している為にいずれqはpに追いつく。ここではqはpの２倍のスピードなのでpが一巡し終わった瞬間にqは二巡して、その時点でpとqは同じセルを指す事になる。

12個の要素を持つループを走査したときのpとqが指しているセルの位置をトレースすると：
(1, 2) (2, 4) (3, 6) (4, 8) (5, 10) (6, 12) (7, 2) (8, 4) (9, 6) (10, 8) (11, 10) (12, 12)

13個の要素の場合：
(1, 2) (2, 4) (3, 6) (4, 8) (5, 10) (6, 12) (7, 1) (8, 3) (9, 5) (10, 7) (11, 9) (12, 11) (13 13)

動作確認をする。

> (define long (lots2 12))
> (lenkth2 long)
12
> (finite-lenkth long)
12
> (set-kdr (last-kons long) long)
> (finite-lenkth long)
#f
>

プログラミング再入門

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