うらおブログ(移転しました)スマートフォン用の表示で見るやねうらおブログ(移転しました)この広告は、90日以上更新していないブログに表示しています。2013-01-02多次元メモリ空間プログラミングprogram新年会で酒を飲み過ぎて頭が痛くて眠れないので、新年の挨拶代わりにプログラミングの話でも適当に書き散らしておく。text)でいいんですかね?」みたいなことを言っていた。フローチャートは普通、二次元上に表現する。条件分岐(菱形の図形)が何箇所もあるようなフローチャートを描く場合、本来のソースコードよりも流れが見やすいということは多々ある。それは何故だろうか?「条件が成立したらソースコードのXXX行目に移動する」というような1次元的な移動より、「条件が成立したら下に移動、成立しなかったら右に移動する」というような2次元的な移動のほうが可視化する上ではわかりやすいというのがあるのではないかと私は思う。考えると、ソースコードは最終的に直列化(1次元化)するにせよ、頭のなかではそのように直列化されているわけではなく、マインドマップのように2次元、もしくはN次元で構成されていて、それを1次元のソースコードとして書きだすことになる。これが、プログラミングを難しく、そして複雑にしている要因の一つではないだろうか。頭のなかに複数のアイデアがあるとする。そのアイデアは相互に関連づけられているとする。それを話し言葉として話そうと思ったときに、順を追って一つずつ書きだす必要がある。箇条書きにする、なんていう行為もこのシリアル化に相当する。この思考のシリアル化は、子供のころから国語教育のなかで培われているはずではあるが、苦手な人は苦手だし、そもそも、頭のなかでどう考えるべきかという部分については我々はこれと言った教育は施されておらず、他の人の出力(シリアル化された模範解答)から、自分の頭のなかの思考回路をフィードバック学習のようなことをして学んできたに過ぎない。(ゆえにその部分には個人差がかなりある。)なんにせよ、なるべく頭のなかで考えている図に近い形でソースコードを書き出せたほうがいいというところまで話を進め、次にこれをバイナリレベルで考える。慎一郎さん(id:shinichiro_h)にたまたまお会いした。そのときに私は「FPGAでCPU作ったりするの、コードゴルフ的な側面があって面白いっすよ。」みたいなことを彼に言った。DE0-nanoという8000円ぐらいで買えるFPGAの評価ボードでも相当な規模のCPUが作れるのだと。このように自分で考えたアーキテクチャのCPUが簡単に自作できる時代になったいまこそ、1次元メモリ空間的なプログラミングに拘泥する必要はないのではなかろうか。そこで、もう少し具体的な話をしていく。2次元メモリ空間でのプログラミングを考える。2次元メモリ空間上にどのようにプログラムを書きだすかという問題があるが、まずはお手軽にExcelでいいと思う。Excelは二次元的なメモリ空間を表現したり、編集したりするのにもってこいである。私は以前、VBAを用いて、Excelのワークシート上に書かれたプログラムを実行するインタプリタを作成した。Interpreter(ExcelによるExcelのための変態的プログラム)http://bm98.yaneu.com/rsp/rsp29to2F.htmlもう13年前も経っていることに驚きを隠せないが(開発していたのはそのさらに3年ぐらい前なので15年以上経っているのか...)、当時、私が上記のようなメタプログラミング環境(DSL?)が必要だったのは、私はそのころ、仕事で製図設計に携わっており、定型的な業務に飽き飽きしていたので図面の自動生成をしようと思ったのだが、AutoCADのマクロのようなもので書いてしまうと他の社員が見たときにちんぷんかんぷんになるので、Excel上で処理させようと思ったのがそのきっかけである。これならExcelのワークシート関数を理解している程度の非プログラマであっても、プログラムを追いかけたり、プログラムが定数として使用している値(セル)に計算式を書くことによって、自分なりにカスタマイズしたりすることが出来る。ところで、バイナリアンにとっては時としてソースコードもバイナリコードもほとんど等価である。バイナリコードこそがソースコードという場合も少なくはない。Excelのワークシートを2次元メモリとみなして、そこにプログラムを書いていくと考えたときに、そこに書くコードは、バイナリ(2進数的な)コードであるのか、アセンブリ命令であるのか、それとももう少し粒度の大きな命令セットからなるソースコードであるのか。それは、命令セットの違いという程度の意味しかないので、ここではアセンブリ命令に限定して話を進める。Interpreterのようなコードを書けばいいだけなので30行程度のVBAのコードで容易に実装できるだろう。この部分は問題としない。いま問題とするのは、条件分岐に関してである。条件分岐は従来のプログラミング言語では制御構文(if,while,forなど)が必要であった。バイナリレベルで捉えるとこれらは条件ジャンプである。2数を比較をしたときに、その値が等しいとEqualフラグが1になる。「Equalフラグが1のときだけジャンプしなさい」という命令(例えばjumpzero、略してjz命令)が用意されていて、それによって条件ジャンプが実現できる。このjz命令ではジャンプでの飛び先を書かなければならない。それは相対アドレスか絶対アドレスか、いずれにせよ、飛び先の番地を書かなければならない。バイナリアン(バイナリ好き)でもこの番地を計算するのは少々面倒くさい。ハンドアセンブルする場合、CISCアーキテクチャだとそれぞれの命令のサイズが異なるので、それぞれの命令をサイズを足していき、飛びたい先の番地を求める必要がある。これが面倒なので、バイナリアンと言えども長いコードを書かなければならない場合、簡易アセンブラを自作するのが普通で、この簡易アセンブラでは普通ラベルジャンプをサポートする。LOOP_STARTのような書き方が出来るというわけだ。バイナリアンにとって、このような条件ジャンプ時のアドレス計算こそが癌であって、これさえなければハンドアセンブル上等!なのである。(バイナリアンの総意ではなく、あくまで私個人の見解です)そこで、今回の2次元メモリプログラミングモデルでは、jz命令のあとは、ラベルやアドレスではなく何も書かないことにする。条件が成立したときは右のメモリに移動する(非成立であれば下のメモリに移動する)というようにする。いうメモリモデルというのは、実用上も価値がある場合がある。FPGAでこのようなメモリモデルのCPUを実装するとしよう。)を採用していて、それぞれのCPUコアはなるべく小さく保ちたいとする。そこに書くプログラムは非常に小さなコードなのでコードサイズはそれほど問題とはならず(どうせCPUコアからアクセスするコードメモリはFPGA内のブロックRAMで実装されるのでブロックRAMを一つに収まればそれで良い)、条件ジャンプのときに飛び先の番地を計算するためにフルサイズの加算器(メモリ空間が12bitならば12bitの加算器)を用意するのがもったいないとする。そこで、条件成立時は現在のアドレスに0x100(256)を加算したアドレス(二次元メモリだとみなしたときの“右”がこれだとしよう)にジャンプするような条件ジャンプ命令を実装したとする。これなら、フルサイズの加算器よりはいくぶん規模を小さくできるし、条件ジャンプ命令がジャンプ先のアドレスを含まなくて済むので、データバスのビット数とアドレス空間のビット数を合わせる必要がなくなるというようなメリットもあるかも知れない。二次元メモリモデルというのは、空想の産物ではなく、案外実用になるのではないかというところまで話が進んだので、次に、これをN次元に拡張していく。さきほどまでの話だとプログラムは基本的に下方向に向かって命令が実行されていく。条件ジャンプがあると、条件が成立したときにのみ右側に1つ移動するだけであった。これだとループが書けない。メモリ空間自体がどこかでメビウスの輪のように終端と開始アドレスが繋がっているのならば別だが、その仮定は制約が強すぎる。(たとえば0x1FFのつぎの番地が0x100に戻るような実装は可能かも知れない。条件ジャンプの条件成立時には実行アドレスを指すレジスタに0x100が加算されるとして)そこで、プログラムの実行方向を下ではなく、現在の亀の向いている方角だとしよう。ここでいきなり“亀”が何故出てくるかというと、その昔(1970年代に)、LOGO言語というタートルグラフィックス環境が流行った。(仮想的な)亀にペンを持たせて、その亀に対して次のような命令を指令する。これにより正方形が描かれる。このタートルグラフィックスの考え方を、この2次元メモリプログラミングに応用し、現在の亀が向いている方向に命令を実行していくとするわけだ。条件分岐であれは、条件成立時には左90度回転。(非成立時には直進)無条件左90度回転命令(無条件ジャンプに相当する)も欲しいところではあるが、それはしかし、わざと成立するような条件比較を行ない、そのあと条件ジャンプ命令を書けばかならず条件が成立し、左90度回転するという動作になるので、命令セットを最小化するという観点からは不要だとも言える。このようなプログラミングモデルであれば、ループを実現したければ、無条件ジャンプを4回行えば、もとの位置に戻ってくることも出来るであろうことがわかった。次に、このプログラム同士を戦わせることを考える。Warsという1985年ごろに流行った、小さな命令セットを持つ仮想CPU同士をサンドボックス環境で走らせ、相手にhalt(実行停止命令)を実行させれば勝ちというバトルゲームである。Warsのtiny版がOh!MZ誌(のちのOh!X誌)に掲載されていたので、これでずいぶん遊んだ覚えがある。Warsでそのような自己修復機能を持ったプログラムを書けないかとやってみた。sum的なものを調べ、コードが破損していたら、それを元のコードに戻すというわけである。戻すためには元のコードが必要なので自分自身のプログラムを+0x100番地離れたところにコピーしておく。そのコピーしたほうも壊れるといけないので、そのプログラムもさらに+0x100番地離れたところにコピーしておく。Warsは仮想的なマルチスレッドモデルを採用しており、forkに相当する命令があったので、それぞれのスレッドがそれぞれ自己修復(破損していれば+0x100番地先からコピーして復元)、また、増殖(+0x100番地に自分のコピーがいなければ、自己をコピーしてfork。正確に言えば、+0x100番地のプログラムのheartbeat(自分が生きていることを示すためにメモリに書き込む値)が確認されなければそこの担当スレッドが死んでいることを意味するので復元してfork)みたいなプログラムを書いた。いまにして思えば、それは自己修復型のワームなのだが、当時私はそういう用語すら知らなかった。このようなそこそこ複雑なプログラム(とは言っても30命令程度ではあったが)を書いて満足していたのだが、他の人が作ったプログラムと対戦させてみると、このプログラムがなかなか勝てないプログラムがあった。それは一寸法師と呼ばれるたった5命令から成るプログラムである。その5命令のうちのひとつは5命令目に書かれたhaltであり、ここはそのプログラムは実際には実行せず、この5命令目に書かれた命令をその5番地先にコピーするというだけのプログラムである。要するに5番地ごとにhaltを書きこんでいくプログラムで、そのプログラム自体のコアは4命令から成るので自分自身には被害は及ぼさないというプログラムであった。Warsのゲームバランスを損ねる元凶でもあった。Warsを作れないかと私は考えていたわけではあるが、ここに至って、今回の2次元メモリプログラミングモデルがすこぶる有効なのではないかと気づいたわけである。アドレスジャンプではないので、急にあっちからこっち、というようなジャンプをしないので視覚化したときに非常にわかりやすい。バンバンのように必ず隣のメモリにしか移動しないからである。ループを構成するために、ダミー比較(Equalフラグを立てるためのもの)と条件ジャンプ(jz命令)の2命令を4回使わないとループにならないので少なくとも8命令は必要であり、一寸法師的なプログラムであっても12命令では書けないような命令セットであれば、16命令か20命令程度使わざるを得なくなってくる。するとフットプリントを小さくしておいて絨毯爆撃するというようなプログラムが書きにくくなるので、もっと高度で高機能なプログラムのほうが勝率が上がるのではないかと思う。Warsとしては面白い。Warsの試合用のサーバーを用意して、比較的大きなメモリ空間で複数のプログラムを放って、その生存率(24時間に何回死んだかをカウントし、その平均生存時間から算出する)を競わせるような競技場を気が向いたら作ることにする。(注:いま酔っ払っているので、酔が覚めたら忘れているかも知れません。Warsのような試合用のアーキテクチャとしても非常に興味深いことがわかった。次に、これをN次元に拡張していく。N次元なので現在の命令の番地はベクトルρで表されるとしよう。向いている方向はベクトルνだ。νは単位ベクトルとしよう。このとき次に実行する命令の番地はρ+νである。条件ジャンプ命令で条件が成立時には左90度回転をするのであるが、N次元空間での回転だと回転軸が必要で、それを固定してしまうとうまくメモリ全体を巡れない。(-1,0)左方向のように推移するので、同様にN次元でも(たとえば3次元ならば)(1,0,0)→(0,1,0)→(0,0,1)→(-1,0,0)→(0,-1,0)→(0,0,-1)→(1,0,0)のように推移すれば、メモリ全体を巡ってもとの場所に戻ってこれるのではないかという。この変換行列をΤとすると、新しいν=Τνみたいな計算でどうか。]みたいな直交行列かつ、テプリッツ行列(対角一定行列)でどうかいな。以上の方法でN次元メモリプログラミングも出来そうではある。(ExcelのワークシートがN次元に対応したようなソフトウェアがないとプログラムを書くのは困難かも知れないが)行列Τのバリエーションを変えれば、もう少し面白い実行が出来るかも知れないが、話が収拾がつかなくなるので今回は割愛する。・条件分岐では条件成立時にν=Τν、非成立時は直進としてきた。ところが、ここで「条件分岐では条件成立時に直進」となるようなプログラミングモデルだとどうだろうか。・基本的にはうねうね・条件分岐では条件成立時に直進、非成立時はそのままうねうねこうなるわけである。この“うねうね”として、全メモリを被覆するようなうねうねした直線を持ってくればいい。ヒルベルト曲線にする。ヒルベルト曲線は空間充填曲線である。2次元だと次図のようになる。http://d.hatena.ne.jp/ototoi/20090315/p13次元だと次図のようになる。・基本的にはヒルベルト曲線上の番地を実行していく・条件分岐では条件成立時に直進、非成立時はそのままヒルベルト曲線上を辿るのようなプログラミングモデルを考えることが出来る。この場合、さきほどまでの90度回転や行列Τで向きを変えるのとは違って、少しパズルじみた要素が出てくるし、条件分岐がなければ基本的にすべてのメモリを使い切る(空間充填曲線なので)のでメモリ効率はいいかも知れない。このような実行モデルをプログラムの難読化に利用することを考える―――という話を書いていこうと思ったところで眠くなってきたのでこのへんでお休みなさい。以上、酔っ払いの戯言を新年の挨拶に代えまして。Turtlesが、本記事で書いた二次元プログラミングっぽいゲーム仕様になっているのでご紹介。電子書籍になるに至るまでの話ブログちょっとだけ移転のお知らせ時代はまだゲームセンターあらしに追いつかないのかやねうら王、電王戦バージョン提出しました将棋の神様のレーティングはいくつなのか?月別アーカイブはてなブログをはじめよう!yaneuraoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。