Brainf*ck による言語処理系 第1回 〜値のロードとストア〜

今回は以下の命令を実装します。
- `load_constant <imm>`
  - 即値 `<imm>` をスタックトップにプッシュ
- `load_variable <imm>`
  - 即値 `<imm>` 番地から値をコピーし、スタックトップにプッシュ
- `store_variable <imm>`
  - スタックトップの値を `<imm>` 番地に書き込んでポップ
  
# ポインタ移動と値のインクリメント
`<` や `>` をたくさん書いたり、`+-`をたくさん書くのは面倒なので、以下の関数で略記します。
```python
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` 命令
この命令を実行すると、オペランドとして与えられる即値をスタックトップに積みます。

命令はこのような形になります。
```brainfuck
[-]     ; 値のクリア
+++++++ ; imm 回インクリメント
>       ; データポインタを一つ上に移動
```
この方法では、値の大きさと同じ数の `+` を書く必要があり、その分コードが長くなります。
乗算等を用いてコード長を最小化するような実装も考えられますが、簡単のため最小化は考えません。
また、連続した `+`/`-` や `>`/`<` を圧縮して実行するインタプリタも多いため、こちらの方が性能も出やすい気がします。

コード生成を行う Python のコードは以下のようになります。
```python
def load_constant(value):
    return f'[-]{inc(value)}>'
```

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

以下のコードで、現在のデータポインタの位置の値を一つ右のセルに加算することができます。
また、移動先がもともと 0 ならば移動したことになります。
処理としては現在の値が 0 になるまで、現在の値から 1 引いて隣の値に 1 足すことを繰り返します。
```brainfuck
[->+<]
```
例えば、データ配列が以下のような状態で、データポインタが 0 にあるとします (() でデータポインタの位置を示します) 。

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

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

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


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

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

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

```brainfuck
[->+>+<<]
>>
[-<<+>>]
```

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

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

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

```python
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 増やしています。
```python
class StackMachine:
    def __init__(self):
        self.dp = 0 # データポインタの位置

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

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

```python
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` 命令はコピーを意識する必要がないので簡単ですが、一旦値のクリアを行う必要があります。

```python
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

# 記事リンク
- 第 0 回: [Brainf\*ck による言語処理系](https://qiita.com/voidhoge/items/672d56a512eaa4c0e7b9)
- 第 1 回: [値のロードとストア](https://qiita.com/voidhoge/items/d9b9fcc6efe1017a0a7b)
- 第 2 回: [加算, 減算, 乗算](https://qiita.com/voidhoge/items/e175a5b19793c6711ec2)
- 第 3 回: [bool化, 等値比較](https://qiita.com/voidhoge/items/c414a0791ed53da3db70)
- 第 4 回: [非破壊分岐, 比較, 除算, 剰余算](https://qiita.com/voidhoge/items/317ee453d0cbe0339939)
- 第 5 回: [while, if, スコープ内変数](https://qiita.com/voidhoge/items/ebf91788b953b900cfac)
- 第 6 回: [配列, 多次元配列](https://qiita.com/voidhoge/items/3374976e70976705b523)
- 第 7 回: [コンパイラと言語仕様](https://qiita.com/voidhoge/items/e553220edc255c7fb508)