テーマは befunge + π計算。
ちなみにπ計算の知識は sumii 様のπ-calculus 超入門を読んだだけしかない。
以下、befunge はみな知っているものとしています。
基本部分
実行モデルは基本的には befunge で、2 次元上のコードをカーソルが走って fetch しながら実行が進む。初期状態では左上の原点から右方向に向かって走るプロセスが 1 本だけ。各プロセスは数値またはチャンネルからなるスタック (っぽいもの) を持っている。
'|' は fork 。進行方向に対して左右に分かれて走り出す。
v > AAA > | > BBB
上のコードでは、 AAA と BBB を並列実行する。fork したらスタックは全部コピーされる (fork した後でスタックをいじっても、相方のスタックは変化しない) 。
'&' はチャンネルを生成してスタックに乗せる。'!' は送信、'?' が受信。
v > 9 1! AAA
> & |
> ? BBB上のコードは、生成したチャンネルに対して 9 を送信・受信している。まずチャンネルが生成されスタックに詰まれる。その後 fork して、上側に回ったプロセスは 9 をチャンネルに送信する ('9' や '1' はスタックに数字を push する命令。1 は引数の数を表す。つまり複数の値を送信することもできる) 。送信は非同期で、受信しているプロセスがなくても送信する。送信をしたプロセスはそこで実行を終了する (つまり AAA は実行されない) 。一方、下側に回ったプロセスはチャンネルを受信するデータがなかったらブロックする) 。受信すると、チャンネルを pop し、受信した値 (ここでは 9 だけ) を順にスタックに push し、実行が続く (つまり BBB が実行される) 。
複数の引数を送信した場合、引数の順序は受信した方でも保存される。例えば、[C, 1, 2, 2] の状態で送信をし、別プロセスで [C] の状態で受信をした場合、受信プロセスの受信後のスタックは [1, 2] になる。
入出力
入出力はチャンネルへの送受信として行う。実行開始直後のスタックには、標準入出力を表すチャンネルが 1 つだけ乗っている。
まずは出力。出力する文字の ASCII コードと、出力完了イベントを受け取るチャンネルをスタックに載せて標準入出力チャンネルに送信する。
v > 2 5 * \ 2!
> & |
> ? AAA 上のコードは \n (文字コード 10 = 2 * 5) を出力した後 AAA を実行するコード ('\' はスタックの上位 2 個を入れ替える命令) 。出力が完了すると、送信のときに与えたチャンネルが 0 引数で呼ばれる。
入力は入出力チャンネルを受信するだけ。
? AAA
上のコードは 1 文字読み込んでスタックに積んだあと、AAA を実行する。EOF の場合は -1 が読み込まれる。
実行終了
実行を終了させるには 2 つの方法がある。1 つは実行中のプロセスを (送信によって) 全部なくすこと。もう 1 つは -1 を出力すること (このとき他に生きているプロセスがあっても強制的に終了する) 。
& 0 !
0 1 - & 2!
上のコードはどちらも終了するだけのコード。
具体例その 1
そろそろ具体例を出す。以下は echo を行うプログラム。
> v ^ | : ? & 2!
左端のループでプロセスをどんどん複製する。':' はスタックのトップを複製する命令。'?' で標準入出力を受信し、受信した値をそのまま標準入出力に送信する。ただし上の echo にはバグがある。というのは、この echo では出力される文字の順序が保証されていない。受信待機するプロセスは複数あるので、受信した直後でコンテキストスイッチした場合*1、他のプロセスが次の文字を読み込み、先に出力してしまうことがあるからだ。
$ cat foo foo bar baz qux quux $ ./2dpi.rb buggy.2dpi < foo > bar $ cat bar foo bar baz quxquux
落ち穂拾い
正しい echo の前に、befunge と異なる二つの命令 '_' と 'G' を説明する。
'_'が条件分岐。スタックを pop して、その値が 0 だと次のセルの命令をスキップする。
1 _v AAA
> 0 _v BBB
> CCC上のコードだと BBB が実行される。
'G'はスタックの n 番目の値を複製する (!) 。なので、厳密にはスタックではない。
1 2 3 4 5 2G
上のコードを実行した後、スタックには [(stdio), 1, 2, 3, 4, 5, 3] が積まれている。
':' と "0G" は同値。
具体例その 2
まず正しい echo 。
> & v ^ ? | \ : ? 2G 2!
1 文字の出力が終了するまで次のプロセスを起動しないようにしている。
頭のよくない Hello, world!
&v v?|"H"\2! >&v v?|"e"\2! >&v v?|"l"\2! >&v v?|"l"\2! >&v v?|"o"\2! >&v v?|","\2! >&v v?|" "\2! >&v v?|"w"\2! >&v v?|"o"\2! >&v v?|"r"\2! >&v v?|"l"\2! >&v v?|"d"\2! >&v v?|"!"\2! >&v v?|25*\2! >01-&2!
もちろんもっと短く書ける。
ちょっと大きな例で、階乗。π-calculus 超入門の最後に乗っている例をベースに。
v
=== print_int(n, r) ===
> :?\ : _v $ 0! <-- r![]
> | > / 3G 1G 3G 2! <-- print_int[n / 10, c]
& ^ < > & \ 55+ |
> | > % 68* + \ ? 3G \ 2G 2! <-- c? . putc(n % 10 + 48, r)
v <
=== fact(n, r) ===
> 1 1! <-- r![1]
> :? 1G _v^ > 3G 3G 1 - 2G 2! <-- fact![n-1,c]
> | > & |
& ^ < > ? 2G * 1! <-- c?[x] . r![n * x]
> |
v <
=== main ===
& > 5 \ 2! <-- fact![5, c]
> | > 2! <-- c?[x] . print_int[x, c2]
> \$ ? & | > 55+ \ 2! <-- putc[10, c3]
> ? $$ : & |
> ? 01- & 2! <-- putc[-1, _]
Quick Reference
befunge と違うところ。
| ｜ | fork | 90 度曲がった 2 方向に分かれる |
| & | チャンネル生成 | Create new channel, and push it |
| ? | チャンネル受信 | Pop C, receive value A1, A2, ..., AN from C, then push AN, ..., push A2, push A1 |
| ! | チャンネル送信 | Pop N, pop A1, pop A2, ..., pop AN, pop C, send A1, A2, ..., AN to C, then terminate execution |
| _ | 条件分岐 | Pop A, then skip next cell if A == 0 |
| G | n 番目取得 | Pop N, and push the n-th value of the stack ("n-th" は n をポップした後の深さ。トップは 0) |
以下の命令は befunge と同じ。
| 0-9 | 数字リテラル | 数値をスタックに載せる |
| " | 文字列リテラル | 次の"までの文字の ASCII コードを順に push する |
| > | 右 | 右へ進む |
| < | 左 | 左へ進む |
| ^ | 上 | 上へ進む |
| v | 下 | 下へ進む |
| + | 加算 | pop a, pop b, then push (b+a) |
| - | 減算 | pop a, pop b, then push (b-a) |
| * | 乗算 | pop a, pop b, then push (b*a) |
| / | 除算 | pop a, pop b, then push (b/a) |
| % | 剰余 | pop a, pop b, then push (b%a) |
| ` | 比較 | pop a, pop b, then push 1 if b>a, otherwise zero. |
| \ | スワップ | pop a, pop b, push a, push b |
| # | ジャンプ | 次のセルを飛ばす |
| : | 複製 | pop a, push a, push a |
| $ | Discard | pop a |
自己書き換え命令 (befunge では 'p', 'g') はなし*2。これによって各プロセスは一切状態を共有しないはず。Erlang と同じでとてもスケーラブル (笑) 。
befunge の入出力 (',', '.', '~', '&') もなし。数値入出力 ('~' や '.') は、インタプリタを作るのが楽しくないので嫌い。',' や '&' まで削ったのはなんとなく。
ランダム方向に移動 ('?') はあった方がいい？ Haskell でインタプリタ実装するときにめんどうくさいから入れたくないんだけど (笑)
課題
改善案大募集。
Reference Implementation
http://dame.dyndns.org/misc/pefunge/2dpi.rb
設計しながら書いたコードなので工夫はないし、汚いです。1 プロセスを Ruby のスレッドにそのまま割り当てているので、プロセスをどんどん作るようなコードを書くとどんどん重くなります。
$ ./2dpi.rb hello.2dp Hello, world! $ ./2dpi.rb -d hello.2dp | head tid:fdbe53ba6, 0@( 0, 0) stack:[(stdio)] tid:fdbe53ba6, 2@( 1, 0) stack:[(stdio), 0] tid:fdbe53ba6, 5@( 2, 0) stack:[(stdio), 0, 2] ...
おまけ
befunge-93 と違って 80 桁 25 行制限はしないけど、80 桁 25 行で収まった方がかっこいいのは言うまでもないことです (笑) 。
更新履歴
- Reference Implementation のバグをとりました。
- 言語名を pefunge にしました。
- Quick Reference に Discard ('$') を書き忘れていたので追加しました。
- 複数引数を送信したときの挙動 (値の順序) が曖昧だったので修正しました。
*1:実装方法は規定しないため、コンテキストスイッチという表現は必ずしも正しくないが、わかりやすさのため。
*2:まあ別にあってもいいんだけど、befunge の「コンパイルしにくい言語」はテーマじゃないし、絶対座標を指定する API がださくて気に入らないので採用したくない。
