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 に遭遇すると停止します。この際、データの破壊は行われないので、これをうまく使うことで非破壊の分岐を実現することができます。

[>]

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

greater_than 命令

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

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

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

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

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

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

[>]

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 番地で停止します。

>>>   ; 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 ならば繰り返します。

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

; 前処理
[-]>[-]+>[-]+>[-] ; 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 のコードは以下のようになります。

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

less_than 命令

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

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 の否定を取ることで得られます。

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) を計算するためには以下の疑似コードを実装すれば良いです。

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 箇所で条件を計算する必要があります。

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/ )

+[[-]<+]

まとめ

今回は 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 による言語処理系
• 第 1 回: 値のロードとストア
• 第 2 回: 加算, 減算, 乗算
• 第 3 回: bool化, 等値比較
• 第 4 回: 非破壊分岐, 比較, 除算, 剰余算
• 第 5 回: while, if, スコープ内変数
• 第 6 回: 配列, 多次元配列
• 第 7 回: コンパイラと言語仕様