多次元メモリ空間プログラミング

新年会で酒を飲み過ぎて頭が痛くて眠れないので、新年の挨拶代わりにプログラミングの話でも適当に書き散らしておく。

以前、私の知り合いのラノベ作家である土屋つかささんが、「プログラミングのソースコードって本当に１次元(plain text)でいいんですかね？」みたいなことを言っていた。

例えば、フローチャートは普通、二次元上に表現する。条件分岐(菱形の図形)が何箇所もあるようなフローチャートを描く場合、本来のソースコードよりも流れが見やすいということは多々ある。それは何故だろうか？

「条件が成立したらソースコードのXXX行目に移動する」というような１次元的な移動より、「条件が成立したら下に移動、成立しなかったら右に移動する」というような２次元的な移動のほうが可視化する上ではわかりやすいというのがあるのではないかと私は思う。

こう考えると、ソースコードは最終的に直列化(１次元化)するにせよ、頭のなかではそのように直列化されているわけではなく、マインドマップのように２次元、もしくはＮ次元で構成されていて、それを１次元のソースコードとして書きだすことになる。

これが、プログラミングを難しく、そして複雑にしている要因の一つではないだろうか。

例えば、頭のなかに複数のアイデアがあるとする。そのアイデアは相互に関連づけられているとする。それを話し言葉として話そうと思ったときに、順を追って一つずつ書きだす必要がある。箇条書きにする、なんていう行為もこのシリアル化に相当する。

この思考のシリアル化は、子供のころから国語教育のなかで培われているはずではあるが、苦手な人は苦手だし、そもそも、頭のなかでどう考えるべきかという部分については我々はこれと言った教育は施されておらず、他の人の出力(シリアル化された模範解答)から、自分の頭のなかの思考回路をフィードバック学習のようなことをして学んできたに過ぎない。(ゆえにその部分には個人差がかなりある。)

なんにせよ、なるべく頭のなかで考えている図に近い形でソースコードを書き出せたほうがいいというところまで話を進め、次にこれをバイナリレベルで考える。

そういや、私は年末に「Binary Hacks ―ハッカー秘伝のテクニック100選」(asin:4873112885)の著者の一人である浜地 慎一郎さん(id:shinichiro_h)にたまたまお会いした。

そのときに私は「FPGAでCPU作ったりするの、コードゴルフ的な側面があって面白いっすよ。」みたいなことを彼に言った。DE0-nanoという8000円ぐらいで買えるFPGAの評価ボードでも相当な規模のCPUが作れるのだと。

このように自分で考えたアーキテクチャのCPUが簡単に自作できる時代になったいまこそ、１次元メモリ空間的なプログラミングに拘泥する必要はないのではなかろうか。

そこで、もう少し具体的な話をしていく。

まず、２次元メモリ空間でのプログラミングを考える。２次元メモリ空間上にどのようにプログラムを書きだすかという問題があるが、まずはお手軽にExcelでいいと思う。Excelは二次元的なメモリ空間を表現したり、編集したりするのにもってこいである。

私は以前、VBAを用いて、Excelのワークシート上に書かれたプログラムを実行するインタプリタを作成した。

第２９回　Ｅｘｃｅｌ　Ｉｎｔｅｒｐｒｅｔｅｒ（ＥｘｃｅｌによるＥｘｃｅｌのための変態的プログラム）
http://bm98.yaneu.com/rsp/rsp29to2F.html

もう13年前も経っていることに驚きを隠せないが(開発していたのはそのさらに3年ぐらい前なので15年以上経っているのか…)、当時、私が上記のようなメタプログラミング環境(DSL?)が必要だったのは、私はそのころ、仕事で製図設計に携わっており、定型的な業務に飽き飽きしていたので図面の自動生成をしようと思ったのだが、AutoCADのマクロのようなもので書いてしまうと他の社員が見たときにちんぷんかんぷんになるので、Excel上で処理させようと思ったのがそのきっかけである。

これならExcelのワークシート関数を理解している程度の非プログラマであっても、プログラムを追いかけたり、プログラムが定数として使用している値(セル)に計算式を書くことによって、自分なりにカスタマイズしたりすることが出来る。

ところで、バイナリアンにとっては時としてソースコードもバイナリコードもほとんど等価である。
バイナリコードこそがソースコードという場合も少なくはない。

Excelのワークシートを２次元メモリとみなして、そこにプログラムを書いていくと考えたときに、そこに書くコードは、バイナリ(2進数的な)コードであるのか、アセンブリ命令であるのか、それとももう少し粒度の大きな命令セットからなるソースコードであるのか。それは、命令セットの違いという程度の意味しかないので、ここではアセンブリ命令に限定して話を進める。

命令を解釈して実行する部分は上記のExcel Interpreterのようなコードを書けばいいだけなので30行程度のVBAのコードで容易に実装できるだろう。なので、この部分は問題としない。いま問題とするのは、条件分岐に関してである。

条件分岐は従来のプログラミング言語では制御構文(if,while,forなど)が必要であった。バイナリレベルで捉えるとこれらは条件ジャンプである。例えば、２数を比較をしたときに、その値が等しいとEqualフラグが1になる。「Equalフラグが1のときだけジャンプしなさい」という命令(例えばjumpzero、略してjz命令)が用意されていて、それによって条件ジャンプが実現できる。

このjz命令ではジャンプでの飛び先を書かなければならない。それは相対アドレスか絶対アドレスか、いずれにせよ、飛び先の番地を書かなければならない。

バイナリアン(バイナリ好き)でもこの番地を計算するのは少々面倒くさい。ハンドアセンブルする場合、CISCアーキテクチャだとそれぞれの命令のサイズが異なるので、それぞれの命令をサイズを足していき、飛びたい先の番地を求める必要がある。

これが面倒なので、バイナリアンと言えども長いコードを書かなければならない場合、簡易アセンブラを自作するのが普通で、この簡易アセンブラでは普通ラベルジャンプをサポートする。そうすると、

LOOP_START:
なにか命令
jz LOOP_START

のような書き方が出来るというわけだ。

つまり、バイナリアンにとって、このような条件ジャンプ時のアドレス計算こそが癌であって、これさえなければハンドアセンブル上等！なのである。(バイナリアンの総意ではなく、あくまで私個人の見解です)

そこで、今回の２次元メモリプログラミングモデルでは、jz命令のあとは、ラベルやアドレスではなく何も書かないことにする。すなわち、条件が成立したときは右のメモリに移動する(非成立であれば下のメモリに移動する)というようにする。

こういうメモリモデルというのは、実用上も価値がある場合がある。

例えばFPGAでこのようなメモリモデルのCPUを実装するとしよう。NUMAアーキテクチャ( http://ja.wikipedia.org/wiki/NUMA )を採用していて、それぞれのCPUコアはなるべく小さく保ちたいとする。

そこに書くプログラムは非常に小さなコードなのでコードサイズはそれほど問題とはならず(どうせCPUコアからアクセスするコードメモリはFPGA内のブロックRAMで実装されるのでブロックRAMを一つに収まればそれで良い)、条件ジャンプのときに飛び先の番地を計算するためにフルサイズの加算器(メモリ空間が12bitならば12bitの加算器)を用意するのがもったいないとする。

そこで、条件成立時は現在のアドレスに0x100(256)を加算したアドレス(二次元メモリだとみなしたときの“右”がこれだとしよう)にジャンプするような条件ジャンプ命令を実装したとする。これなら、フルサイズの加算器よりはいくぶん規模を小さくできるし、条件ジャンプ命令がジャンプ先のアドレスを含まなくて済むので、データバスのビット数とアドレス空間のビット数を合わせる必要がなくなるというようなメリットもあるかも知れない。

まあともかく、二次元メモリモデルというのは、空想の産物ではなく、案外実用になるのではないかというところまで話が進んだので、次に、これをＮ次元に拡張していく。

まずさきほどまでの話だとプログラムは基本的に下方向に向かって命令が実行されていく。条件ジャンプがあると、条件が成立したときにのみ右側に１つ移動するだけであった。

しかし、これだとループが書けない。メモリ空間自体がどこかでメビウスの輪のように終端と開始アドレスが繋がっているのならば別だが、その仮定は制約が強すぎる。(たとえば0x1FFのつぎの番地が0x100に戻るような実装は可能かも知れない。条件ジャンプの条件成立時には実行アドレスを指すレジスタに0x100が加算されるとして)

そこで、プログラムの実行方向を下ではなく、現在の亀の向いている方角だとしよう。なぜここでいきなり“亀”が何故出てくるかというと、その昔(1970年代に)、LOGO言語というタートルグラフィックス環境が流行った。(仮想的な)亀にペンを持たせて、その亀に対して次のような命令を指令する。

REPEAT 4 [FD 100 LEFT 90]
※ 100歩歩いて(直進して)90度左回転という動作を4回繰り返せ の意味。これにより正方形が描かれる。

このタートルグラフィックスの考え方を、この２次元メモリプログラミングに応用し、現在の亀が向いている方向に命令を実行していくとするわけだ。

つまり条件分岐であれは、条件成立時には左90度回転。(非成立時には直進)

無条件左90度回転命令(無条件ジャンプに相当する)も欲しいところではあるが、それはしかし、わざと成立するような条件比較を行ない、そのあと条件ジャンプ命令を書けばかならず条件が成立し、左90度回転するという動作になるので、命令セットを最小化するという観点からは不要だとも言える。

まあともかく、このようなプログラミングモデルであれば、ループを実現したければ、無条件ジャンプを4回行えば、もとの位置に戻ってくることも出来るであろうことがわかった。

次に、このプログラム同士を戦わせることを考える。

プログラム同士を戦わせるというのは、一例として挙げるならCore Warsという1985年ごろに流行った、小さな命令セットを持つ仮想CPU同士をサンドボックス環境で走らせ、相手にhalt(実行停止命令)を実行させれば勝ちというバトルゲームである。

※ 画像引用元 : http://www.gamesetwatch.com/2009/03/column_pixel_journeys_corewar_the.php

私は高校1年のときにこのCore Warsのtiny版がOh!MZ誌(のちのOh!X誌)に掲載されていたので、これでずいぶん遊んだ覚えがある。

私は当時、「ダロス」というアニメ(スタジオぴえろが制作、世界初のOVAと言われている)を観て、そのアニメに出てくる「自己修復機能」を持った要塞都市という中二病的な設定がいたく気に入り、Core Warsでそのような自己修復機能を持ったプログラムを書けないかとやってみた。

つまり、自分のプログラムのcheck sum的なものを調べ、コードが破損していたら、それを元のコードに戻すというわけである。戻すためには元のコードが必要なので自分自身のプログラムを+0x100番地離れたところにコピーしておく。そのコピーしたほうも壊れるといけないので、そのプログラムもさらに+0x100番地離れたところにコピーしておく。(以下、繰り返し)

このCore Warsは仮想的なマルチスレッドモデルを採用しており、forkに相当する命令があったので、それぞれのスレッドがそれぞれ自己修復(破損していれば+0x100番地先からコピーして復元)、また、増殖(+0x100番地に自分のコピーがいなければ、自己をコピーしてfork。より正確に言えば、+0x100番地のプログラムのheartbeat(自分が生きていることを示すためにメモリに書き込む値)が確認されなければそこの担当スレッドが死んでいることを意味するので復元してfork)みたいなプログラムを書いた。

いまにして思えば、それは自己修復型のワームなのだが、当時私はそういう用語すら知らなかった。

さて、このようなそこそこ複雑なプログラム(とは言っても30命令程度ではあったが)を書いて満足していたのだが、他の人が作ったプログラムと対戦させてみると、このプログラムがなかなか勝てないプログラムがあった。

それは一寸法師と呼ばれるたった5命令から成るプログラムである。その5命令のうちのひとつは5命令目に書かれたhaltであり、ここはそのプログラムは実際には実行せず、この5命令目に書かれた命令をその5番地先にコピーするというだけのプログラムである。要するに5番地ごとにhaltを書きこんでいくプログラムで、そのプログラム自体のコアは4命令から成るので自分自身には被害は及ぼさないというプログラムであった。

これが単純ではあるが、そのような、フットプリント(≒コア部分のメモリ使用量)が小さなプログラムはいたく強烈で、ある意味チートであり、ある意味、Core Warsのゲームバランスを損ねる元凶でもあった。

そのあと長年、このゲームバランスをなんとか改善し、そして、視覚的に現在実行している命令がわかりやすいCore Warsを作れないかと私は考えていたわけではあるが、ここに至って、今回の２次元メモリプログラミングモデルがすこぶる有効なのではないかと気づいたわけである。

つまり、アドレスジャンプではないので、急にあっちからこっち、というようなジャンプをしないので視覚化したときに非常にわかりやすい。チクタクバンバンのように必ず隣のメモリにしか移動しないからである。

また、ループを構成するために、ダミー比較(Equalフラグを立てるためのもの)と条件ジャンプ(jz命令)の2命令を4回使わないとループにならないので少なくとも8命令は必要であり、一寸法師的なプログラムであっても12命令では書けないような命令セットであれば、16命令か20命令程度使わざるを得なくなってくる。

そうするとフットプリントを小さくしておいて絨毯爆撃するというようなプログラムが書きにくくなるので、もっと高度で高機能なプログラムのほうが勝率が上がるのではないかと思う。そうなったほうがCore Warsとしては面白い。

これは大変いいアイデアなので、Core Warsの試合用のサーバーを用意して、比較的大きなメモリ空間で複数のプログラムを放って、その生存率(24時間に何回死んだかをカウントし、その平均生存時間から算出する)を競わせるような競技場を気が向いたら作ることにする。(注:いま酔っ払っているので、酔が覚めたら忘れているかも知れません。)

さて、以上で、２次元メモリプログラミングモデルというのは、実用上も、そして、Core Warsのような試合用のアーキテクチャとしても非常に興味深いことがわかった。次に、これをＮ次元に拡張していく。

Ｎ次元なので現在の命令の番地はベクトルρで表されるとしよう。向いている方向はベクトルνだ。νは単位ベクトルとしよう。

このとき次に実行する命令の番地はρ＋νである。条件ジャンプ命令で条件が成立時には左90度回転をするのであるが、Ｎ次元空間での回転だと回転軸が必要で、それを固定してしまうとうまくメモリ全体を巡れない。

２次元での左90度回転だとベクトルνは (0,1)下方向 → (1,0)右方向 → (0,-1)上方向 → (-1,0)左方向のように推移するので、同様にＮ次元でも(たとえば３次元ならば)(1,0,0)→(0,1,0)→(0,0,1)→(-1,0,0)→(0,-1,0)→(0,0,-1)→(1,0,0)のように推移すれば、メモリ全体を巡ってもとの場所に戻ってこれるのではないかという。

この変換行列をΤとすると、新しいν＝Τνみたいな計算でどうか。

例えば3次元時なら
Τ= [ [ 0 , 0 , -1],[ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ]
みたいな直交行列かつ、テプリッツ行列(対角一定行列)でどうかいな。

とりあえず、以上の方法でＮ次元メモリプログラミングも出来そうではある。
(ExcelのワークシートがＮ次元に対応したようなソフトウェアがないとプログラムを書くのは困難かも知れないが)

行列Τのバリエーションを変えれば、もう少し面白い実行が出来るかも知れないが、話が収拾がつかなくなるので今回は割愛する。

ここまでは命令の実行を、
・基本的に直進
・条件分岐では条件成立時にν＝Τν、非成立時は直進
としてきた。

ところが、ここで「条件分岐では条件成立時に直進」となるようなプログラミングモデルだとどうだろうか。

・基本的にはうねうね
・条件分岐では条件成立時に直進、非成立時はそのままうねうね

こうなるわけである。この“うねうね”として、全メモリを被覆するようなうねうねした直線を持ってくればいい。

たとえば、ヒルベルト曲線にする。ヒルベルト曲線は空間充填曲線である。

２次元だと次図のようになる。

※画像引用元 : http://d.hatena.ne.jp/ototoi/20090315/p1

３次元だと次図のようになる。

※画像引用元 : http://blog.atake-i.com/?eid=1060863

ヒルベルト曲線はＮ次元空間でも充填できるので、これを採用し、
・基本的にはヒルベルト曲線上の番地を実行していく
・条件分岐では条件成立時に直進、非成立時はそのままヒルベルト曲線上を辿る
のようなプログラミングモデルを考えることが出来る。

この場合、さきほどまでの90度回転や行列Τで向きを変えるのとは違って、少しパズルじみた要素が出てくるし、条件分岐がなければ基本的にすべてのメモリを使い切る(空間充填曲線なので)のでメモリ効率はいいかも知れない。

さて、このような実行モデルをプログラムの難読化に利用することを考える―――という話を書いていこうと思ったところで眠くなってきたのでこのへんでお休みなさい。

以上、酔っ払いの戯言を新年の挨拶に代えまして。

■ 追記 2013/09/09

KickstarterのプロジェクトのRobot Turtlesが、本記事で書いた二次元プログラミングっぽいゲーム仕様になっているのでご紹介。

Robot Turtles: The Board Game for Little Programmers
http://www.kickstarter.com/projects/danshapiro/robot-turtles-the-board-game-for-little-programmer