Brainf*ck による言語処理系 第5回 〜while, if, スコープ内変数〜

今回は演算ではなく、制御に関する命令を実装します。
- `begin_while`, `end_while`
  - スタックトップの値を評価し、0 ならば `begin_while` から `end_while` までを実行
  - 実行終了後に再びスタックトップの値を評価し、`begin_while` に戻る
- `begin_if`, `begin_else`, `end_if`
  - スタックトップの値を評価し、0 ならば `begin_else` から `end_if` までを実行、0 以外ならば `begin_if` から `begin_else` までを実行
- `pop <imm>`
  - `<imm>` 個の領域を配列から削除しデータポインタを `<imm>` 個左に動かす

# while
brainfuck の `[]` は while と似た制御構造ですが、コンパイラを作るにあたってそのまま使うと以下のような不都合があります。
- `[]` の前後でデータポインタの位置が変わってはいけない
- `[]` の対応が取れていなければならない

特に、前者が保証されない場合、while の実行回数に応じてデータポインタ位置が変わってしまい、コンパイラがデータポインタ位置を見失う原因になります。

これを、スタックマシンのアセンブラで保証します。

```python
def begin_while(self):
    assert 0 < self.dp
    self.controlstack += [('while', self.dp)]
    code = '<[[-]'
    self.dp -= 1
    return code

def end_while(self, debug=False):
    assert self.controlstack
    assert self.controlstack[-1][0] == 'while'
    assert self.controlstack[-1][1] == self.dp
    _, dp = self.controlstack.pop()
    code = '<]'
    self.dp = dp - 1
    return code
```

アセンブラに `controlstack` というフィールドを追加し、現在のコンテキストを保持します。
また、`controlstack` で while 開始時のデータポインタ位置を保持し、`end_while` でチェックすることにより while 前後でデータポインタの位置が変わっていないことを保証します。

以下の疑似コードをコンパイルしたとき、生成される Brainf\*ck コードは以下のようになります。

```python
while cond:
    body
```

```brainfuck
push cond
<[[-] ; begin_while
body
push cond
<]    ; end_while
```

評価に用いた値は破壊され、そこに再び条件を積むことになります。

# if

if は必ず else 句付きで使用するものとします。else 句なしの if を使いたいときは単に `begin_else` の直後に `end_if` を使用します。

```python
def begin_if(self, debug=False):
    assert 0 < self.dp
    self.controlstack += [('if', self.dp)]
    code = '+<[[-]>->'
    self.dp += 1
    return code + '\n' if debug else code

def begin_else(self, debug=False):
    assert self.controlstack
    assert self.controlstack[-1][0] == 'if'
    assert self.controlstack[-1][1] == self.dp - 1
    _, dp = self.controlstack.pop()
    self.controlstack += [('else', dp)]
    code = '<<]>[->'
    self.dp = dp + 1
    return code + '\n' if debug else code

def end_if(self):
    assert self.controlstack
    assert self.controlstack[-1][0] == 'else'
    assert self.controlstack[-1][1] == self.dp - 1
    _, dp = self.controlstack.pop()
    code = '<]<'
    self.dp = dp - 1
    return code
```

以下の疑似コードをコンパイルしたとき、生成される Brainf\*ck コードは以下のようになります。

```python
if cond:
    then_
else:
    else_
```

```brainfuck
push cond
+<[[-]>-< ; begin_if
then_
<<]>[->   ; begin_else
else_
<]<       ; end_if
```

else のために、cond の隣に一時領域を設け、1 で初期化します。then 句の最初で一時領域をクリアし、else 句では一時領域を評価します。

# スコープ内変数
前述したとおり、while や if では `[]` の前後でデータポインタが同じ位置である必要があります。即ち、while や if の内部で新しい変数を作ることはできず、新たな変数を作る場合には while や if の前に積んでおく必要があります。

以下のようなコードをコンパイルすることを考えます。
```c
var cond;
while (cond) {
    var a = getint();
    cond = a;
}
```
このとき、while に入ったときのメモリレイアウトは以下のようになります。

| addr | 0        | 1     | 2    | ... |
|------|----------|-------|------|-----|
| data | var cond | var a | cond | ... |

while の body のコード生成の前に、新たな変数を宣言している部分を探索して、予め領域の確保と変数表への登録を行っておきます。

以下はコンパイラ本体の while のコード生成を行うクラスです。

このメソッドでは以下のことを行います。
- body のスコープ変数を探索、確保、変数表に登録
- 条件をプッシュ
- begin_while
- body を生成
- end_while
- 再び条件をプッシュ
- end_while
- スコープ変数を削除

```python
class StWhile(Statement):
    def __init__(self, cond, body):
        self.cond = cond
        self.body = body

    def string(self, level):
        code = f'{indent(level)}while ({self.cond}) {{\n'
        for st in self.body:
            code += st.string(level + 1) + '\n'
        code += f'{indent(level)}}}'
        return code

    def codegen(self, sm, tables, debug): # while のコード生成を行うメソッド, sm はスタックマシンアセンブラのインスタンス, tables は変数表
        base = sm.dp
        lvars = {} # ローカル変数表
        code = ''
        for st in self.body: # while のスコープ変数を宣言している部分を探索
            if isinstance(st, StInitVariable) or isinstance(st, StInitArray):
                code += st.allocate(sm, tables + [lvars], debug) # 領域の確保と変数表への登録
        size = sm.dp - base # while スコープ変数の合計サイズ
        code += self.cond.codegen(sm, tables + [lvars], debug) # 条件を積む
        code += sm.begin_while(debug)
        for st in self.body: # body の生成
            code += st.codegen(sm, tables + [lvars], debug)
        code += self.cond.codegen(sm, tables + [lvars], debug) # 再び条件を積む
        code += sm.end_while(debug)
        code += sm.pop(size, debug) # スコープ変数を削除
        return code
```

スコープ変数の削除にあたって、指定したサイズだけ領域をクリアしてデータポインタを左に動かす `pop` 命令を実装しています。以下のように実装できます。

```python
def pop(self, size):
    self.dp -= size
    return '<[-]' * size
```

# まとめ
今回は while や if といった制御構造と、スコープ変数の扱いについて述べました。
- `begin_while`, `end_while`
- `begin_if`, `begin_else`, `end_if`
- `pop <imm>`

次回は配列と多次元配列について解説します。

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