Reasoned Schemer (21) かけ算

8. Just a Bit More

> (run 10 (x y r) (*o x y r))
((() _0 ())
 ((_0 . _1) () ())
 ((1) (_0 . _1) (_0 . _1))
 :
 :

パターンで(つまりnonground valueで)いっぱい出てくる

(run* (x y) (addero x y '(1 0 1)))ってすると足すと5になる組み合わせがすべて出てくる

のときnonground valueが出てこないのは答えが決まってたから？

*oの定義の方がadderoよりも詳しく説明してある
こっちの方が初心者向きってことかな？

(defrel (*o n m p)
  (conde
    ((== '() n) (== '() p))
    ((poso n) (== '() n) (== '() p)

0とかけ算すると0
ここでは明確に「overlappingを避ける」と言っている

    ((== '(1) n) (poso m) (== m p))
    ((>1o n) (== '(1) m) (== n p))

1とかけ算しても変わらない
overlapしていない

    ((fresh (x z)
       (== `(0 . ,x) n) (poso x)
       (== `(0 . ,z) p) (poso z)
       (>1o m)
       (*o x m z)))

nが偶数ならば、nを半分にしたものとmをかけ算して2倍する

    ((fresh (x y)
       (== `(1 . ,x) n) (poso x)
       (== `(0 . ,y) m) (poso y)
       (*o m n p)))

nが奇数でmが偶数ならばnとmを入れ替える
上の式でnが減っていくように

    ((fresh (x y)
       (== `(1 . ,x) n) (poso x)
       (== `(1 . ,y) m) (poso y)
       (odd-*o x n m p)))))

nもmも奇数のときはodd-*oで

ってところで*oの定義は終わり

(defrel (odd-*o x n m p)
  (fresh (q)
    (bound-*o q p n m)
    (*o x m q)
    (+o `(0 . ,q) m p)))

nから1引いて2で割ったもの(x)にmをかけて、2倍してmを足すとpになる
これだけで計算はできる
bound-*oは何をしてるんだ？