西尾泰和のブログ

今朝夢の中で阪神大震災の予震が3倍くらいの長さになったような地震を感じたのだけど、実際に地震があったらしい9時45分には起きていたと思うんだけどな。シャワーを浴びて地震情報を検索している今が9時55分だもの。でも起きているときに地震を感じていないのも考えると…やっぱり寝てたんだろうか？

また洗濯物を干すの忘れて放置してる…。 あと一昨日買った鶏肉のことも忘れてた…。傷むと困るから冷凍庫にいれとこうかな。 今日は早めに帰って一昨日買った野菜を調理しないと。

__ 論文提出完了。

__ Brainf*ckが一部で流行っているみたいなので An introduction to programming in BF へのリンクを張っておきます。

__ 今年度の若手の会(第39回情報科学苔手の会) の申し込み。GRINEdit発表するのも悪くないかもなぁ。

__ 下期の未踏って終わるのが来年の9月末なんですねぇ。思っていたよりも長いです。

__ Boost勉強中、と言ってもC++のBoostではなくAdaBoostですが。

__ 書かないと気になって集中すべきことに集中できないので書いておきます。 PythonBrainf*ckコンパイラの話ですが、一応周囲のコマンドの情報から適切なGoやKillを挟むようにはなったので次はコード内で領域の確保が出来るようにしたいわけです。その為にはどこが破壊していい領域でどこが破壊しては行けない領域かを知る必要性があるわけです。それと、現在は　[ ] を使ったジャンプが生で直接操作されるようになっていますが、これはp回繰り返すTimes命令 [- (command) (go p)] やIf命令(Kazuho@Cybozu Labs: brainf*ck で計算機を参照)を作っておいてそれを使うようにし、生の [ ] はなるべく使わないようにすることで1カ所のミスが全体に波及して困難なバグを生み出す可能性を減らすことが出来ます。 そうすれば、Times命令が使う領域に「破壊禁止」のマークをつけた上でその中身のコマンドをコンパイルすることで中身のコマンドが新しい領域を確保しようとした場合にTimesの作業領域を破壊することが防げます。

デジャヴですね。これぞ構造化プログラミングの誕生です。

必要な変数は最初に全部宣言してしまうタイプの方が、whileやifが現れるたびにその場であいている領域から作業領域を確保する今作っているようなタイプよりも楽でしたね…。

それはさておき、Brainf*ckで特定の数を作るための最小のコマンドは何か、という問題は作業領域として使っていいセルがどこにあるかによって異なりますね。[0]以外は全部使っていいとするのが問題としては一番簡単ですが、コンパイラを作る側としてはそれでは実用性がないわけです。Brainf*ckには元から実用性がないじゃないかというつっこみは禁止。

Cを機械語にするのは機械語コンパイラじゃなくてCコンパイラで、JavaをバイトコードにするのもJavaコンパイラだから、PythonをBrainf*ckにするのはPythonコンパイラ(違う) 任意のPython言語がBrainf*ckになるわけではないので、あくまで「Pythonで実装された小さな言語」のコンパイラなのですね。じゃぁPyBrainf*ckコンパイラって呼ぶことにします。

__ Pythonは2.4あたりから複数同時に起動しようとすると怒るようになったので、 何かプログラムを書いていて時間のかかる処理を実行した後、待ってる間に別のプログラムを書こうとすると対話的に短いコードのテストとかが出来なくて不便です。何とかならないんですかね。 しばらく考えてCygwinのPythonを起動しましたがコピペ出来ないから不便…。

__ おなかすいたなぁ。

__ 腰が痛いなぁ。 いい椅子のはずなのに何故だろう。

__ ふう。そろそろ帰ろうと思ったのでBrainf*ck(ぇ)

もっと完成してからまとめて公開するので今日はクラス定義は全部省きます。

e = Environ()
e.nameSpace.update({"A":0, "B":1, "C":2})
print "".join([x.make() for x in [
	Copy("A", "tmp1", "tmp2"),
	Copy("B", "C", "tmp2"),
	AddTo("tmp1", "C")]])

name tmp1 not found
  alloc. at 3
name tmp2 not found
  alloc. at 4
[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<[>+>>+<<<-]>>>[<<<+>>>-]<[<+>-]

bf = BFInterpreter()
bf.simplify("""
+++>++++< # [0] = 3, [1] = 4
[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<[>+>>+<<<-]>>>[<<<+>>>-]<[<+>-]
(showMem)
""")
bf.runCode()

0 3
1 4
2 7
3 0
4 0

Brainf*ckインタプリタはコードの中に括弧で囲ってデバッグ用のコマンド(メモリダンプやassert, 任意文字列のprintなど)を入れられるようにしました。PyBrainf*ckコンパイラの方は、名前空間を処理系が1つだけ持つ(原始的な)形に変えました。実装がすごく楽でした。

あ、もう8時だ。晩ご飯食べて帰っちゃダメなんだった。野菜と鶏肉が僕を待っている…。

__ ポトフ作りは暑くて大変です。

スープは悪くない味だと思うのだけど(っていうかコンソメだし)タマネギを食べてみると味がしみてないのはなぜでしょうねぇ。もっと煮ないといけないのかなぁ。

そういうわけでさっきからずっとぐつぐつやっています。

__ 出来ました。 これポトフなんでしょうか。 なんか、カレーみたいなにおいがします。カレー粉とかは使っていないのでもちろんそういうにおいではないのですけど「タマネギやニンジンを煮詰めました」というにおいがします。それから何か予想と違ってかなり茶色いです。いわゆるカレーほどではないですけど、こういう色のスープカレーはありそうです。最後に、割と辛いです。コンソメだけではぼんやりした味だったのでこしょうを瓶のふたに半分くらい入れたからだと思います。食べると汗が出ます。

__ Kazuho@Cybozu Labs: brainf*ck でマジメに素数探索

ひゃー。もう解かれちゃいましたか。

こちらの現状は「[1]が[0]で割り切れるかどうかを判定するBrainf*ckコード」を生成するプログラムが出来たところでした。素数への道のりはまだ遠い…。

e = Environ()
e.nameSpace.update({"A":0, "B":1, "Result":2})
print Seq([
    Create("A", 3),
    Create("B", 6),
    Create("toLoop", 1), # True
    While("toLoop", [
        Copy("A", "tmp1", "tmp2"), # free tmp2
        Times("tmp1", [
            If0("B", Dec("toLoop"), "tmp2", "tmp3"),
            Dec("B")]),
        If0("B", Seq([
            Dec("toLoop"),
            Inc("Result")]), "tmp2", "tmp3"),
        ]),
    ]).make()

name toLoop not found
  alloc. at 3
name tmp1 not found
  alloc. at 4
name tmp2 not found
  alloc. at 5
name tmp3 not found
  alloc. at 6

(start_Seq)
  +++>++++++>>+[
  (start_Copy)
    <<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
  (end_Copy)
  <[
  (start_If0)
    (start_Copy)
      <<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
    (end_Copy)
    +<[[-]>-<]>[[-]<<<->>>]
  (end_If0)
  <<<<<->>>-]
  (start_If0)
    (start_Copy)
      <<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
    (end_Copy)
    +<[[-]>-<]>[[-]
    (start_Seq)
      <<<-<+
    (end_Seq)
    >>>>]
  (end_If0)
  <<<]
(end_Seq)

If0("B", Dec("toLoop"), "tmp2", "tmp3"), とかを見ると、どこを作業領域に使うかを人間が指定するのはやっぱり嫌な感じですね。 この「割り切れるかどうか判定」を一つのコマンドにまとめると IsDividable("A", "B", "Result", "tmpToLoop", "tmp1", "tmp2", "tmp3") になります。おぞましい。 作業領域の指定は省略できるようにして、省略した場合は適当に確保することにしましょうかねぇ。 必要になったときにメモリに「使用していますマーク」をつけて、いらなくなったときに「使用していますマーク」を消せばいいんですよね…。

AB間の移動が5回、BC間の移動が4回、CA間の移動が3回ある場合に、移動距離が最短になるようにABCを並べる方法は、っていうとまず一番大きいABを隣接させ、次にCをA側につけるのとB側につけるののどちらがいいかを調べてABCという順に決定されるわけですけど、もっと要素が多くなった場合もそれでいいのかなぁ。いや、違うなぁ。仮にA1からA100までがそれぞれ隣の数と太さ100の辺で繋がっているとして、A100とCが太さ99の辺で繋がっているとするとCはA100の側につけたくなるけど、CがA1,A2,A3のそれぞれと太さ50の辺で繋がっているならCはA1の側に行くべきだもの。難しい問題かも知れない。