Common LispでPrologのようなものを作りましたが。
こういうことをしてる人っていっぱいいると思います。
目新しい事ではないと思いますけど、苦労したので公開します。

もっと簡単にできると思ってたのに難しかったです。
本当はPrologを作るにあたっての注意点など書いて行くつもりでしたが、全部難しかったので全部注意点です。

ファイル

match.lisp

上記のファイルは現時点で700～800行くらい。
Prologを作りたくなったらこのファイルを見ればわかると思います。
本当はC言語などで作り直せるよう、あまりLispっぽく作りたくなかったのですが、いろいろ難しくて結局lambda式のつなぎ合わせで作成しました。
別の言語への変換はそれなりに苦労すると思います。

あとはどこまで使えるか見て行こうと思います。
動作はかなり遅いと思いますが、何ができるのかいろいろ試していきたいです。
現時点ではテストが足りてないかも。

以降、使い方。

1. 使い方

まずは読み込ませます。

* (load #p"match.lisp")

matchというpackageができますので、そこで作業します。

* (defpackage work (:use cl match))
* (in-package work)

初期化が必要ですが、次のどちらかを行って下さい。

* (init-match)

あるいは局所的に初期化します。

* (with-match form...)

init-matchの方を行ったことにして話を続けます。

ルールを作成しましょう。
下記のようなルールを作成することを考えます。

aaa.
bbb(ccc, ddd).
eee(X) :- bbb(X, ddd), aaa.

defruleマクロで追加できます。

(defrule aaa)
(defrule (bbb ccc ddd))
(defrule (eee ?x) (bbb ?x ddd) aaa)

マクロではなく、式を評価したい場合は次のようにします。

(define-rule 'aaa)
(define-rule '(bbb ccc ddd))
(define-rule '(eee ?x) '(and (bbb ?x ddd) aaa))

最後のeeeだけ、and文にしていることに注意してください。

それでは実行してみます。

* (match aaa)
NIL
T

第一返却値nilは、変数があった場合のalistになります。
第二返却値tは、マッチしたことを意味します。

* (match (bbb ccc ddd))
NIL
T

* (match (bbb ccc eee))
NIL
NIL

変数を使用する場合は、?を付与します。

* (match (bbb ?x ?y))
((?X . CCC) (?Y . DDD))
T

_も使用できます。

* (match (bbb _ ?y))
((?Y . DDD))
T

最後にeeeを実行します。

* (match (eee ccc))
NIL
T

* (match (eee zzz))
NIL
NIL

少し複雑な例を示します。

* (defrule (append () ?x ?x))
* (defrule (append (?u . ?x) ?y (?u . ?z))
    (append ?x ?y ?z))
* (match (append ?x ?y (a b c d e f)))
((?X) (?Y A B C D E F))
T
*

これだけで終わってしまいました。
もしバックトラッキングを確認したいのであれば、 queryマクロを使います。

* (query (append ?x ?y (a b c d e f)))
?X = NIL
?Y = (A B C D E F)
(y or n) n  ★入力
?X = (A)
?Y = (B C D E F)
(y or n) n  ★入力
?X = (A B)
?Y = (C D E F)
(y or n) y  ★入力
((?X A B) (?Y C D E F))
T
*

あるいは、match-lisp関数を使います。

* (match-lisp
   '(append ?x ?y (a b c d e f))
   (lambda (list)
     (= 3 (length (cdr (assoc '?x list))))))
((?X A B C) (?Y D E F))
T
*

全部failにしたいなら、次のように実行します。

(defun match-collect (expr)
  (let (list)
    (match-lisp
      expr
      (lambda (alist)
        (push alist list)
        nil))
    (nreverse list)))

(dolist (x (match-collect '(append ?x ?y (a b c d e f))))
  (format t "~S~%" x))

実行結果

((?X) (?Y A B C D E F))
((?X A) (?Y B C D E F))
((?X A B) (?Y C D E F))
((?X A B C) (?Y D E F))
((?X A B C D) (?Y E F))
((?X A B C D E) (?Y F))
((?X A B C D E F) (?Y))

2. 機能一覧

Prologとして使える機能は非常に少ないです。
下記に列挙します。

true
fail
! (カット)
and
or
is
progn

notすらありません。
notは次のように定義するんですって。

(defrule (not ?p)
  (or (and ?p ! fail)
      true))

あと、isは分かりづらいかもしれません。
isは計算を行いますが、計算のオペレーターは全部Lispのevalに渡されます。
意図してませんでしたが、isはPrologとLispの橋渡しのような機能を持ちます。
例えばこんな感じで実行します。

* (with-match
    (defrule (aaa 100))
    (query (aaa ?x) (is ?y (+ 200 ?x))))
?X = 100
?Y = 300
(y or n)

上記の例である(+ 200 ?x)は、 evalに渡す前に?xのような変数を値に置き返しますが、 listとsimple-vectorくらいしか置換の対象にしませんので、あんまり複雑な式は渡さないようにしてください。

戻り値を無視したいなら、_に代入してください。

* (with-match
    (defrule (aaa 100))
    (match (and (aaa ?x) (is _ (format t "<<<~S>>>~%" '?x)))))
<<<100>>>

prognは、名前の通りLispのprognです。
isと同じように、式をevalで実行します。
返却値はbooleanとして解釈されます。

例えば、数値を比較する際の<なんかを作成したいときに使って下さい。

(defrule (< ?x ?y) (progn (< ?x ?y)))

3. Lisp関数

ルール初期化

【関数】init-match

matchを初期化します。
ルールを保存するspecial変数の準備を行います。

使用例

(init-match)

【関数】free-match

matchを開放します。
ルールを保存していたspecial変数をunboundにします。

使用例

(free-match)

【関数】clear-match

全てのルールを削除します。

使用例

(clear-match)

【マクロ】with-match

局所的にmatchを使用するためのマクロです。
次のように使用します。

使用例

(with-match
  (defrule aaa)
  (match aaa))

【マクロ】defrule

ルールを追加します。
マクロなので引数は評価されません。
評価が必要な場合は、define-rule関数を使用して下さい。

第一引数はルールの名前と引数です。
第二引数以降はルールのボディ部であり、goalの集合です。
goalは全てandで結合されます。

使用例

(defrule aaa)
(defrule (bbb ccc ddd))
(defrule (eee ?x) (bbb ?x ddd) aaa)

【関数】define-rule

ルールを追加します。
defruleと機能は同じですが、引数が評価されます。

第一引数はルールの名前と引数です。
第二引数はボディ部です。
defruleとはちがい、第三引数以降はありません。
第二引数は省略可能であり、デフォルト値はtrueです。

使用例

(define-rule 'aaa)
(define-rule '(bbb ccc ddd))
(define-rule '(eee ?x) '(and (bbb ?x ddd) aaa))

defruleとは違い、andを用いて定義しています。

【関数】delete-rule

ルールを削除します。

使用例

(delete-rule 'bbb)

マッチ関数

【関数】match-lisp

問い合わせの基本となる関数です。

第一引数は問い合わせ内容。
第二引数は、最後に実施するlambda式です。

第一引数の結果がtrueであった場合は、第二引数のlambda式を実行します。

第二引数のlambda式がtrueを返却した場合は、本関数が(values alist t)を返却します。
alistは、第一引数に含まれていた変数と値のリストです。

第二引数のlambda式がfalseを返却した場合は、バックトラッキングが実行されます。
結果に応じて第二引数が何度も実行されます。

実行例

(with-match
  (defrule aaa)
  (match-lisp 'aaa (constantly t)))
-> nil, t

【関数】match-true

問い合わせを行い、得られた結果をtrueで受け入れます。

第一引数は問い合わせ内容です。

match-lispの第二引数に(constantly t)を指定したものと同じです。
すなわち下記の通り。

(defun match-true (expr)
  (match-lisp expr (constantly t)))

【関数】match-fail

問い合わせを行いますが、すべて否定します。

第一引数は問い合わせ内容です。

match-lispの第二引数に(constantly nil)を指定したものと同じです。
すなわち下記の通り。

(defun match-fail (expr)
  (match-lisp expr (constantly nil)))

例えば次のような使い方ができます。

(defrule (prefix () _))
(defrule (prefix (?x . ?xs) (?x . ?ys)) (prefix ?xs ?ys))
(match-fail
  '(and (prefix ?x (a b c d))
        (is _ (format t "~S~%" '?x))))

★出力結果
NIL
(A)
(A B)
(A B C)
(A B C D)

【マクロ】match

問い合わせを行います。

可変引数を受け取り、andで結合した内容を問い合わせます。

match-trueのマクロ版です。
下記の定義と同じです。

(defmacro! match (&rest args)
  `(match-true '(and ,@args)))

【関数】query-lisp

問い合わせを行い、結果をCommon Lispのy-or-n-p関数で確認します。
Prologでいう、Queryです。

第一引数は問い合わせ内容です。

【マクロ】query

問い合わせを行い、結果をCommon Lispのy-or-n-p関数で確認します。
query-lisp関数をマクロ化したものです。

次の定義と同等です。

(defmacro query (&rest args)
  `(query-lisp '(and ,@args)))

実行例

(with-match
  (defrule (append () ?x ?x))
  (defrule (append (?u . ?x) ?y (?u . ?z))
    (append ?x ?y ?z))
  (query (append ?x ?y (a b c d e f))))
?X = NIL
?Y = (A B C D E F)
(y or n) n  ★入力
?X = (A)
?Y = (B C D E F)
(y or n) n  ★入力
?X = (A B)
?Y = (C D E F)
(y or n) y  ★入力
((?X A B) (?Y C D E F))
T
*

nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

Prologのようなものを作る

1. 使い方

2. 機能一覧

3. Lisp関数

ルール初期化

【関数】init-match

【関数】free-match

【関数】clear-match

【マクロ】with-match

【マクロ】defrule

【関数】define-rule

【関数】delete-rule

マッチ関数

【関数】match-lisp

【関数】match-true

【関数】match-fail

【マクロ】match

【関数】query-lisp

【マクロ】query