ニューラル株式会社｜ハイブリッドOS｜File System｜ARM｜Android｜Java｜制御システム｜オープンシステム

筆者：村田

 

こんにちは。

 

今回からプログラミング言語OCamlを使ってへびゲーム(SnakeGame)を作ってみたいと思います。へびゲームは有名なゲームで、プレイヤーはへびを操作し、エリア内のえさを食べ続けるというゲームです。へびの頭が自分の体に触れないように操作するのですが、えさを食べると体（尻尾？）が伸びるので、ぶつからないように食べ続けることが段々難しくなるところがミソです。へびゲームには色々なバリエーションがあり検索するといっぱい見つかると思います。今回作成するへびゲームのポイントは以下の通りです。

 

・コンソール画面(CUI)で動かす

・へびはキーボード(WASDキー)で操作する

 

一般的(?)なへびゲーでは、へびは一定速度で頭の進行方向に移動し続け、プレイヤーはへびの方向転換だけを操作するのですが、今回はタイマー処理などを省くため、へびの移動はキーボード押下時のみとします。

 

ゲームのイメージはこんな感じです。

 

*記号がへびです。頭だけ違う記号にしようかと思いましたが、頭がどっちか分からなくなる方が少しだけ難易度が上がるかもと思い、全身*記号にしました。ほんとはコードを単純にしたかっただけです。O(大文字オー)はエサです。なぜかエサはリンゴであることが多いです。へびに唆されてアダム&イブがリンゴを食べた？という話から来ているのでしょうか。今回はへびがリンゴ食べちゃうんですけど。

 

前回までのHaskell,Clojureのコードをちょっとだけ思い出してください。書いたプログラムはどちらも副作用の無いプログラムでした。入力値は固定(大きな素数/盤面サイズ)で、何回実行しても結果は変わりません。この性質は関数型プログラミングでよくでてくる話ですね。以下の言葉は同じことを言っています。

・副作用が無い（代入が無い）

・純粋な関数

・参照透過性がある（成り立つ）

・関数は引数にしか依存しない

・宣言的プログラム

上の言葉の逆の意味を説明することで、参照透過性についての説明を試みてみましょう。

 

関数内でグローバル変数を読み書きしたり、ファイルI/O操作をしたり、ランダム値、時刻などを扱っている場合は副作用を持った関数と言えます。引数以外に依存して結果が変わるし、純粋な関数とも言えません。副作用のある関数内で使っている参照（変数）は「いつ見るか」で値が変わるし、時刻／ファイル／グローバル領域など「どこに記憶された値なのか」を意識しなければなりません。純粋な値ではなく不透明な値ですね。つまり参照を「透過的」に見れないのです。

 

次に参照透過性（純粋関数）のいいところをいくつか挙げましょう。引数にしか依存しないのでプログラムが読みやすく、バグも作り込みにくくなります。もちろんプログラムの読みやすさはコメント、変数名、関数の粒度など他にも大切な要因がありますが:-) そして、引数にしか依存しない、すなわち関数外部を参照しないので、関数評価をマルチコアで分散処理しやすくなります。また、いつ評価しても同じ結果が返ってくるので遅延評価にも向いています。宣言的プログラムとは、変数というメモリ操作を意識した手続き中心に書くのではなく、y = f(x)と書くとき、関数(引数)と関数値は数学的宣言の通りに等しく、いつでも交換可能という考え方でプログラムを書くことです。

 

と、いっぱい書きましたが、いいことばかりじゃありません。関数と引数しか無い世界では、ユーザ入力やファイル内容に応じて動作が変わるプログラムが書けません。したがって、いつまでも純粋じゃいられないのです。どこかで副作用・入出力のあるリアルワールドに飛び出さなければならないのです。そんなわけで今回のお題はゲームです。副作用としては画面出力、キーボード入力、リンゴ出現のランダム処理が該当します。それ以外はなるべく純粋のままでいたいと思います。

 

オーキャムル、オーキャメルって呼びます。ラクダがイメージキャラのようですね。個人的にはラクダっていうとPerlのイメージがありますが。ML言語を祖先とし、フランスで開発されている言語です。いくつか特徴を紹介しましょう。強い静的型チェックが行われる言語ですが、型推論があるので型情報をいちいち書かなくてもコンパイラが補ってくれます。関数型言語の仲間なので、関数を貼り合わせてプログラムを書いていきますが、Haskellのような堅物？とは違い副作用が書きやすい言語であります。printデバッグもしやすいかと。参照という機能で変数を書き換えられます。ってことで再代入できるのでfor式、while式もあり、再帰じゃなくてもループを書けます。それとOCamlのオーはObjectiveのオー！、クラスシステムがありオブジェクトを使ってプログラムを書けます。えーとあとは、バイトコードやネイティブコードを吐くコンパイラがあります。ちょっと使いにくいけど、対話式コンパイラ（REPL）もあります。まとめると、関数型プログラミングを中心としつつも、手続きが書きやすく、クラスシステムもあるハイブリッドな言語と言えるでしょう。このようなハイブリッド言語としてはScalaの方が有名かもしれません。

 

OCamlのインストールの話は省略します。なおTryOCamlというWebサイト上のREPLがあり、そちらで手軽に遊ぶこともできます。それでは早速REPLを起動しましょう。

$ ocaml

 

式を入力してみます。

# 1 + 2;;

- : int = 3

 

#がプロンプトです。式の終わりにはセミコロン２つが必要です。結果の型がintであることも分かります。

 

# 10 / (* comment *) 4;;

- : int = 2

 

コメントは(*と*)でくくります。終了方法を確認しましょう。

 

# #quit;;

 

#で始まるコマンドは対話式コンパイラへのコマンドです。関数ではありません。次は値と関数の定義方法を見てみます。

 

# let ewing = 33;;

val ewing : int = 33

 

# let square x = x * x;;

val square : int -> int = <fun>

 

値も関数もletで定義します。関数の型はint -> intです。Haskellで見たような表記ですね。引数の型がint、結果の型がintということです。関数のそのものを表す値として<fun>と表示されています。それでは関数に引数を与えて呼んでみましょう。

 

# square ewing;;

- : int = 1089

 

では続けて、よく使うデータ構造を確認しましょう。まずはリストです。

# [1; 0; 8];;

- : int list = [1; 0; 8]

 

セミコロンでデータを区切って[]で括ります。型はint listとなります。次は先頭に一つ要素を追加する演算です。これはHaskellだと:(コロン1つ)という演算子、clojureだとconsという関数でしたね。よく「コンスする」って言います。OCamlのコンス演算は::(コロン2つ)で行います。

 

# 1 :: [2; 3; 4];;

- : int list = [1; 2; 3; 4]

 

リスト同士を結合する演算は@で行います。

# [1; 2; 3] @ [4; 5; 6];;

- : int list = [1; 2; 3; 4; 5; 6]

 

次のタプルもよく使うデータ構造の一つです。タプルは異なる型のデータをまとめるのに便利です。

# ("su-xing-chu", 4);;

- : string * int = ("su-xing-chu", 4)

 

カンマでデータを区切って()で括ります。文字列と数値の組み合わせなので、string * intという型になります。次は無名関数です。無名関数は 「fun 引数 -> 式」って書きます。

# List.map (fun x -> x + 1) [1; 2; 3];;

- : int list = [2; 3; 4]

 

List.mapという表記はListモジュールのmap関数という意味です。map関数は第一引数に関数を取る高階関数です。リストの各要素に第一引数の関数を適用し、結果をリストにして返します。駆け足で基本部分をざーっと流したところで、本日最後になりますが、ネイティブコンパイラを試しておきます。まずお好みのエディタでコードを書いて下さい。拡張子はmlです。

# emacs SnakeGame.ml

 

let () = print_endline "Hasta la vista, baby...b";;                             

 

print_endline関数は文字列をコンソールに表示して改行する関数です。ところでOCamlはmain関数がありません。スクリプト言語みたいに宣言だけでなく実行式もソースに書けるので、適当にファイルの末尾あたりで宣言した関数を呼び出せばいいのですが、let ()=と書いたトップレベル宣言は実行されることになっているのでmain関数の代わりになります。コンパイルして実行してみましょう。

 

$ ocamlopt SnakeGame.ml

$ ./a.out 

Hasta la vista, baby...b

 

以上

筆者：村田

 

こんにちは。

 

前回は列のチェック関数を作成し、末尾再帰について紹介して終わったのでした。check-col関数の動作をもう一度おさらいします。第1引数にチェックしたい行の先頭である(3 1)や(4 1)を渡し、第2引数には盤面上に置いたクイーンのリストを渡します。例えば、(1 1)と(2 4)にクイーンがある場合、3行目にクイーンが置けるかをチェックすると、

 

user=> (check-col '(3 1) '((2 4) (1 1)))

((3 2) (2 4) (1 1))

 

(3 2)に置けることが分かり、(3 2)を加えた盤面上クイーンリストを返してくれます。今度は行のチェック関数を作りましょう。前回の記事の前半にて、手動でアルゴリズムの動きを確認しましたが、改めて手順をイメージします。->の後は盤面上のクイーンリストを示しています。

 

1. 1行目はどこに置けるか? -> ((1 1))

2. 2行目はどこに置けるか? -> ((2 3) (1 1))

3. 3行目はどこに置けるか? -> nil -> 置けなかった

4. 2行目に戻って、別の場所に置けるか? -> ((2 4) (1 1))

5. 3行目はどこに置けるか? -> ((3 2) (2 4) (1 1))

 

関数名と引数はこんな感じです。第1引数は分配束縛して分解しておきます。

(defn check-row [[row col :as pos] queens] ...

 

次に、引数に渡された位置に基づいて、その行のどの列なら置けるか調べます。

(defn check-row [[row col :as pos] queens]

  (if (check-col pos queens) ;; どの列に置けるか?

      (置ける場合の処理)

      (置けない場合--nilの処理)

 

と書けます。置ける場合は、次の行のチェックに進めばいいので、行をインクリメントして再帰呼び出しします。

 

(defn check-row [[row col :as pos] queens]

  (if (check-col pos queens)

      (check-row (list (inc row) 1) (check-col pos queens)) ;; 再帰呼び出し

      (置けない場合--nilの処理)

 

(list (inc row) 1)の部分は、次の行の先頭ですね。rowが3ならば(4 1)となります。問題はcheck-col関数を2回呼び出している点です。1回目は真偽値判定として、2回目は戻り値のクイーンリストが欲しいからですが、2回もcheck-colを動かすのは効率が悪いです。関数内で一時的に変数を作って、呼び出し結果を取っておきましょう。letフォームを使えば関数内で一時変数を使えます。書式は、

 

(let [束縛名1 式1 束縛名2 式2...] (束縛名1,2を使った式))

 

ちょっと具体例が必要ですね。

user=> (let [x 1 y 2] (+ x y 3))

6

 

xに1、yに2を束縛し、xとyと3を足しています。ところで関数型言語では、変数に「代入」と言わず、変数に「束縛」って言ったりします。オブジェクト指向言語では変数は「入れ物」であり、値を入れたり(代入)、値を入れ替えたり(再代入)できます。関数型言語では、変数はただの「名前」です。何かの値や、関数/式の結果や、関数そのものを指し示します。100という値に一度aという名前を付けたら(束縛)、aはずーっと100となります。そう名前を付けたのですからね。200という値にもaという名前を付ける、ということはできません。まあ、束縛(bind)という言葉から、このニュアンスが伝わるかはさておき、重要なことは再代入(名前の付け替え)はできないということです。

 

話を戻します。letフォームの[]内は束縛名と式を順番に並べます。この束縛はletフォーム内での一時束縛ですので、letフォームの外側からは参照できません。さて、letフォームを使ってcheck-colの結果を取っておけるようにしましょう。

 

(defn check-row [[row col :as pos] queens]

  (let [newqueens (check-col pos queens)] ;; 結果をnewqueensに束縛

       (if newqueens

           (check-row (list (inc row) 1) newqueens)

           (置けない場合--nilの処理)

 

letフォームを使うとどんどんネストが深くなってしまいますが仕方ないです。見づらくなったら関数に切り出す、マクロを作るなど対処が必要かもしれません。

 

次は置けない場合の処理です。一つ前の行に置かれたクイーンを取り出して、他の場所に置けないか続きを調べさせます。

 

(defn check-row [[row col :as pos] queens]

  (let [newqueens (check-col pos queens)]

       (if newqueens

           (check-row (list (inc row) 1) newqueens)

           (let [[row col] (first queens)]

                (check-row (list row (inc col)) (rest queens)))))) ;; 一つ前のクイーンの位置を調べ直す

 

だんだん横に長くなってきますね。インデントは自由に書けます。ifフォームは条件/True処理/False処理のカラムを揃えた方が見やすいと思いますが、letフォームのインデントは浅くした方がいいかもしれません。

 

5行目でまたもやletフォームで一時束縛しています。queensの先頭を取り出して一つ前のクイーン位置を分配束縛しています。[]が２重になっているので注意。

 

(let [pos (first queens)] ...)

 

と書いてもいいですが、この後posのrowとcolを分解したいので、

 

(let [[row col] (first queens)] ...)

 

と分配束縛しています。このように分配束縛は関数の引数だけでなくletフォームでも使えます。6行目は (list row (inc col))で、行はそのままで列をインクリメントして再帰呼び出ししています。(rest queens)で盤面上のクイーンリストから一つ前の行のクイーンを除いています。これで一つ前の行のクイーンは一度取り除き、続きの列から置ける場所を探させているというわけです。この辺りのアルゴリズムは再帰も絡んでいてイメージしづらいかもしれません。その場合は、前回記事のようにcheck-rowに手動で引数を渡して実際に動かしてみるといいと思います。REPLでも紙でもいいのですが、複雑なアルゴリズムは手を動かすと理解が深まると思います。

 

昔話ひとつ。異業種からプログラマになりたての頃です。(26だったかな・・遠い目)　C言語の入門書を読み、プログラムを書き始めて最初にハマったのはポインタでは無く(もちろんポインタでもその後"ど"ハマりするわけですが・・)、for文を使って歯抜けになった配列を詰めるというアルゴリズムでした。慣れないviの画面をにらみ、ひたすら頭の中で考えるも、まーったく書けず、先輩に相談しました。こいつ大丈夫か〜と思われながらも、モニタを消され裏紙と鉛筆を渡され、「一度に全部考えず、手順をバラバラにしろ、手を動かせばバラバラにできるだろ〜」と言われました。その後しばらく書いたり消したりして、ようやく手順(アルゴリズム)を書くことができました。今でもアルゴリズムやクラス設計で悩むと、紙を取り出してお絵描きしています。(そしてその時間が一番楽しかったりします)　弊社内では、みんなでアルゴリズムやデータ構造の学習問題に取り組む機会があるのですが、私の場合はたいてい頭にすぐ浮かばず、お絵描きが始まるのです。

 

え〜、脱線するからpart5までかかってしまうのですが、とにかく、時には紙に自由に絵を描いたり、REPLで気の済むまで実験すると理解が深まったりしますという意見でした。

 

ところで先程の関数は再帰を使っていますが、停止するか確認していませんでした。アルゴリズムの動作をイメージします。6行目で対象の行を増やしながら再帰を繰り返すと、いつかは盤面をはみ出しますね。この関数もcheck-colと同じように最初に盤面をはみ出していないかチェックするようにします。少しインデントも狭めましょう。

 

(defn check-row [[row col :as pos] queens]

  (if (not (on-board? pos)) queens ;; 盤面のチェック

      (let [newqueens (check-col pos queens)]

        (if newqueens

            (check-row (list (inc row) 1) newqueens)

            (let [[row col] (first queens)]

              (check-row (list row (inc col)) (rest queens)))))))

 

お、この関数も末尾再帰になっています。recurフォームに変えて末尾再帰最適化しておきます。

 

(defn check-row [[row col :as pos] queens]

  (if (not (on-board? pos)) queens

      (let [newqueens (check-col pos queens)]

        (if newqueens

            (recur (list (inc row) 1) newqueens) ;; 末尾再帰最適化

            (let [[row col] (first queens)]

              (recur (list row (inc col)) (rest queens))))))) ;; 末尾再帰最適化

 

ちょっとテストしてみましょう。今回も盤面サイズは4x4(4-Queens問題)にしておきます。

 

user=> (def board-size 4)

user=> (check-row '(1 1) nil)

((1 1))

 

1行1列にクイーンを置くと解答を得られませんでした。1行2列ならどうでしょう。

 

user=> (check-row '(1 2) nil)

((4 3) (3 1) (2 4) (1 2))

 

4個置けたので、これが解答の一つとなります。ちなみに1行3列から開始するとどうなるでしょう。

 

user=> (check-row '(1 3) nil)

((4 2) (3 4) (2 1) (1 3))

 

これも4-Queens問題の解答ですね。最後の関数は今の手順を自動化する関数です。1行1列目、2列目・・・と順番にテストして結果を検査します。なおテスト結果の検査関数はpart2で最初に作っていましたね。ええ、忘れてますよね。再掲します。

 

(defn goal? [queens]

  (= board-size (count queens)))

 

それでは最後の関数名は、answerにしたいと思います。さっきの手動テストの通り、この関数もループが必要です。また今回も引数を変えながらanswerを再帰呼び出しすればいいのですが、answerは引数無しでいきたいな〜と。実はclojureの再帰呼び出しは、もっとforループっぽくできます。末尾再帰最適化では、スタックを消費しない単純なジャンプに変換できると言いました。語弊がありそうですが、単純なジャンプなので関数内の狙ったところに飛べます。実際のところ、このあたりはlisp方言の一つであるSchemeを紹介して継続、継続渡し形式(CPS)の話がしたくなるのですが、今回は省きたいと思います。ではclojureでのテクニック、loopフォームを紹介します。

 

(loop [束縛名1 初期化式1 束縛名2 初期化式2] (束縛名1,2を使った式... recurフォームでloopに戻る))

 

これも例を見てみましょう。なおREPLは途中で改行しても括弧が閉じるまでフォームを入力できます。

 

user=> (loop [i 0]                    ;; iを0に初期化

  #_=>   (if (= i 10) i                ;; iが10ならiを返しておしまい

  #_=>       (do (println "i ->" i)  ;; 途中経過のiを表示(doフォームは副作用を書ける)

  #_=>           (recur (inc i)))))  ;; iが10未満なら+1してloopにジャンプ

i -> 0

i -> 1

i -> 2

...

i -> 9

10

 

唐突にdoフォームを出してしまいました。詳しくは述べませんが副作用を書くためのフォームです。loopの各ステップでiが変わっていることをprintlnで表示させています。このloopのようなマクロ的構文拡張はlispならでは、clojureの利点なのでしょう。2重ループとかloopで書きたくない感じではありますが。というわけで、これを使ってanswerを書いてみます。

 

(defn answer []

  (loop [[row col :as startpos] '(1 1)]

    ...

 

loopの初期値を設定しています。startposとして(1 1)を束縛し、ついでに分配束縛もしています。ふ〜もう少しだ・・・

 

(defn answer []

  (loop [[row col :as startpos] '(1 1)]

    (let [queens (check-row startpos nil)]  ;; check-rowで(1 1)から調べ、結果をqueensに束縛します

         (if (goal? queens) queens              ;; 答えが得られた! のでqueensを返しておしまい

             (recur (list 1 (inc col)) nil)))))      ;; 駄目なら(1 2)のようにcolを増やしてloopへジャンプ

 

再帰の停止が不十分ですね。答えがずーっと見つからないとcolが増えて無限ループします。盤面を超えても答えが見つからない場合は停止させてnilを返しましょう。

 

(defn answer []

  (loop [[row col :as startpos] '(1 1)]

    (if (not (on-board? startpos)) nil    ;; startposが盤面になければnilでおしまい

        (let [queens (check-row startpos nil)]

          (if (goal? queens) queens         

              (recur (list 1 (inc col)) nil))))))

 

とりあえず4-Queensでテストしましょう。

user=> (answer)

((4 3) (3 1) (2 4) (1 2))

 

答えがでましたが、クイーンリストの順番を逆にした方がいいかな。loopフォームの結果をひっくり返します。リストを逆順にする関数は標準ライブラリにあります。(doc reverse)で見てみてください。

 

user=> (reverse '(1 2 3))

(3 2 1)

 

使い方を見たところで、まずanswer関数全体の大雑把な構造をおさらいします。

 

(defn answer []

  (loop [...] (... queensを返す))

 

となっているので

 

(defn answer []

  (reverse (loop [...] (...queensを返す)))

 

と書けば結果をひっくり返せますね。最終的なanswerは以下の通り。

 

(defn answer []

  (reverse 

    (loop [[row col :as startpos] '(1 1)]

      (if (not (on-board? startpos)) nil

          (let [queens (check-row startpos nil)]

               (if (goal? queens) queens

               (recur (list 1 (inc col)))))))))

 

user=> (answer)

((1 2) (2 4) (3 1) (4 3))

 

やはり逆順に並べ替えた方が見やすくなりますね。それではよーやく8-Queensの解答を見れそうです。試してみましょう。

カチャカチャ、ッターン!

 

user=> (def board-size 8)

user=> (answer)

((1 5) (2 1) (3 4) (4 6) (5 8) (6 2) (7 7) (8 3))

 

んーたぶん正解だと思います。このリストを引数にして盤面を表示する関数が欲しいところですが、今回はもうゴールしてもいいよね・・。なお、関数型言語では副作用を用いる箇所は少ない方がいいので、answerのような関数は結果を値で返す方がいいです。後でその値を表示するだけの関数を作ればよく、answerのようなロジックを書いている純粋関数と、副作用関数はなるべく分けた方がいいです。今回は手動で確認してみます。下の通りで、答えの一つを無事答えてくれたようです。（アスキーアートだと斜めが見づらいですが）

 

 

この問題はまだまだ発展できます。全解答を導きだし、その解答数を求めるのはなかなか面白そうです。それを並行処理で求めるとしたら。むむむ。

 

[おわりに]

clojureはいかがでしたでしょうか。haskellと似たところも違うところもありますが、関数型言語でプログラミングする過程には似たところがあったと思います。まあ前回の素数の問題も8-Queensも問題の性格が似ているからかもしれません。どちらも副作用は無く、再帰を中心としたアルゴリズム問題で、基本的なリスト操作関数しか使っていません。clojureについてはまた機会があれば触れたいと思います。残念ながら、clojureのパワーは全然引き出せていません。

ほんとは、『奇跡も、魔法もあるんだよ！！』

テーマとしては遅延シーケンスやカリー化を活用した効率的なアルゴリズム・関数設計、Javaとの連携、プロトコルやマルチメソッドでの抽象、clojureと言えばSTMなどの非同期/並行処理の安全な記述、そしてマクロの深淵へ・・・

 

今回のコード全体を載せて終わりにします。お付き合い頂き有り難うございました。

 

以上。

筆者：村田

 

こんにちは。

 

時事ネタということで、少し前にAppleの開発者向けイベントWWDC2014がありましたね。関連ニュースをチェックした程度ですが、ハード関連のトピックスは無かったようで。それでも興味津々のトピックスありましたね、新言語Swiftです。Objective-Cに置き換わる言語として、高速、スマートな記法、インタラクティブな開発環境、といいこと尽くめのようです。早くもSwiftでiOSアプリを作ったという人もいるし、解説記事も既にたくさんあって驚きました。ホヤホヤの最新言語ですね、iPhoneを持っている人はiBooksで言語マニュアルをDLできます。もちろんWebでも見れます。

 

残念ながらXcode開発環境(Beta)が無ければSwiftに触れないのですが、サンプルコードを眺めてあれこれ想像して楽しみ、味わうことができます。これはいいな〜と思う機能は色々ありましたが、個人的にはクロージャがずっと書きやすくなっている点がいいですね。ObjCのブロック構文はちょっと書きにくかったですし。

 

さてclojureに戻って前回の続きと参りましょう。

valid-queen?関数を作ってクイーンが置けるかどうかをテストできるようになりました。もう大分ゴールが見えてきている気がします。まず一つクイーンを置いて、問題なく置けるならば盤面上クイーンリストに加えておいて、その次のクイーンを置いてみて・・・と繰り返していけば解けそうです。

 

ちょっとここでクイーンを置く手順をイメージしながら関数をテストしてみましょう。複雑なアルゴリズムはいきなり書こうとしても難しいので、こうやって一歩一歩動きを確認することが役に立ったりします。そして関数型言語は引数でのテストがしやすく、またREPLはこのような実験にぴったりです。というものの１個だけ大域変数(定数)を使用していました。ボードのサイズですが、8では以降の手動テストが大変なので4に変更しておきましょう。

user=> (def board-size 4)

 

1. 一番左上(1 1)に最初のクイーンを置けるか? 

user=> (valid-queen? '(1 1) nil)

true

 

2. 盤面上のクイーン(第2引数に渡すリスト)に(1 1)を加え、次のクイーン(1 2)を置けるか?

user=> (valid-queen? '(1 2) '((1 1)))

false

 

気がついた方もいるでしょう。(1 1)にクイーンを置いたら同じ行である(1 2)〜(1 4)まではテストしても絶対falseになるため無駄ですね。これはアルゴリズムに取り入れましょう。ある行に対してクイーンが置けたらその行はもうテスト不要ですので、次の行に移ることにします。では続きを一歩一歩確認していきます。

 

2'. 2行目のどこに置けるかテストします

user=> (valid-queen? '(2 1) '((1 1)))

false

user=> (valid-queen? '(2 2) '((1 1)))

false

user=> (valid-queen? '(2 3) '((1 1)))

true

 

3. ２行目は(2 3)ですのでクイーンリストに加えて3行目をテストします

user=> (valid-queen? '(3 1) '((1 1) (2 3)))

false

user=> (valid-queen? '(3 2) '((1 1) (2 3)))

false

user=> (valid-queen? '(3 3) '((1 1) (2 3)))

false

user=> (valid-queen? '(3 4) '((1 1) (2 3)))

false

 

4. 3行目はどこにも置けませんでした。さてどうするか。アルゴリズムの重要なポイントです。一つ前の行である2行目は(2 3)までテストしましたが(2 4)にも置けるかもしれません。無事置けたら再度3行目戻ってきてテストしてみましょう。

 

(2 4)におけるか?

user=> (valid-queen? '(2 4) '((1 1)))

true

 

3行目をもう一度テストします。

user=> (valid-queen? '(3 1) '((1 1) (2 4)))

false

user=> (valid-queen? '(3 2) '((1 1) (2 4)))

true

 

よし、(3 2)に置くことができました。頭の中で以下のような盤面がイメージできますでしょうか。

 

 

このあたりでアルゴリズムの具体的な手順がイメージできたので、コードに落とし込んでいきたいと思います。それなりに複雑になりそうなので、ひとつの関数で作らず共通部分を見出して関数を分けて作りましょう。そうですね〜、「ある行に対してどこに置けますか？」という部分は先程の手動テストでも繰り返し行っていました。ここをパーツとして作るのが良さそうです。またもや繰り返しです、再帰ループです。それと関数の戻り値(関数値)ですが、ちょっと工夫したいと思います。どこに置けますか？でtrue/falseを返してもいいのですが、置けるならばクイーンリストに加えて新しいクイーンリストを返してあげましょう。置けないならば空のクイーンリストを返します。こうすれば呼び出し側で真偽値を判定してクイーンリストに加えるという作業をしなくても良いですね。

 

関数名は、えーっと行のチェックなんですが、よく考えると行を固定して、その行の列をずらしながらチェックしているんですよね。(1 1)、(1 2)、(1 3)という風に。ですからcheck-colとしたいと思います。(いい関数名浮かばないな・・)　次に引数ですが、必要な情報を全部渡すように考えましょう。

(defn check-col [pos queens] ())

 

クイーンが置けるならばクイーンリストに加えるという処理を書いてみます。

(defn check-col [pos queens]

  (if (valid-queen? pos queens)

      (cons pos queens)

      ....

 

consとはリストに要素を加える関数です。リストのおしりではなく先頭に加わっちゃいますが、今回のアルゴリズムはクイーンリスト内の順序は関係ないので問題ありません。ちょっと動きを確認しておきます。

user=> (cons 3 '(1 2))

(3 1 2)

 

それではクイーンが置けない場合はどうしましょう。一つ列をずらして再帰呼び出しすれば繰り返してチェックできますね。pos引数から現在の列を取り出したいので、(second pos)とやってもいいのですが、前回のコラムでやったテクニックである分配束縛を使いましょう。

 

(defn check-col [[row col :as pos] queens]

  (if (valid-queen? pos queens)

      (cons pos queens)

      (check-col (list row (inc col)) queens)))

 

いい感じです。inc関数は+1する関数です。(+ 1 col)と書いても同じです。list関数と合わせてちょいちょいっと確認しましょう。

user=> (list 1 (inc 1))

(1 2)

 

さて再帰ループのポイントは２つありましたね。引数が変わることと、引数の変化を見て再帰呼び出しを止める(停止する)ことです。if式の条件がtrueならば3行目で停止しますが、ずっとfalseになる場合を考えるとこの関数は停止しません。盤面をはみ出してもずっとcolを+1したままチェックし続けてしまうバグがイメージできますか？ということで、盤面のサイズを超えたら関数を停止し、その際は置ける場所が見つからなかったということなのでnil(空リスト)を返しましょう。盤面をはみでたかのチェックは関数にまとめたいと思います。

 

(defn on-board? [[row col]]

  (and (>= row 1) (<= row board-size) (>= col 1) (<= col board-size)))

 

and関数で行も列もチェックすることにしました。ちょっとテストを。

user=> (on-board? '(1 1))

true

user=> (on-board? '(1 9))

false

user=> (on-board? '(9 1))

false

 

良さそうですので、これをcheck-colに取り込みます。

 

(defn check-col [[row col :as pos] queens]

  (if (not (on-board? pos)) nil      ;; ボードに載っていなかったらnilね

      (if (valid-queen? pos queens)

          (cons pos queens)

          (check-col (list row (inc col)) queens))))

 

それでは、check-colもちょっとテストしましょう。先程の盤面3行目に置けるかどうかのテストがちょうどいいかな。まずは失敗するテストです。あと第一引数のposはループの起点ですのでテスト行の先頭(3 1)を与えます。

user=> (check-col '(3 1) '((1 1) (2 3)))

nil

 

次は成功するテストです。

user=> (check-col '(3 1) '((1 1) (2 4)))

((3 2) (1 1) (2 4))

 

うまく動いているようです。あ〜やはりというか今回でファイナルアンサーできなそうですので、ちょっと別の話題に移ります・・

 

C言語など他の言語を知っている方は、再帰ループを目にすると、確かに奇麗に書けるけどスタックメモリを消費するし、関数呼び出しコストで遅くなるよと思われるかもしれません。基本的に変数の再代入ができない言語では再帰でループを書くわけですが、これらの問題については末尾再帰最適化というテクニックが使われています。

 

末尾再帰とは何か？

例を見ながら考えましょう。とりあげる例はfact関数です。10!で階乗計算するやつです。まずは素直に書いてみましょう。なお3行目の*'関数は数値が大きくなったときBigIntegerに変換してくれる関数です。普通のかけ算*と使い方は同じです。(本ページでは＊記号が見えづらいかもしれないのでここだけフォントを変えます)

 

 

user=> (fact 10)

3628800

 

この関数は末尾再帰関数ではありません。上記関数の3行目を見てください。factの再帰呼び出し後、その戻り値とnを掛け合わせて、ようやく関数を抜けられます。つまりfact再帰呼び出し時に「nは捨てられず、スタックに取っておく」必要があります。したがって、末尾再帰関数でない場合は、スタックメモリを消費します。試しに大きい数で実行してみましょう。

 

user=> (fact 100000)

StackOverflowError

 

それでは末尾再帰関数に変えてみましょう。色々なやり方がありますが分かりやすいところで、計算結果を溜め込む蓄積変数を引数に持たせましょう。

 

 

このように書くとfactの再帰呼び出しが『関数の最後の処理』、言い換えれば『末尾』にあります。前の書き方の場合のnは「factの結果」とかけ算するため、捨てられませんでしたが、今度のnは蓄積変数とかけ算してその結果を引数に渡した後、捨ててしまってもいいですよね。このように再帰呼び出しを関数の末尾に置くと、コンパイラがスタックを消費する関数呼び出しの替わりに、for文のようなジャンプを主体とした高速なループに書き換えてくれます。これが末尾再帰最適化です。多くの関数型言語は末尾再帰最適化をサポートしています。HaskellもScalaもOcamlも、もちろんClojureも。

 

では上の関数を試してみましょう。まずは小さい数で。あとかけ算の蓄積変数であるacc引数にはかけ算のタネ(単位元)である1を渡します。

user=> (fact 10 1)

3628800

 

それでは大きい数を渡しましょう。

user=> (fact 100000 1)

StackOverflowError

 

ぐぬぬ〜! って種明かしするとclojureは末尾再帰で書いても、それだけでは最適化してくれません。最適化する場合は再帰呼び出しをrecurフォームに置き換える必要があります。うーん、理由など説明を省略しますが自動でやってくれないんです。ちなみにHaskell/Ocaml/Scalaは末尾再帰を自動的に検出し最適化します。というわけで早速置き換えてみましょう。

 

 

これから呼び出してみますが、PCが重くなったりするかもしれないので、大事なファイルがあったら保存しておいてください:P

 

user=> (fact 100000 1)

スタックオーバーフローは発生せず、しばらく待つと大量の計算結果がでますが、表示が終わらないのでブチッと中断してください。

 

ところで末尾再帰最適化は、高速でメモリ消費量も押さえられるわけですが、今回の例のように関数を書き換える必要があったり、その結果、素直じゃないコードになったりします。したがって、まずは素直に書きましょう、その関数が大量のデータを扱うループだったり、頻繁に呼び出されるため少しでも高速にしたいのであれば、その時に末尾再帰に書き換えるといいと思います。

 

最後に8クイーンに戻ってきましょう。check-col関数はよく見ると既に末尾再帰関数ですね。それならば最適化しておくのもいいでしょう。

 

(defn check-col [[row col :as pos] queens]

  (if (not (on-board? pos)) nil

      (if (valid-queen? pos queens)

          (cons pos queens)

          (recur (list row (inc col)) queens))))  ;; 末尾再帰最適化

 

今回はここまでにしたいと思います。

 

以上。

 

 筆者：村田

 

こんにちは。

 

6月ですね、6月1日と言えば衣替え・・・ネタも無いので早速前回の続きといきましょう。作った関数を再掲します。

 

(defn unique-row? [pos queens]

  (if (empty? queens) true

    (if (= (first pos) (first (first queens)))

      false

      (unique-row? pos (rest queens)))))

 

引数のposとはクイーン位置の行と列を2要素のリストにしたものでした。例えば2行3列目の位置は(2 3)と表現します。プログラム3行目で(first pos)と書いて行を取り出しています。これも悪くはないですけどrowという名前で参照できた方が見やすくなるはず。(frist pos)をrowとして参照するためにはいくつかの方法が考えられます。まずは関数にしてしまうことです。

 

(defn row [pos] (first pos)) ;; rowを取り出す関数

 

この関数をテストしてみます。

user=> (def pos '(2 3)) ;; テストの準備としてpos変数を設定

user=> (row pos) ;; posの行は?

2

 

他の方法として、let式を使って関数内で一時的に変数束縛する方法がありますが、これは他の機会に紹介したいと思います。今回おすすめのテク二ックは、引数posを渡してもらうときに一緒にその"中身"にも名前を付けてしまう方法です。関数の引数定義がちょっと変わります。簡単な関数で例を作ってみます。

 

(defn greet [[name age]]

  (str "Hello, " name))

 

上記の関数の引数は[[name age]]と２重で括られています。外側の[]は引数の並びを表現していますが、内側の[name age]は一つの引数を分解して最初の要素をnameに、次の要素をageに束縛します。関数greetを実行してみましょう。

 

=> (greet '(murata 17))

"Hello, murata"

 

(murata 17)という引数から名前を取り出すとき、引数に束縛した時点で分解しているため、greet関数でfirstを使う手間が省けました。あと上記関数では年齢をageに束縛してみたものの使っていません。使わない変数に関しては慣用的に_(アンダースコア)に束縛することが多いです。

 

(defn greet [[name _]] (str "Hello, " name))

 

この機能はclojureでは分配束縛と言います。単純な変数束縛ではなく、変数のデータ構造を解析して、要素毎に別の変数に束縛できます。今回の8-Queen問題では使わない予定ですが、clojureにはリスト以外にもベクタやマップといったコレクションデータ構造があり、これらのデータ構造でも分配束縛が可能です。さらに余談になりますが、clojureでは分配して束縛するだけですが、他の関数型言語ではより便利な機能としてパターンマッチと呼ばれる機能があります。分配束縛するだけでなく、データ構造(パターン)を解析して処理の分岐にも使えます。さて、この分配束縛を使ってunique-row?関数を修正してみます。

 

(defn unique-row? [[row col] queens] ;; 引数(pos)をrowとcolに分解束縛

  (if (empty? queens) true

    (if (= row (first (first queens)))

      false

      (unique-row? (list row col) (rest queens)))))

 

最初の引数posを[row col]に分配束縛したことで3行目のif条件式でrowという名前が使えるので少しだけ読みやすくなった気がします・・・しかし5行目の再帰呼び出しではpos変数の代わりにrowとcolからリストを再構築しています。これでは前の方がまだマシだった感じもしますので、もう少しテクニックを使います。

 

分配束縛すると同時に、元のデータ構造のままの変数も束縛することができます。:as節を使うのですが、実際に使ってみたコードを見た方がいいでしょう。

 

(defn unique-row? [[row _ :as pos] queens] ;; 引数をrowと_に分配束縛しつつposとしても参照できる

  (if (empty? queens) true

    (if (= row (first (first queens)))

      false

      (unique-row? pos (rest queens)))))

 

:as posと書くと、元の構造のままposとして参照できるので、5行目の再帰はリストを再構築する必要はなく、posとしてそのまま渡せます。

 

それでは次のリファクタリングに取りかかりましょう。この関数のループって、リストを走査して、各要素に対して条件をチェックするというものであり、これは典型的なリスト処理です。自分で再帰ループを書かなくても便利な関数があるはずです。というわけでclojureのWebサイトでAPIドキュメントを眺めてみたところ、良さそうな関数を見つけることができました。ついでにdoc関数(マクロ)についても紹介しましょう。doc関数は関数や変数の説明ドキュメントを表示してくれます。docを使ってdoc自身の説明を表示させてみましょう。

 

user=> (doc doc)

-------------------------

clojure.repl/doc

([name])

Macro

  Prints documentation for a var or special form given its name

 

ふーん。ではWebサイトで見つけてきた関数、every?関数について見てみましょう。

 

user=> (doc every?)

-------------------------

clojure.core/every?

([pred coll])

  Returns true if (pred x) is logical true for every x in coll, else

  false.

 

引数の説明を見ると[pred coll]とあります。predはpredicate関数のことで、真偽値を返す述語関数のことです。collはcollectionの略でリストやベクタなどを渡すことができます。説明文を見るとコレクションの各要素に述語関数を適用し全てがtrueかどうかを検査する関数のようです。REPLを使って実験してみましょう。あと、even?関数を突然使っていますが、引数が偶数ならばtrueを返す関数です。

 

user=> (every? even? '(2 4 6))

true

user=> (every? even? '(2 4 5))

false

 

さてunique-row関数でevery?関数を使うことが目的です。引数に渡す述語関数ですが、クイーンの行を調べる述語関数はさすがに標準APIにありませんので、自分で作らなければなりません。まずはevery関数に渡す関数の仕様をもう一度理解しましょう。コレクションの要素が一つずつ引数に渡されるので、それを見てtrue/falseを返す関数を作れということです。今回のコレクションとは盤面上のクイーンリストです。((1 1) (2 2))のようなリストのリストです。その要素、つまり(1 1)のようなクイーンの位置を引数にしてtrue/falseを返す関数を作るのです。試しに関数を書き始めてみると・・・

 

(defn check-row [pos] ...)

 

うーん、この関数は引数に盤面上のクイーンが渡されますが、これだけ渡されてもtrue/falseを返すことができません。元のif式を思い出すと検査したい行(row)がないと条件判定できません。ところがevery関数の仕様から引数を増やすことはできません。ちょっとわざとらしく遠回りしていますが、こんなときは無名関数(というかクロージャ)が役に立ちます。クロージャを使えば、レキシカルスコープという制限がありますが、引数以外にも外部の環境(変数row)を参照できます。無名関数の書き方は以下のとおり。

 

(fn [引数の並び] (本体フォーム))

 

普通の関数の書き方との違いを見ておいて下さい。

(defn 関数名 [引数の並び] (本体フォーム))

 

さっきの例のeven?関数を無名関数に置き換えて練習してみましょう。(クロージャの例にはなっていませんが)

 

user=> (every? (fn [n] (= (rem n 2) 0)) '(2 4 6))

true

 

rem関数を使って2で割った余りが0と等しいかどうかで真偽値を返しています。それではようやく素材がそろったのでunique-row関数を書き換えます。

 

(defn unique-row? [[row _] queens]

  (every? (fn [pos] (not= row (first pos))) queens))

 

一気に短くなりました。大きな違いは自分で再帰ループを書いていないことです。リストの走査というループ処理はevery?関数の中で行われており表に出てきていません。あと引数について、分配束縛を使っていますが、せっかく登場した:as節は結局使っていません:P　無名関数部分は独特の見辛さがありますが、ゆっくり眺めて下さい。"無名関数の引数"はposです。queensの各要素が渡されますので、例えば(1 1)が渡されます。その行(first pos)と、本体関数のrowを比較し、"全てが等しくない"ことをevery関数を使って検査しています。それと無名関数の内部から、外側の関数の引数rowを参照することができていますね。こういうことをやりたければ無名関数でクロージャを作るのが一番手っ取り早いです。

 

この時点で十分コンパクトになりましたが、無名関数はよく使うので、clojureにはもう少し短く書けるマクロが用意されています。マクロは他の関数型言語に無いclojure/Lispならではの機能なので、いつか取りあげたいのですが、今回は無名関数マクロをちょっと使うだけにします。無名関数マクロの書式は

 

#(本体フォーム)

 

です。ほぼ本体フォームだけです。おぉ短い。引数は本体フォーム中で%記号で参照できます。引数が複数ある場合は%1 %2 ... と番号をつけて参照できます。引数名を付けられなくなっちゃいましたが、肝心な本体フォームだけになるので慣れると見やすいです。では書き換えてみます。

 

(defn unique-row? [[row _] queens]

  (every? #(not= row (first %)) queens))

 

queensの要素は無名関数にきちんと渡されます。ただしposのような引数名の記述はなくなって、%記号で参照しています。以上でリファクタリング完了です。

 

再度ポイントを確認しましょう。コレクションを走査(ループ)して何らかの処理をするというのは典型処理なので、ループ部分を抽象化してくれる便利な関数が色々あります。例えば条件フィルタリング(filter)、関数適用(map)、畳み込み(reduce, fold)などは、どの関数型言語でもあると思うのでAPIマニュアルを探してみるといいと思います。これらの便利関数を使えば自分で再帰ループを書くよりもバグが出にくいですし、読む側も再帰ループを追うより、何がやりたいかをすぐに理解できます。

 

では、盤面上のクイーンリストの行をチェックできるようになったので、次は列のチェック関数を作ります。もう細かい説明は不要かと思います。

 

(defn unique-col? [[_ col] queens]

  (every? #(not= col (second %)) queens))

 

queensから取り出した各posのsecond(列)を見ています。次は斜めです。斜めは２方向あります。4x4マスの例で説明しましょう。

 

下斜め(down) 上斜め(up)

 

下斜めが同一線上に並ぶ条件とは行と列の差が等しい場合です。左側の盤面を見ると(1 1) (2 2) (3 3) (4 4)は同一線上で、その差は全て0です。上斜めが同一線上に並ぶ条件とは行と列の和が等しい場合です。右側の盤面を見ると(4 1) (3 2) (2 3) (1 4)は同一線上で、その和は全て5です。これをチェックする関数もそれほど難しくありません。

 

(defn unique-down? [[row col] queens]

  (every? #(not= (- row col) (- (first %) (second %))) queens))

 

(defn unique-up? [[row col] queens]

  (every? #(not= (+ row col) (+ (first %) (second %))) queens))

 

%が一杯でてくると目を反らしたくなりますね。queensから一つずつ要素が渡されるプレースホルダとして見て下さい。最後にこれらの関数を一つにまとめて、縦横斜めに被らずに置けるかを判定する関数を書いてみます。

 

(defn valid-queen? [pos queens]

  (and (unique-row? pos queens)

       (unique-col? pos queens)

       (unique-up? pos queens)

       (unique-down? pos queens)))

 

and関数は可変長引数を取り、全ての引数がtrueならtrueを返します。ちょっと試しましょう。

 

user=> (and true (=1 1) (even? 2))

true

 

それではvalid-queen?関数を少しテストしてみましょう。

 

user=> (valid-queen? '(1 1) '((2 3) (3 4)))

true

user=> (valid-queen? '(1 1) '((3 3) (3 4)))

false

 

テストが少ないですが良さそうです。今回は縦横斜めのチェック関数ができたので次回はこれを使って問題の解答までいけるといいな〜と思います。いけるかな・・

 

以上。

筆者：村田

 

こんにちは。

 

前回は８クイーンの盤面を定義したところで終わってしまいした。今回ものんびりペースですが、お付き合い下さい。

 

早速関数を考えて・・といきたいところですが、その前に盤面やクイーンの表現方法、つまりデータ構造を考える必要がありますね。クイーンは文字"Q"で表す？いや、チェスのように戦うわけではないですし識別用のシンボルは要らないかな。盤面上の位置だけ分かれば良いでしょう。そして盤面の方は８x８マスの２次元配列を用意して・・いやいや、こちらもクイーンのいる場所だけが分かればよく、クイーンがいない場所を確保しておく必要はありません。クイーンの位置は具体的には行(row)と列(column)で表せますのでclojureのリストを使うのが簡単そうです。例えば1行1列のマスにいるクイーンは(1 1)と表せます。

 

リストは括弧内に要素を並べるだけです。Haskellのリストとは異なり(1 5.0 "hoge")のように数値と文字列など任意のデータを並べられます。早速REPLで試してみましょう。

 

user=> (1 5.0 "hoge")

ClassCastException java.lang.Long cannot be cast to clojure.lang.IFn

 

くっ、エラーです。エラーは最初のうちはフォーマットも分かりませんし、たくさん出ると心が折れますが、分からないなりにも読もうとしなければ読めるようになりませんので、ぶつぶつ言わず目を左から右へ動かします。ClassCastException、ふーんキャストエラーですか・・javaのLong型がclojureのIFn型にキャストできぬと申しておられる。IFnとはなんだか分かりませんが、Longは数値ですよね、ってことでリストの先頭の1がIFnにキャストできなかった、と言っているようです。

 

前回少しお話したclojureの構成要素であるフォームと上記のリストはどちらも()で囲む形をしています。ここがややこしいのですが、フォームは先頭要素が関数として扱われ、２番目以降を引数として扱います。clojureは括弧で囲まれたものをフォームとして扱うので、上記の例では1を関数(IFn)として評価してしまったようです。したがってフォームなのか、それともデータとしてのリストなのか区別しなければなりません。データとしてのリストを表したい場合は()の前にシングルクォートをつけます。やってみましょ。

 

user=> '(1 5.0 "hoge")

(1 5.0 "hoge)