Reasoned Schemer (67) 関数整理

ひとつひとつの関数のお仕事をひとことで言えて

やってみよう
その前に用語のまとめ

• association: carが変数で、cdrが変数または値のpair
  • cdrの値には変数が含まれることもある
• substitution: associationのリスト
  • 同じ変数がcarに2回以上出てくることはない
• stream: substitutionのリスト（suspensionあり)
  • goalが成功するための条件みたいなもの
  • Anがassociationだとすると((A1 A2) (A3))というストリームは「A1かつA2であるかまたはA3である」という条件みたいなもの（まだたぶんうまく言えてない）
• goal: substitutionを初期条件として取り、substitutionのstreamを返す関数
• reified-name substitution: 変数とreified-nameを置き換えるsubstitution

呼び出し関係を軽く意識して並べてみる

とりあえず小物

• (var name): nameという名前の変数を定義する
• (var? x): xは変数か
• empty-s: からっぽのsubstitution

ユニフィケーション

• (unify u v s): uとvが同じになるようにsubstitusionsを拡張する
  • (walk v s): 変数vをsubstitutionsで置き換える
    • 置き換えた結果が変数であればさらに置き換えを進める
    • リストになったらそれ以上は置き換えない
  • (ext-s x v s): 変数xと値vのassociationでsubstitutionsを拡張する
    • 拡張できない場合は#f
    • (occurs? x v x): 変数xと値vのassociationがsubstitutionsに循環を作るか

goal

• succeed: 常に成功するgoal
• fail: 常に失敗するgoal
• (== u v): uとvをsでunifyしたstreamを返すgoal
• (disj2 g1 g2): g1とg2のどちらがが成功すれば成功するgoal
  • (g1 s)と(g2 s)をappend-infして返す
  • (append-inf s-inf t-inf): ふたつのstreams-infとt-infをひとつのstreamにつなぐ
• (conj2 g1 g2): g1とg2の両方が成功するときだけ成功するgoal
  • stream: (g1 s) の各要素(substitution)にg2を適用する
  • (append-map-inf g s-inf): streams-infの各要素にgoal gを適用する

run

• (run n (x0 x ...) g ...): goal g ...を満たす変数の組x0 x ...をn個求める
  • (call/fresh name f): nameという名前の変数を作ってfに適用する
    • fはgoalを返す関数
  • (reify v): 変数vをreifyする関数を返す
    • その関数にstreamを適用するとvをreifyしたものが返される
    • (walk* v s): 変数vをリスト内部までsubstitutionsで置き換える
    • (reify-s v r): 値vに現れるfreshな変数をreified variableに置き換えるためのreified-name substitutionを返す
      • (reify-name n): _0のような変数名を作る
  • (run-goal n g): goal gを満たすsubstitutionをn個まで返す
    • (take-inf n s-inf): stream s-infの先頭からn個の要素を返す

まだ手ごたえがちょっと不足しているんだがどうすれば