はじめに

前から、「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.pl

permutation([], []).
permutation(L, [H|T]) :-
	select(H, L, Rest),
	permutation(Rest, T).

をそのまま ELPI の記法に直すだけです。

このとき必要な select/3 もやはりなかったので、
GNU-Prolog のソースコード
にある

select.pl

select(X, [X|T], T).
select(X, [H|T1], [H|T2]) :-
	select(X, T1, T2).

も ELPI の文法で書き直すことにします:

permutation.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.

全体

これらを組み合わせて

処理全体を以下のように書くことができました。

esp1.elpi

% 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 の理論的背景を含めてわかるようになりたいと思います。