Brainf*ck による言語処理系第2回〜加算, 減算, 乗算〜

Last updated at 2025-02-28Posted at 2025-02-28

今回は基本的な算術演算命令を実装します。
これらは前回説明した値の移動などのテクニックを使って実装できます.

add
- スタックトップの 2 数をポップし、その和をプッシュ
subtract
- スタックトップの 2 数をポップし、2 番目から 1 番目を引いたものをプッシュ
multiply
- スタックトップの 2 数をポップし、その積をプッシュ

`add` 命令

前回説明した足し算を用いて実装します。

<       ; スタックトップに移動
[-<+>]  ; スタックトップの値をスタックの 2 番目に加算

自動生成するコードは以下です。データポインタは差し引き 1 減ります。

def add(self):
    assert 1 < self.dp
    self.dp -= 1
    return '<[-<+>]'

`subtract` 命令

足し算を引き算にするだけで実装できます。

<       ; スタックトップに移動
[-<->]  ; スタックトップの値をスタックの2番目に対して減算

自動生成するコードもほぼ同じです。

def mul(self):
    assert 1 < self.dp
    self.dp -= 1
    return '<[-<->]'

`multiply` 命令

multiply 命令は、スタックトップの 2 数をポップした上、その積をプッシュします。

ここでは、以下の状態を初期状態とし、A * B を計算します。
2 番地と 3 番地を一時領域として使用するので 0 で初期化しておきます。

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

ステップ 1: 以下のステップ 2, 3 を 1 番地が 0 になるまで繰り返します。

ステップ 2: まず B から 1 引いて A を 2 番地と 3 番地に加算します。

addr	0	1	2	3
data	0	B-1	A	A

ステップ 3: 次に A を 3 番地から 0 番地に戻します。

addr	0	1	2	3
data	A	B-1	A	0

以上 2 ステップを 1 番地が 0 になるまで行うと 2 番地に積が格納されます。

addr	0	1	2	3
data	A	0	A * B	0

ステップ 4: 0 番地を 0 でクリアして、2 番地の値を移動すると完了です。

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

[-]>[-]            ; 一時領域のクリア
<<                 ; スタックトップに移動
[                  ; ステップ 1: スタックトップが 0 でない間実行
    -              ; ステップ 2: スタックトップを 1 減らす
    <              ; ステップ 2: スタックの 2 番目に移動
    [->>+>+<<<]    ; ステップ 2: スタックトップの隣 2 つにに値を加算
    >>>            ; ステップ 3: 一時領域に移動
    [-<<<+>>>]     ; ステップ 3: スタックの 2 番目に値を復元
    <<             ; スタックトップに移動
]                  ; ステップ 1: スタックトップが 0 ならば終了
<                  ; ステップ 4: スタックの 2 番目に移動
[-]                ; ステップ 4: 結果を格納するためにスタックの 2 番目だった場所をクリア
>>                 ; ステップ 4: 結果が格納されている場所に移動
[-<<+>>]           ; ステップ 4: 結果を移動
<                  ; 新しいスタックトップの一つ隣に移動

自動生成するコードは以下のようになります。

def multiply(self, debug=False):
    assert 1 < self.dp
    self.dp -= 1
    return '[-]>[-]<<[-<[->>+>+<<<]>>>[-<<<+>>>]<<]<[-]>>[-<<+>>]<'

まとめ

今回は以下の命令を説明しました。

add: 加算
subtract: 減算
multiply: 乗算

次回は除算ではなく、先に bool 命令と等値比較について説明します。

リポジトリ

https://github.com/void-hoge/brainfuck

記事リンク

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Brainf*ck による言語処理系 第2回 〜加算, 減算, 乗算〜

add 命令

subtract 命令

multiply 命令

まとめ