安敦誌


つまらない話など
by antonin
S M T W T F S
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
検索
最新の記事
婦人画報創刊号
at 2017-07-07 01:36
アキレスと亀
at 2017-05-02 15:44
受想行識亦復如是
at 2017-05-02 03:26
仲介したことはあまりないが
at 2017-04-29 03:36
サンセット・セレナード
at 2017-04-12 23:17
水分子と日本人は似ている
at 2016-06-04 01:49
ほげ
at 2015-06-05 03:46
フリーランチハンター
at 2015-04-17 01:48
アメリカのプロテスタント的な部分
at 2015-04-08 02:23
卯月惚け
at 2015-04-01 02:22
記事ランキング
タグ
(296)
(147)
(122)
(95)
(76)
(65)
(59)
(54)
(45)
(41)
(40)
(39)
(33)
(31)
(28)
(27)
(25)
(24)
(22)
(15)
最新のコメント
>>通りすがり ソ..
by Appleは超絶ブラック企業 at 01:30
>デスクトップ級スマート..
by 通りすがり at 03:27
7年前に書いた駄文が、今..
by antonin at 02:20
助かりました。古典文学の..
by サボり気味の学生さん at 19:45
Appleから金でも貰っ..
by デスクトップ級スマートフォン at 22:10
以前の記事

タグ:PC ( 40 ) タグの人気記事

イカレた脳のためのマクロ・メタリファクタリング

久しぶりにBrainfuckと戯れている。

Brainfuck処理系のベンチマークとして有名なmandelbrot.bには、C言語用プリプロセッサを使ったマクロ・メタプログラミングで書かれたソースコードがある。

Index of /brainfuck/utils/mandelbrot

そのソースコードを解読すると、BFのメモリモデルであるバイトデータ1個を1ビットとして扱い、それを16個組み合わせて半精度浮動小数点数を作っていた。このメタ浮動小数点数に対してBFコードでビット演算を行うことで、マンデルブロー集合の計算に必要な精度の複素数演算を実現している。なかなか面白い発想だし、複雑な演算の割に実行パフォーマンスも結構良い。

で、そのソースコードの細かいところを解読しようと思ったが、結構プリミティブな表現が直接使われていて、意味が読み取りにくかった。まあ、わかるんだよな。メタプログラミング作業の最初のほうでは、Brainfuck命令で書くよりも自然言語に近いマクロで書いたほうが読みやすいんだけど、だんだんBFに親しんでくると、今度は冗長な名前付きマクロで書くよりも、BFの簡潔な記号を組み合わせたイディオムで書いたほうが理解しやすくなってくる。ここらへんがBrainfuckの病的なところというか、人間様の適応能力の不思議というか、そういうところがある。

そうは言っても、あとからそういうコードを読むと、やはり意味が分からない。ということで、高度な集中力と勢いで書かれたmandelbrot.bのソースコードをリファクタリングし、プリプロセッサ処理のパフォーマンスよりも可読性を重視した形に書き換えてみることにした。まだ基本処理に if と while と for の区別をつけるとか、move だの copy だのを導入するとかその程度だけれども、今のところ元のBFコードと同一性を保っている。このレベルでも詳細処理がだいぶ読みやすくなった。最終的には動作レベルの同一性までの保証になり、BFコード上の同一性までは担保できなくなるだろう。ただ、最初からそこまでもっていくのは危険だ。

こういう作業は面白いんだが、寝不足で頭が痛い。面白いことをやって脳が活性化する効果が勝つか、睡眠不足でグリアが死んでいく効果が勝つか。まあ後者だという気がするが、とにかく面白い。
[PR]
by antonin | 2014-03-29 01:35 | Trackback | Comments(0)

RAIIとかtry-catchとか

久しぶりにウィークエンド・プログラミングなんかをしている。業務ではなかなか手を出しにくいテンプレート周りの記法を試しに利用しているが、C++03時代には細かいところで高度なバッドノウハウを要求されて挫折していたことが、C++11では概ね思ったとおりに書ける方法が用意されていたりして、なかなかいい感じになっている。そもそも今まではunique_ptrすらなかったわけで、tr1::shared_ptrだとかboost::scoped_ptrがあるよと言われても、sharingしたくなかったりboostの複雑なconfigureに悩まされたりしたくなかったりすると、結局自分でスマートポインター作りから始めるなんていう状況が多かった。

最近、まだ新しいPCの電源部がぶっ壊れ、借り物のPCにCygwin+GCCを入れたりなんかしたついでに、整数型を完全にテンプレートの向こうに追いやって素数計算なんかをするとどんな感じになるか、なんてことを試して遊んでみた。C++11の制定から2年以上経過して、GCCもだいぶ安定して「カバのダンス」もうまくなったらしいので、-std=c++11で新しい機能を少し試しながら書いてみた。今回、テンプレートの中でstd::vectorだとかstd::unique_ptrだとかを使ってみたが、autoだとかtemplate aliasなんかがとても便利で、いままではテンプレート中なのにCっぽく泥臭い記述でお茶を濁さざるを得なかった表現が、ずいぶんスッキリと書けるようになっていた。

次に、Brainfuckの実装をstrategyパターンっぽくして、命令実行エンジンの最適化レベルとか、メモリ部のモデルとかに依存しないように実装してみることにした。まずはソースファイルのオープンでしょう、ということで、設定オブジェクトがコマンドラインから拾ってきたソースファイル名でリードオープンするクラスを作っていたのだが、さて、コンストラクタでオープンさせるのか、別途メンバ関数のOpenを呼んで成功チェックするかどうか悩んでいた。古典的には、コンストラクタは本当に例外的な事象以外では成功するようにしておいて、エラーの予期される初期化にはそれ用のメソッドを呼ぶべき、という作法があった。

が、現代的なC++の思想では基本的にRAIIで、普通のブロック中だろうが別のクラスの初期化リストの中だろうがポインタを取る演算式の中だろうが、どこでも完全なオブジェクトを生成するか、あるいは例外を投げて正しく失敗しなければならない。そうすれば、別の誰かが例外をブン投げたりしてスコープを外れた場合は必ずお行儀よくデストラクトする仕組みが言語レベルで提供されている。であるからには、きっとC++11にはそういうスタイルのための基本的な道具立てはそろっているはずだと思い、イディオムを探してみた。すると、案外混乱している様子が見て取れた。

コンストラクタでの例外はあり?なし? - Togetterまとめ

河野 真治さんが意外と古風な論を展開していて驚いたが、実用的な実装を重ねてきた経験からの意見なんだろう。が、週末プログラマーとしては憚ることなく安っぽい理想論を展開していきたい。週末プログラミングは保守的な実務プログラミングでのフラストレーションを晴らす意味もあるので、あんまり現実的なのは嫌だ。しかし実際問題として、オンデマンドでオブジェクトを生成するRAIIに対して例外処理を安直に書くと、文法上の障壁があって困っていた。下のリンク先にとても上質な議論があって、その中に言いたいことがずばり書かれていた。

C#のvarとtry~catchが糞すぎる - やねうらお-俺のやねうら王がこんなに弱いわけがない。 (第2期)

using (var sr = new StreamReader(path))
{
var text = sr.ReadToEnd();
}
Console.WriteLine(text); // なんでここでtextにアクセス出来ないの?馬鹿なの?死ぬの?

そうそう。これこれ。上記のコードはC#のサンプルだが、C++11でも同様のスコープの問題がある。まずリソース確保のためにオブジェクトを確保するのだが、それをtryブロックに入れてしまうと、その後のコードから参照できず、せっかくコンストラクトが成功してもtryブロックを出るときにデストラクトされてしまう。馬鹿かと。アホかと。

結論としては、例外を投げて失敗する可能性のあるコンストラクタを呼んで、しかも失敗時にリカバリーできる失敗なのだとしたら、スタック上に実体で受けるんじゃなくてヒープへのポインタで受けて、tryブロックの外にあるスマポに入れればいいじゃない、ということになる。オブジェクト本体はコンストラクタで例外を投げるとしても、スマポを使えば、そのコンストラクタはno_throwだし、newしたポインタの登録が初期化になるわけで、スマポの使用を前提とすれば、結局は失敗の可能性の高い初期化とオブジェクトの定義を自由に分離できる。だから、ポインタの先にあるプリミティブなクラスの実装がコンストラクタで例外を投げても全く問題ないということになる。

コーノさんは基底クラスのコンストラクタが例外を投げるようだと継承しにくいという問題を挙げていたが、他の人が述べていたように、インターフェイスと実装が分離されていないクラスを継承によって再利用しようとすること自体に何らかの設計ミスがある、という考え方のほうが(現実的にはともかく理想的には)正しいのだと思う。レガシーシステムに組み込むような事態を考えないで済むなら、コンストラクタは積極的に例外を投げていいと思う。コンストラクタにno_throwが必須の汎用クラスもあれば、no_throw制約が馬鹿げているような特殊リソース管理クラスもあって然るべきだろう。まあ、そういう場合もno_throwなデフォルトコンストラクタを持っているのは有用だろうけれども。

ただ上記引用の本論はvarで型情報を受けること、C++11で言うところのautoで受けるようなところが問題の核心なので、またちょっと別の話になるのだけれど。そのあとのコメントにあったouterみたいなのはいいと思ったが、利便性のためにブロックの機能を破壊するよりも、カジュアルに関数なりクラスなりを作って、外部から見て適切な振る舞いとなるようにラッピングしていくのが正攻法なんだろう。そのために静的なドキュメントを膨大に書かされるようなことのない現代的な開発環境であれば。

感想として、なんだかC++もだんだんCommon LISPみたいになってきたな、と思う。文法上の道具は充分に用意してあるから、文句があったら自分の使いやすいC++ベースのドメイン言語を自分で構成しろと。まあマクロありのS式みたいな構文上の柔軟性はないけれども、演算子のオーバーロードから始まって、C++14/17に向けてエキスパート向けの変態ツールがますます豊富になってくるみたいだから、JSF++みたいにエキスパートチームが先にコアライブラリなりフレームワークなりを定義して、アプリケーションプログラマはそのドメイン言語の範疇でプログラミングしていくことになるんだろう。

ただ、エキスパート不在の現場だとか、エキスパートたちの意思統合が下手な現場だとか、エキスパートの思想を末端のプログラマまで浸透させるだけの言語能力に欠ける現場だとか、そういう場合にはISO標準化以前のC++に匹敵するくらいマズい状況も予想されるだけに、ちょっと恐ろしい。LLVMが組み込み用に普及するような時代になると、もうC++の出番はないんじゃないかというような気もしないでもないが、まあ将来のことはわからないので、眠れなくならない程度にC++の進歩を見守っていきたい。
[PR]
by antonin | 2014-02-22 15:48 | Trackback | Comments(0)

アメリカ組曲ほか

音楽の話を書いたが、昔話が混ざったりして話が煩雑になってしまったので、今日久しぶりにCDから取り込んで聴いた曲だけ記録することに。

Amazon.co.jp: American Suite, B.190, Op.98b: II. Allegro: Royal Liverpool Philharmonic Orchestra: 音楽ダウンロード

YouTubuなんかで探しても出てくるが、リンクしたために削除されたりすると悲しいので、ここには出さないことにする。

音楽を聴くから気分が落ち着くのか、気分が落ち着いてきたからじっくりと音楽が聴けるのか、どちらでも妥当なような気がしてわからない。まあどちらでもいいか。

--

Brainfuckなんかもコツコツ進めている。非常に早い処理系を見つけたのだが、そこで使っているC++用のJITライブラリなんかも見ていて面白い。RPythonでBrainfuckというのもあった。

hogelog/fast-bf · GitHub

XBYAK

PyPy を使ってインタプリタを書く

BF用バックエンド・ライブラリの実装はちょっと後回しにして、有名なmandelbrot.bの生成用マクロコードを解読していたりしている。複素数演算はバイトを1ビット扱いしてキャリー計算することで実装しているらしい。面白い。

なんというか、平和です。
[PR]
by antonin | 2013-09-06 02:24 | Trackback | Comments(0)

Tortoisesvn 1.7.12 でWordファイルの差分を取ると失敗する

日常的にTortoisesvnを利用させていただいている。非常に便利でありがたい。いつもローカルリポジトリしか使っていないのでショボイ使い方ではあるのだが、Wordで書いた管理文書のdiffが取れたりするので非常に重宝している。

で、なんだかセキュリティアップデートが出たというので、自分の使い方では外部アクセスはしていないのでリスクは低いものの、ログ表示に新しいバージョンがあるから更新しろと赤文字メッセージが出て鬱陶しい。そこで tortoisesvn 1.7.12.24070 にアップデートしてみた。ところが、それからWordファイルのdiffが取れなくなった。

.docファイルのdiffを取ろうとすると、Windows Script Hostのダイアログが出て、

"You must have Microsoft Word or OpenOffice installed to perform this operation."

とかのたまう。原因を調べてみると、

%ProgramFiles%\Tortoisesvn\Diff-Scripts\diff-doc.js

というスクリプトファイルの実行でエラーが発生していた。r23995の改修でWord 2013用の処理が追加されているのだが、その条件文で使われている、

66: if(parseInt(word.Version) >= vOffice2013)

このvOffice2013という定数の定義が存在しないため、条件文が常に成立してしまいWord 2013専用の処理が例外を吐いてcatchされ、しかもそこでWordが存在しない時にOOoを探すとかいう処理に流れて、OOoもインストールされていない場合に上記のエラー表示が出てしまう。

なんでこんなことになったかというと、trunc上でr23995のパッチが当たったのだけれど、これをリリースパッケージに取り込むためのbranches/1.7.x/contrib/diff-doc.js (r23996) へマージする際に、かなり古いコードへ最新パッチの部分だけ取り込んでしまったためにこんなことになってしまったらしい。

これを解決するには、%ProgramFiles%\Tortoisesvn\Diff-Scripts\diff-doc.js の25行目あたりに定数定義を追加してやればいい。

25: var vOffice2013 = 15;

あるいはgoogle codeあたりからtruncの最新版を落として上記ファイルに上書きしても動く。

merge-doc.js - tortoisesvn - A Windows Subversion client, implemented as a shell extension - Google Project Hosting

まあ、上記の問題はbranches/1.7.x/contrib/diff-doc.js (r24094) ではもう修復されているので、次のリリースを待っていても早晩解決するでしょう。
[PR]
by antonin | 2013-04-10 22:20 | Trackback | Comments(2)

日常的妄想のあれこれ

時間がない。手短に。

--

国債全然OK学派の人々の最大の論拠とは、国債の大部分が国内で消化されているから大丈夫、という説にある。比喩的に、お父さんがお母さんから借金しているようなものだから大丈夫、とある。これが、家計を預っている主婦たるお母さんが、経済労働の主体であるお父さんから借金して使い込んでいるという比喩に置き換えてもまだ同様に借金無問題という結論が出るのか、そのあたりはよくわからない。

わからないわからない言っていてもしかたがないので、久しぶりにマンキューを引っ張りだしてきた。流し読みしてみて、少し分かる部分もあるのだけれど、まだマクロ経済の問題を理解できるほどには理解が進んでいない。このあたり、喉に小骨が刺さったような異物感を時々覚えて具合が悪い。

国内で債券が消化される場合、債権者を国外に持つ場合との相違点は何か。箇条書きにしてみる。

・債権者が国民であれば、国家の定める法律に従う義務があり、国民は立法府が公布する非常事態法(預金引出制限や一定資産の接収など)に逆らうことができない。

・円通貨を発行しているのは日本銀行であるが、非常時においてはその政府に対する独立性を制限することができるため、国債の額面を記述している円の価値を下げるために、紙幣増刷を命令することができる。

・国家は国民に対し情報統制が可能であり、国債の保有に心配はないとする、債務に対する国民の信用を維持する方法を有している。

というあたりか。マクロ経済においては、通貨圏の中で通貨流通が閉じているので、開放系の数学ではなく閉鎖系の数学が適用される(開放系の数学に対して、通貨の循環を前提とすることによる暗黙の境界条件がいくつか付加される)という違いがある。しかし、現在の国際経済は、地球全体ではもちろん閉じているけれども、国家単位では解放度合いが大きく、通貨統合したヨーロッパ連合ほどではないにしても、日本円も為替の影響を大きく受けている。

たとえば、わかりやすく発電所の発電機で考えてみると、1次冷却水は復水器によって循環するが、そこで加熱される2次冷却水は外部環境へと放流される。こういう場合に、1次冷却水の質量系は閉鎖系になるけれども、エネルギーの系は、ボイラーからの熱流入、タービン内膨張によるエンタルピー流出、復水器での熱流出によって、開放系になっている。円も同様で、取引通貨としての円は日本国内に閉じているが、貿易と投資を通じた価値の交換は為替を経由した開放系になっており、古典的なマクロ経済が前提としている閉鎖系依存の境界条件の一部は既に成立しなくなっている。このあたりの加減がまだよく理解できていない。

日銀の量的緩和も、キャリー・トレードによって国内ではなくスペインやギリシアでの不動産価格高騰を招いただけに終わり、ヨーロッパの中銀各行に迷惑だからほどほどにしてくれと注意されたから続けられなくなったという説があって、もしそれが本当だとすると、日本国内だけを向いた政治家の口から、あの時もっと緩和を続けていれば日本の経済が自律回復したのに途中でやめた日銀の不見識は云々という意見が出るのは、国際経済の規模に対して無視できないほどの規模に成長した円の番人としての、日銀の重要な役割を過小評価した意見なのではないかと思える。説が正しければ、だけれども。

分子が分母に対して十分に小さいうちは成立する近似式が、分子が大きくなると成立しなくなることがあり、逆にそれまでは成立しないと言われていた近似式が徐々に成立してくるという現象も、工学の世界にはしばしば見られる。そういうビリアル係数的なものが経済学ではどうなっているのか、このあたり、真相を知りたい。

--

Brainfuckの処理系の仕様がだいたい固まったのだけれども、規模が大きくなりすぎて、実装する時間がない。素直に実装するとgcc-coreくらいの規模になってしまう。これはこれで美しくないような気がする。あと、やっぱり安全なコードと速いコードの両立は難しいと実感した。処理系とユーザープログラムが暗黙の契約を結んだような(契約を破ると即座にsegmentation faultで堕ちるような)コードは、処理系が水も漏らさぬような処理をするコードに比べると、やっぱり10倍くらい速い。工夫によってこの差はもう少し縮められると思うが、それでも2倍は割らないだろう。

Javaの、遅いがネットにさらしても安全に動く処理系というのは、素人が世界のいかなる道路を運転しても破綻しない乗用車のようなもので、その速度というのはどうしても限度がある。しかし、道路に陥没もなく、横断する歩行者もなく、ドライバーが事故を起こしてもドライバーがメーカーを訴えないことが保証されているような、つまりサーキットレーシングの世界では、同じような排気量のエンジンでも数倍速く走ることができる。これは、実はFortranの世界であり、こういうスパルタンな環境下では、Brainfuckのような非効率な言語でも結構な速度で問題を解くことができる。

最初は現代的で安全重視の処理系をstd::dequeなんかを使って書いていたのだけれど、これだと有名なmandelbrot.bの実行に3分くらいかかる。これをstd::vectorに変更して、segmentation fault上等な(代わりに開始アドレスから±1GBのアドレス空間を確保した)処理系でこれを実行してやると、30秒を切る。そこから最適化などをしてやると、最終的に10秒を切るあたりで落ち着く。これとは別に、BFからCのコードへ直訳するコンバータを書いて、出力されたコードに2GBのstaticメモリを与えてやると、gcc 4.5.3 の -O3 オプションによって処理時間は1.2秒ほどにまで縮まった。やっぱりコンパイラは強い。

この過程で最適化技法などについても思うことが多々あったのだけれども、CPUパフォーマンスを古典的な意味で引き出す方へ興味が行ってしまい、ここ2週間ほどはopenmpだとか、sse2だとか、汎用レジスタのSIMD的手法による演算(32bit intを8個の4bit intとして加算や論理演算を行う)だとかを試行していた。ネタは再びライフゲームに里帰りしている。今のところ睡眠不足のためにパフォーマンス測定できるところまでコードが書けていないが、L1キャッシュの32KBからデータを落とさないように注意しながら3個のALUを占領して走り続けるコードなんかを考えていて、何かと楽しい。

もはや「公道を走る」タイプのプログラミングにおいて、こういうあまりにも趣味的なコードを書くことは許されないのだけれども、ひどくプライベートな空間を走るプログラムというのは今の時代にもわずかに残されている。それにしたってプログラムの方を極度にチューニングするよりは、最新のアルゴリズムを適用してみたり、適正な従量コストを引っ張ってきてプロセッサのスケーリングで解決する方が主流ではあるのだけれども、素人に毛の生えたようなレーサーが週末に筑波を攻めるようなプログラミングスタイルというのがあってもいいのだろうと思う。

--

育児とか仕事とかもいろいろと厄介ですが、まあそのあたりはアレということで。
[PR]
by antonin | 2012-11-11 17:31 | Trackback | Comments(2)

Brainfuckが可愛すぎて生きるのが辛い

本当につらい。具体的にどうつらいのかというと、頭が痛い。おそらく睡眠不足がいけないのだと思うが、それに加えて、起きている間は少しでも暇ができると、Brainfuck(以下BF)をいかにして多機能化するかということを考えてしまうので、脳が休まる暇がないということもあるのかもしれない。

C++やJavaなどはもうすでに十分多機能であり、BoostやOracleならいざしらず、一般のプログラマはどちらかと言うと、これ以上仕様を複雑にしないでくれという気持ちのほうが強いのではないかと思う。しかしBFはというと、色々な人々が訪れてはいるが、言語仕様も処理系も、それほど開発が進んでいないエデンの園状態がまだ残されている。そして、出発点があまりにもシンプルなため、少々手を加えてもそう簡単にはシンプルさを失わない。そういうBFは、プログラムの初心者には手強い言語かもしれないが、処理系の初心者には最高のオモチャといえる。

BFの楽しみというのは、チューリング完備な言語として最低限の機能しか持たないが、しかし抽象的で実装の難しい概念が全く入り込んでいないから、実際に動作する処理系を組んで、色々と工夫をしながらプログラムを動かしてみることができるというところにあるだろう。そして、簡単な問題が解けると、次はもう少しずつ難しい問題に手を出したくなってくる。BFの場合、言語仕様も処理系も最小構成であるので、言語仕様の拡張という方向と、処理系の拡張という方向の2つの方向に発展の余地がある。

BFを考案したMüllerさんは、Amiga OS上で98バイトのインタプリタを書いた。この原始BF処理系では、0で初期化された30000個の1バイト整数が与えられ、入出力はOSのコンソールに接続された。結果としてデータはASCII符号として扱われ、そして "Hello, World!" が書かれた。先人たちはまず、この30000バイトの上限を取っ払って、マシンが確保できるメモリの上限まで与えるような拡張を行った。リニアメモリの要素を16bitなどのint型にしてみたり、アドレスをマイナス方向にも広げたり、そういう拡張もあった。

私が最初に考えたのも処理系の拡張という方向で、FORTRAN以来の高級言語が持っている演算子が実行するような基本演算や、Cの標準ライブラリ程度のシステム操作機能を、処理系に結びついたライブラリとして実装し、BF命令単位あたりの実行複雑度密度を引き上げる方向というのもこの方向に当たる。これはこれで面白い。

ただ、そうして標準ライブラリを備えた処理系に向けてBFコードを書いているうちに、BFでコードを書くコツがだんだんとつかめてくる。そしてついに、素のBFのままでどこまで書けるんだ、というようなことに挑戦してみたいという誘惑が頭をもたげてくる。そして、そういうチューリングマシンの深みから、高級言語で見慣れた水準まで崖を這い上がるための道具を揃えたくなってくる。そういうマクロ言語によるメタBFへの拡張を試みたくなってくる。

そこで、(+ 100)や(+ 0x64)と書けば、'+' が100個並んで、これを出力すれば画面に 'd' と表示される道具を最初に考えた。どうせなら、ということで、(+ \d)と書けば(+ 100)と同じ結果になるような拡張も考えた。{=foo 100} とやっておけば、(+ foo)で(+ 100)と同じになるよう、マクロ変数も考えた。
{=$copy(N) [-(>+ N)>+<(< N)]>(> N)[-(< N)<+>(> N)]}
とやっておけば、{$copy(10)}でデータ10個分のコピーが書けるような、普通の文字列型マクロも考えた。そんな感じで、結構リッチでいい具合のマクロ言語が設計できた。

さて、ここまでは良かった。しかし、この先は結局、マクロとマクロを再帰的に入れ子にしたり、マクロ引数で条件選択して展開結果を調整したり、というようなことがしたくなる。BFは言語レベルが非常に低機能なので、そのプログラミング能力はマクロの構築能力に依存してくる。深さに制限のないネスト、定義時の解釈と展開時の解釈の選択、オプション引数による展開内容の調整、などなど、欲しくなる機能は無数に膨らむ。

そうなってくると、どこぞのLISP系言語を使って、最終的にBF文字列に展開されるマクロ系列を書けばいいんじゃないか、それどころか、S式にBFによる基本ルーチンだけを書いて、あとはそれを組み上げてLISPプログラムを組み、実行結果としてBFのコードを出力したらいいんじゃないか、自分でプリプロセッサを書いてもLISPに勝てる気がしない、なんてことも思った。で、今はとりあえずマクロ言語と処理系の仕様だけ作り上げ、実装の段になったらlibguileなんかに構文解析を丸投げしようか、なんてことを考えている。

それでも、処理系の仕様設計はそれなりに楽しい。ライブラリはなんだかんだ言いつつも結局使ってみたいので、関数コールを楽にするpush系コマンドだとか、スタックを逆ポーランド的に使える演算子コマンドだとかをリストアップし、マイナス値の関数テーブルに配置していく。BFのメモリ上に書き込まれたバイト列をBFコードとしてevalし、それを関数テーブルに登録して利用できるようにするコマンドだとか、登録した関数を別スレッドで実行するコマンドだとか、そういうものを考えている。

メモリモデルも、起動時にメモリ要素を 8, 16, 32, 64 bit int から選べるようにする。他にも、アドレスを bit 単位で移動できる 1bit モード(Bitfuck mode)や、加減算命令にキャリー付き演算を使って隣接アドレスのデータと結合するモード(gigabit mode)なんかも考えている。それぞれに、どう実装してやろうかなんてことを考えだすと楽しくて止まらず、しばらくすると頭が痛くなる。

そんなわけで、Brainfuckが可愛すぎて生きるのが辛い。というか頭が痛い。こういう遊びは25歳までに済ませておくべきだったのだが、40にもなって何をやっているんだか。
[PR]
by antonin | 2012-10-01 23:56 | Trackback | Comments(0)

雑記

エーテルについて、好奇心について、命題論理とか述語論理とか様相論理とか集合論とかについて、ぼちぼち考えていた。ヒッグズ粒子も観測されたことだし、そろそろ超多時間論より下位に来るエーテルレベルの話が活発になってもいい時代なんじゃないかと思う。M理論なんかはまったく意味がわからないけれども、いい本があったら読んでみたい。

森田さんが新書で出した本を見つけたので、読んでいる。まだ途中までしか読んでいないが、ベルの定理とその周辺がわかりやすく説明されていたりして、読んでいて楽しい。良識的な物理学者が無批判に信じているような定説を、科学哲学の人らしく正確な位置づけで書いてくれるので、読んでいてストレスを感じなくていい。ネット接続が回復してからネットに入り浸って紙の本から離れてしまっているが、少しずつまとまった読書ができる習慣を取り戻して続きを読んでいきたい。

量子力学の哲学――非実在性・非局所性・粒子と波の二重性 (講談社現代新書)

森田 邦久 / 講談社



Brainfuck用ライブラリの構築も、目立った進捗はないけど、ぼちぼち考えている。入出力命令の接続先を、ライブラリ用スタックへの push / pop と標準入出力で切り替える方式にしてみたら、少しだけBFプログラムが書きやすくなった。世の中には素のBFでマンデルブロ集合の計算とかやっているすごい人がいて、驚きつつ感心した。その人はCプリプロセッサでメタプログラミングして、すべてマクロによる記述でBFのソースを生成していた。私もまずはマクロというかメタ言語というか、そういうものを書くところから始めてみた。あんまりマクロ機能を強力化しすぎるのは言語間コンパイラを作ることにしかならないので程々にしないといけないのだけれど、同時に楽しい作業でもある。

Index of /brainfuck/utils/mandelbrot

インタプリタ設計もいろいろ考えている。マクロを使ったBFのソースというのは、うっかりするとすぐメガバイト単位に膨張してしまうのだが、結局繰り返しが多いので圧縮をかけると数百分の1くらいにまで小さくなる。ソースが巨大でも、文法解釈して冗長度を取り除いたあとの中間言語は非常に小さくなるだろう。ゼロクリアは普通 "[-]" と書くが、このあたりも繰り返しをゼロ代入へ最適化できるだろう。どれくらい巨大なソースを実時間で動かせるか、なんてのも楽しそうだ。

BFに公開するメモリは 32bit int の配列で行こうと思っているけれど、メモリ空間は広く使いたいので、インタプリタは 64bit アプリを前提としてみたい気もしてきた。BFのアドレス空間を 32bit 値でポイント可能な4ギガワードとすると、そこに 32bit int を割り当てると全部で16GBになる。幸い今度のノートPCの主記憶は16GBあるので、いい実験になりそうだ。実際には通常のリニアメモリが1GW、ライブラリ用スタックが1GW、32bit int 以外のオブジェクトを確保できるヒープメモリ用アドレスを1GW取り、どの記憶領域も動的に確保しようと思っているので、単純計算はできないが、2GBで終わりというのはつまらない。また近いうちに続編を書けるといいけど、場合によっては数年かかるかもしれない。

今度の火星表面探査機の名前は "Curiosity" というらしい。好奇心が持てるというのは幸せなことです。
[PR]
by antonin | 2012-08-28 23:38 | Trackback | Comments(0)

イカれた脳のためのダンス教室(1)

まだ書いていなかったけれども、空白の1ヶ月余の間に、PC環境を更新した。このあたり、また別途詳しく書こうかと思っているけれども、今回は1点に絞って。PC環境の更新に伴って、いろいろと無料のプログラミング環境を構築してみた。Visual C++ 2010 Express + Windows SDK + CUDA SDK だとか、Cygwin + gcc だとか。

で、まずは hello.exe なんかを作ってみる。それから、ライフゲームとか素数計算など、いつもの遊びをやってみる。今度は Core i7 でスレッドが8本まで動かせるようになったので、スレッド周りの実験などもやってみたが、2スレッド程度では体験できなかったスケーリング実験なんかができて面白かった。32bit int に収まる奇数全てに1バイトずつ与えても2GBに収まるので、エラトステネスのふるいで素数表をゴリゴリ計算させてみると、下手にアルゴリズム的に素数を求めるよりシンプルかつ高速になったので驚いた。空間計算量恐るべし。

それから、簡単なインタプリタなども作ってみようかと思って既存言語を物色していた。最初は whitespace あたりにしようかと思っていたのだが、言語のシンプルさに比べてマシンモデルが案外複雑だったので、面倒になってやめた。一方、単なるイロモノ言語かと思っていた brainfuck が、実は非常に良くできた言語であり、名前の下品さに反して言語仕様は恐ろしくエレガントだった。マシンモデルも言語仕様以上にシンプルにできていたので、これを実装してみることにした。元々が、言語処理系を最小化するために設計された言語だとうので、なるほどそういうことか、と感じた。

brainfuck(以下、BFと書く)の素晴らしいところは、チューリング完備な言語としては、おそらく史上最低水準言語なんじゃないかということ。IA32みたいなCISCの機械語は言うに及ばず、RISC系の機械語より命令数は少ないし、素の turing machine に匹敵するほどシンプルにできている。それでいて、BF にはジャンプ命令がない。あるのは while loop を表す "[" と "]" だけだ。これだけ低水準言語のくせに、イッパシの構造化言語だなんて洒落ている。

Brainfuck - Wikipedia

上記の Wikipedia の説明では、BF は「難解プログラミング言語」と説明されているが、こんなに簡単なプログラミング言語は無いのではないか、という気もする。確かに、BF で実用的なプログラムを組むのは難しそうだし、できあがったプログラムコードを読んでも、それが何を意味するかを読み解くのは難しそうだ。だけれども、私が最初に触れた、あの 8bit 時代の BASIC も同じじゃなかったか。

BASIC の命令を覚えただけでは遊べるレベルのゲームが作れるとは到底思えなかったし、素人が組んだ BASIC のプログラムを読んでその意図を読み解こうとしても、たいていは無理な話だった。だからといって BASIC を「難解プログラミング言語」とは呼ばないだろう。確かに実用的な作業をするまでの距離は遠いけれども、BFほど簡単に、その言語仕様の全貌を把握できる言語もないだろう。

Cは「高級言語の中では一番低級な言語」という特異な地位を占めているが、実はCの言語仕様範囲だけで実用的なプログラムを組むのは難しい。とは言っても、世の中にはCで書かれた実用的なプログラムがあふれている。それはなぜかというと、Cにはリンクして利用可能なライブラリが満ち溢れているからだ。コンパイラベンダが提供する標準ライブラリはもちろん、他にも様々なハードウェアのドライバがCで利用可能な関数の形として提供されている。逆に言えば、標準ライブラリ関数も含めた全てのライブラリを剥ぎ取られた "C language core" だけでプログラミングしろと言われたら、それは結構「難解」な作業なのではないかと思う。

同じ事は BF についても言えて、BF には定められた標準ライブラリも無いし、当たり前の話だけれども、OSベンダやハードウェアベンダが提供する、BF 向けライブラリなどというものも無い。とは言っても、BFで書かれた "Hello world" プログラムは存在する。BFには出力命令があるので、これはできて当たり前と思うかもしれない。しかし、BFにはマシンに文字を伝えるための文法がない。BFを解釈する処理系の方に「データを出力するとASCIIとして解釈する」という機能が盛り込まれているので、"Hello, World!" のASCIIコードに相当する数値を順次出力すれば、BFであっても文字列出力が可能になる、ということに過ぎない。

自作のBFインタプリタでは、BFの出力命令をCのputcharで、入力命令をgetcharで実装した。だから、出力命令はint 型の引数を取るputcharにBFのint型データを渡しているだけで、8bit表現可能な文字以外は適当に切り詰められる。そして、入力命令も8bit文字しか扱えない代わりに、EOFが-1という数値として特別扱いできて、BFプログラムは入力データの終端を検出できるようになる。この前提を自明のものとすると、",+[-.,+]" という短いBFプログラムでFIFOを組むことができる。これは入力用関数としてgetcharを使う処理系に依存したプログラムなのだけれど、たったこれだけの機能でかなり便利なプログラムを簡単に組めるようになる。

BFは1次元に並んだ整数列を増減させる機能と、その入出力機能しか持たない。その入出力を数値として解釈するか、あるいは文字として解釈するかは処理系依存であって、BFの言語仕様の外側の話である。実用的な機能が関連付けられているのはデータであって、文法上の命令ではない。だとすれば、BFが扱うデータに対して、もっとずっとリッチな意味付けをしたならば、「実用言語としてのBF」なんてものも作れるのではないか。

試しに、BFに欠けている基本機能である、代入演算、算術演算、論理演算、ファイル入出力などを、データを解釈するだけのライブラリとして実装してみたら何が起こるだろう、ということを今週末はずっと考えていた。

まず、BFの言語拡張になるようなことは一切したくない。史上最低水準言語としてのBFの美しさは守りたい。あくまでBFの範囲内で、データに対して機能を紐付けるという方法でのみライブラリ化をしたいと思った。それから、BFのプログラミング能力を無力化するような、ライブラリ自身が極端にプログラマブルになってしまうような拡張も避けたかった。このための縛りとして、ライブラリはBFの命令ポインタ及びデータポインタを一切動かさない(参照は可能である)ことと、ライブラリはBF配列上のデータ以外の内部状態をなるべく持たないこと、の2点を指針とすることにした。

まず最初に、ライブラリ内の機能呼び出し規約を定義する必要がある。というより、そもそもどうやってライブラリコールするのか、という問題がある。これについては、メモリアドレスの一部を機能レジスタとして割り付け、特定のメモリアドレスにデータ書き込みするのを検出して関数呼び出しとするか、BFの持つ出力機能を拡張して、特定のデータを出力することで特定の機能を呼び出す、という方式しかないと考えている。ただし、このライブラリはBFの機能を「拡張」するものであって、BF本来の機能に制約を課す部分は最小化したかった。

なので、ライブラリが認識する特別なデータを出力した場合以外では、この拡張処理系は素朴なBF処理系として振る舞うことを期待して設計したい。となると、どこか固定のアドレスに特殊な意味付けをするのは避けたい。"Hello, World!" の系を考えると、出力値が unsigned char の範囲に収まる場合は、それを素直にputcharするようにしたい。欲を言えば、出力にはintデータをUnicode文字として扱えるような機能も用意したい。となると、Unicodeにも現れない「負の数値」は素朴なBFの出力値には現れないデータとみなして、これを特別扱いとして関数の識別符号に利用してみることにした。

つまり、負の値を出力すればライブラリを利用する拡張モードになるし、それをしなければ素朴なBFの処理系となるという、素朴なBF処理系の上位互換系となるようにした。この拡張処理系でも、 "Hello, World!" はそのまま動くということである。

ライブラリの各「機能(function)」はCの「関数(function)」に近いスタイルにしたかったので、関数によって定められた複数個の引数と、1個以下の戻り値(voidを含むただ1個の戻り値)をインターフェイス基盤とした。となると、ライブラリはスタックマシンとするのが妥当なのではないか、という結論になった。

最初のうちは、データポインタを関数インデックスと見て、そこから正方向に引数が並び、データポインタ-1の位置に戻り値が書かれる、というようなインターフェイスを検討していたのだけれど、これだと関数コールのネストによって複雑な処理を記述するときに、データ移動が煩雑になってしまうという問題があった。それに、関数ポインタというアルゴリズムに属するデータと、引数や戻り値という状態に関するデータを、同じ領域に混在させなくては関数コールできないことになってしまって、ハーバード的な命令とデータの分離ができなくなるので断念した。

ライブラリにスタックを持たせるとなると、この領域は基本的にライブラリ専用になる。早くも基本指針と矛盾してくるので困ったが、ここは関数コールに負の値を利用したことの応用で、ライブラリスタックは、BFのリニアアドレス上でマイナスアドレスを持つ領域に負の方向に向かって成長する、というように決めた。こうすると、負のアドレスを持つBFのデータというのは標準的ではないけれども、負のアドレスというものを別とすれば、ライブラリ用データスタックがBFのデータモデルと自然に共存できる。

ちなみに、スタックに引数を積んでいく順番を右から始めるというcdeclなスタイルにしてやれば、printfみたいな可変個引数の関数も呼び出せる。printf関数を持ったBFというのは、ちょっと魅力的ではないだろうか。

--

遅くなったので、続編はまた後日。
[PR]
by antonin | 2012-08-06 01:31 | Trackback | Comments(0)

夜想

なんか、Direct2DだQuartzだ言う前に、Pythonでいいんじゃねぇかという気がしてきた。日本人なら愛国心を発揮してRubyを使うべきところだろうが、Pythonの妙に潔癖なところは嫌いじゃないし、エグいコードを書くならPerlのほうが楽しそうだし、まぁどのみちLLというのはライブラリの質で決まるのだし、webよりスタンドアロンが好きならPythonじゃなかろうかというところに落ち着きつつある。エディタのTAB幅は4でいいんでしょうか。

暇だった頃にライフゲームを触ってグラフィックの伴うプログラミングをリハビリ運転してみたが、エピステーメー師匠がなんだか同じようなことをやっているのを発見した。

.NETでマンデルブロ集合を描く(番外編)(1/3):CodeZine

私の場合は「昔は遅いマシンで頑張ってライフゲームのプログラムを組んだ」「今のマシンなら劇的に早いに違いない」「・・・思った程でもないな」「x64のSSE2でも使うか」となったのだが、師匠の場合は「昔は遅いマシンで頑張ってマンデルブロ集合のプログラムを組んだ」「今のマシンなら劇的に早いに違いない」「・・・思った程でもないな」「OpenCLでGPGPUでも使うか」となって、演算方面では劇的な効果を得られたらしい。複素数だものな、あちらは。表示方面はまだこれからお勉強だそうですので、関心を持ってウォッチ。

--

いつの頃からか、PCで音楽を再生すると妙なイメージ映像が動くようになった。あの手のリアルタイム動画のほとんどはポップスとかロックとかその辺に合わせた作りになっているので、クラシックを再生したりすると間の悪いことになる。なのであまり表示させる機会はなかったのだが、素朴なスペアナ表示に近いモードがあって、しかも分解能がかなり高いので面白いことになっている。弦楽セレナードのように全て同種の弦楽器からなる音色のシンプルな合奏の場合だと、個々のパートが演奏している音が見えてしまったりする。

b0004933_17075.jpg


楽譜も読めないのにスコアを買ってみたりした頃があって、手許にチャイコフスキーの方のスコアが残っている。安敦誌の周辺には音楽に詳しい御仁もいるので下手なことは書けないが、第一ヴァイオリンや第二ヴァイオリンがスプリットする箇所などは確かにスペクトルのピークが分裂スプリットしているのがわかる(ような気がする)。

これがフルオーケストラになったりすると、基本周波数が同じ所に倍音比率の異なる楽器を複数重ねてきたり、シンバルみたいなブロードなピークを持つ楽器が鳴り出すと小さいピークが見えなくなったりして音符の解読は難しくなるのだが、それはそれで今度は楽器ごとのスペクトルパターンが見えて面白い。「打楽器の音色は雑音である」とうような旨が楽典にも書いてあるらしいが、それってスペクトルパターンの話ですよね。昔はPSGで乱数を二値音源に流し込んでノイズを作り、減衰エンベロープをかけてドラム音を作ったりしたものでした。

--

宇都宮にいた頃は11月に入ると帰宅時に車のガラスに霜が降りたものだが、今では電車の中で汗をかいたりしないように注意しないと風邪をひくという生活になった。その前に、今年の11月にはどこにいるものやら皆目見当が付かない。

--

古い知人の名前を検索していると、新聞社と宗教法人と芸能プロダクションの名前が出てくるのだが、どれもこれも、陰と陽の対比のきつい業界だな、という感じがする。

美しいものの周りには、美しさを求めて醜い欲を持った者が集まり、醜い者の周りには取り残されたような清廉さを見出すことがある。もちろんそればかりではなくて、陰陽表裏はコーヒーに浮かべたクリームのように複雑な濃淡を描く。

強い人間がいつも強いわけではなく、弱い人間がいつも弱いわけでもない。そこに、小さな渦が結んでは消える。

--

さて、明日は録画用のハードディスクでも買ってこようか。来月は倹約が必要になるだろう。OSの再インストールなど、手持ちの資産でチマチマした作業をするには良い頃合となるかもしれない。
[PR]
by antonin | 2010-10-26 02:04 | Trackback | Comments(0)

プログラムの話、その後

先日から再開したライフゲームのプロトタイプ作りが、ひとまず動くところまで到達した。15年間のハードウェアの進歩を実感するような高速にはならなかったが、着手した当初の、GDI+を使った絶望的な遅さからはDXライブラリによって解放され、及第点程度の出来にはなった。80x60の小さな領域ながら、ランダムな初期配置から毎秒150世代程度の計算速度が出た。

調子に乗って、試しに800x600としてセル数を100倍に拡大して、そのうちの80x60だけを表示するようにしてみたが、プロトタイプで使った計算モデルがあまり効率の良いものでもないので、かなり残念な速度にまで低下してしまった。次はセルのデータ構造を変更して、もう少し効率の良いものにしてみたい。現代のプロセッサスピードなら1000万セルくらいは実時間で計算できるに違いないので、表示はともかく演算の速度は効率を追求してみたい。

計算のオーダーはセル数に対してO(n)だとして、単純に計算すると最低でもプロトタイプの50倍速程度には加速しないといけない。10メガセルだと、セルをビット表現すれば1280KBに収まる。メモリはふんだんにあるのでデータ容量を節約する意味はないが、データが小さいとプロセッサ上のキャッシュに乗る率も上がるので、計算速度の面から役に立つこともある。それにデータをビット単位にするとビット演算命令が使えるので、レジスタ長に収まる複数セルの計算を同時に処理するアイデアも使える。最終的にはSSE2のSIMD命令を組み立ててコアルーチンを書いてみたい。こういうネタを考えるのは楽しい。

ついでにWindowsのコントロール類やイベントの扱い方を練習しておけば、どこかで何かの役には立つだろう。GUIまわりのプログラミング経験はExcel VBAのフォームで多少練習したくらいだが、今回も全く知識ゼロから手を付けるよりはいくらか理解しやすかった。久しぶりにVisual Studioを触ってみると、デバッグ操作やC++の細かい文法をかなり忘れてしまっていた。覚えるのと違って調べて思い出すのは時間を食わないから、いいリハビリになった。

9月からは1日が24時間に戻りそうな気配もあり、まぁいいんじゃないかな、という具合の今日この頃。
b0004933_22351414.jpg

[PR]
by antonin | 2010-08-21 22:53 | Trackback | Comments(0)


フォロー中のブログ
外部リンク
外部リンク
ライフログ
ブログパーツ
Notesを使いこなす
ブログジャンル