Reasoned Schemer (38) 8章 未体験ゾーン1

ここからが未体験ゾーン

(logo n b q r)でn = b^q + rの関係

見るからに複雑そう
単にq（やr）を求めるだけでなくnやbを求めるのにも使えたり
無限に値を探し続けたりしないようにしたりするだけでここまで書かなきゃ
いけないものなのか

condeがあると実行が複数の流れに分かれたり
式も上から順に読めばいいとは限らなかったり
どの変数が決まっててどの変数を決めようとしてるのかわからなかったり
読んで理解するのがうんと大変になってる気がするんですけど
Prologとかやってるひとはすんなり読めたりするんですかね

でもとりあえず読もうとはしてみる
まずは3つのヘルパー関係から

(repeated-mulo n q nq)はn^q = nqという関係
これは読める

次は(exp2o n b q)
2^q = nという関係っぽいけどbの役割がちょっとわからない
logoからは(exp2o n '() q)という形で呼ばれている
splitoにも似てる

condeの中身を見ていく

まず1行目 ((== '(1) n) (== '() q))
これは2^0 = 1ということ
問題ない

2行目 ((>1o n) (== '(1) q) (fresh (s) (splito n b s '(1))))
nが1より大きくて、qが1で(splito n b s '(1))なら成功
(splito n b s '(1))であるというのは
nをbの長さ+1でsと(1)に分けられるってことだな
とりあえずb == '()の場合で考えると
nは(0 1)から(1 1)になるのかな
splitoの理解からして怪しい
2^q = nという関係じゃなくて
2^q <= n（ただしqは最大）という関係、って感じ？
bがどうなっていくかも見てみないとわからないな

3行目

((fresh (q1 b2) 
   (== `(0 . ,q1) q)        # qの最下位ビットは0
   (poso q1)                # ただしq1が()ではダメ
   (<lo b n)                # bはnより短い
   (appendo b `(1 . ,b) b2) # ??
   (exp2o n b2 q1)))        # 再帰

appendoは何をしているんだろう
一見bをちょっとずつ伸ばしてるだけに見えたけどよく見ると
bが()ならb2は(1)として
bが(1)ならb2は(1 1 1)
bが(1 1 1)ならb2は(1 1 1 1 1 1 1)
だよな
なんか見間違えてるか
長さが2倍+1になっていくんだけどそんなことあるか

ちょっと脳内で動かしてみるか

たとえば(exp2o '(1 0 1) '() q)を評価するとする
(== ``(0 . ,q1) q)はあとに取っておいて
(exp2o '(1 0 1) '(1) q1)を評価する
そうすると2行目にマッチしてq1は(1)ってことになるのか
遡って(== ``(0 . ,q1) q)からqは(0 1)
合ってそうではある

bは何に使われているかというと
(<lo b n)と2行目の(splito n b s '(1))
(<lo b n)はたぶん無限に探し続けないためのチェック
(splito n b s '(1))では下位ビットを無視するために使ってる？

bがさらに伸びる場合っていうとどんなんかな
もうちょっとすっきり書けないとつらい気がするが

まあnを大きくすればいいだろう
(exp2o '(1 0 1 1) '() q)くらいでどうか
(== ``(0 . ,q1) q)はあとに取っておいて
(exp2o '(1 0 1 1) '(1) q1)を評価する
こんどは2行目にはマッチできないはず 4行目も
3行目にトライする
b2が(1 1 1)になって
(exp2o '(1 0 1 1) '(1 1 1) q)を評価
そうすると今度は2行目にマッチできない・・・のでは？
どうなるんだ？

ちょっと無理感出てきた
人力でできるものなのか

とりあえずスルーして処理系書いて動かしながらかなあ
動かしながらでもできる自信ないけど
printデバッグとかできるんだろうか