昨年、「プログラミング多言語主義」という記事を書きました。
それを踏まえて。 ふだんと違うプログラミング言語を使ったとき、実際にどんな風景が見えるのか、それ見に行こう… というのが、今回の記事の表のテーマです。
先に弁明をしておくと。 今回書くコードは「いつもと違う風景を見る」ことに重心を置いていて、効率とかは脇によけてあります。 その点はご容赦を。
どう書く？：すべての順列を生成するプログラム
早速ですが、一連の要素の順番を入れ替えてできる並びをすべて挙げる例を考えてみましょう。
例えば
という入力に対して、
という出力をえる、というものです。
Rubyで書いたばあいであれば、このような結果になると想像してください。
perm([1, 2, 3]) # => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]]
あるいはイテレータで、
perm([1, 2, 3]) do |output| p output end # [1, 2, 3] # [1, 3, 2] # [2, 1, 3] # [2, 3, 1] # [3, 1, 2] # [3, 2, 1]
Thinking Time
お時間のある方はここで立ち止まって、自分ならどんなコードを書くか、想像してみてください…。
順列を定義する
さて、ここではふだん触れられることの少ない言語を使って順列を定義してみたいと思います。
Prologです。
ふだんあまり使われない言語（たぶん）、Prolog
Prologプログラミングは、ふだん手続的なプログラミングをしている人にとっては、視点の転換をしいてくる面白い言語です。 いつもと違う視点のプログラミングをしてみる例として、今回はPrologで実装していきたいと思います。
Prologを紹介した書籍としては「7つの言語 7つの世界」が割と有名です。 わたしもこの本で関心を持った一人です。
気付くと邦訳が出てから十年になるんですね。
Prolog利用者人口をわたしも把握しているわけではありませんが、周囲を見るかぎり使用している人を見かけません。 そこであえて、Prologを使ってコードを書いてみたいと思います。 はい、わたしの趣味です。
なお今回のコードは、2つの処理系 GNU Prolog と SWI-Prolog で動作を確認しています。
思考の準備運動
まずはじめに、Prologプログラミングの面白いところを append という述語を例に説明してみたいと思います。
この append はとても使い出がある述語で、この後の実装でも利用する予定です。
「述語」という言葉を使いましたが、Prolog は、関数(function)やメソッド(method)でなく、述語(predicate)でプログラムを書きます。 述語とは入力に対して真偽を返すものです。
append は3つの引数を受け取り、第1引数のリストに第2引数のリストを連結したリストが第3引数のリストであるばあいに真を返します。
実際に処理系を起動して動きを見てみましょう。
GNU Prologの例：
$ gprolog # GNU Prolog を起動 | ?- append([1, 2], [3, 4], [1, 2, 3, 4]). yes
SWI-Prolog の例：
$ swipl # SWI-Prolog を起動 ?- append([1, 2], [3, 4], [1, 2, 3, 4]). true.
GNU Prologでは真偽を yes, no で返し、SWI Prologでは true, false で返すという違いはありますが、どちらも同じように真を返しています（以降はGNU Prologを使います）。
Prologは、ここが面白いところですが、述語の引数の一部を変数にすると、結果が真になるような値をその変数に割り当てて返してくれます。
例えば、第3引数を変数にすると次のようになります。
ちなみに Prolog では変数名は大文字から書き始めるルールになっていて、ここでは L が変数になります。
| ?- append([1, 2], [3, 4], L). L = [1,2,3,4]
式が真になるために必要な値が、変数 L に割り当てられました。
これは第1引数を変数にしても、第2引数を変数にしても同じです。
| ?- append([1, 2], L, [1, 2, 3, 4]). L = [3,4]
| ?- append(L, [3, 4], [1, 2, 3, 4]). L = [1,2]
第1引数と第2引数の両方を変数にすると、他のプログラミング言語ではあまり見かけない結果を返してくれます。
| ?- append(L1, L2, [1, 2, 3, 4]). L1 = [] L2 = [1,2,3,4] ?
まず、[] に [1, 2, 3, 4] を追加すると [1, 2, 3, 4] になるので、結果が真になる値の組み合わせです。
結果を表示した後は入力待ちの状態になっているので、ここでセミコロン ( ; ) を入力します。
| ?- append(L1, L2, [1, 2, 3, 4]). L1 = [] L2 = [1,2,3,4] ? ; L1 = [1] L2 = [2,3,4] ?
[1] と [2, 3, 4] の組み合わせが表示されます。
これも式が真になる値の組み合わせです。
このように真になる値が複数あるばあいに、すべての結果を出力してくれます。 セミコロンは他の値の出力を促す入力になっています。
他にも組み合わせがあるので、何回かセミコロンを入力してましょう。
| ?- append(L1, L2, [1, 2, 3, 4]). L1 = [] L2 = [1,2,3,4] ? ; L1 = [1] L2 = [2,3,4] ? ; L1 = [1,2] L2 = [3,4] ? ; L1 = [1,2,3] L2 = [4] ? ; L1 = [1,2,3,4] L2 = []
とりうる値のすべての組み合わせが出力されると、ようやく通常のプロンプトに戻りました。
Prolog自体の詳細は、先に紹介した「7つの言語 7つの世界」やドキュメントを参照してみてください。
これらを踏まえて。
ようやく順列をえる述語 perm を実装します。
順列の Prolog での実装
% agile-dev-blog.pro perm([], []). % 空のばあい perm([Head | Tail], Output) :- % 第1引数を Head と Tail に分割 perm(Tail, Partial), % Partial は Tail の順列であり、 append(Left, Right, Partial), % Partial は Left と Right から成り、 append(Left, [Head | Right], Output). % Output は、その Left と Right の間に Head を置いたもの
このコードは agile-dev-blog.pro というファイル名のファイルに保存しておいてください。
[Head | Tail] という記述は、リストを先頭の要素と後続のリストにわけて表現したものです。
| ?- [1, 2, 3] == [1 | [2, 3]]. yes
先頭の複数の要素については次のように書くこともできます。
| ?- [1, 2, 3, 4] == [1, 2 | [3, 4]]. yes | ?- [1, 2 | [3, 4]] == [1 | [2 | [3, 4]]]. yes
では実行してみましょう。
GNU Prologでのばあいは次のようにファイルを読み込みます。
$ gprolog --consult-file agile-dev-blog.pro
SWI-Prologのばあいは次のようになります。
$ swipl -f agile-dev-blog.pro
起動してファイルの読み込みが完了するとプロンプトが表示されれますので、次のように入力します。
| ?- perm([1, 2, 3], Output).
今回実装した perm も、先ほどの append のばあいと同じように、変数がとりうる値は複数あるので、セミコロンを入力して残りを表示しましょう。
| ?- perm([1, 2, 3], Output). Output = [1,2,3] ? ; Output = [2,1,3] ? ; Output = [2,3,1] ? ; Output = [1,3,2] ? ; Output = [3,1,2] ? ; Output = [3,2,1]
いかがでしょう？。 コードも動きも見慣れない、不思議な印象を受けたのではないでしょうか。
ふだんプログラミングをするとき、多くのばあいで「問題を『どのように』解くか」と、手順を考えると思います。
一方Prologプログラミングでは「問題に対して解は『どうあるべき』なのか」と考えることが求められれます。 脳のふだん使わない部分を、がんばって稼働させる感覚さえしてきます。
どう書く？：ソートプログラム
これで順列をえる手段を入手することができました。
これを利用して、今度はソートを考えてみたいと思います。
Thinking Time
お時間のある方はここで立ち止まって、自分ならどんなコードを書くか、想像してみてください…。
Prolog でなく、先ほどの Thinking Time で想像したご自身のコードをもとに考えてもらって大丈夫です…。
ソートを定義する
ソートのアルゴリズムは多々ありますが、いざソートを定義しようとすると、その手順が頭に浮かんでしまいます。
その思いをふりはらい、入力と出力に注目してみます。
入力: [5, 1, 4, 2, 3]
出力: [1, 2, 3, 4, 5]
ここまでの話の流れをふまえて。 入力と出力をじっと見てみると。 出力は「入力の要素を並べ替えてできる列のうち、隣り合うどの2つの要素を取り出しても、左の要素が右の要素以下であるもの」という見方も見えてきませんか？
ソートの Prolog での実装
そのような見方をPrologのコードにしてみましょう。
% agiile-dev-blog.pro perm([], []). perm([N | Rest], Perm) :- perm(Rest, Partial), append(Left, Right, Partial), append(Left, [N | Right], Perm). my_sort(Input, Output) :- % ※ 組み込みの述語 sort と名前が衝突しないようにしています perm(Input, Output), % 順列のうち、 forall( % すべての、 append(_, [N, M | _], Output), % 出力内の、隣接する要素は、 N =< M % 左の要素が右の要素以下である ).
起動してファイルを読み込ませて実行してみます。
| ?- my_sort([5, 1, 4, 2, 3], L). L = [1,2,3,4,5] ?
結果が出力されました。 が、入力待ちになっています。
これは見つけた結果以外で条件に合うものが残りの中にある可能性があるためです。 この入力では1つだけですが、重複した要素があるばあいにそれぞれを別の要素として扱っているので、それぞれの順序が結果として出力されます。
| ?- my_sort([2, 1, 1], L). L = [1,1,2] ? ; L = [1,1,2]
このようなばあい、Prolog のプログラミングの手法として、条件に合う結果がえられたら探索の打ち切りを指示することができます。
my_sort(Input, Output) :- perm(Input, Output), forall( append(_, [N, M | _], Output), N =< M ), !. % 条件に合致したら探索を打ち切る
| ?- my_sort([2, 1, 1], L). L = [1,1,2]
最初に見つかった結果だけが出力されるようになりました。
どこかで見覚えがありません？
プログラミングとしては、見慣れないコードだったかと思いますが、ここ感じどこかで覚えがありませんか？
ある集まりから、条件に合う結果を出力する。
Ruby on Railsプログラマでしたらよくご存知の、SQLがそれですね。 SQLを書くことは、条件を組み合わせてDBに格納されているデータから欲しいデータを取得する、プログラムを書いていることでもあるわけです。
SQLは、実際にデータ検索以外の問題を解くこともできます（これとかこれとかこれとか）。 ですが、あまり無茶をなさらぬよう…。
まとめ：いつもと違う風景を見に行く
ある問題を解くアルゴリズムが複数あることからもわかるように、複数の解法があることが一般的です。
一方で、解法に注目するのでなく、ここでPrologで書いたように、結果に注目して問題に取り組むという方法もあるわけです。
複雑化する問題に頭を抱えたとき、この記事が「そもそも問題はなんだっけ？」「欲しいものはなんだっけ？」という気付きの一助になれば幸いです。
「情報化技術を通じて社会と共生する」株式会社永和システムマネジメント アジャイル事業部では、エンジニアを絶賛募集しています。 応募エントリお待ちしております！ 一緒にいつもと違う風景を見に行きませんか？ 応募エントリお待ちしております！
