関数型とオブジェクト指向型プログラミング

近年、関数型言語というものが流行っている。関数型言語というのは、数学の関数を扱う感覚でプログラミングが行える言語だ。数学の関数は、インプットを与えると一意なアウトプットが得られるもののことである。

一般に、プログラムは数学の関数とは異なり、同じインプットに対しても内部の状態によって異なるアウトプットを返す。内部の状態とは、例えば、C言語の静的変数、オブジェクト指向言語のクラス変数、ディスク上のデータのことである。関数やメソッドが、内部の状態を変える場合には、その関数やメソッドは副作用を持つと言われる。プログラムはデータを保存したりしなければならないから、副作用はあって当然だ。今あるコンピュータは副作用があることを前提にできている。

しかし、副作用があるとプログラミングの難易度が上がる。インプットを網羅することは頑張ればできるが、状態を網羅することは難しい。テストですべての状態を作り出すことも大変だ。また、バグの発生条件が内部の状態にあれば、原因の特定も難しい。だれがその状態を作ったのかを見つけなければならないからだ。

そのため、なるべく副作用をなくしましょうというコンセプトで、関数型言語というのが最近注目されている。プログラミング言語は、書き方を制限してきれいな書き方に矯正しようというものだ。別に関数型言語を使わなくても、関数型プログラミングの目論見にあったコードはかけるが、関数型言語は関数型プログラミングがやりやすい。

最近の代表的なものは、Scalaだろう。Apache SparkがScalaで作られている。ただし、Scalaは純粋な関数型言語ではなく、オブジェクト指向型言語でもある。正直、関数型プログラミングだけではどういうふうに設計していいか分からない。人間の言葉はオブジェクト指向になっているので、人間の頭にはオブジェクト指向が馴染みやすく、設計も簡単だ。数学や論理学のように、記号を用いて表現した方が簡単な事柄には関数型がいい。なので、関数型とオブジェクト指向型をミックスするのは有用だと思う。

しかし、オブジェクト指向プログラミングは副作用を積極的にしましょうという技法とも言える。クラス変数にオブジェクトの状態変数を保存して、オブジェクトの状態を表現しようとしているのだから、当然だ。世の中のモノは、過去に受け取った入力を内部に保持して、それらを畳み込んだものを出力している。世の中のモノをコード上で表現しようとするオブジェクト指向は、副作用ありきだ。

そうすると、副作用が嫌いな関数型プログラミングと、副作用ありきのオブジェクト指向型プログラミングは食い合せが悪いようにも思える。

この問題を軽減する方法がないわけではない。思いつくのは以下のアイデアだ。要するにオブジェクト指向を関数型っぽく改変する。

1. クラス変数は定数として、コンストラクタに与えられた値のみ保存する
2. setterメソッドのようなオブジェクトの状態をの変えるメソッドは新しい値が入ったオブジェクトを返す
3. getterメソッドのような値を返すメソッドは副作用を認めない

副作用があるメソッドとないメソッドを明確に区別することが大事だと思う。

1, 2は処理系の中では副作用をしていても構わないが、外からは副作用がないように見せて、状態変化を射影とするべきという考えである。

Obj obj = new Obj(val0)
obj = obj.setVal(val1)

こんな感じの書き方を強制しましょうということです。setValの中でreturn new Objみたいなことをするのを規定する。

obj .= setVal(val1)
あるいは
obj..setVal(val1)

みたいに省略可能なら冗長にもならない。実際古いobjなんて使わないから、処理系としてはreturn thisとすればいいんじゃないかな。古いobjを使う場合だけ、インスタンスのコピーを作っておけばよいのだ。

3はgetter的なメソッドも、オブジェクトを値に射影する関数と見せようという考えだ。ログ出力や標準出力、エラー出力は普通プログラムの動作に影響しないから副作用とみなさなくていいと思う；でないとデバッグにならない。

オブジェクトの状態を変えつつ、値を返す処理がしたいときは

obj.setVal(val0).method()

と書いたらよい。

Scalaとかこうなっていればよいのに。こういう風に決まっているプログラミング言語はあるのだろうか？

C-Python間のたらい回し

前回「C, Java, Pythonでのたらい回し関数」にて，C, Java, Pythonの生産性と性能を比較した．Cは面倒だが速い；一方でPythonは楽だが遅いということがわかった．
そうならば，全てCで書くのはだるいから，性能に影響しないところはPythonで書いてやれとなるかもしれない．あるいは，既存のCで書かれたプログラムを拡張するのに，Pythonを使うという場面もあるだろう．Pythonには，Javaと同じようにCと行ったり来たりするためのインターフェイスが用意されている．
そこで，CとPythonの間でたらい回しが行われるような，たらい回し関数の計算を行ってみた．
下の式のようなイメージで，Tarai_CをC，Tarai_PyをPythonで計算する．

ソースコードは以下のとおり．tarai.cとtaraiC.cからtaraiCmodule.soという名前の共有ライブラリをつくると，PythonからはtaraiCモジュールとして見える．上のTarai_C(x,y,z)がtaraiC.taraiToPython(x,y,z)，Tarai_Py(x,y,z)がtarai.taraiToC(x,y,z)に相当する．

Tarai_C(12, 6, 0)とTarai_Py(12, 6, 0)の計算時間をグラフに示す（それぞれ項目C-Python, Python-C)．参考として，通常のたらい回し関数をCのみ，Pythonのみで実行した場合の時間も示す．

Tarai_C(12, 6, 0)とTarai_Py(12, 6, 0)の計算時間はほぼ同じであった．
Pythonのみより遅くなっているのは，Tarai_Cにて関数の呼び出し毎にモジュールのインポートを行っているからである．最初の１回のみ呼び出す方法もあるのだろうけど，ちょっと分からなかった．通常CとPythonを組み合わせるときにこんな使い方はしないだろうけど，非常に頻繁にPythonとCでやりとりをさせるのは，高速化という観点からはよくないようだ．
モジュールを独立させれるなら，プロセス間で通信した方がいいのだろうか？

C, Java, Pythonでのたらい回し関数

CとJavaとPythonを業務で使ってみて，同じことをさせるプログラムを書くのに労力が全然異なる．Cと比べたらJavaはすごく楽で，Javaと比べたらPythonは楽だ．コーディングに要する時間が大きく変わる．特に，C言語はエラーチャックから全て行わなければならないし，標準ライブラリも貧弱で使いにくい．処理速度の問題さえ解決できれば，CなんてOS専用言語でアプリケーションには使用するべきではないと思う．

と思ったものの，実際CとJavaとPythonの性能がどの程度違うのか良く知らない．そこで，同じ処理をするプログラムを３種類の言語で作って性能を比較した．

たらい回し関数を計算するプログラムを作った．たらい回し関数は，

と定義される．計算に時間がかかるだけの特に意味のない関数だ．

x, y, zの引数と試行回数を入力すると平均の計算時間を表示するプログラムを以下に示す．上から順にC, Java, Pythonである．エラー処理は最低のみで，異常があったら停止するようにしている．わざわざコードを貼るのは，ソースコードの分量の違いを示したいからである．なお，CはLinux環境用である．

C, Java, Pythonでそれぞれ行数は44, 24, 10行と開発規模が大きく異なる．実際作成にかかった時間もかなり異なる．

特に，Cのエラー処理は非常に面倒で，異常があったらとりあえず止まる，いわゆる「自働化」をさせるのにも工数を割かなければならない．今回はメモリを解放する必要がなかったが，メモリの管理を加えたらCのコードはさらに肥大化する．

Pythonが非常に簡潔なのは，timeitという実行時間測定のモジュールがあったことが大きい．また，Javaと比較して，いちいちクラスを作らなくてもいいということや，整数もクラスなので，Integerクラスのようなわかりにくいクラスがないことが規模を小さくしている．また，関数の引数や返り値の型を決めていないので，doubleでもそのまま使えるというメリットがある．逆に動かしてみないと動くかどうかわからないという問題はあるが，どうせテストするので大した欠点ではない．

Tarai(16, 8, 0)の10回の計算時間の平均値を比較すると，グラフのようになった．ちなみにJava, Pythonの環境はそれぞれOracle JDK7, Python 2.7である．

結果を見ると，Cが最も速く，Pythonが非常に遅い．JavaとCを比較すると４倍程度の差なので，CPUがボトルネックになる場合以外はJavaを使用するべきだ言える．Pythonに関してはやはり遅すぎるので速度が問題になるのであれば，避けるべきだろう．しかし，速度が問題になるのでなければ，開発効率だけでなく，教育や保守に要する費用を考えるとPythonは積極的に使用するべきだろう．

MapReduceとN体問題

天体や分子動力学（MD）といったN体問題は計算量が多い問題としてよく知られている．近年流行しているHadoopのMapReduceの計算モデルがN体問題にも適用できると気づいたので，記録しておく．

N体問題とは，複数の質点が各々相互に作用して運動する系について解く問題である．この問題がやっかいなのは，位置と運動量が与えられた１個の質点に関して，次の瞬間の位置と運動量を求めるためには，他のN-1個の質点の位置を知る必要があることだ．１個の質点に関してN-1個の質点との作用を計算しなければならないので，全体ではN*(N-1)回の計算を行う必要がある．計算量の多い問題は，複数のマシンで並列に計算をしたいが，１ステップの計算に全ての質点の情報が必要なので，マシン間の通信が問題となる．こういったプログラミングをするのは非常に面倒だ．

最近にわかに注目を集めているHadoopはMapReduceという計算モデルに落とし込める計算に関しては，簡単に並列分散処理を行うプログラムを作ることができる．MapReduceは演算をMapとShuffleとReduceの３段階に分ける．Map，ReduceフェイズにもちいるMap関数とReduce関数はユーザーが独自にプログラミングできる．

Map関数は，KeyとValueのデータの組から，異なるKeyとValueの組のリストを作成する．

Map(<K1, V1>) -> list <K2, V2>

Shuffleのフェイズで同じKeyをもつ組が集められ，<K2, list V2 >の形になる．

Reduce関数で，Valueが一つの値になる．

Reduce(<K2, list V2>) –> <K2, V3>

この一連のMapReduceの流れをN体問題に置き換える．iが質点の番号，xi, piが質点iの位置と運動量である．

Map関数で，質点iの位置を全てのj = 0…N-1に対して割り当てる．

Map(<i, xi>)　-> list <j, xi> (0<j<N-1, j != i)

そうするとShuffleで全ての質点の位置が集まるので，Reduce関数で質点jの次のステップでの位置と運動量を求めることができる．

Reduce(<j, list xi>, xj, pj) –> <j, x’j, p’j>

Reduce関数の入力値には，当然質点jの現在の位置と運動量が必要とされる．

MapReduceジョブ１回が１ステップの計算となる．現実的には，HadoopではMap, ReduceでそれぞれN回JVMを立ち上げることになるので（JVMの再利用を行うならプロセス数分），1ステップで2N回JVMを起動して落とす．また，MapReduceの度にHDFSに書き込みが行われる．インメモリで計算すべきだが，HDFSのキャッシュ機能がどう働くかは分からない．MapReduceジョブはオーバーヘッドが大きいから，現実的ではないと思う．

一様なライフゲームの統計的性質４：フラクタル解析

高エントロピーなライフゲームにフラクタル分析を適応してみる．

ビットマップを用いた高速計算

１セルに8ビット割り当てて，セルごとに次のステップの値を計算するのは時間が非常にかかるので，ビットマップを用いて，高速に計算できるコードを新たに作成した．また，4x4セルの取りうる全て場合について，次の値をキャッシュすることで，4セル毎に同時に計算している．マルチスレッド計算も行っている．

コードはGitHubにある

ボックスカウント法

対象は8192セルx8192セルで周期境界条件のフィールド．最もエントロピーの高いと思われる，確率0.364でtrueとなる一様にランダムな配置を初期値とする．

フラクタル解析にはボックスカウント法という方法を用いる．ライフゲームのtrue/falseの値と，一様なライフゲームの統計的性質３で定義した生存/死滅の値について調べる．

図１に，ボックスサイズとtrueセル（上のGIF動画で黒と赤のセル）を含むボックス数の関係を示す．16x16セル以上のボックスサイズでは，傾きは-2でありフラクタル次元は2となっている；のっぺりとしているということ．16x16セルがあれがライフゲームの特徴が現れているといえる．１６セル以下のでは傾きが一定となっておらずフラクタル性は見出せない．

図１　ボックスサイズと真セルを含むボックス数

図２に，ボックスサイズとaliveセル（下のGIF動画で赤とピンクのセル）を含むボックス数の関係を示す．この場合は１６セルに収まらない．ステップ数が大きくなるほど，フラクタル次元が2となるボックスサイズは大きくなる．ボックスサイズが小さい領域でも，傾きがほぼ一定となっておりフラクタル性を持っているといえる．グラフの読み取り方にもよるが，フラクタル次元はおよそ1.2である．

図２　ボックスサイズと生セルを含むボックス数

結論

生存／死滅でみると，ライフゲームもフラクタル性を持っている．

安定結婚問題を解くAndroidアプリ

2013年末にNHK教育の『オイコノミア』という経済学の番組で，合コンにてGale-Shapleyアルゴリズムを用いて最適なカップルを求めるということをしていた．是非，これを私もやってみたいと思ったので，簡単にできるAndroidアプリを作った．

ここからインストーラ： StableMatching.apkをダウンロードできる．

Android端末にて「サードパーティアプリケーションのインストールを許可する」と設定すれば，インストール可能．

2014-01-13 追記
せっかくつくったので$25払ってAndroidマーケットに出品しました

いわゆる安定結婚問題というもので，「実は今の彼女よりお前のほうが好きやってん」「え！？私も##」という悲劇がなくなる組み合わせを探してくれる．参加者全てに，好みを入力して貰って，Arrangeボタンを押すと，みんなが幸せになるカップルをつくる．

用途は合コンに限る必要はないが，合コン以外の用途は思いつかない．しかし，こんなアプリをおもむろに取り出したら，引かれないかというおそれはある．また，こういうのに興味してしてくれる素敵過ぎる人は，そもそも合コンなんかに来ないという問題もある．

ただ，安定結婚問題なんてものは，全員が好みの順位をつけることができて，かつ，それを教えてくれる（一応人の好みは見れないようになっているが）という特殊な状況を想定している．しかし，そういう状態になった段階，すでに問題の９割は解決している．それぞれの嗜好がわからないから人間関係はやっかいなものだと思う．まあ，数学者の考えそうな現実を無視した理想的な問題ということか．嗜好を推論してくれる機能とかがあれば，画期的な発明になるのだろうけど，まだアイデアはない．

タイムトラベルの分類 改定版

先日，タイムトラベルの分類についての記事で，歴史改変がなくて；かつ同一人物が同時代にいないタイプのタイムトラベルはないとした．しかし，『タイム・リープ　あしたはきのう』（電撃文庫　上下巻）が，まさにそのタイプであったので改定することにする．

---

タイムトラベルはSFでは一般的な仕掛けである．SF上のタイムトラベルにはいくつかの種類が存在する．そこで，SF物語上のタイムトラベルを分類していこう．

よくみられるように，２つの軸に分けて，４象限のマトリクスで分類していく．１つ目の軸は，歴史改変がある／ないの分類；２つ目の軸は同時代に同一人物がいる／いないの分類．

歴史改変がある／ないとは，時系列もしくは因果関係の系列が一本なのか；それともタイムトラベルによってそれらが変化するかどうかということである．設定で歴史改変が認めれていたとしても，物語の上で歴史改変がなされないものは，歴史改変がないに含める．

同時代に同一人物がいるこる／いないとは，昨日に飛んだときに，昨日の自分がそこにいるタイプなのか；いないタイプなのかという分類だ．意識のみが時間を越えるのか；もしくは，身体も含めて時間を越えるのかは問わない．この分類は『傾物語』で少し言及されていた．『傾物語』は最後まで見ていないので，まだ分類できない．

以下の表に具体的な作品を分類する．便宜上それぞれに[A],[B],[C],[D]とラベルをつける．

	歴史改変がある	歴史改変がない
同一人物が同時代にいる	[A] バック・トゥ・ザ・フューチャー ルーパー	[B] 夏への扉 涼宮ハルヒの憂鬱 ドラえもん(？)
同一人物が同時代にいない	[C] 時をかける少女 シュタインズゲート 魔法少女まどか☆マギカ	[D] タイム・リープ　あしたはきのう

[A]が映画ではもっとも一般的だ．タイムトラベルによる混乱が生じて，物語的に面白くなりやすい．

しかし，どうしても歴史改変による矛盾：タイムパラドックスが生じてしまう．タイムトラベルなんで存在しないのだから仕方がない．それを強引にどう解決するかもタイムトラベルものの面白さのひとつだ．有名なタイムパラドックスに親殺しのパラドックスというのがある．過去に戻って自分が生まれる以前に親を殺したら自分が存在できないというやつだ．これを表現するにはどうすればよいのか．

映画でよくあるのが，歴史的な時系列を無視して，物語の中での時系列で因果関係を表現するというものだ；『バック・トゥ・ザ・フューチャー』では，自分の存在が危うくなると，体が透けてくる；また，『ルーパー』では，現在の自分の体に傷をつけると，未来の自分にその傷あとが現れる．親を殺せば，存在自体が最初からなくなってしまうのだから，自分が過去に行くというイベントが成立しえないはずだ．しかし，この表現では過去にいくというイベントは存在するけど，親殺しの影響は受けるとするのである．過去での歴史改変の影響は，時間を越えて現れるのである．

[B]は，時間軸が完全に一本でタイムトラベルの結果が，タイムトラベルするまえに既に反映されている．登場人物が過去に行って，いくら頑張ってもすでに未来は決定していて変えようがない既定事項なのだ．親を殺ろそうといくら努力して，成功しない．パラドックスが生じないのが利点である．しかし，結果が分かっているので終着点の意外さは損なわれてしまう．また，結果が決まっているのに登場人物はなんで頑張っているのだろうと思ってしまう点もある．一方で，伏線を貼りやすいという利点もある．未来の情報を頼りにして，すでに分かっている結果に帰着するように工作する．結果でなくてプロセス重視のタイプである．

『ドラえもん』を（？）をつけてここに入れたのは，設定が一貫していないからだ．[A]にも思えるが，タイムパトロールが頑張っているので，結果として[B]となっているのだろうか？ドラえもんがやっていくる未来は一定だ．昔話題になった同人作品のドラえもん最終話は[B]に分類される．

[C]は『時をかける少女』に代表されるタイプだ．過去の自分に戻ることができる．このタイプも，意識が過去の自分に飛ぶだけならタイムパラドックスが生じない．なぜなら，歴史が改変されて，時間軸が分岐することはあっても，[A]のように時間軸がループすることはないからだ．タイムパラドックスは，本来一方向であるはずの因果関係が，過去と未来がくっつくことで輪になってしまうために生じるのだ．また，自分の生前にタイムリープしたらどうなるのだという問題は残る．生前にタイムリープしたら，タイムパラドックスが生じてしまう．間宮千昭もしくは深町一夫はどうやって未来に帰るのだろうか？

『魔法少女まどか☆マギカ』の暁美ほむらの能力も[C]に分類される．世界の時間軸を分岐させるという相当すごい能力である．（2013/11/3）

[D]は一般には成立しない．過去の自分にタイムリープしただけで，必然的に歴史が改変されるからだ．『ドラえもん』の『人生やりなおし機』は[D]に近い．今の頭で過去に戻っても，結局同じことになるというオチ．『ドラえもん』はいろんなパターンを含んでいる興味深い作品だ．

『タイム・リープ　あしたはきのう』は，同じ時間を繰り返さないという制約を付け加えることで，[D]を実現している．[D]は成立しないと思っていたが，この作品で[D]のタイプが成立することが証明された．作中で[A][B][C]それぞれのタイプの作品について言及されていたので，この作品はあえて[D]の位置を狙っていると思われる．『タイム・リープ』はタイムトラベルものの中でも，特異な位置にある重要な作品である．