今回は以下の命令を実装します。
-
load_constant <imm>- 即値
<imm>をスタックトップにプッシュ
- 即値
-
load_variable <imm>- 即値
<imm>番地から値をコピーし、スタックトップにプッシュ
- 即値
-
store_variable <imm>- スタックトップの値を
<imm>番地に書き込んでポップ
- スタックトップの値を
ポインタ移動と値のインクリメント
< や > をたくさん書いたり、+-をたくさん書くのは面倒なので、以下の関数で略記します。
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: 即値で指定した番地にスタックトップの値を移動
次回は基本的な算術命令、加算、減算、乗算を説明します。
リポジトリ
記事リンク
- 第 0 回: Brainf*ck による言語処理系
- 第 1 回: 値のロードとストア
- 第 2 回: 加算, 減算, 乗算
- 第 3 回: bool化, 等値比較
- 第 4 回: 非破壊分岐, 比較, 除算, 剰余算
- 第 5 回: while, if, スコープ内変数
- 第 6 回: 配列, 多次元配列
- 第 7 回: コンパイラと言語仕様