ESP カードを使ってλProlog に触ってみる

## はじめに

前から、「Prolog で書く時 ',' や括弧を書くのが面倒だから Ocaml みたいな文法で書けるといいなあ」と思っていました。

[λProlog (Lambda Prolog) の紹介](https://qiita.com/suharahiromichi/items/a046859da0c0883e7304) を読んでいて、これは良さそうなのではと触ってみることにしました。

まずは、「[ESP カード５枚の正答率は？（その１）](https://qiita.com/tadashi9e/items/bfd4778b28c5f0c28840)」の Prolog コードをλProlog で動かしてみようと思います。

## ELPI のインストール

まずは処理系が必要なので、インストールします。

```bash
$ 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 のソースコード](https://github.com/tadashi9e/gprolog-utf8/blob/gprolog-utf8/src/BipsPl/list.pl#L142)
のソースにある

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

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

このとき必要な `select/3` もやはりなかったので、
[GNU-Prolog のソースコード](https://github.com/tadashi9e/gprolog-utf8/blob/gprolog-utf8/src/BipsPl/list.pl#L125)
にある

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

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

```prolog: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` を移植できたことに気を良くしてさらに進めます。

実際のカードの並びと推測したカードの並びとを比較して、幾つ正解があるか数える述語

```prolog
% ２つのリストについて、一致する要素をカウントする
正答数を数える([], [], _累計, _正答数) :-
    _正答数 = _累計.
正答数を数える([H1|R1], [H2|R2], _累計, _正答数) :-
    ( H1 = H2 ->
      _累計2 is _累計 + 1,
      正答数を数える(R1, R2, _累計2, _正答数)
    ; 正答数を数える(R1, R2, _累計, _正答数)
    ).
正答数を数える(_実際のカードの並び, _解答として与えたカードの並び, _正答数) :-
    正答数を数える(_実際のカードの並び, _解答として与えたカードの並び, 0, _正答数).
```

も同様に、機械的に書き換えることで移植できます。

```prolog
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 っぽい書き方をしたい

というわけで若干書き直したのが以下です。

```prolog
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 枚の並び順を当てようとしたときの正答カード数を得る述語を以下のように実装することができます:

```prolog
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.
```

### 全体

これらを組み合わせて

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

```prolog: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 カード５枚の正答率は？（その１）](https://qiita.com/tadashi9e/items/bfd4778b28c5f0c28840)」の Prolog コードを ELPI で動かしてみました。

- `select/3`, `permutation/2` は見当たらなかったので、GNU-Prolog の実装を移植しました。
- Prolog で書いているときには、「いちいち括弧をつけるのが面倒だから Ocaml みたいな文法で書きたい」と思っていたのですが、いざ書いてみるとうっかりカンマをつけてしまいます。
- Prolog で書いたソースコードを ELPI 上で動かした、というだけのことなので、結局のところ一階述語論理の枠でしか捉えられていません。
- λProlog の理論的背景を含めてわかるようになりたいと思います。