Hatena::ブログ(Diary)

菊やんの雑記帳

2007-06-01 GなしPefunge

[] 14:48 GなしPefunge - 菊やんの雑記帳 を含むブックマーク

pefungeのGはスタックの奥底に眠ってる値をトップにコピーする命令だ。

pefunge自身でGを実装しようとしたときに何が問題になるかというと、スタックの先頭二つしか入れ替えられないことだ。深さnから値を取り出す関数が呼び出された直後のスタック

[…,v3, v2, v1, v0, ret_c, n]

ここで、スタックは右に向かって伸びる。

ret_cは返り値を返すチャンネル。

n=0の場合はスタックを操作して、

[…,v3, v2, v1, ret_c, v0]

とすればよい。これは「$\$」で pop, swap, pop とすればいいので簡単である。

問題は n>0 の場合で、スタック

[…,v3, v2 v1, ret_c, n-1]

のようにしないといけない。これは pop とswap (と先頭から1引く)だけではどう考えても不可能である。

これを解決するためには、ret_c と n をまとめてひとつの値として扱えればいいわけだ。

チャンネルにこの二つをメッセージとして保存しておけば、簡単に実装できる。

まず、「&」で新しいチャンネルをトップに置く

[…,v3, v2, v1, ret_c, n-1, ch]

チャンネルに送信コマンドはスタックに「チャンネル、値、メッセージの長さ」の順で積んでおかないといけないので、並び替えて

[…,v3, v2, v1, ch, ret_c, n-1, 2]

にして「!」を実行すれば、送信できるはずである。

でもこの状態にもっていくのにも先頭二つのスワップでは不可能だ…

そこでチャンネルには一個ずつ送信して値を蓄えておくことにする。まず

[…,v3, v2, v1, ret_c, ch, n-1, 0, 2]

にして ch に (n-1, 0) を送信して、続いて

[…,v3, v2, v1, ch, ret_c, 1, 2]

にして ch に(ret_c, 1) を送信する。1とか0とかを付加して受信したときにどちらかを区別できるようにしてある。

この結果

[…,v3, v2, v1, ch((n-1,0),(ret_c,1))]

となるので、めでたく v1 をスタックから取り除くことができるわけだ。

[…,v3, v2, ch((n-1,0),(ret_c,1))]

次は、チャンネルから n-1 を読み出して、0 と比較すればよい。

しかし、「?」で読み出すと (n-1,0) が読み出させるか (ret_c,1) を読み出せるかは不定である。

なぜかというと、送信の操作は並列で行う以外に方法がないからだ。

片方の送信が終わってから、もう一方を送るなんてことはできない。

しかたがないので、「?」で (ret_c,1) が読み出されたら、それは ch に送信しなおして、もう一回読み出すことになる…

とここまでが昨日実装した「G」の内容で、今日は