はじめに
前から、「Prolog で書く時 ',' や括弧を書くのが面倒だから Ocaml みたいな文法で書けるといいなあ」と思っていました。
λProlog (Lambda Prolog) の紹介 を読んでいて、これは良さそうなのではと触ってみることにしました。
まずは、「ESP カード５枚の正答率は？（その１）」の Prolog コードをλProlog で動かしてみようと思います。
ELPI のインストール
まずは処理系が必要なので、インストールします。
$ opam install elpi
を実行するだけで elpi コマンドが使えるようになりました。
ELPI への移植
permutation/2, select/3 の実装
permutation/2 で実際のカードの並びと推測するカードの並びの全組み合わせを出して正誤を判定する、というのが実装の肝です。
ELPI を起動して、
goal> permutation [1,2,3] X.
などと投入してみましたが、constant permutation has no declared type. で Failure となります。
どうやら permutation/2 がないようです。
仕方がないので自分で実装することにします。
といっても
GNU-Prolog のソースコード
のソースにある
permutation([], []).
permutation(L, [H|T]) :-
select(H, L, Rest),
permutation(Rest, T).
をそのまま ELPI の記法に直すだけです。
このとき必要な select/3 もやはりなかったので、
GNU-Prolog のソースコード
にある
select(X, [X|T], T).
select(X, [H|T1], [H|T2]) :-
select(X, T1, T2).
も ELPI の文法で書き直すことにします:
pred permutation o:list A, o:list A.
permutation nil nil.
permutation (X :: Rest) L :- permutation Rest L1, select X L L1.
pred select o:A, o:list A, o:list A.
select X (X :: T) T.
select X (H :: T1) (H :: T2) :- select X T1 T2.
これで ELPI 上でも permutation/2 が使えるようになりました。
正答カード数を数える
select/3, permutation/2 を移植できたことに気を良くしてさらに進めます。
実際のカードの並びと推測したカードの並びとを比較して、幾つ正解があるか数える述語
% ２つのリストについて、一致する要素をカウントする
正答数を数える([], [], _累計, _正答数) :-
_正答数 = _累計.
正答数を数える([H1|R1], [H2|R2], _累計, _正答数) :-
( H1 = H2 ->
_累計2 is _累計 + 1,
正答数を数える(R1, R2, _累計2, _正答数)
; 正答数を数える(R1, R2, _累計, _正答数)
).
正答数を数える(_実際のカードの並び, _解答として与えたカードの並び, _正答数) :-
正答数を数える(_実際のカードの並び, _解答として与えたカードの並び, 0, _正答数).
も同様に、機械的に書き換えることで移植できます。
pred count_same_cards i:list A, i:list A, o: int.
count_same_cards L1 L2 N :- count_same_cards.aux L1 L2 0 N.
count_same_cards.aux nil nil N N.
count_same_cards.aux (X :: L1) (X :: L2) Ac N :-
!, Ac1 is Ac + 1, count_same_cards.aux L1 L2 Ac1 N.
count_same_cards.aux (_ :: L1) (_ :: L2) Ac N :-
count_same_cards.aux L1 L2 Ac N.
しかし、これだと Prolog そのまますぎる、もう少し ELPI っぽさが欲しい、とすこし欲が出てきました。
もう少しだけ ELPI っぽい書き方をしたい
というわけで若干書き直したのが以下です。
pred count_same_cards2 i:list A, i:list A, o: int.
count_same_cards2 L1 L2 N :-
pi aux \ (
(aux nil nil N :- !),
(pi x \ pi l1 \ pi l2 \ pi ac \ pi ac1 \
(aux (x :: l1) (x :: l2) ac :- !, ac1 is ac + 1, aux l1 l2 ac1)),
(pi x \ pi l1 \ pi l2 \ pi ac \
(aux (_ :: l1) (_ :: l2) ac :- aux l1 l2 ac))
) => aux L1 L2 0.
ここまで実装した述語を部品として、カード 5 枚の並び順を当てようとしたときの正答カード数を得る述語を以下のように実装することができます:
pred guess_5_cards o:int.
guess_5_cards OkCount :-
permutation [1,2,3,4,5] RealCards,
permutation [1,2,3,4,5] GuessCards,
count_same_cards2 RealCards GuessCards OkCount.
全体
これらを組み合わせて
処理全体を以下のように書くことができました。
% permutation/2
pred permutation o:list A, o:list A.
permutation nil nil.
permutation (X :: Rest) L :- permutation Rest L1, select X L L1.
% select/3
pred select o:A, o:list A, o:list A.
select X (X :: T) T.
select X (H :: T1) (H :: T2) :- select X T1 T2.
% count_same_cards2/3
pred count_same_cards2 i:list A, i:list A, o: int.
count_same_cards2 L1 L2 N :-
pi aux \ (
(aux nil nil N :- !),
(pi x \ pi l1 \ pi l2 \ pi ac \ pi ac1 \
(aux (x :: l1) (x :: l2) ac :-
!, ac1 is ac + 1, aux l1 l2 ac1)),
(pi x \ pi l1 \ pi l2 \ pi ac \
(aux (_ :: l1) (_ :: l2) ac :-
aux l1 l2 ac))
) => aux L1 L2 0.
% guess_5_cards/3
pred guess_5_cards o:int.
guess_5_cards OkCount :-
permutation [1,2,3,4,5] RealCards,
permutation [1,2,3,4,5] GuessCards,
count_same_cards2 RealCards GuessCards OkCount.
% histgram2/3
pred histgram2 i:int, i:list A, o:int.
histgram2 OkCount ListOfOk N :-
pi aux \ (
(aux nil N),
(pi lst \ pi ac \ pi ac1 \
(aux ((guess_5_cards OkCount) :: lst) ac :-
!, ac1 is ac + 1, aux lst ac1)),
(pi lst \ pi ac \
(aux (_ :: lst) ac :-
aux lst ac))
) => aux ListOfOk 0.
% esp1/0
pred esp1.
esp1 :-
std.findall (guess_5_cards _) Sols,
histgram2 0 Sols N0,
histgram2 1 Sols N1,
histgram2 2 Sols N2,
histgram2 3 Sols N3,
histgram2 4 Sols N4,
histgram2 5 Sols N5,
print N0, print N1, print N2, print N3, print N4, print N5.
実行すると、以下のような結果が得られます:
$ elpi esp1.elpi
goal> esp1.
Parsing time: 2.295
Compilation time: 0.003
Typechecking time: 0.082
5280
5400
2400
1200
0
120
Success:
Time: 0.112
Constraints:
State:
表示をきれいにフォーマットするのは今後の課題です。
まとめ
「ESP カード５枚の正答率は？（その１）」の Prolog コードを ELPI で動かしてみました。
-
select/3,permutation/2は見当たらなかったので、GNU-Prolog の実装を移植しました。 - Prolog で書いているときには、「いちいち括弧をつけるのが面倒だから Ocaml みたいな文法で書きたい」と思っていたのですが、いざ書いてみるとうっかりカンマをつけてしまいます。
- Prolog で書いたソースコードを ELPI 上で動かした、というだけのことなので、結局のところ一階述語論理の枠でしか捉えられていません。
- λProlog の理論的背景を含めてわかるようになりたいと思います。