アルゴリズムを書かない！？論理型言語 Prolog 紹介

この記事について

論理型言語 Prolog について、数学的な概念の説明を省いて概要を説明し、ごく簡単な文法だけを用いて魔方陣のパズルの解を得るプログラムを作ります。

Prolog との出会い

ある日、「７つの言語 ７つの世界」という本が面白いと聞いて、早速買って読んでみました。
そのうちの１つに Prolog があったのですが、それまで手続き型言語しか書いたことのなかった私は、この言語がアルゴリズムを書かないというところに、衝撃を受けました。
で、興味がわいたのです。

Prolog とは？

Prolog は 1972 年に Colmerauer と Philippe Roussel によって開発された論理型言語で、数学や自然言語処理の分野で使われています。
ちなみに、名称の由来はフランス語の「PROgrammation en LOGique」だそうです。

Prolog では、手続き型言語のように「あれやって、これやって、こうやって答えを出してね！」といったコードは書きません。
ある問題に対して、答えの定義を「◯◯は××である」という形で並べていき、最後に「□□の条件を満たす△△は？」とプログラムに質問し、解を得るのです。
定義を並べていくあたり、論理型言語が宣言型言語に分類されているのも分かる気がします。
（宣言型プログラミング(Wiki)）

Prolog の実行環境

今回は Web 上で Prolog のプログラムを実行できる SWISH にお世話になります。
https://swish.swi-prolog.org/ にアクセスしてみると、次のような画面が出てきます。

ここで、「Program」ボタンをクリックすると、次のような画面になります。

左側はコード記述欄、右下は質問欄となります。

これで準備ができました。

Prolog の要素

Prolog のプログラムは「事実」と「ルール」で構成され、プログラムを実行し、「質問」することによって、ある問題に対する解を得ます。
それぞれについて説明していきます。

事実

事実とは、いわゆる「◯◯は××である」といった事柄です。
たとえば、「たまねぎは野菜である」なら次のように書きます。

food_category(onion, vegetable).

Prolog では、１つの定義は「.」で終わります。
「food_category」の部分は、事実やルールを識別する名前です。
同じ名前で複数定義することもできます。
「(onion, vegetable)」の部分は、事実の内容となります。
Prolog では、小文字で始まる単語はアトム（プログラム中の固有の識別子）です。
少しイメージしづらいですが、ここでは前述のとおり、「たまねぎは野菜である」くらいに覚えておいてください。

ルール

ルールとは、「◯◯なら××である」というような推論です。
たとえば、「指定された２つの食べ物が共に野菜であり、かつ異なる種類であれば野菜サラダである」なら次のように書きます。

vegetable_salad(X, Y) :- food_category(X, vegetable), food_category(Y, vegetable), X \== Y.

ルールは、「事実」と「ルール」を組み合わせることができ、「:-」の右側に、そのルールが成立する条件（「サブゴール」といいます）を書いていきます。
サブゴールをカンマでつなぐと AND、セミコロンでつなぐと OR になります。
「\==」は右辺と左辺が等しくないという演算子です。
X や Y 等の大文字で始まる文字や、「_」で始まる単語は変数です。
ひとまず、「指定された２つの食べ物が共に野菜であり、かつ異なる種類であれば野菜サラダである」と覚えておいてください。

質問

質問とは、定義した事実とルールに照らし合わせて、プログラムに問い合わせたい事柄のことです。
Prolog では、定義された事実とルールに基づき、質問に対して肯定または否定で答えてくれます。

さっそく、「たまねぎは野菜ですか？」と尋ねてみましょう。
まず、SWISH のコード記述欄に次のコードを記述します。

food_category(onion, vegetable).
food_category(carrot, vegetable).
vegetable_salad(X, Y) :- food_category(X, vegetable), food_category(Y, vegetable), X \== Y.

内容的には、
- たまねぎは野菜である
- にんじんは野菜である
- 指定された２つの食べ物が共に野菜であり、かつ異なる種類であれば野菜サラダである
と記述しました。

次に、SWISH の右下に次のように質問を記述し、「Run!」ボタンをクリックします。

food_category(onion, vegetable).

右側に回答用の小さなペインが現れ、「true」と表示されました。
事実として「たまねぎは野菜である」と定義しているので、肯定で返ってきたのです。

次はルールのほうで質問してみます。
「たまねぎとにんじんの組み合わせは野菜サラダですか？」と尋ねてみます。

vegetable_salad(onion, carrot).

やはり「true」と表示されました。

続いて、「たまねぎとトマトの組み合わせは野菜サラダですか？」と尋ねてみます。

vegetable_salad(onion, tomato).

今度は「false」が返ってきました。
「トマトは野菜である」という事実またはルールがないため、否定で返ってきたというわけです。

ユニフィケーション

ユニフィケーションは、2 つの項が等しくなるように解を補完することをいいます。
たとえば、「x = 3」なら、プログラムの方で x に 3 を補完し、解を求めます。
これがユニフィケーションです。

ユニフィケーションを使ってる感がでるように、今度はもう少し複雑な質問をしてみましょう。
先ほどは「たまねぎとにんじんの組み合わせは野菜サラダですか？」と質問しましたが、次は「食べ物の種類が野菜である食べ物はどれですか？」と質問します。

次の事実とルールを記述します。

food_category(onion, vegetable).
food_category(carrot, vegetable).
food_category(apple, fruit).
vegetable_salad(X, Y) :- food_category(X, vegetable), food_category(Y, vegetable),  X \== Y.

このコードの中に、「食べ物の種類が野菜である食べ物を求める」コードはどこにもありません。

さて、質問してみます。

food_category(Food, vegetable).

すると、次のような答えが返ってきます。

Prolog では、質問をすると答えが肯定になるようにユニフィケーションを用いて変数を推測します。
これにより、プログラマがアルゴリズムを書かずとも、プログラムが推論を駆使して解を探し出してくれるのです。
ちなみに、今回は、たまねぎ以外ににんじんも解になるので、画面に表示された「Next」を押すと、次に carrot が返ってきます。

変数は複数でもいけます。
たとえば、

vegetable_salad(Food1, Food2).

と質問すると、

というように、すべての野菜サラダの組み合わせを得ることができます。

面倒な途中計算はすべてプログラムがやってくれます。
プログラマは、あるルールを満たす条件を定義していくだけです。

魔方陣を作る

ここまでで事実、ルール、質問、そしてユニフィケーションについてご紹介しました。
なんとなく「パズル解くのとかいけそうな言語だな」という感じが出てきませんか？
ということで、3 x 3 の魔方陣を作ってみたいと思います。

魔方陣とは

みなさん知ってるかと思いますが、魔方陣の特徴は次のようなものです。

1. 各マスには 1 ～ 9 までの数字が割り振られる
2. 各マスの数字は重複しない
3. 縦、横、斜めのどの一直線も、足したら合計 15 である

こういうやつですね。

2	7	6
9	5	1
2	7	6

今回は、左上から順に変数を C11 ～ C33 に割り振ります。
次のようになります。

C11	C12	C13
C21	C22	C23
C31	C32	C33

ざっとこんな感じでしょうか。
それでは定義を順に書いていきましょう！

ルール 1: 各マスには 1 ～ 9 までの数字が割り振られる

「セルの値は数字である」というルールを定義します。

magic_number(C) :-
    C is 1;
    C is 2;
    C is 3;
    C is 4;
    C is 5;
    C is 6;
    C is 7;
    C is 8;
    C is 9.

「is」は代入です。
よって、magic_number は「Number は 1 ～ 9 のいずれかである」ルールということになります。

ルール 2: 各マスの数字は重複しない

「どの数字も重複しない」ルールを定義します。
（ちょっと長くなります）

unique_numbers(C11, C12, C13, C21, C22, C23, C31, C32, C33) :-
    C11 \== C12, C11 \== C13,
    C11 \== C21, C11 \== C22, C11 \== C23,
    C11 \== C31, C11 \== C32, C11 \== C33,
    C12 \== C13,
    C12 \== C21, C12 \== C22, C21 \== C23,
    C12 \== C31, C21 \== C32, C21 \== C33,
    C13 \== C21, C13 \== C22, C13 \== C23,
    C13 \== C31, C13 \== C32, C13 \== C33,
    C21 \== C22, C21 \== C23,
    C21 \== C31, C21 \== C32, C21 \== C33,
    C22 \== C23,
    C22 \== C31, C22 \== C32, C22 \== C33,
    C23 \== C31, C23 \== C32, C23 \== C33,
    C31 \== C32, C31 \== C33,
    C32 \== C33.

ルール 3: 縦、横、斜めのどの一直線も、足したら合計 15 である

まず、「3 つのセルの合計は 15 である」ルールを定義します。

cell_total_is_15(C1, C2, C3) :-
    C1 + C2 + C3 =:= 15.

「=:=」は算術演算子で、いわゆるイコールです。

行については次のように記述します。

cell_total_is_15(C11, C12, C13),
cell_total_is_15(C21, C22, C23),
cell_total_is_15(C31, C32, C33).

列。

cell_total_is_15(C11, C21, C31),
cell_total_is_15(C12, C22, C32),
cell_total_is_15(C13, C23, C33).

斜め。

cell_total_is_15(C11, C22, C33),
cell_total_is_15(C31, C22, C13).

最後に、コードの全文を載せておきます。

magic_number(C) :-
    C is 1;
    C is 2;
    C is 3;
    C is 4;
    C is 5;
    C is 6;
    C is 7;
    C is 8;
    C is 9.

unique_numbers(C11, C12, C13, C21, C22, C23, C31, C32, C33) :-
    C11 \== C12, C11 \== C13,
    C11 \== C21, C11 \== C22, C11 \== C23,
    C11 \== C31, C11 \== C32, C11 \== C33,
    C12 \== C13,
    C12 \== C21, C12 \== C22, C21 \== C23,
    C12 \== C31, C21 \== C32, C21 \== C33,
    C13 \== C21, C13 \== C22, C13 \== C23,
    C13 \== C31, C13 \== C32, C13 \== C33,
    C21 \== C22, C21 \== C23,
    C21 \== C31, C21 \== C32, C21 \== C33,
    C22 \== C23,
    C22 \== C31, C22 \== C32, C22 \== C33,
    C23 \== C31, C23 \== C32, C23 \== C33,
    C31 \== C32, C31 \== C33,
    C32 \== C33.

cell_total_is_15(C1, C2, C3) :-
    C1 + C2 + C3 =:= 15.

magic_square(C11, C12, C13, C21, C22, C23, C31, C32, C33) :-
    /* ルール 1 */
    magic_number(C11),
    magic_number(C12),
    magic_number(C13),
    magic_number(C21),
    magic_number(C22),
    magic_number(C23),
    magic_number(C31),
    magic_number(C32),
    magic_number(C33),

    /* ルール 2 */
    unique_numbers(C11, C12, C13, C21, C22, C23, C31, C32, C33),

    /* ルール 3 */
    cell_total_is_15(C11, C12, C13),
    cell_total_is_15(C21, C22, C23),
    cell_total_is_15(C31, C32, C33),
    cell_total_is_15(C11, C21, C31),
    cell_total_is_15(C12, C22, C32),
    cell_total_is_15(C13, C23, C33),
    cell_total_is_15(C11, C22, C33),
    cell_total_is_15(C31, C22, C13).

まずはすべての解を求めてみましょう！

magic_square(C11, C12, C13, C21, C22, C23, C31, C32, C33).

で質問すると、3 x 3 で得られるすべての魔方陣の解が得られます。

また、

magic_square(6, 1, C13, C21, C22, C23, 2, C32, C33).

というように一部だけ数字を入れた状態で質問すると、次のように変数の部分の条件を満たす解を得ることができます。

C13 = 8,
C21 = 7,
C22 = 5,
C23 = 3,
C32 = 9,
C33 = 4

なんとなく感じはつかめたでしょうか？

なお、今回ご紹介したコードは最初の解が得られるまで大体 40 秒くらいかかります。
Prolog も他の色々な言語と同様、無駄と分かっている計算はしないようになっているので、先ほどの magic_square のサブゴールの記述順をちょっと変えるだけで計算時間を短くすることが可能です。
また、コードが異様に長いですが、組み込みのルールを使えばこんなにいろいろ書かずに済みます。
ぜひやってみてください。

まとめ

今回は論理型言語の Prolog についてごく簡単に触れてみました。
Prolog を使うと、問題に対する解の定義を書くだけで、あとはプログラムが解を導き出してくれます。

今回は初歩の初歩ということで取り扱いませんでしたが、Prolog にはリストという可変長のデータを扱う仕組みがあったり、初めから使える組み込みのルールがあったり、強力な言語仕様がたくさんあります。

一風変わった Prolog という言語、一度触れてみてはいかがでしょうか？