ポインタ移動と値のインクリメント

< や > をたくさん書いたり、+-をたくさん書くのは面倒なので、以下の関数で略記します。

def mvp(num): # num 個移動する。正は右、負は左
    if num < 0:
        return '<' * -num
    else:
        return '>' * num


def inc(num): # num 足す
    if num < 0:
        return '-' * -num
    else:
        return '+' * num

`load_constant` 命令

この命令を実行すると、オペランドとして与えられる即値をスタックトップに積みます。

命令はこのような形になります。

[-]     ; 値のクリア
+++++++ ; imm 回インクリメント
>       ; データポインタを一つ上に移動

この方法では、値の大きさと同じ数の + を書く必要があり、その分コードが長くなります。
乗算等を用いてコード長を最小化するような実装も考えられますが、簡単のため最小化は考えません。
また、連続した +/- や >/< を圧縮して実行するインタプリタも多いため、こちらの方が性能も出やすい気がします。

コード生成を行う Python のコードは以下のようになります。

def load_constant(value):
    return f'[-]{inc(value)}>'

値の移動

load_variable を実装する前に、Brainf*ck における基本的なイディオムである値の足し算 (移動) について説明します。

以下のコードで、現在のデータポインタの位置の値を一つ右のセルに加算することができます。
また、移動先がもともと 0 ならば移動したことになります。
処理としては現在の値が 0 になるまで、現在の値から 1 引いて隣の値に 1 足すことを繰り返します。

[->+<]

例えば、データ配列が以下のような状態で、データポインタが 0 にあるとします (() でデータポインタの位置を示します) 。

addr	(0)	1	2	3
data	10	0	0	0

上記のコードを実行すると、このような状態になって停止します。

addr	(0)	1	2	3
data	0	10	0	0

足し込む先を複数にすることもできます。最初の状態から、以下のコードを実行すると、次の状態になって停止します。

[->+>+<<]

addr	(0)	1	2	3
data	0	10	10	0

さらに、ポインタを 2 個右に動かして、2 番地から 0 番地に値を移動します。

[->+>+<<]
>>
[-<<+>>]

addr	0	1	(2)	3
data	10	10	0	0

これにて、0 番地から 1 番地への値のコピーがめでたく実現できました。これを使って load_variable 命令と store_variable 命令を実装します。

ここで、複数宛先の加算を行う Brainf*ck コードを生成する関数を作っておきます。この関数には複数の足し算の宛先を、現在との相対位置で表したリストで与えます。

def multi_dst_add(dsts):
    assert dsts # 1 つ以上の宛先が必要
    assert 0 not in dsts # 宛先に自分を含めることはできない
    data = sorted(set(dsts)) # 行ったり来たりするのは無駄なので、単調増加列になるようにしておく
    ascending = [data[i + 1] - data[i] for i in range(len(data) - 1)] # 最初の場所からの増加分のリストにする
    begin = data[0]
    code = ''
    code += f'[-{mvp(begin)}+' # 自身から 1 引いて最初の場所に移動し、1足す
    ret = begin
    for diff in ascending: # 2 個目以降の場所に足す
        ret += diff
        code += f'{mvp(diff)}+'
    code += f'{mvp(-ret)}]' # 開始番地に戻る
    return code

例えば、 multi_dst_add([1, 2]) == '[->+>+<<]' です。

`load_variable` 命令

この命令を実行すると、オペランドで示される即値の番地の値をスタックトップにロード (コピー) します。

式の中で登場する変数の値はこの命令でスタックトップにロードします。例えばa + b は「a をロード」「b をロード」「加算」の命令列で実現できます。

前回触れたとおり、Brainf*ck では相対アドレッシングしかできません。できる操作は「現在のポインタ位置から定数個離れた位置に移動する」このとのみです。一方、コンパイラの変数テーブルはどうしても絶対番地を保持する必要があり、この間を取り持つ必要があります。

そこで、今回のスタックマシンにおいては、命令の実行時のポインタ位置を把握しておき、そこから相対アドレスを計算します。また、実行時にデータポインタの位置が決まる命令を許さず、データポインタ位置が静的に定まる命令のみを実装します。

スタックマシンをクラスにし、self.dp に最後に生成した命令の実行後のポインタ位置を持っておきます。最初はなんの命令も実行していないのでポインタ位置は 0 番地です。また、load_constant 命令を実行するとスタックに値が 1 つ積まれるので self.dp の値を 1 増やしています。

class StackMachine:
    def __init__(self):
        self.dp = 0 # データポインタの位置

    def load_constant(self, value):
        self.dp += 1
        return f'[-]{inc(value)}>'

load_variable 命令は以下のようになります。一時領域として開始番地の一つ右を使います。

def load_variable(self, pos):
    assert 0 <= pos < self.dp # データポインタより右の場所は指定できない.
    rpos = pos - self.dp # 相対アドレスを計算
    code = '>[-]<' # 一つ右をクリアする
    code += mvp(rpos) # ロードする値の場所に移動
    code += multi_dst_add([-rpos, -rpos + 1]) # 開始番地とその一つ右に移動
    code += mvp(-rpos + 1) # 開始番地の一つ右に移動
    code += multi_dst_add([rpos - 1]) # もとのアドレスにコピー
    self.dp += 1 # データポインタを 1 つ増やす
    return code

`store_variable` 命令

store_variable 命令はコピーを意識する必要がないので簡単ですが、一旦値のクリアを行う必要があります。

def store_variable(self, pos):
    assert 0 <= pos < self.dp # データポインタより右の場所は指定できない.
    rpos = pos - self.dp # 相対アドレスを計算
    code += mvp(rpos - 1) # ストア先に移動
    code += '[-]' # ストア先をクリア
    code += mvp(-rpos) # スタックトップに移動
    code += multi_dst_add([rpos]) # 値を移動
    self.dp -= 1 # スタックトップを移動
    return code

まとめ

今回は Brainf*ck の値の移動イディオムと、以下の命令を説明しました。

load_constant: 定数のロード
load_variable: 即値で指定した番地から値をコピー
store_variable: 即値で指定した番地にスタックトップの値を移動

次回は基本的な算術命令、加算、減算、乗算を説明します。

リポジトリ

https://github.com/void-hoge/brainfuck

記事リンク