「ほっ」と。キャンペーン

安敦誌


つまらない話など
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
検索
最新の記事
水分子と日本人は似ている
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
光は本当に量子なのか
at 2015-03-17 23:48
自分のアタマで考えざるを得な..
at 2015-03-06 03:57
折り合い
at 2015-03-01 00:19
C++とC#
at 2015-02-07 02:10
浮世離れ補正
at 2015-01-25 01:21
記事ランキング
タグ
(294)
(146)
(120)
(94)
(76)
(64)
(59)
(54)
(45)
(40)
(40)
(39)
(32)
(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
以前の記事

イカれた脳のためのダンス教室(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)
トラックバックURL : http://antonin.exblog.jp/tb/18784258
トラックバックする(会員専用) [ヘルプ]
※このブログはトラックバック承認制を適用しています。 ブログの持ち主が承認するまでトラックバックは表示されません。
<< 人間不信 ニュートリノその後 >>


お気に入りブログ
外部リンク
外部リンク
ライフログ
ブログパーツ
Notesを使いこなす
ブログジャンル