|ハイブリッドOS|File System|ARM|Android|Java|制御システム|オープンシステム

 

技術者コラム

 
フォーム
 
第47回目:Prologでさめがめを解く(Part3)
2015-07-26
筆者:村田

こんにちは。

暑いですね〜。都心もとうとう今年初の猛暑日となったそうで。暑さが一層厳しくなりますが皆さんも体に気をつけて夏を過ごしましょう。でもまあ夏ですね。昨日、立川では花火まつりがあり、今日は地元福生でも夏祭りがありました。駅前は神輿や山車などが出ていて賑やかでした。暑くてあまり長居はできませんでしたが、お祭りの雰囲気、お囃子を聞いていると夏だな〜と感じますね。

さて、5月の更新から間が空いてしまいました。久しぶりのPrologです。今回はさめがめのボードをPrologで表現してみます。コマはアルファベット1文字にします。単純な3x3マスのボードは以下のように表せます。

+-+-+-+
|g|b|r|
+-+-+-+
|g|g|r|
+-+-+-+
|r|b|b|
+-+-+-+

r ... red
g ... green
b ... blue

この3x3のさめがめ問題は以下のようにg->b->rの順に消すとクリアできます。

+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+
|g|b|r|    | | |r|    | | | |    | | | |
+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+ 
|g|g|r| -> | |b|r| -> | |r| | -> | | | |
+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+ 
|r|b|b|    |r|b|b|    |r|r| |    | | | |
+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+ 

2次元のマスはリストを使って表現します。上記のボードは以下のように定義できます。

board([[g,b,r],
       [g,g,r],
       [r,b,b]]).

swiplで読み込んでボードを表示させてみます。

$ swipl -f samegame.pl
?- board(B).
B = [[g, b, r], [g, g, r], [r, b, b]].

これは問題をわかりやすく定義するための並び順です。このまま問題を解くことができるかもしれませんが、今回はプログラムで解きやすいように並び順を変換します。さめがめはコマを消すとその上のコマがストンと落ちてきます。このストンという動作は、リストの並び順を工夫すると簡単に実装できます。例題の一番左の列は下からr,g,gです。この並び順でリストにすると[r,g,g]となります。rを削除すれば[g,g]となりコマがストンと落ちた結果と一致します。というわけで、以下の手順でボードを並び替えるのが今回の目標です。

① ボードの行を逆順にします。
[[g, b, r], [g, g, r], [r, b, b]] -> [[r, b, b], [g, g, r], [g, b, r]]

② 各行の1つ目を集めて1行にします。2つ目以降も同様に繰り返します。これは行と列の入れ替えに相当します。
[[r, b, b], [g, g, r], [g, b, r]] -> [[r, g, g], [b, g, b], [b, r, r]]

では並び替える方法を考えていきます。まず①ですが、マニュアルを探すと逆順にする述語reverseがみつかります。使い方を見てみます。

?- reverse([1,2,3], R).
R = [3, 2, 1].

ではボードの行を逆順にします。

?- board(B), reverse(B, Reversed).
B = [[g, b, r], [g, g, r], [r, b, b]],
Reversed = [[r, b, b], [g, g, r], [g, b, r]].

①の結果が得られました。次に②を考えます。なかなか難しいですが色々なやり方があるので面白い題材です。これから紹介する方法以外にも考えてみると面白いでしょう。 まずは各行の先頭を集めて一つにまとめる述語を考えます。BoardをもらってHeadRowを返す述語なので、書き出しは・・・

headline(Board, HeadRow) :-

となります。最初にBoardから先頭行(Row)の先頭(H)をとります。

headline(Board, HeadRow) :-
  [Row|Remain] = Board,
  [H|T] = Row,

次にBoardの残りの部分(Remain)からも同じように先頭を集めるのですが、ここは「繰り返し」ですね。他の言語ならfor文を用いるところですがPrologでは再帰を使います。ゆっくり考えましょう。Boardを[Row|Remain]に分けると以下のようになります。

Board = [[r, b, b], [g, g, r], [g, b, r]],
Row = [r, b, b],
Remain = [[g, g, r], [g, b, r]].

よく見るとRemainは少し小さくなったBoardであることがわかります。BoardもRemainも2次元リストであり、RemainはBoardと同型で、Boardの一部分です。このように同型の部分を見つけることは再帰を思いつく上でポイントになります。RemainはBoardと同型なのでheadlineに渡すことができます。headlineの仕様はBoardの先頭を集めた行を返してくれるのですから、返してくれた値(RemainHeadRow)を組み合わせましょう。

headline(Board, HeadRow) :-
  [Row|Remain] = Board,
  [H|T] = Row,
  headline(Remain, RemainHeadRow),
  HeadRow = [H|RemainHeadRow].

再帰を書くときには停止性に気をつけます。Remainはどんどん小さくなり、最後は空リスト[]になります。その場合はHeadRowも空リストです。このパターンを付け加えます。

headline(Board, HeadRow) :-
  [Row|Remain] = Board,
  [H|T] = Row,
  headline(Remain, RemainHeadRow),
  HeadRow = [H|RemainHeadRow].
headline([], []).

ちょっと試してみます。

?- headline([[1, 2, 3], [a, b, c], [A, B, C]], HeadRow).
HeadRow = [1, a, A].

先頭行を集めることができました。さて、他の行についても同じことをやりたいのですが、どうすれば良いでしょう。これも「繰り返し」ですので再帰を考えます。ただしheadlineはすでに内部に一つの再帰ループを抱えており、ここにさらにもう一つ再帰を書いて2重ループを作るのは大変です。そこでheadlineは1重ループのままにして、先頭行を集めたら、残りの部分をBoardの部分同型として、headlineの第3項(TailBoard)で返すようにします。実装してみましょう。Rowを分割した際の残り(T)とheadlineの残り(RemainTailBoard)を集めてTailBoardを返します。

headline(Board, HeadRow, TailBoard) :-
  [Row|Remain] = Board,
  [H|T] = Row,
  headline(Remain, RemainHeadRow, RemainTailBoard),
  HeadRow = [H|RemainHeadRow],
  TailBoard = [T|RemainTailBoard].
headline([], [], []).

試してみます。

?- headline([[1, 2, 3], [a, b, c], [A, B, C]], HeadRow, TailBoard).
HeadRow = [1, a, A],
TailBoard = [[2, 3], [b, c], [B, C]].

先頭行の残りを返すことができました。なお以下のようにリファクタリングして変数を減らすことができます。

headline([Row|Remain], [H|RemainHeadRow], [T|RemainTailBoard]) :-
  [H|T] = Row,
  headline(Remain, RemainHeadRow, RemainTailBoard).
headline([], [], []).

ではheadlineを繰り返し呼び出して行列をひっくり返す述語(transepose)を考えます。

transpose(Board, Transposed) :-
  headline(Board, HeadRow, TailBoard),    % 行列の1列目を集めた先頭行と残りを得る
  transpose(TailBoard, TailTransposed),   % 残りをひっくり返す
  Transposed = [HeadRow|TailTransposed].  % 先頭行とひっくり返した残りを結合する

なお再帰停止用の節には注意が必要です。TailBoardはどんどん短くなりますが、最後は空リスト[]ではなく、空リストのリスト[[], [], ...]になります。したがって以下のように書くとパターンマッチしません。

transpose([], []).

正しいパターンマッチは以下です。

transepose([[]|_], []).

これもリファクタリングして変数を減らし、以下のように書けます。

transpose(Board, [HeadRow|TailTransposed]) :-
  headline(Board, HeadRow, TailBoard),
  transpose(TailBoard, TailTransposed).
transpose([[]|_], []).

では試してみます。

?- transpose([[1, 2, 3], [a, b, c], [A, B, C]], R).
R = [[1, a, A], [2, b, B], [3, c, C]] ;  <- あれ?バックトラックした・・・
false.

得られた結果(R)は問題ないのですが、バックトラックが動いて別の解を探しに行っているようです。;を入力して次の解を探しても見つからずfalseになっています。今回は説明を端折りますがカット(!)という機能でバックトラックを抑制できます。

transpose(Board, [HeadRow|TailTransposed]) :-
  headline(Board, HeadRow, TailBoard),
  transpose(TailBoard, TailTransposed), !.  %% ここまで来たらバックトラックを抑制(!はカット記号)
transpose([[]|_], []).

これで以下のように一つのみ解を得られます。

?- transpose([[1, 2, 3], [a, b, c], [A, B, C]], R).
R = [[1, a, A], [2, b, B], [3, c, C]].

最後に①と②を組み合わせてボードを並び替える述語を組み立てましょう。

convert_board(Board, Converted) :-
  reverse(Board, Reversed),
  transpose(Reversed, Converted).

試してみます。

?- board(Board), convert_board(Board, Converted).
Board = [[g,b,r],[g,g,r],[r,b,b]],
Converted = [[r,g,g],[b,g,b],[b,r,r]].

今回の目標であるボードの並び替えができました。今回はここまでにします。それと、ようやく、さめがめのコードを書き始めたということで、本ページの下のリンクから今回のソースコードを参照できます。ところで今月のSoftware Design誌に「なぜ関数型プログラミングは難しいのか?」というテーマでLisp/Scala/Haskell/Elixir/Python/Clojureを使った特集が載っています。まだ全部読んでいませんが、個人的にはElixirっていう言語が初めてなので興味深いです。Prologは関数型言語に分類されることは少ないのですが、副作用を抑え、再帰を多用する考え方は関数型と通じるものがあり、このような関数型の特集記事などは参考になる点が多いです。

以上。
 
第46回目:Prologでさめがめを解く(Part2)
2015-05-24
筆者:村田

こんにちは。

前回は某家族のPrologコードを書いてパターンマッチを試しました。次のような「質問」をPrologで実行したのでした。

?- male(X).
X = katsuo.

この時、Prologはmale(X)にマッチする項をコードから探し、male(katsuo).という節を見つけます。そして、変数Xにkatsuoをマッチングすることで節が成り立つことを見つけ出します。とまあ用語はさておき、Prologはmale(X)という「形」にマッチする定義を探してくれるのです。このパターンマッチは「=」(イコール)を使っても行うことができます。

?- X = katsuo.
X = katsuo.

イコールの左辺と右辺の項が同じになるように、変数Xにkatsuoがマッチングされたのです。両辺が同じになるように同一視するということを言い換えて、単一化する、あるいはユニフィケーションと言います。厳密には違うかもしれませんが、パターンマッチの方が分かりやすいので、以降はパターンマッチという用語を基本的に使います。さて、両辺にはアトムだけでなく、構造を持った項でもマッチングすることができます。以下ではcoupleという構造を定義してみました。

?- A = couple(male(masuo), female(sazae)).  %% masuoとsazaeのカップル
A = couple(male(masuo), female(sazae)).

変数Aにcoupleという構造全体をマッチングできました。今度は構造の一部分にマッチさせて、任意の部分項を取り出してみましょう。

?- couple(male(X), female(Y)) = couple(male(masuo), female(sazae)).
X = masuo,
Y = sazae.

変数Xにmasuo、変数Yにsazaeというアトムが割り当てられることで、全ての構造が一致しますね。ところが次の例のように構造が異なっているとパターンマッチに失敗します。(例 femaleとmaleの順番が逆)

?- couple(male(X), female(Y)) = couple(female(fune), male(namihei)).
false.

Prologはイコールの両辺のデータ構造(パターン)が一致するかを判断してくれます。

今度はリストについて見ていきましょう。よく使うデータ構造ですね。Prologのリストは要素を大括弧[]で括って表現します。

?- [1,2,3].
ERROR:

おっとエラーが出ました。PrologのREPLには述語(パターンマッチの質問)を書かなければなりません。「Aは[1,2,3]である」という述語を書いてみましょう。

?- A = [1,2,3].
A = [1,2,3].

Aという変数に[1,2,3]というリスト全体がマッチされました。リストの要素を変数にマッチすることもできます。

?- [A,2,C] = [1,2,3].
A = 1,
C = 3.

リスト構造で非常によく使うマッチング方法として、ヘッド(先頭)とテイル(残り)に分けてマッチさせる方法があります。なおヘッドには変数H、テイルには変数Tという変数名がよく使われます。Head、Tailを使った方が分かりやすいかもしれませんが。

?- [H|T] = [1,2,3,4].
H = 1,
T = [2, 3, 4].

カンマでは無くパイプ(縦棒)で区切ります。パイプの手前の変数にヘッド要素がマッチし、パイプの後ろの変数にテイルリストがマッチします。重要なポイントとして、ヘッドには「要素」、テイルには「リスト」がマッチします。それでは1要素からなるリストを[H|T]パターンで分解するとどうなるでしょうか。

?- [H|T] = [1].
H = 1,
T = [].

Hは先頭要素、Tは空のリストになります。では空のリストは[H|T]パターンで分解できるのでしょうか。

?- [H|T] = [].
false.

少なくとも一つ要素があるリストでなければ[H|T]パターンにはマッチしません。次にいきましょう。パイプの前はカンマ区切りで複数の要素をマッチすることができます。

?- [H1,H2|T] = [1,2,3,4].
H1 = 1,
H2 = 2,
T = [3, 4].

そしてテイル部分もまたリストなので、再帰的に[H|T]パターンをマッチさせることができます。

?- [H1,H2|[H3|T]] = [1,2,3,4,5].
H1 = 1,
H2 = 2,
H3 = 3,
T = [4, 5].

ふう、リストのパターンマッチについてはここまでにして、次に算術計算を試してみましょう。

?- 1 + 2.
ERROR:

先にも試した通り、PrologのREPLには述語を書きます。算術式の場合「1足す2は3ですか?」と聞いてみましょう。

?- 3 = 1 + 2.
false.

おっとまた失敗しました。右辺が1 + 2の「並び」のままで、算術式として評価されていないためです。右辺を算術式として評価するためには「=」の代わりに「is」を使ってパターンマッチします。

?- 3 is 1 + 2.
true.

今度は成功しましたね。ではisの左辺に変数を置いて色々な計算をパターンマッチさせてみましょう。

?- X is 123 + 456.
X = 579.

?- X is (3 - 7) / 2.
X = -2.

?- X is 1.2 * 5.
X = 6.0.

?- X is 5 mod 2.
X = 1.

?- X is 3 ^ 2.
X = 9.

四則演算、剰余、累乗の計算もできました。さて、いくつか道具が揃ってきたので、もう少し複雑なコードに取り組みたいと思います。まずはリスト[1,2,3]の合計値を求めるsumという述語(ルール)を作ってみましょう。なお前回同様ファイルにコードを書いていきます。

sumについて、ぱっと思いつくところではfor文のようなループ処理が必要な感じがします。しかしPrologにはfor文がありません。関数型言語と同じように再帰呼び出しでループさせます。Prologで書く前に関数型言語(Haskell)で考えてみたいと思います。

-- Haskellで書いたsum関数
sum [] = 0              -- ① 
sum (x:xs) = x + sum xs -- ②

空リストなら0(①)、そうでなければ先頭要素を、残りの要素の合計(sum)に加えたもの(②)と定義しています。関数や式は値を返すことができるため、sum xsの戻り値にxを加える、という記述を簡単に書くことができます。Prologの場合は関数ではなく述語で書かなければならず、計算結果を戻り値として返せません。ぐぬぬ。一つ前の述語の「結果」に対して足し算を行ってループしたいのに。さてどうしましょう。ここでもPrologのパターンマッチを使います。まずはHaskellの例の①をPrologで書いてみましょう。

sum([], 0).

Haskellでは戻り値として0を返していましたが、Prologでは「空リストのsumは0である」という節(事実)として定義します。読み込んでテストしてみましょう。まずは事実そっくりそのままでパターンマッチするでしょうか。

?- sum([], 0).
true.

もちろん成功します。次に変数を使って質問してみましょう。

?- sum([], X).
X = 0.

というわけで空リストなら0という結果を得ることができました。関数型言語では結果を戻り値にしていましたが、Prologでは結果(戻り値)も一つの項にするのです。関数では引数と戻り値が明確に区別されます。一方Prologの述語では、引数と戻り値の区別は無く、2つの関係を表すルールとして定義します。ですからこんなことができます。

?- sum(X, 0).
X = []

sumの結果が0になるリストは?という質問をすると、空リストであると答えが返ってきました。それでは次にHaskell例②の再帰部分を書いていきます。Haskellでは引数(x:xs)としてリストを分割していましたが、Prologは[H|T]パターンを使って先頭要素と残りのリストを分割すれば良いでしょう。

sum([H|T],・・・ん?)

えっとどうやって書こう。ひとまず結果を表す項を置いてみましょう。考えやすいので。

sum([H|T], Sum)

次にSumという変数をどうやって導くか(ルール)を書きます。Prologにおいてルールは「頭部 :- 条件1, 条件2・・・」という風に定義します。条件1、条件2・・・が全て成り立てば頭部も成り立つという意味を持ちます。これから条件を書き出してSumを定義するのですが、ここは少し慣れが必要な気がします。まずは答えを見てください。

sum([H|T], Sum) :-
  sum(T, Sum1),
  Sum is H + Sum1.

残りのリスト(T)の合計をSum1にマッチさせ、それに先頭(H)を足せば全体の合計(Sum)になるというわけです。合計の定義の中で合計(sum)を使っています。再帰的な感覚に慣れましょう。前述のHaskellのような「関数」を使った再帰では、戻り値を変数に束縛しないためシンプルに書けましたが、PrologではSumやSum1のように一時的に結果を束縛するための変数が必要になります。少し無理がありますが、Haskellでも戻り値を変数に束縛し、Prologと同じように記述することができます。

sum [] = 0
sum (x:xs) = let sum1 = sum xs in
             let sum' = x + sum1 in
             sum'

こんな感じです。もちろんHaskellでは最初のシンプルな書き方で書くべきでしょう。さて、作成したPrologのsumが正しく動くか確認してみます。

?- sum([1,2,3], X).
X = 6.

OKです。では次の例にいきます。リストの要素を全て2倍するtwiceを作ってみましょう。まずは空リストから考えます。再帰の終了条件になります。

twice([], []).

空リストのtwiceは空リストってわけです。次に[H|T]パターンの場合について考えましょう。

twice([H|T], [H1|T1]) :- ???

まずは頭部から考えます。よく考えれば結果(第2項)がどういう形(パターン)になるか分かるはずです。twiceの結果である第2項はリストになるはずです。そして先頭要素も残りの要素も、2倍した結果は第1項の[H|T]とは違うはずです。というわけで???の条件部分を考えなくても、twiceの結果は[H1|T1]と書けることが分かります。twiceの具体的な「手続き」を考える前に、結果を「宣言」してから考えるのです。ふむ。

では???の条件部はどう書きましょう。H1とT1それぞれが「何か」を考えていけば良いです。まず、結果の先頭要素(H1)は元の先頭要素(H)を2倍したものです。

twice([H|T], [H1|T1]) :-
  H1 is H * 2,
 ???

次に結果の残り要素(T1)ですが、これは元の残り要素(T)をtwiceしたものです。ここで再帰を使うということが頭に浮かんでくるかどうかは慣れの問題だと思います。(私も得意ではない)

twice([H|T], [H1|T1]) :-
  H1 is H * 2,
 twice(T, T1).

これで定義できました。先頭要素を2倍したもの(H1)と、残りの要素をtwiceしたもの(T1)を合わせると全体を2倍したことになります。これもHaskellの定義と比較してみましょう。

twice [] = []
twice (x:xs) = x * 2 : twice xs

やはり、Haskellの定義ではH1やT1のような一時結果変数が無い分スッキリしていますね。

さてさて、もう一つだけ練習してみましょう。次の例には算術計算はありません。2つのリストを結合して1つのリストを得るappendという述語を定義します。まずは空リストとリストをappendした場合です。具体例を挙げると、[]と[1,2,3]を結合したら[1,2,3]となります。そのまま書いてみます。

append([], L, L).

次は[H|T]パターンを考えます。具体例を挙げると[1,2,3]と[4,5]を結合したら[1,2,3,4,5]となります。今回もtwiceの例と同じように、まずは頭部から考えてみます。

append([H|T], L, [H|L1]) :- ???

後でも説明しますが第2項(L)は分解マッチしてもしなくても良いです。では結果(第3項)を見て下さい。先頭は第1項の先頭(H)と同じです。残り部分は第1項のTとも第2項のLとも異なるはずです。したがってL1と置きます。さあL1をどうやって定義すれば良いか分かりますか? 再帰に慣れているとすぐに分かります。appendの定義の中でappendを使います。

append([H|T], L, [H|L1]) :-
  append(T, L, L1).

そうです、TとLをappendした結果がL1です。手続き的な思考では、リストのメンバを一つずつ移動させる方法(How)をイメージしますが、宣言的な思考では、それが何(What)であるかを考えようとします。まずは結果(第3項)が何であるべきかを考え、次にL1はどうやって定義できるかを考えました。ちなみに第2項を分解した場合の定義ですが、

append([H|T], [H1|T1], [H|L1) :-
  append(T, [H1|T1], L1).

となり、[H1|T1]部分は分解する必要が無いことがわかります。しつこいようですが、これもHaskellの定義と比較してみます。

append [] ys = ys
append (x:xs) ys = x : append xs ys

やはりL1という一時結果変数が無い分スッキリしています。先程からHaskellの方がスッキリ書ける!と、これではまるでPrologの述語における結果項が邪魔者みたいに思われるかもしれません。しかし、sumの例でも少し触れましたが、Prologのように結果を項として置くことで面白いことができます。その前にまずは作成したappendをテストしてみましょう。

?- append([1,2,3], [4,5], X).
X = [1, 2, 3, 4, 5].

ちゃんとリストを結合してくれました。それでは今度は結果項にリストを与え、逆に元のリストを求めてみましょう。

?- append([1,2,3], X, [1,2,3,4,5]).
X = [4, 5].

ふふん。さらに第1項、第2項とも変数にしてみましょう。

?- append(X, Y, [1,2,3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
...

ふふふん。このようにXとYの組み合わせパターンをバックトラックで求めることができます。appendはリストをくっつけるだけではなく、リストを分割することもできるのです。これは引数と戻り値が区別される「関数」ではできません (もちろんリスト分割の関数を別に定義すれば良いのですが)。Prologの「述語」では、各項の関係を定義し、パターンマッチとバックトラックで様々な答えを求めることができます。この仕組みはとても面白いですね。

ふう。今回はここまでにします。途中で少し触れましたが、宣言的プログラミングには慣れが必要です。手続きを見せない分スッキリ書かかれていることが多いのですが、特にユニフィケーションやバックトラックが効果的に使われているコード例を見ると、どうしてこれが動くのか?とクラクラします:-P それにしても今のところタイトルに偽りあり、さめがめ要素0ですね。次回は話を進められたらと思います。

以上。
 
第45回目:Prologでさめがめを解く(Part1)
2015-04-26
筆者:村田

こんにちは。

前回プチコン3号で「さめがめ」というゲームを作ったのですが、今度はさめがめを解くプログラムを書いてみたいと思います。ここで言う「解く」とは、さめがめの盤面の全てのコマを消すことを指します。さめがめの盤面から最高得点を得られる消し方を探すプログラムではありませんが、まあとにかく全部消せたらOKです。

使用するプログラミング言語はPrologです。PrologはC言語と同世代で1970年代初頭に開発されました。しかし、PrologはC言語とは大分雰囲気が異なるプログラミング言語です。CやBASICのように手続きを書き並べる言語ではなく、またHaskellのように関数を組み合わせる言語でもありません。Prologは論理型プログラミング言語と呼ばれていますが、一体どんな言語なんでしょうか。というわけで、これからしばらくPrologにチャレンジしたいと思います。今では雑誌や新刊で取り上げられることも少ない言語で、私もWebの情報を頼りに学習中です。一緒に雰囲気だけでも味わってもらえたらと思います。

さて、何はともあれまずは処理系をインストールしましょう。GNU PrologやSWI-Prologが有名な処理系です。今回はSWI-Prologを使いたいと思います。公式サイトから簡単にインストールできます。GUIインタフェースもありますが、ターミナルの方が使いやすいので私はコマンドラインから使っています。実際に試される方は好みに応じてどちらでも良いでしょう。起動コマンドはswiplです。

$ swipl
Welcome to SWI-Prolog ...

?- 

?-がプロンプトです。この後に入力できます。まずはHello worldをやってみます。

?- write('Hello World!').
Hello World!
true.

シングルクォートは文字列ではなくアトムというものを表します。writeは画面に文字を表示する「述語」です。writeの引数にアトムを渡して呼び出しています。呼び出しの最後にはピリオドが必要です。述語とアトムについては後でも出てきますのでさらりと次にいきます。今度は簡単な算術演算を試してみましょう。

?- 1 + 2.
ERROR: ・・・

上記のような書き方はエラーです。以下のように足し算を表す組込述語を使って演算結果を取得します。

?- plus(1, 2, X).
X = 3.

Xのように大文字から始まるシンボルは変数を表します。ふむ〜、足し算からして何だか他の言語と違う様相ですね。というところでいったん区切ります。そもそもPrologは記号処理に向いた言語であって、数値演算や副作用(画面出力)を主目的にした言語ではないのです。というわけで、ハローワールドや算術演算はちょっとだけ難しいのです。

それでは、SWI-Prologを終了するためにhaltという述語を呼び出しましょう。引数は不要です。

?- halt.

さてさて、Prologの入門では定番の「とある家族の例」でPrologを触っていきましょう。これからはコードはファイルに保存し、SWI-Prologからロードして呼び出すことにします。SWI-PrologのREPL上でコードを定義することもできるのですが、素直にファイルに保存する方法が良いでしょう。拡張子はplを使っています。(Perlスクリプトと間違えそうですが・・・)

$ emacs seafamily.pl

% 某有名一家の定義
female(sazae).
female(wakame).
male(katsuo).

コードを書く前にまずはコメントの書き方を覚えちゃいましょう。%記号を書くと行末までがコメントとなります。またはC言語スタイルの/* ~ */を使って複数行のコメントを書くこともできます。

上記では3つの「節」というものを定義しています。節はピリオドで終了します。この例は単純そのものですが、Prologのプログラムは「節」の集まりから成っているのです。そして上記はfemaleという「関係」とmaleという「関係」を定義しています。sazaeやwakameは「対象」と言います。female関係には2つの節がありますね。一方male関係は1つの節からできています。そしてfemale関係は、"sazaeは女性である"と"wakameは女性である"という「事実」を定義しています。male関係も"katsuoは男性である"という事実を定義しています。節・関係・対象・事実とちょっと慣れない用語が出てきますが、まあそんなものかって感じでいいと思います。用語はさておき書き方は難しくありませんね。事実の例をいくつか書いて練習してみましょう。

fruit(apple).        % りんごはフルーツである
drink('Meat Sauce'). % ミートソースは飲み物である 

事実を書くときの注意として、対象にはアトム(または数値)を書かなければなりません。アトムは英小文字から始めます。ただし上記の'Meat Sauce'の例のようにシングルクォートで囲んだ場合は、英大文字から始めたり、空白文字を含めることができます。アトムは他の言語での定数やSymbolのようなものです。

それではseafamily.plをSWI-Prologでロードしてみましょう。コマンドラインオプション(-f)でファイル名を渡すことができます。

$ swipl -f seafamily.pl
% seafamily.pl compiled 0.00 sec, ・・・

?-

ほ〜読み込み時にコンパイルしているようですね。構文・意味解析し、何らかの内部構造を作り上げているのでしょう--; (テキトーな理解ですね・・・)プログラムにおかしなところがあればコンパイル時にエラーが出ます。なおREPLからロードすることもできます。

?- [seafamily].
% seafamily compiled 0.00 sec, ・・・
true.

大カッコの中に拡張子を除くファイル名を書いて末尾にピリオドを書きます。さて、プログラムをロードするとPrologに対して簡単な「質問」を行うことができます。「?-」プロンプトは?記号が表すように質問を受け付けるプロンプトです。では質問してみましょう。

?- female(sazae).
true.

上記のようにsazaeさんは女性です(か?)との質問に対し、Prologはtrueと答えてくれました。

?- female(katsuo).
false.

katsuoくんは女性です(か?)に対してはfalseですね。では、masuoさんは男性ですか?

?- male(masuo).
false.

seafamily.plに"masuoさんは男性である"という事実は書かれていないのでfalseが返ってきました。このように「?-」プロンプトの後に質問を書くことでPrologと対話し、プログラムを実行することができます。まだ単純な質問しか試していませんが、今度は変数を導入してもう少し複雑な質問をしてみましょう。

?- male(X).
X = katsuo.

アトムは小文字からでしたが、変数はXのように大文字アルファベットから始めます。単純な例ではXのような一文字変数を使っても良いですが、複雑になってきたらNameとかAddressのように意味の取りやすい変数名を使った方が良いでしょう。今度はfemale関係についての質問をしてみます。

?- female(Y).
Y = sazae □

Prologはsazaeという答えを返したあと、次の答えを出すべきかユーザーの入力を待っています。セミコロンを入力してみましょう。

?- female(Y).
Y = sazae ;
Y = wakeme.

wakameという答えを返し、female関係の対象を全て答えたので終了しています。もし続きの答えが不要ならばセミコロンではなくピリオドを入力することもできます。このように変数を使うとtrue/falseを答えるのではなく、変数部分に一致する対象を探し出して答えてくれます。この変数と対象を一致させることを「ユニフィケーション」と言います。また先ほどのfemale関係の質問で見たように、Prologは複数ある答えを順番に教えてくれました。このように複数の答えを自動的に探し出してくれる機構を「(自動)バックトラック」と言います。ユニフィケーションとバックトラックはPrologプログラミングの特徴的な機能であり中心機能です。ユニフィケーションは他の(主に関数型)言語でのパターンマッチと言われる機能と似ていますね。これらはPrologプログラミングで何度も使いますので是非覚えておきましょう。

さて今度はseafamily.plに2つの対象(項)を持つ事実を4つ追加してみます。

parent(masuo, tarao).
parent(sazae, tarao).
parent(namihei, sazae).
parent(fune, sazae).

お分かりの通り某家族の親子関係をいくつか表しています。第一項が親、第二項が子ですね。それではPrologに読み込ませて質問してみましょう。

?- [seafamily].
true.

?- parent(masuo, tarao).
true.

?- parent(fune, sazae).
true.

ふむ。問題ないようです。では変数を使ってsazaeの子供が誰なのか聞いてみましょう。

?- parent(sazae, X).
X = tarao.

OK、taraoくん。今度は逆に子を指定して親が誰なのか聞いてみましょう。

?- parent(X, tarao).
X = masuo ;
X = sazae.

parent関係を定義するだけで、両方向、つまり子だけでなく親も簡単に推論してくれます。ふむ、Prologのユニフィケーションは柔軟ですね。では、さらに親子いっぺんに聞いてみましょうか。

?- parent(X, Y).
X = masuo,
Y = tarao ; ・・・①
X = sazae,
Y = tarao ; ・・・② 
X = namihei,
Y = sazae ; ・・・③
X = fune,
Y = sazae.  ・・・④

①〜④の4つの答えをバックトラックして探し出してくれました。まるでデータベースに対するクエリのようです。次は複数の質問を組み合わせて大きな質問を作ってみましょう。

?- parent(namihei, sazae), parent(sazae, tarao).
true.

複数の質問をカンマでつなげています。「かつ(and/連言)」の意味で使うことができます。namiheiはsazaeの親で、かつsazaeはtaraoの親ですか?という質問ですのでtrueが返ってきました。もちろん複数の質問をする際にも変数を使うことができます。次の質問で試してみましょう。namiheiの子供であり、かつtaraoの親でもある人は誰ですか?

?- parent(namihei, X), parent(X, tarao).
X = sazae.

OK。sazaeさんですね。この例のポイントは、namiheiの子供という条件を満たす人と、taraoの親という条件を満たす人が同一人物であることを表すため、Xという同じ変数にユニフィケーションさせている点です。たった4つの事実から成るparent定義ですがもう少し遊べますよ。今度はtaraoの祖父母を探してみましょう。どう書けば良いか分かりますか?

?- parent(X, Y), parent(Y, tarao).
X = namihei,
Y = sazae ; ・・・①
X = fune,
Y = sazae.  ・・・②

バックトラックして2つの答えを返してくれました。Yはtaraoの親を表した一時的な変数として使用しています。Xが求めたい祖父母を表していますので、Xの結果に着目すると、taraoの祖父母はnamihei及びfuneであることが導けていますね。祖父母を求める上記の質問は有意義ですが、記述量が多くて毎回入力したくありません。そこで質問の組み合わせに対して新しい名前を与え、さらにファイルに追加していつでも呼び出せるようにしましょう。

$ emacs seafamily.pl

% 祖父母の関係
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

「:-」の左側を「頭部」と言い、右側を「条件部」と言います。まあ呼び方はさておき意味を追いかけましょう。grandparentという新しい「関係」を定義しています。Xが祖父母、Yが孫という関係は、間の親にZという変数を使うと、Xの子供がZで、そのZの子供がYであると定義できます。それではPrologにロードしてテストしてみましょう。

?- grandparent(X, tarao).
X = namihei ;
X = fune.

OK。taraoの祖父母はnamiheiとfuneです。

?- grandparent(namihei, X).
X = tarao.

OKOK。namiheiの孫はtaraoです。最後にいっぺんに問い合わせてみましょう。

?- grandparent(X, Y).
X = namihei,
Y = tarao ; ・・・①
X = fune,
Y = tarao.  ・・・②

祖父母と孫の関係にあるのはnamiheiとtarao、及びfuneとtaraoであることがバックトラックで求められました。

このようにparentのような基本的な「事実」を組み合わせて新しい「関係(ルールとも言います)」を定義していくことで、複雑なプログラムを作っていきます。他の言語では関数やクラスを定義してプログラムを作っていくわけですが、Prologの場合は事実と関係(ルール)を定義してプログラムを作っていくのですね。

今回はここまでにしたいと思います。Prologのサンプルコードを一つ書いただけですね・・・次回はリスト構造ともう一度算術式に触れたいと思います。さめがめソルバーを書き始めるのはもう少し先になりそうです。長くなる場合は途中で違うテーマを挟んだりするかもしれませんが、気楽に宜しくお付き合い下さい。
 
 
第44回目:プチコン3号(BASIC)でさめがめ(Part3)
2015-03-29
筆者:村田

こんにちは。

桜の季節ですね。東京の満開予想は3/30だそうで、4/6頃までが見頃のようです。弊社のある立川近辺でしたらやはり昭和記念公園が有名ですね。広い敷地でたくさんの桜を見ることができます。とっても綺麗です。私は花見のアルバイトで売り子、資材搬出入をした思い出があったりします:-) 花見会場となるような大規模な桜も良いですが、身近な桜も良いです。週末に通う地元の図書館の桜はいよいよという感じでした。(参考画像1) ここの桜は本数が少ないですが、枝振りも良く、図書館の屋根に冠る様はとても綺麗で、図書館の落ち着いた雰囲気に合うところがお気に入りです。今週は通勤電車の車窓から見える桜にも注目すべく、いつもはスマホ、読書に当ててしまう時間ですが顔を上げて見ようかな^^

さて、今回はさめがめのスコアを計算して画面に表示するところから始めます。PRINTコマンドを使って画面に文字列を表示します。

PRINT "HELLO WORLD"

変数や式の結果も表示できるのでデバッグにも使えます。

A=10
PRINT A '「10」と表示
B=20
PRINT A+B '「30」と表示

セミコロンを挟むと複数の変数や文字列をくっつけて表示することができます。

X=5
Y=10
PRINT "X=";X;" Y=";Y;" X+Y="X+Y '「X=5 Y=10 X+Y=15」と表示

LOCATEコマンドを使って文字表示位置を指定することができます。"LOCATE X座標,Y座標,Z座標"と指定します。Z座標は液晶面を0として手前がマイナス、奥がプラスの値となります。実際に3DSの3D表示を有効にするとマイナスZ座標で浮き上がって見え、プラスZ座標で奥に引っ込んだように見えます。

LOCATE 10,15,-100
PRINT "POIPOI"

では位置決めと画面表示を関数にまとめて使いやすくしておきましょう。

' スイヘイ チュウオウニ モジ ヒョウジ
DEF PRI A,Y
 LOCATE 25-LEN(A)/2,Y,-100
 PRINT A
END

引数Aに表示したい文字列を渡し、引数Yに表示したい上下位置を渡します。文字列の長さから、水平中央に表示させるためのX座標位置を計算しています。では次はスコア計算です。まずはグローバル変数SCOREを用意しておきます。

SCORE=0

前回、隣接した同種のコマを削除するNDEL関数を作成しました。NDELの戻り値は削除できたコマ数ですので、ここからスコアを計算します。さめがめの一般的なスコア計算かどうかわかりませんが、今回は以下の算出式を使います。

スコア=(削除したコマ数−2)の2乗

削除したコマ数が3個以上なら有効得点になります。そして一度にたくさん削除する方が高得点となります。それでは上記算出式をプログラムに書きましょう。

C=NDEL(CX,CY,PMAP[CX,CY]) 'リンセツ コマ サクジョ
C=C-2
SCORE=SCORE+C*C

それでは先ほど作った文字表示関数PRTを使って画面にスコアを表示してみましょう。

'スコア ヒョウジ
PRT "スコア "+STR$(SCORE),3

STR$関数は数字を文字に変換する関数です。BASICの型には数値型と文字型があり、異なる型を+で足す(連結)することはできませんので型変換が必要です。

上記のスコア計算は変数Cが2以上(2の場合は得点0)ならうまくいきますが、1以下の場合は正しくありません。そもそもコマを消すことができるのは、1個以上の隣接コマがある場合であり、一人ぼっちのコマは削除できないのです。そこで、現在カーソルが指しているコマに、少なくとも1個以上の隣接コマがあるかチェックしてみましょう。

'サクジョ デキルカ?
DEF CANDEL(X,Y)
 P=PMAP[X,Y]
 IF P==0 THEN RETURN 0
 IF X>0      && P==PMAP[X-1,Y] THEN RETURN 1
 IF X<XMAX-1 && P==PMAP[X+1,Y] THEN RETURN 1
 IF Y>0      && P==PMAP[X,Y-1] THEN RETURN 1
 IF Y<YMAX-1 && P==PMAP[X,Y+1] THEN RETURN 1
 RETURN 0 'リンセツスル コマ ガ ナイ
END
  
このCANDEL関数でチェックしてからNDEL関数を呼ぶようにします。

IF CANDEL(CX,CY)==1 THEN 'サクジョ デキル?
 C=NDEL(CX,CY,PMAP[CX,CY]) 'リンセツ コマ サクジョ
 C=C-1 '3コ イジョウ ケセレバ トクテン
 SCORE=SCORE+C*C 'スコアUP
 ・・・
ENDIF

これでコマの消し方と得点の関係は以下のようになります。

コマ1個:消せない
コマ2個:消せる(0点)
コマ3個:消せる(1点)
コマ4個:消せる(4点)
コマ5個:消せる(9点)
・・・

もう少しで完成です。ゲームオーバー/ゲームクリア処理を書きましょう。画面上のコマを全て消せたらゲームクリアとなります。クリア時には1000点のスコアボーナスをあげましょう。逆に画面上に一つ以上コマが残っているにも関わらず、どれも同種の隣接コマが無くて消せない状態になったらゲームオーバーとなります。ゲームクリアかどうかは、ボード左下にコマがあるかどうかで簡単に判断できます。コマを削除すると左下に向かって隙間が詰められるからですね。

'ゲームクリア?
DEF GCLEAR()
 IF PMAP[0,YMAX-1]==0 THEN RETURN 1
 RETURN 0
END

ゲームオーバーかどうかはボード左下から順番にコマを走査し、削除可能なコマが一つでも残っているかを調べて判断します。

'ゲームオーバー?
DEF GOVER()
 FOR X=0 TO XMAX-1
  FOR Y=YMAX-1 TO 0 STEP-1
   IF PMAP[X,Y]==0 THEN BREAK 'ツギノ レツ ヲ シラベル
   IF CANDEL(X,Y)==1 THEN RETURN 0 'マダ サクジョ デキル
  NEXT
 NEXT
 RETURN 1 'サクジョ デキル コマガ ナイ'
END

今回作った、スコア表示、ゲームクリア判定、ゲームオーバー判定はゲームループ内で毎回呼び出す必要はありません。これらはコマが削除され、スコアやゲーム状態が変わった時にのみ呼び出せば良いです。そこで@JUDGEサブプロシージャとしてまとめておいて、コマが削除できた時にまとめて呼び出せるようにしましょう。

'ゲーム ノ ケイゾク ハンテイ
@JUDGE
'ゲームクリア ナラバ ボーナス
IF GCLEAR()==1 THEN SCORE=SCORE+1000

'スコア ヒョウジ
PRT "スコア "+STR$(SCORE),3

'ゲームクリア?
IF GCLEAR()==1 THEN
 PRT "C L E A R",12
 BEEP 72 'オメデトー ノ コエ
 GOTO @PROGEND
ENDIF

'ゲームオーバー?
IF GOVER()==1 THEN
 PRT "GAME OVER",12
 BEEP 73 'バイバーイ ノ コエ
 GOTO @PROGEND
ENDIF
RETURN

これで完成です。ゲーム終了後のリトライなど、もう少しだけ処理を追加した全コードについては、本コラム一番下のリンク(GitHub)を参照してください。それではせっかく作ったので遊んでみます。(参考画像2) なかなかクリアまではできませんでした。さめがめ攻略法をネットで検索しようかな・・・まあ作る方が楽しいのですけどね。えっと、もう一つ機能紹介を。プチコン3号では作成したプログラムを公式サーバーにアップロードし、審査後に公開キーを発行してもらうことができます。他のユーザーは公開キーを使ってプログラムをダウンロードすることができます。公開キーの発行手順は簡単です。

・プチコン3号のトップメニューから「作品公開とダウンロード」を選択
・「アップロード(送信)」を選択
・アップロードしたいプログラムを選択 => アップロード実行
・「二次利用可能な作品を他の人に公開」を選択
・先ほどアップロードしたプログラムが見えるので選択(*) => 公開申請を実行
・しばらく待つと(*)のプログラム名の横に公開キーが表示される

ちなみに今回作成したさめがめの公開キーは 4ENX3VHV です。興味のある方はダウンロードしてみて下さい:-) 改造ネタとしては、削除して垂直方向を詰めた後(VPACK)、上から新たなコマを降らせても面白そうですね。その場合は全部消すことがゲーム目的では無く、如何に大量消しを維持するかで得点が変わるシステムとかどうでしょう:-)

[おわりに]
プチコン3号のBASICプログラミングはいかかでしたか?クラスやラムダのようなプログラミング言語機能はありませんが、むしろ設計にあまり悩まずゴリゴリ書いていけるスタイルが楽しいです。そして狭い画面やペンタッチのキーボード操作は一見プログラミングに不向きな環境に思えますが、ヘルプ、入力補完、検索、ボタン割り当てなどに工夫があり、意外と気にならないのです。ネットで検索すると「こんなこともできるのか」と驚くようなプログラムがあり、それらをダウンロードして改造してみるのも楽しそうです。昨今、プログラミングを義務教育に〜なんて話題もあり、ビジュアルプログラミングや子供向けプログラミングワークショップなどのニュースを見ることも多いです。教育向けプログラミング言語BASICであるプチコン3号は、最初の敷居は低くて入りやすく、それでいてしっかりアルゴリズムを書けて深い理解が得られる、とてもいいツールだと思いました。3DSをお持ちの方、お試しあれ。

以上。
 
参考画像1〜2
2015-03-29
 

連載記事のソースコード

連載記事のソースコード
 
・Haskellで問題を解く(Part1〜Part4) ソースコード
・Clojureで8クイーン問題にチャレンジ(Part1〜Part5) ソースコード
・OCamlでへびゲームを作る(Part1〜Part5) ソースコード
・Swiftでオセロを作る(Part1〜Part5) ソースコード
・Processingでシューティング(Part1〜Part4) ソースコード 
Haskellでテトリス(Part1〜Part9) ソースコード
・プチコン3号(BASIC)でさめがめ(Part1〜Part3) ソースコード
・Prologでさめがめを解く(Part1〜Part6) ソースコード