西尾泰和のブログ

今朝ナカバヤシから製本された論文が届きました。昨日送ったメールにはまだ返事が来ていません。見事なまでのすれ違いです。(というか発送した時点で連絡くれればよかったのに)

Brainf*ckは、破壊しても構わないtemporary memoryをどこに置くのかの調整が重要ですね。使用期間が重ならない処理は同じ場所をテンポラリに使って構わないですし、テンポラリメモリの位置が離れているとステップ数も増えるのできれいに分けるよりも混ざっていた方が実行効率は高いですし。どのメモリがどの期間で使用されているかを理解して適切な位置にテンポラリを作ってくれるといいですね。

PythonによるBrainf*ckインタプリタ @ NISHIO HIROKAZU # Archived COREBlog。アーカイブのpreタグがもれなく1行とばしになってますね。やっかいだなぁ。そしてバグいりのインタプリタなので直したくなってきた、やばい、そんなことをしている場合ではない。

__ @柏

携帯の充電ケーブルを忘れてしまいました。まぁ、電話は明日すればいいか。

暑いですね。暑いけども、夜に冷房で体をこわさないように長袖を持ち歩かないと行けないのが面倒です。3年間通学をしてなかったので忘れてました。

__ 行きの電車の中で考えたことをメモしときます。 Brainf*ckは、本当の機械語よりも遙かにシンプルで、チューリングマシンよりは高級なので、名前さえ別のものだったら高校や大学の情報系の授業で使われていたかも知れませんね。「Brainf*ckのコードをいかにして生成するか」と考えていくと、過去のプログラミング言語の進化を追体験することが出来て興味深いです。

まず真っ先に考えたのは、アドレス位置の抽象化です。同じ「足し算をする」というコードでも、入力セルがどこで出力セルがどこかによって、コード中の「移動命令(「>」や「<」)」の個数が変わります。でもこれは本質的ではなく、アドレス位置に名前をつけて(add A B)と言うような表現をしても内部でAとBの位置関係から適切な個数の移動命令を生成することが容易に出来ます。擬似コードで書くとこう。

def move(A, B):
  "AからBへカーソルを移動する"
  before:
    assert cur == A
  do: (略)
  after:
    assert cur == B

次に、オブジェクトの生成と消滅に関して。create(A, n) と kill(A) が必要だと思います。

def create(A, n):
  "セルAの値をnにする。"
  destructive: [A] # 破壊されるセルのリスト
  before:
    assert A == 0
    assert cur == A
  do:
    return "+" * n  # 将来的にはもっと効率的な実装に変えることも可能だがとりあえずこれでOK
  after:
    assert A == n
    assert cur == A


def kill(A):
  "セルAを0にする。"
  destructive: [A]
  before:
    assert cur == A
  do:
    return "[-]"
  after:
    assert A == 0
    assert cur == A

説明が遅れましたが、before節の中でのassertはそのコードが実行される前に満たされているべき条件、after節の中でのassertはそのコードが実行された後に満たしているべき条件です。たとえばある命令のafterでcur == Aと宣言されており、その次の命令のbeforeでcur == Bが宣言されているなら、間に(move A B)を挟む必要があります。これは人間の頭を患わせなくても機械的に判断できますし、機械的に解決できる作業です。他にassert A == 0 というのもありますが、これが満たされていない場合には(kill A)を呼べばいいわけです。各命令は破壊するセルのリストを持っていますが、これは「その命令を包む命令」がセルを確保する場合には破壊されないセルを確保する必要があるからです。

さて、破壊の話が出ましたけど、Brainf*ckでの演算は基本的に破壊的です。関数型言語が副作用のない演算を追い求めたり、他の言語でもスコープを限定したりカプセル化したりして破壊を防ごうという努力がされてきたりしたのですが、基本はやっぱり破壊なのです。世界は破壊の中から生まれた(ぇ)

冗談はさておき、生成されたオブジェクトが演算のたびに破壊されるとなると、「破壊されたくないシチュエーション」で困るわけです。そういう場合に必要なのがcloneによるオブジェクトの複製です。

def clone(A, B, C):
  "セルAの内容をBとCに複製する"
  destructive: [A, B, C]
  before:
    assert cur == A
    assert B == 0
    assert C == 0
  do:
    return "[- (move A B) + (move B A) + (move C A)]"
  after:
    assert cur == A
    assert A == 0

たとえば足し算addは

def add(A B):
  "A+Bの結果をBに入れる"
  destractive: [A, B]
  before:
    assert cur == A
  do:
    return "[- (move A B) + (move B A)]"
  after:
    assert cur == A
    assert A == 0

とりあえず出勤途中の電車でメモ帳に手書きした内容はデジタル化出来たので続きは帰りの電車ででも考えることにしましょう。とりあえずアドレスのエイリアスとして生まれた変数はポインタへと進化する必要があるのが1点と、他のコードに副作用を及ぼさずに使うことの出来るテンポラリ領域を取得するための関数allocateが必要です。

__ 遅めの昼ご飯食べながら考えたのですが、Brainf*ckでエラトステネスの篩を実装するくらいはわざわざBrainf*ckを出力するプログラムを作らなくても作れそうな気がしますね。 どっちが大変なのかはよくわからないですけど、でも一度Brainf*ckジェネレータを作っておけばネタとして何度も使い回せそうです。Don't Repeat Yourselfですね。

__ 今日は携帯の充電器を忘れただけにとどまらず、上着も持ってくるのを忘れたようです。

はさみも持ってくるのを忘れました…。

__ 暑いけど席が冷房の直撃する場所なので冷房をつけると寒い。

帰りの電車の中で考えたBrainf*ckの続き。 とりあえず(move A B)は(move B)だけでいいですね。あと、セルが持ちうる値を「正の整数」とすると演算が閉じていないです。つまり0をデクリメントしたときに問題が起きます。そこで「整数」にすると今度はkillの実装が"[-]"ではダメになります。元の数が負の数の場合に問題が起きますから。でもそれでも別に頑張れば実装は出来るからいいのか…とか思ったのですが、WikipediaのBrainfuckの記事が正しければbyte型なので255をインクリメントすると0になる仕様だと考えるべきかも知れませんね。

Index of /brainfuck/compiled/winの実装では確かに255を超えた場合に0にリセットされてますね。でもこれメモリの内容を見る機能がないんですね、使いにくいです。

とりあえず今ちょっと昔書いたインタプリタをいじって、byteとかループのネストとかがきちんと動くバージョンを作ってみました。[]の仕様を誤解してましたね。英語版Wikipediaのプログラムが動いたので今回は正しいと思います。

__

>>> Move(frm = 3, to = 1).make()
'>>>[-<<+>>]'
>>> Move(frm = 1, to = 2).make()
'<<[->+<]'

class Move(Command):
    "Move(frm, to)"
    beforeCur = "frm"
    afterCur = "frm"
    destructive = "frm to"
    beforeZero = "to"
    afterZero = "frm"

    def do(self):
        result =  "".join(["[-",
         Go(to = self.args["to"]).make(),
         "+",
         Go(to = self.args["frm"]).make(),
         "]"])
        return result

寝ようっと。