Brainf*ck による言語処理系 第4回 〜非破壊分岐, 比較, 除算, 剰余算〜

今回は比較演算と、それを使った除算と剰余算命令を実装します。
- `greater_than`, `less_than`, `greater_or_equal`, `less_or_equal`
  - スタックトップの 2 数の比較命令
- `divide`
  - スタックトップの 2 数をポップして、2 番目を 1 番目で割った商をプッシュ
  - (スタックトップ (除数) が 0 の場合は停止しないものとする)
- `modulo`
  - スタックトップの 2 数をポップして、2 番目を 1 番目で割った剰余をプッシュ
  - (スタックトップ (除数) が 0 の場合は停止しないものとする)
  
# 実装方針

`greater_than` の否定が `less_or_equal` であり、`less_than` の否定が `greater_or_equal` であることが利用できるので、`greater_than` と `less_than` を実装すれば他も実装できます。

`greater_or_equal` が実装できれば、「A >= B の間 A から B を引き続ける」という処理で除算と剰余算が実装できます。

`greater_than` (A > B) ですが、「A と B の少なくとも一方が 0 になるまで、両方から 1 を引き続ける」という処理を実行した後、A の値に `boolean` を適用すると得られます。逆に `less_than` は B に `boolean` を適用すると得られます。


# 非破壊分岐

前回解説した Brainf\*ck の if 文は、評価に使用した変数を破壊 (0 でクリア) してしまいます。`greater_than` は 1 を引くたびに比較を行わなければならないため、この方法では毎回コピーする必要があり効率がよくありません。そこで、値を破壊せずに分岐を実現する方法を考えます。

以下のコードを実行すると、データポインタが指す値が 0 でない間、ポインタを右に動かし続け、初めて 0 に遭遇すると停止します。この際、データの破壊は行われないので、これをうまく使うことで非破壊の分岐を実現することができます。

```brainfuck
[>]
```

ただしこのような方法は、データポインタの位置によって結果を表現しますが、実行中にデータポインタ位置を直接知る方法はないので工夫が必要です。また、これを実行すると結果によってデータポインタ位置が動的に変わってしまうのも問題なので、データポインタを静的な位置に回収する仕組みも必要です。

# `greater_than` 命令

以下の状態から始めて、最終的に 0 番地に (A > B) の結果が格納され、1 番地で停止するようにします。

| addr | 0 | 1 | (2) | 3 |
|------|---|---|-----|---|
| data | A | B | 0   | 0 |

基本的な方針は、「A か B の少なくとも一方が 0 になるまで 1 を引き続け、A の値に boolean を適用」となります。

以下の疑似コードで表現される処理を実現します。

```python
def gt(A, B):
    while A and B:
        A -= 1
        B -= 1
    return bool(A)
```

ここで「A か B の少なくとも一方が 0 になるまで」を判定するために非破壊分岐を使います。
まず、配列を以下の状態にします。

| addr | (0) | 1 | 2 | 3 | 4 | 5 |
|------|-----|---|---|---|---|---|
| data | A   | B | 0 | 1 | 1 | 0 |

ここで、A と B の状態は以下の 4 通りが考えられます。なお、A と B が 1 以上の場合もありますが、1 と区別する必要はないのでここでは 1 とします。最初、データポインタは 0 番地にあるものとします。また、比較プロセスを継続すべきかどうかを continue? で表します。上 3 つは少なくとも一方が 0 なので停止し、下 1 つは両方とも 1 なので継続 (A と B から 1 を引いて再び判定) します。


| addr  | 0   | 1 | 2 | 3 | 4 | 5 | continue? |
|-------|-----|---|---|---|---|---|-----------|
| data0 | (0) | 0 | 0 | 1 | 1 | 0 | No        |
| data1 | (0) | 1 | 0 | 1 | 1 | 0 | No        |
| data2 | (1) | 0 | 0 | 1 | 1 | 0 | No        |
| data3 | (1) | 1 | 0 | 1 | 1 | 0 | Yes       |

この状態で、先程のコードを実行するとそれぞれ以下の状態で停止します。

```brainfuck
[>]
```

| addr  | 0   | 1   | 2   | 3 | 4 | 5 | continue? |
|-------|-----|-----|-----|---|---|---|-----------|
| data0 | (0) | 0   | 0   | 1 | 1 | 0 | No        |
| data1 | (0) | 1   | 0   | 1 | 1 | 0 | No        |
| data2 | 1   | (0) | 0   | 1 | 1 | 0 | No        |
| data3 | 1   | 1   | (0) | 1 | 1 | 0 | Yes       |

ここで、それぞれのシナリオでデータポインタの位置に違いが発生しました。このデータポインタ位置の差を、どうにかセルの値に反映することにより比較を実現します。

この状態では、データポインタの位置はバラバラになっているので、どこかに回収する必要があります。
以下のコードでデータポインタをそのまま 3 つ右に (3 4 5 番地のいずれかに) 移動し、3 4 番地の 1 を破壊して 5 番地で停止します。

```brainfuck
>>>   ; 3 4 5 番地のいずれかに移動
[->]  ; 3 4 番地の 1 を破壊しながら 5 番地で停止する
```

| addr  | 0 | 1 | 2 | 3 | 4 | 5   | continue? |
|-------|---|---|---|---|---|-----|-----------|
| data0 | 0 | 0 | 0 | 0 | 0 | (0) | No        |
| data1 | 0 | 1 | 0 | 0 | 0 | (0) | No        |
| data2 | 1 | 0 | 0 | 1 | 0 | (0) | No        |
| data3 | 1 | 1 | 0 | 1 | 1 | (0) | Yes       |

ここで、4 番地が continue? と一致していることがわかり、比較結果をセルの値として取り出すことができました。4 番値の値が 1 ならば A と B (0 番地と 1 番地)から再び 1 を引いて、4 番地が 1 ならば繰り返します。

全体のコードは以下のようになります。

```brainfuck
; 前処理
[-]>[-]+>[-]+>[-] ; 2 3 4 5 番地を初期化
<                 ; 4 番地に移動
; メインループ
[                 ; 4 番地が 1 の間繰り返す
    <<<<          ; 0 番地に移動
    [>]           ; 0 1 2 番地のどこかで停止
    >>>           ; 3 4 5 番地のどこかで停止
    [->]          ; 初期化した 1 を破壊しながら 5 番地で停止
    <<<<-<-       ; 1 番地と 0 番地から 1 を引く
    >>>>          ; 4 番地にもどる
]
; 後処理    
<[-]              ; 3 番地のゴミを掃除
<<[-]            ; 1 番地は使わないので掃除
<+                ; 0 番地の結果は 1 回過剰に引かれて 0 → 255、 1 → 0 になっているので 1 足してもどす
[[-]>+<]          ; 0 番地に boolean を適用
>[-<+>]           ; 1 番地に結果が出てくるので 0 番地に移動
```

Python のコードは以下のようになります。
```python
def greater_than(self):
    assert 1 < self.dp
    self.dp -= 1
    code = '[-]>[-]+>[-]+>[-]<'           # 前処理
    code += '[<<<<[>]>>>[->]<<<<-<->>>>]' # メインループ
    code += '<[-]<<[-]<+[[-]>+<]>[-<+>]'  # 後処理
    return code
```

# `less_than` 命令

ほぼ `greater_than` と同様ですが後処理に若干違いがあり、こちらは 1 番地を結果として利用します。

```python
def greater_than(self):
    assert 1 < self.dp
    self.dp -= 1
    code = '[-]>[-]+>[-]+>[-]<'           # 前処理
    code += '[<<<<[>]>>>[->]<<<<-<->>>>]' # メインループ
    code += '<[-]<<+<[-]>[[-]<+>]'        # 後処理
    return code
```

# `greater_or_equal`命令, `less_or_equal` 命令

`greater_or_equal` は `less_than` の否定、`less_or_equal` は `greater_than` の否定を取ることで得られます。

```python
def greater_or_equal(self):
    assert 1 < self.dp
    code = self.less_than()
    code += self.boolnot()
    return code

def less_or_equal(self):
    assert 1 < self.dp
    code = self.greater_than()
    code += self.boolnot()
    return code
```

# `modulo` 命令, `divide` 命令

`greater_or_equal` が実装できているので剰余算や除算の実装は簡単です。(A % B), (A / B) を計算するためには以下の疑似コードを実装すれば良いです。

```python
def modulo(A, B):
    while A >= B:
        A -= B
    return B

def divide(A, B):
    C = 0
    while A >= B:
        A -= B
        C += 1
    return C
```

以下のコードで剰余命令と除算命令が実装できます。比較命令は破壊的なので、毎回 A と B をコピーする必要があります。また、while は入るときと出るときの 2 箇所で条件を計算する必要があります。

```python
def modulo(self):
    assert 1 < self.dp
    # 前処理
    # A と B を隣にコピー
    code = '<<[->>+>+<<<]'
    code += '>>>[-<<<+>>>]'
    code += '<<[->>+>+<<<]'
    code += '>>>[-<<<+>>>]'
    self.dp += 1
    code += self.greater_or_equal()
    code += '<'
    # メインループ (A -= B を計算し、A <= B を計算するためにコピー)
    code += '[-<'
    code += '[-<->>+>+<<]'
    code += '>[-<+>]'
    code += '<<[->>+>>+<<<<]'
    code += '>>>>[-<<<<+>>>>]'
    self.dp += 1
    code += self.greater_or_equal()
    code += '<]'
    # 後処理
    code += '<[-]'
    self.dp -= 1
    return code

def divide(self):
    assert 1 < self.dp
    # 前処理 (A と B を隣にコピー、C を初期化)
    code = '<<[->>>+>+<<<<]'
    code += '>>>>[-<<<<+>>>>]'
    code += '<<<[->>>+>+<<<<]'
    code += '>>>>[-<<<<+>>>>]'
    self.dp += 1
    code += self.greater_or_equal()
    code += '<'
    # メインループ (C をインクリメントし、A -= B を計算、A <= B を計算するためにコピー)
    code += '[-<'
    code += '+<'
    code += '[-<->>>+>+<<<]'
    code += '>>[-<<+>>]'
    code += '<<<[->>>+>>+<<<<<]'
    code += '>>>>>[-<<<<<+>>>>>]'
    self.dp += 1
    code += self.greater_or_equal()
    code += '<]'
    # 後処理
    code += '<<[-]<[-]'
    code += '>>[-<<+>>]<'
    self.dp -= 1
    return code
```

## 0 除算の扱い
この Brainf\*ck コードで除数が 0 の場合は実行が停止しません。疑似コードを見れば明らかですが、A の値が変化しないため永遠に条件を満たし続けます。

ただし、やろうと思えば実行時エラーにする方法もないわけではありません。例えば、以下のコードを実行すると、どのような状況でも負番地へのアクセスが発生し、負番地へのアクセスが禁止された処理系ならば必ずエラーになります。
(なお、負番地へのアクセスがエラーになるかどうかは実行系に依存するようです。https://kmyk.github.io/blog/blog/2016/03/21/brainfuck-on-services/ )

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

# まとめ
今回は Brainf\*ck における非破壊の分岐と、それを用いた比較演算、さらにそれを使った除算と剰余算を解説しました。
- `greater_than`, `less_than`, `greater_or_equal`, `less_or_equal`
- `divide`, `modulo`

次回は if や while 等の制御文について解説します。

# リポジトリ
- 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)