Clojureで論理プログラミング

core.logicについて

Clojureではロジックプログラミングのライブラリーとしてcore.logicが利用可能です。

使い方

leinigenの場合

project.cljのdependenciesに以下を追加。

[org.clojure/core.logic "0.8.11"]

ネームスペースで

(ns logic-demo.core
  (:refer-clojure :exclude [==])
　 (:require [clojure.core.logic.fd :as fd])
  (:use [clojure.core.logic]  ))

基本的な使い方

(run* [q] (== 1 q))

実行結果

(1)

上のコードでは、「1と等しくなるようなもの」を全て求めるように命令しています。ここでのqは「論理変数」と呼ばれるもの。
run*は条件を満たす解を全て求めます。解の個数に上限nを置きたいときは

 (run n bindings & goals)

のように書きます。

論理変数は複数扱うことができます。

(run 1  [q r] (== [ 1 q  3] [1 2 r] ))

実行結果

([2 3])

fresh

freshは新しい論理変数を導入できるマクロです。

例えば、下記のようにすれば、偶数かどうかを判定する関係を作れます。

下記のコードでは、0から9までの偶数を全て求めています。

(defn eveno [x] (fresh [z] (fd/* z 2 x)))

(run* [q] (membero q [0 1 2 3 4 5 6 7 8 9 ]) (eveno q))

実行結果

(0 2 4 6 8)

(fd/* z　2 x)は、数学っぽく言えば、

「ある整数に対して 2*z=x　となる」

と理解するとすっきりするのではないでしょうか。

また、上で登場したmemberoは

(membero x l)

で「xが集合lの要素である」という関係です。

例：かけて100になる数の組み合わせを0から99のなかで列挙する。

(run* [q r]
  (membero q (range 100) )
  (membero r (range 100))
  (fd/* q r 100))

実行結果

([2 50] [4 25] [5 20] [10 10] [20 5] [25 4] [50 2])

conde defne

conde は与えられた条件のどれかを満たすようなものを全て求めます。論理の「または」に対応しています。

(run* [q r]
  (conde [(membero q '("French" "English" "German")) (== r "Europe")]
         [(membero q '("Japanese " "Chinese")) (== r "Asian")]))

実行結果

(["French" "Europe"]
 ["Japanese " "Asian"]
 ["English" "Europe"]
 ["Chinese" "Asian"]
 ["German" "Europe"])

conso, firsto, appendo

コレクションに関する問題を扱うときとても便利なのがこれらの関数です。

conso

(conso a d l)で,コレクションlのfirstがa,restがdという関係を規定します。

(run* [q] (conso q  [:a :b :c] [:x  :a :b :c]))

実行結果

(:x)

consoを使えば、以下のように再帰的なアルゴリズムで関係を作ることができるようになります。

例:　コレクションの和を求める。

(sumo l n)でコレクションlの要素の和がnという関係を定義する。

(defn sumo [l n]
  (conde
   [(emptyo l) (== n 0)]
   [(fresh [h t m] (conso h t l) (fd/+ m h n) (sumo t m))]))

(run* [q] (sumo [ 1 2 q] 6))

実行結果

(3)

core.logicではパターンマッチによるデストラクチャリングが利用可能です。デストラクチャリングをうまく使うと、上のようにconsoを使わなくてもコレクションに対する関係を簡潔にかけるようになります。

[a . r] => コレクションのfirstがa, restがｒ

上のsumoをパターンマッチを使って書き直してみます。

(defne sumo [l n]
  ([[] 0 ])
  ([[a . r ] _] (fresh [m] (fd/+ m a n) (sumo r m))))

(defne f (...))は(defn f (conde ...)と同じです。

応用例　（10を作るパズル)

ここまでの知識を使った応用例として

「10を作るパズル」

をcore.logicで解いてみたいと思います。

パズルのルール

与えられた4つの数字（1から9までの整数)を使って10を作る。演算は足し算、引き算、掛け算とする。

例：
1234 -> 1+2+3+4=10

(def ops [:add :sub :mul])

(defne solver [nums ops run-sum sum]
  ;; run-sum はここまでの総計。再帰の終わりでrun-sumはsumと一致する必要がある。
  ([[] _  _  _ ] (== run-sum sum))
  ([[n . rest-num] [op . rest-op] _ _ ]
   ;; まだ計算が残っている場合は、run-sumと次の数にすべての計算をためす。
   (conde
    [(== :add op) (project [n run-sum] (solver rest-num rest-op (+  run-sum n) sum))]
    [(== :mul op) (project [n run-sum] (solver rest-num rest-op (*  run-sum n) sum))]
    [(== :sub op) (project [n run-sum] (solver rest-num rest-op (-  run-sum n) sum))])))

(defn make-ten [n1 n2 n3 n4]
  (run* [op1 op2 op3]
    (membero op1 ops)
    (membero op2 ops)
    (membero op3 ops)
    (solver [n2 n3 n4] [op1 op2 op3]  n1  10)))

いくつか問題を与えてみます。

(make-ten 1 2 3 4) -> ([:add :add :add] [:mul :mul :add])
(make-ten 2 3 5 6) -> ([:sub :add :add])
(make-ten 1 1 9 3) -> ()

参考にしたサイトなど

core.logic

A Very Gentle introduction to Relational Programming

@nobkzさんのブログ