リストの要素を全て2倍するtwiceを作ってみましょう。空リストから考えます。再帰の終了条件になります。[]).空リストのtwiceは空リストってわけです。次に[H|T]パターンの場合について考えましょう。???まずは頭部から考えます。考えれば結果(第2項)がどういう形(パターン)になるか分かるはずです。twiceの結果である第2項はリストになるはずです。先頭要素も残りの要素も、2倍した結果は第1項の[H|T]とは違うはずです。いうわけで???の条件部分を考えなくても、twiceの結果は[H1|T1]と書けることが分かります。twiceの具体的な「手続き」を考える前に、結果を「宣言」してから考えるのです。???の条件部はどう書きましょう。H1とT1それぞれが「何か」を考えていけば良いです。結果の先頭要素(H1)は元の先頭要素(H)を2倍したものです。2,???次に結果の残り要素(T1)ですが、これは元の残り要素(T)をtwiceしたものです。ここで再帰を使うということが頭に浮かんでくるかどうかは慣れの問題だと思います。T1).これで定義できました。先頭要素を2倍したもの(H1)と、残りの要素をtwiceしたもの(T1)を合わせると全体を2倍したことになります。これもHaskellの定義と比較してみましょう。xsやはり、Haskellの定義ではH1やT1のような一時結果変数が無い分スッキリしていますね。一つだけ練習してみましょう。次の例には算術計算はありません。2つのリストを結合して1つのリストを得るappendという述語を定義します。空リストとリストをappendした場合です。具体例を挙げると、[]と[1,2,3]を結合したら[1,2,3]となります。そのまま書いてみます。L).次は[H|T]パターンを考えます。具体例を挙げると[1,2,3]と[4,5]を結合したら[1,2,3,4,5]となります。今回もtwiceの例と同じように、まずは頭部から考えてみます。???後でも説明しますが第2項(L)は分解マッチしてもしなくても良いです。結果(第3項)を見て下さい。先頭は第1項の先頭(H)と同じです。残り部分は第1項のTとも第2項のLとも異なるはずです。したがってL1と置きます。再帰に慣れているとすぐに分かります。appendの定義の中でappendを使います。L1).そうです、TとLをappendした結果がL1です。手続き的な思考では、リストのメンバを一つずつ移動させる方法(How)をイメージしますが、宣言的な思考では、それが何(What)であるかを考えようとします。結果(第3項)が何であるべきかを考え、次にL1はどうやって定義できるかを考えました。L1).となり、[H1|T1]部分は分解する必要が無いことがわかります。しつこいようですが、これもHaskellの定義と比較してみます。ysやはりL1という一時結果変数が無い分スッキリしています。先程からHaskellの方がスッキリ書ける!と、これではまるでPrologの述語における結果項が邪魔者みたいに思われるかもしれません。sumの例でも少し触れましたが、Prologのように結果を項として置くことで面白いことができます。その前にまずは作成したappendをテストしてみましょう。5].ちゃんとリストを結合してくれました。それでは今度は結果項にリストを与え、逆に元のリストを求めてみましょう。第1項、第2項とも変数にしてみましょう。このようにXとYの組み合わせパターンをバックトラックで求めることができます。appendはリストをくっつけるだけではなく、リストを分割することもできるのです。(もちろんリスト分割の関数を別に定義すれば良いのですが)。Prologの「述語」では、各項の関係を定義し、パターンマッチとバックトラックで様々な答えを求めることができます。この仕組みはとても面白いですね。今回はここまでにします。途中で少し触れましたが、宣言的プログラミングには慣れが必要です。それにしても今のところタイトルに偽りあり、さめがめ要素0ですね。次回は話を進められたらと思います。第45回目:Prologでさめがめを解く(Part1)2015-04-26筆者:村田こんにちは。前回プチコン3号で「さめがめ」というゲームを作ったのですが、今度はさめがめを解くプログラムを書いてみたいと思います。ここで言う「解く」とは、さめがめの盤面の全てのコマを消すことを指します。さめがめの盤面から最高得点を得られる消し方を探すプログラムではありませんが、まあとにかく全部消せたらOKです。使用するプログラミング言語はPrologです。PrologはC言語と同世代で1970年代初頭に開発されました。PrologはC言語とは大分雰囲気が異なるプログラミング言語です。CやBASICのように手続きを書き並べる言語ではなく、またHaskellのように関数を組み合わせる言語でもありません。Prologは論理型プログラミング言語と呼ばれていますが、一体どんな言語なんでしょうか。いうわけで、これからしばらくPrologにチャレンジしたいと思います。今では雑誌や新刊で取り上げられることも少ない言語で、私もWebの情報を頼りに学習中です。一緒に雰囲気だけでも味わってもらえたらと思います。何はともあれまずは処理系をインストールしましょう。PrologやSWI-Prologが有名な処理系です。今回はSWI-Prologを使いたいと思います。公式サイトから簡単にインストールできます。GUIインタフェースもありますが、ターミナルの方が使いやすいので私はコマンドラインから使っています。実際に試される方は好みに応じてどちらでも良いでしょう。起動コマンドはswiplです。...?-?-がプロンプトです。この後に入力できます。worldをやってみます。World!true.シングルクォートは文字列ではなくアトムというものを表します。writeは画面に文字を表示する「述語」です。writeの引数にアトムを渡して呼び出しています。呼び出しの最後にはピリオドが必要です。述語とアトムについては後でも出てきますのでさらりと次にいきます。今度は簡単な算術演算を試してみましょう。上記のような書き方はエラーです。以下のように足し算を表す組込述語を使って演算結果を取得します。3.Xのように大文字から始まるシンボルは変数を表します。ふむ〜、足し算からして何だか他の言語と違う様相ですね。いうところでいったん区切ります。そもそもPrologは記号処理に向いた言語であって、数値演算や副作用(画面出力)を主目的にした言語ではないのです。いうわけで、ハローワールドや算術演算はちょっとだけ難しいのです。それでは、SWI-Prologを終了するためにhaltという述語を呼び出しましょう。halt.さてさて、Prologの入門では定番の「とある家族の例」でPrologを触っていきましょう。これからはコードはファイルに保存し、SWI-Prologからロードして呼び出すことにします。SWI-PrologのREPL上でコードを定義することもできるのですが、素直にファイルに保存する方法が良いでしょう。拡張子はplを使っています。某有名一家の定義female(sazae).female(wakame).male(katsuo).コードを書く前にまずはコメントの書き方を覚えちゃいましょう。%記号を書くと行末までがコメントとなります。*/を使って複数行のコメントを書くこともできます。上記では3つの「節」というものを定義しています。節はピリオドで終了します。この例は単純そのものですが、Prologのプログラムは「節」の集まりから成っているのです。上記はfemaleという「関係」とmaleという「関係」を定義しています。sazaeやwakameは「対象」と言います。female関係には2つの節がありますね。male関係は1つの節からできています。female関係は、"sazaeは女性である"と"wakameは女性である"という「事実」を定義しています。慣れない用語が出てきますが、まあそんなものかって感じでいいと思います。用語はさておき書き方は難しくありませんね。事実の例をいくつか書いて練習してみましょう。ミートソースは飲み物である事実を書くときの注意として、対象にはアトム(または数値)を書かなければなりません。アトムは英小文字から始めます。Sauce'の例のようにシングルクォートで囲んだ場合は、英大文字から始めたり、空白文字を含めることができます。アトムは他の言語での定数やSymbolのようなものです。それではseafamily.plをSWI-Prologでロードしてみましょう。コマンドラインオプション(-f)でファイル名を渡すことができます。・・・?-ほ〜読み込み時にコンパイルしているようですね。(テキトーな理解ですね・・・)プログラムにおかしなところがあればコンパイル時にエラーが出ます。REPLからロードすることもできます。・・・true.大カッコの中に拡張子を除くファイル名を書いて末尾にピリオドを書きます。プログラムをロードするとPrologに対して簡単な「質問」を行うことができます。「?-」プロンプトは?記号が表すように質問を受け付けるプロンプトです。female(sazae).true.上記のようにsazaeさんは女性です(か?)との質問に対し、Prologはtrueと答えてくれました。female(katsuo).false.katsuoくんは女性です(か?)に対してはfalseですね。male(masuo).false.seafamily.plに"masuoさんは男性である"という事実は書かれていないのでfalseが返ってきました。このように「?-」プロンプトの後に質問を書くことでPrologと対話し、プログラムを実行することができます。単純な質問しか試していませんが、今度は変数を導入してもう少し複雑な質問をしてみましょう。katsuo.アトムは小文字からでしたが、変数はXのように大文字アルファベットから始めます。単純な例ではXのような一文字変数を使っても良いですが、複雑になってきたらNameとかAddressのように意味の取りやすい変数名を使った方が良いでしょう。今度はfemale関係についての質問をしてみます。□Prologはsazaeという答えを返したあと、次の答えを出すべきかユーザーの入力を待っています。セミコロンを入力してみましょう。wakeme.wakameという答えを返し、female関係の対象を全て答えたので終了しています。続きの答えが不要ならばセミコロンではなくピリオドを入力することもできます。このように変数を使うとtrue/falseを答えるのではなく、変数部分に一致する対象を探し出して答えてくれます。この変数と対象を一致させることを「ユニフィケーション」と言います。先ほどのfemale関係の質問で見たように、Prologは複数ある答えを順番に教えてくれました。このように複数の答えを自動的に探し出してくれる機構を「(自動)バックトラック」と言います。ユニフィケーションとバックトラックはPrologプログラミングの特徴的な機能であり中心機能です。ユニフィケーションは他の(主に関数型)言語でのパターンマッチと言われる機能と似ていますね。これらはPrologプログラミングで何度も使いますので是非覚えておきましょう。今度はseafamily.plに2つの対象(項)を持つ事実を4つ追加してみます。sazae).お分かりの通り某家族の親子関係をいくつか表しています。第一項が親、第二項が子ですね。それではPrologに読み込ませて質問してみましょう。sazae).true.ふむ。変数を使ってsazaeの子供が誰なのか聞いてみましょう。tarao.OK、taraoくん。今度は逆に子を指定して親が誰なのか聞いてみましょう。sazae.parent関係を定義するだけで、両方向、つまり子だけでなく親も簡単に推論してくれます。ふむ、Prologのユニフィケーションは柔軟ですね。親子いっぺんに聞いてみましょうか。・・・41〜4の4つの答えをバックトラックして探し出してくれました。データベースに対するクエリのようです。次は複数の質問を組み合わせて大きな質問を作ってみましょう。tarao).true.複数の質問をカンマでつなげています。「かつ(and/連言)」の意味で使うことができます。namiheiはsazaeの親で、かつsazaeはtaraoの親ですか?という質問ですのでtrueが返ってきました。複数の質問をする際にも変数を使うことができます。次の質問で試してみましょう。sazaeさんですね。この例のポイントは、namiheiの子供という条件を満たす人と、taraoの親という条件を満たす人が同一人物であることを表すため、Xという同じ変数にユニフィケーションさせている点です。4つの事実から成るparent定義ですがもう少し遊べますよ。今度はtaraoの祖父母を探してみましょう。・・・2バックトラックして2つの答えを返してくれました。Yはtaraoの親を表した一時的な変数として使用しています。Xが求めたい祖父母を表していますので、Xの結果に着目すると、taraoの祖父母はnamihei及びfuneであることが導けていますね。祖父母を求める上記の質問は有意義ですが、記述量が多くて毎回入力したくありません。そこで質問の組み合わせに対して新しい名前を与え、さらにファイルに追加していつでも呼び出せるようにしましょう。Y).「:-」の左側を「頭部」と言い、右側を「条件部」と言います。呼び方はさておき意味を追いかけましょう。grandparentという新しい「関係」を定義しています。Xが祖父母、Yが孫という関係は、間の親にZという変数を使うと、Xの子供がZで、そのZの子供がYであると定義できます。それではPrologにロードしてテストしてみましょう。taraoの祖父母はnamiheiとfuneです。tarao.OKOK。namiheiの孫はtaraoです。最後にいっぺんに問い合わせてみましょう。・・・2祖父母と孫の関係にあるのはnamiheiとtarao、及びfuneとtaraoであることがバックトラックで求められました。このようにparentのような基本的な「事実」を組み合わせて新しい「関係(ルールとも言います)」を定義していくことで、複雑なプログラムを作っていきます。他の言語では関数やクラスを定義してプログラムを作っていくわけですが、Prologの場合は事実と関係(ルール)を定義してプログラムを作っていくのですね。今回はここまでにしたいと思います。Prologのサンプルコードを一つ書いただけですね・・・次回はリスト構造ともう一度算術式に触れたいと思います。さめがめソルバーを書き始めるのはもう少し先になりそうです。長くなる場合は途中で違うテーマを挟んだりするかもしれませんが、気楽に宜しくお付き合い下さい。第44回目:プチコン3号(BASIC)でさめがめ(Part3)2015-03-29筆者:村田こんにちは。東京の満開予想は3/30だそうで、4/6頃までが見頃のようです。弊社のある立川近辺でしたらやはり昭和記念公園が有名ですね。広い敷地でたくさんの桜を見ることができます。花見会場となるような大規模な桜も良いですが、身近な桜も良いです。週末に通う地元の図書館の桜はいよいよという感じでした。ここの桜は本数が少ないですが、枝振りも良く、図書館の屋根に冠る様はとても綺麗で、図書館の落ち着いた雰囲気に合うところがお気に入りです。今週は通勤電車の車窓から見える桜にも注目すべく、いつもはスマホ、読書に当ててしまう時間ですが顔を上げて見ようかな^^さて、今回はさめがめのスコアを計算して画面に表示するところから始めます。PRINTコマンドを使って画面に文字列を表示します。WORLD"変数や式の結果も表示できるのでデバッグにも使えます。'「30」と表示セミコロンを挟むと複数の変数や文字列をくっつけて表示することができます。X+Y=15」と表示LOCATEコマンドを使って文字表示位置を指定することができます。X座標,Y座標,Z座標"と指定します。Z座標は液晶面を0として手前がマイナス、奥がプラスの値となります。実際に3DSの3D表示を有効にするとマイナスZ座標で浮き上がって見え、プラスZ座標で奥に引っ込んだように見えます。"POIPOI"では位置決めと画面表示を関数にまとめて使いやすくしておきましょう。AEND引数Aに表示したい文字列を渡し、引数Yに表示したい上下位置を渡します。文字列の長さから、水平中央に表示させるためのX座標位置を計算しています。グローバル変数SCOREを用意しておきます。SCORE=0前回、隣接した同種のコマを削除するNDEL関数を作成しました。NDELの戻り値は削除できたコマ数ですので、ここからスコアを計算します。さめがめの一般的なスコア計算かどうかわかりませんが、今回は以下の算出式を使います。削除したコマ数が3個以上なら有効得点になります。一度にたくさん削除する方が高得点となります。それでは上記算出式をプログラムに書きましょう。サクジョC=C-2SCORE=SCORE+C*Cそれでは先ほど作った文字表示関数PRTを使って画面にスコアを表示してみましょう。"+STR$(SCORE),3STR$関数は数字を文字に変換する関数です。BASICの型には数値型と文字型があり、異なる型を+で足す(連結)することはできませんので型変換が必要です。上記のスコア計算は変数Cが2以上(2の場合は得点0)ならうまくいきますが、1以下の場合は正しくありません。そもそもコマを消すことができるのは、1個以上の隣接コマがある場合であり、一人ぼっちのコマは削除できないのです。そこで、現在カーソルが指しているコマに、少なくとも1個以上の隣接コマがあるかチェックしてみましょう。ナイENDこのCANDEL関数でチェックしてからNDEL関数を呼ぶようにします。'スコアUP・・・ENDIFこれでコマの消し方と得点の関係は以下のようになります。コマ1個:消せないコマ2個:消せる(0点)コマ3個:消せる(1点)コマ4個:消せる(4点)コマ5個:消せる(9点)・・・もう少しで完成です。ゲームオーバー/ゲームクリア処理を書きましょう。画面上のコマを全て消せたらゲームクリアとなります。クリア時には1000点のスコアボーナスをあげましょう。逆に画面上に一つ以上コマが残っているにも関わらず、どれも同種の隣接コマが無くて消せない状態になったらゲームオーバーとなります。ゲームクリアかどうかは、ボード左下にコマがあるかどうかで簡単に判断できます。コマを削除すると左下に向かって隙間が詰められるからですね。0ENDゲームオーバーかどうかはボード左下から順番にコマを走査し、削除可能なコマが一つでも残っているかを調べて判断します。ナイ'END今回作った、スコア表示、ゲームクリア判定、ゲームオーバー判定はゲームループ内で毎回呼び出す必要はありません。これらはコマが削除され、スコアやゲーム状態が変わった時にのみ呼び出せば良いです。そこで@JUDGEサブプロシージャとしてまとめておいて、コマが削除できた時にまとめて呼び出せるようにしましょう。@PROGENDENDIFRETURNこれで完成です。ゲーム終了後のリトライなど、もう少しだけ処理を追加した全コードについては、本コラム一番下のリンク(GitHub)を参照してください。それではせっかく作ったので遊んでみます。クリアまではできませんでした。さめがめ攻略法をネットで検索しようかな・・・まあ作る方が楽しいのですけどね。えっと、もう一つ機能紹介を。プチコン3号では作成したプログラムを公式サーバーにアップロードし、審査後に公開キーを発行してもらうことができます。他のユーザーは公開キーを使ってプログラムをダウンロードすることができます。公開キーの発行手順は簡単です。改造ネタとしては、削除して垂直方向を詰めた後(VPACK)、上から新たなコマを降らせても面白そうですね。その場合は全部消すことがゲーム目的では無く、如何に大量消しを維持するかで得点が変わるシステムとかどうでしょう:-)[おわりに]プチコン3号のBASICプログラミングはいかかでしたか?クラスやラムダのようなプログラミング言語機能はありませんが、むしろ設計にあまり悩まずゴリゴリ書いていけるスタイルが楽しいです。ボタン割り当てなどに工夫があり、意外と気にならないのです。ネットで検索すると「こんなこともできるのか」と驚くようなプログラムがあり、それらをダウンロードして改造してみるのも楽しそうです。昨今、プログラミングを義務教育に〜なんて話題もあり、ビジュアルプログラミングや子供向けプログラミングワークショップなどのニュースを見ることも多いです。教育向けプログラミング言語BASICであるプチコン3号は、最初の敷居は低くて入りやすく、それでいてしっかりアルゴリズムを書けて深い理解が得られる、とてもいいツールだと思いました。