Reasoned Schemer (102) logo 続き

ではコードを1行ずつ

((== '(1) n) (== '() q))はわかる

((>1o n) (== '(1) q) (fresh (s) (splito n b s '(1))))のnは
bの長さ+1をpとしてp個の0または1に1をくっつけたもの
式で書けば2^(p + q) <= n < 2^(p + q + 1)

bが0より大きいときを試してなかったので試しておく

> (run* n (exp2o n '() '(1)))
'((0 1) (1 1))
> (run* n (exp2o n '(1) '(1)))
'((0 0 1) (1 0 1) (_0 1 1))
> (run* n (exp2o n '(1 1) '(1)))
'((0 0 0 1) (1 0 0 1) (_0 1 0 1) (_0 _1 1 1))

あってる

次

    ((fresh (q1 b2)
       (== `(0 . ,q1) q) (poso q1)
       (<lo b n)
       (appendo b `(1 . ,b) b2)
       (exp2o n b2 q1)))

qが偶数ならqを半分にしてその代わりにナントカしてやっても答えは同じ、的な論法
たとえばqが4だったら2の4乗を計算する代わりにどうすると言ってるのか

ここでbが働いてくるんだな
(appendo b `(1 . ,b) b2)で長さが2倍+1になる（長さしか関係ないはず
たとえばqが(0 0 1)、bが()から始めると
qを半分にして(0 1)にしてもbを(1)にすれば同じ答え
さらにqを半分にして(1)にしてもbを(1 1 1)にすれば同じ答え

って言ってるんだな

> (run* n (exp2o n '() '(0 0 1)))
> (run* n (exp2o n '(1) '(0 1)))
> (run* n (exp2o n '(1 1 1) '(1)))

確かに同じだ