第47回目:Prologでさめがめを解く(Part3)2015-07-26筆者:村田こんにちは。都心もとうとう今年初の猛暑日となったそうで。暑さが一層厳しくなりますが皆さんも体に気をつけて夏を過ごしましょう。昨日、立川では花火まつりがあり、今日は地元福生でも夏祭りがありました。駅前は神輿や山車などが出ていて賑やかでした。暑くてあまり長居はできませんでしたが、お祭りの雰囲気、お囃子を聞いていると夏だな〜と感じますね。5月の更新から間が空いてしまいました。久しぶりのPrologです。今回はさめがめのボードをPrologで表現してみます。コマはアルファベット1文字にします。単純な3x3マスのボードは以下のように表せます。blueこの3x3のさめがめ問題は以下のようにg->b->rの順に消すとクリアできます。+-+-+-+2次元のマスはリストを使って表現します。上記のボードは以下のように定義できます。board([[g,b,r],[g,g,r],[r,b,b]]).swiplで読み込んでボードを表示させてみます。b]].これは問題をわかりやすく定義するための並び順です。このまま問題を解くことができるかもしれませんが、今回はプログラムで解きやすいように並び順を変換します。さめがめはコマを消すとその上のコマがストンと落ちてきます。このストンという動作は、リストの並び順を工夫すると簡単に実装できます。例題の一番左の列は下からr,g,gです。この並び順でリストにすると[r,g,g]となります。rを削除すれば[g,g]となりコマがストンと落ちた結果と一致します。いうわけで、以下の手順でボードを並び替えるのが今回の目標です。ボードの行を逆順にします。各行の1つ目を集めて1行にします。2つ目以降も同様に繰り返します。これは行と列の入れ替えに相当します。r]]では並び替える方法を考えていきます。1ですが、マニュアルを探すと逆順にする述語reverseがみつかります。1].ではボードの行を逆順にします。r]].1の結果が得られました。難しいですが色々なやり方があるので面白い題材です。これから紹介する方法以外にも考えてみると面白いでしょう。各行の先頭を集めて一つにまとめる述語を考えます。最初にBoardから先頭行(Row)の先頭(H)をとります。Row,次にBoardの残りの部分(Remain)からも同じように先頭を集めるのですが、ここは「繰り返し」ですね。他の言語ならfor文を用いるところですがPrologでは再帰を使います。Boardを[Row|Remain]に分けると以下のようになります。r]].よく見るとRemainは少し小さくなったBoardであることがわかります。BoardもRemainも2次元リストであり、RemainはBoardと同型で、Boardの一部分です。このように同型の部分を見つけることは再帰を思いつく上でポイントになります。RemainはBoardと同型なのでheadlineに渡すことができます。headlineの仕様はBoardの先頭を集めた行を返してくれるのですから、返してくれた値(RemainHeadRow)を組み合わせましょう。[H|RemainHeadRow].再帰を書くときには停止性に気をつけます。Remainはどんどん小さくなり、最後は空リスト[]になります。その場合はHeadRowも空リストです。このパターンを付け加えます。[]).ちょっと試してみます。A].先頭行を集めることができました。他の行についても同じことをやりたいのですが、どうすれば良いでしょう。これも「繰り返し」ですので再帰を考えます。headlineはすでに内部に一つの再帰ループを抱えており、ここにさらにもう一つ再帰を書いて2重ループを作るのは大変です。そこでheadlineは1重ループのままにして、先頭行を集めたら、残りの部分をBoardの部分同型として、headlineの第3項(TailBoard)で返すようにします。Rowを分割した際の残り(T)とheadlineの残り(RemainTailBoard)を集めてTailBoardを返します。[]).試してみます。C]].先頭行の残りを返すことができました。以下のようにリファクタリングして変数を減らすことができます。[]).ではheadlineを繰り返し呼び出して行列をひっくり返す述語(transepose)を考えます。先頭行とひっくり返した残りを結合するなお再帰停止用の節には注意が必要です。したがって以下のように書くとパターンマッチしません。[]).正しいパターンマッチは以下です。[]).これもリファクタリングして変数を減らし、以下のように書けます。[]).では試してみます。あれ?バックトラックした・・・false.得られた結果(R)は問題ないのですが、バックトラックが動いて別の解を探しに行っているようです。;を入力して次の解を探しても見つからずfalseになっています。今回は説明を端折りますがカット(!)という機能でバックトラックを抑制できます。[]).これで以下のように一つのみ解を得られます。C]].最後に1と2を組み合わせてボードを並び替える述語を組み立てましょう。Converted).試してみます。[[r,g,g],[b,g,b],[b,r,r]].今回の目標であるボードの並び替えができました。今回はここまでにします。それと、ようやく、さめがめのコードを書き始めたということで、本ページの下のリンクから今回のソースコードを参照できます。Design誌に「なぜ関数型プログラミングは難しいのか?」というテーマでLisp/Scala/Haskell/Elixir/Python/Clojureを使った特集が載っています。全部読んでいませんが、個人的にはElixirっていう言語が初めてなので興味深いです。Prologは関数型言語に分類されることは少ないのですが、副作用を抑え、再帰を多用する考え方は関数型と通じるものがあり、このような関数型の特集記事などは参考になる点が多いです。第46回目:Prologでさめがめを解く(Part2)2015-05-24筆者:村田こんにちは。前回は某家族のPrologコードを書いてパターンマッチを試しました。次のような「質問」をPrologで実行したのでした。katsuo.この時、Prologはmale(X)にマッチする項をコードから探し、male(katsuo).という節を見つけます。変数Xにkatsuoをマッチングすることで節が成り立つことを見つけ出します。とまあ用語はさておき、Prologはmale(X)という「形」にマッチする定義を探してくれるのです。このパターンマッチは「=」(イコール)を使っても行うことができます。katsuo.イコールの左辺と右辺の項が同じになるように、変数Xにkatsuoがマッチングされたのです。両辺が同じになるように同一視するということを言い換えて、単一化する、あるいはユニフィケーションと言います。厳密には違うかもしれませんが、パターンマッチの方が分かりやすいので、以降はパターンマッチという用語を基本的に使います。両辺にはアトムだけでなく、構造を持った項でもマッチングすることができます。以下ではcoupleという構造を定義してみました。female(sazae)).変数Aにcoupleという構造全体をマッチングできました。今度は構造の一部分にマッチさせて、任意の部分項を取り出してみましょう。sazae.変数Xにmasuo、変数Yにsazaeというアトムが割り当てられることで、全ての構造が一致しますね。ところが次の例のように構造が異なっているとパターンマッチに失敗します。male(namihei)).false.Prologはイコールの両辺のデータ構造(パターン)が一致するかを判断してくれます。今度はリストについて見ていきましょう。使うデータ構造ですね。Prologのリストは要素を大括弧[]で括って表現します。[1,2,3].ERROR:おっとエラーが出ました。PrologのREPLには述語(パターンマッチの質問)を書かなければなりません。「Aは[1,2,3]である」という述語を書いてみましょう。[1,2,3].Aという変数に[1,2,3]というリスト全体がマッチされました。リストの要素を変数にマッチすることもできます。3.リスト構造で非常によく使うマッチング方法として、ヘッド(先頭)とテイル(残り)に分けてマッチさせる方法があります。ヘッドには変数H、テイルには変数Tという変数名がよく使われます。Head、Tailを使った方が分かりやすいかもしれませんが。4].カンマでは無くパイプ(縦棒)で区切ります。パイプの手前の変数にヘッド要素がマッチし、パイプの後ろの変数にテイルリストがマッチします。重要なポイントとして、ヘッドには「要素」、テイルには「リスト」がマッチします。それでは1要素からなるリストを[H|T]パターンで分解するとどうなるでしょうか。[].Hは先頭要素、Tは空のリストになります。空のリストは[H|T]パターンで分解できるのでしょうか。[].false.少なくとも一つ要素があるリストでなければ[H|T]パターンにはマッチしません。パイプの前はカンマ区切りで複数の要素をマッチすることができます。4].そしてテイル部分もまたリストなので、再帰的に[H|T]パターンをマッチさせることができます。5].ふう、リストのパターンマッチについてはここまでにして、次に算術計算を試してみましょう。2.ERROR:先にも試した通り、PrologのREPLには述語を書きます。算術式の場合「1足す2は3ですか?」と聞いてみましょう。2.false.おっとまた失敗しました。2の「並び」のままで、算術式として評価されていないためです。右辺を算術式として評価するためには「=」の代わりに「is」を使ってパターンマッチします。2.true.今度は成功しましたね。isの左辺に変数を置いて色々な計算をパターンマッチさせてみましょう。いくつか道具が揃ってきたので、もう少し複雑なコードに取り組みたいと思います。リスト[1,2,3]の合計値を求めるsumという述語(ルール)を作ってみましょう。前回同様ファイルにコードを書いていきます。sumについて、ぱっと思いつくところではfor文のようなループ処理が必要な感じがします。Prologにはfor文がありません。関数型言語と同じように再帰呼び出しでループさせます。Prologで書く前に関数型言語(Haskell)で考えてみたいと思います。2空リストなら0(1)、そうでなければ先頭要素を、残りの要素の合計(sum)に加えたもの(2)と定義しています。xsの戻り値にxを加える、という記述を簡単に書くことができます。Prologの場合は関数ではなく述語で書かなければならず、計算結果を戻り値として返せません。一つ前の述語の「結果」に対して足し算を行ってループしたいのに。ここでもPrologのパターンマッチを使います。Haskellの例の1をPrologで書いてみましょう。0).Haskellでは戻り値として0を返していましたが、Prologでは「空リストのsumは0である」という節(事実)として定義します。読み込んでテストしてみましょう。事実そっくりそのままでパターンマッチするでしょうか。0).true.もちろん成功します。次に変数を使って質問してみましょう。0.というわけで空リストなら0という結果を得ることができました。関数型言語では結果を戻り値にしていましたが、Prologでは結果(戻り値)も一つの項にするのです。関数では引数と戻り値が明確に区別されます。Prologの述語では、引数と戻り値の区別は無く、2つの関係を表すルールとして定義します。こんなことができます。[]sumの結果が0になるリストは?という質問をすると、空リストであると答えが返ってきました。それでは次にHaskell例2の再帰部分を書いていきます。Haskellでは引数(x:xs)としてリストを分割していましたが、Prologは[H|T]パターンを使って先頭要素と残りのリストを分割すれば良いでしょう。sum([H|T],・・・ん?)えっとどうやって書こう。結果を表す項を置いてみましょう。Sum)次にSumという変数をどうやって導くか(ルール)を書きます。条件2・・・」という風に定義します。条件1、条件2・・・が全て成り立てば頭部も成り立つという意味を持ちます。これから条件を書き出してSumを定義するのですが、ここは少し慣れが必要な気がします。Sum1.残りのリスト(T)の合計をSum1にマッチさせ、それに先頭(H)を足せば全体の合計(Sum)になるというわけです。合計の定義の中で合計(sum)を使っています。再帰的な感覚に慣れましょう。前述のHaskellのような「関数」を使った再帰では、戻り値を変数に束縛しないためシンプルに書けましたが、PrologではSumやSum1のように一時的に結果を束縛するための変数が必要になります。無理がありますが、Haskellでも戻り値を変数に束縛し、Prologと同じように記述することができます。insum'こんな感じです。Haskellでは最初のシンプルな書き方で書くべきでしょう。作成したPrologのsumが正しく動くか確認してみます。