ゼロから始める Brainf*ck 互換言語制作 第3回

第0回 はじまり
第1回 メモリの使い方の決定・実行部分の作成
第2回 関数を呼ぶために

第3回 実行部分の続き（前編）

第2回で決めた命令セットを実行するような BF のコードをひたすら書いていきます。命令を読み取って switch する部分は第1回で書いたので、今回はその続きです。また、型については深く考えずに、unsigned char（0～255）のみとします。

スタック操作系

push

スタックに値をプッシュします。唯一後ろに即値が続く命令です。

+<<<<             inc pc
>[->+>+<<]<       move i_v1 to i_v2 and i_v3
>>>[-<<+>>]<<<    move i_v3 to i_v1
>>[<<             while i_v2 {
  >>>>[>>>>]        @ sp
  >+<               inc s_v1
  <<<<[<<<<]        @ pc
  >>-<<             dec i_v2
>>]<<             }
>>>>[>>>>]        @ sp
+                 inc sp
[<<<<]            @ pc
+<<<<             inc pc

計算量：プッシュする値を $N$、PC と SP の距離を $D$ として、$O(ND)$

pop

スタックから値をポップします。

>>>>[>>>>]<<<<    @ st
>[-]<             clear s_v1
-                 dec st
<<<<[<<<<]        @ pc
+<<<<             inc pc

計算量：ポップする値を $N$、PC と SP の距離を $D$ として、$O(N+D)$

演算系

add

足し算です。

イメージ

r = pop()
l = pop()
push(l + r)

>>>>[>>>>]<<<<    @ st
>[<               while s1v1 {
  >-<               dec s1v1
  <<<<              @ s2
  >+<               inc s2v1
  >>>>              @ s1
>]<               }
-                 dec sp
<<<<[<<<<]        @ pc
+<<<<             inc pc

計算量：右辺の値を $N$、PC と SP の距離を $D$ として、$O(N+D)$

sub

引き算です。

イメージ

r = pop()
l = pop()
push(l - r)

足し算の5行目の + を - に変えればできます。計算量も同じです。

mul

イメージ

r = pop()
l = pop()
push(l * r)

>>>>[>>>>]<<<<      @ st
>[<                 while s1v1 {
  >-<                 dec s1v1
  <<<<                @ s2
  >[->+>+<<]<         move s2v1 to s2v2 and s2v3
  >>>[-<<+>>]<<<      move s2v3 to s2v1
  >>>>                @ s1
>]<                 }
-<<<<               dec sp
>[-]<               clear s2v1
>>[-<+>]<<          move s2v2 to s2v1
[<<<<]              @ pc
+<<<<               inc pc

計算量：左辺の値を $M$、右辺の値を $N$、PC と SP の距離を $D$ として、$O(MN+D)$

not

スタックトップが 0 なら 1、そうでなければ 0 にします。

イメージ

v = pop()
push(!v)

>>>>[>>>>]<<<<  @ st
>>+<<           set v2 1
>[[-]>-<]<      if v1 { set v2 0 }
>>[-<<+>>]<<    move v2 to v1
[<<<<]          @ pc
+<<<<           inc pc

計算量：反転する値を $N$、PC と SP の距離を $D$ として、$O(N+D)$

eq, ne

同値比較は sub と not を組み合わせればできるので不要です。

入出力

read

>>>>[>>>>]    @ sp
>,<           read s_v1
+             inc sp
[<<<<]        @ pc
+<<<<         inc pc

計算量：PC と SP の距離を $D$ として、$O(D)$

write

>>>>[>>>>]<<<<    @ st
>.<               write s_v1
>[-]<             clear s_v1
-                 dec sp
<<<<[<<<<]        @ pc
+<<<<             inc pc

計算量：出力する値を $N$、PC と SP の距離を $D$ として、$O(N+D)$

その他

オフセット指定操作やフロー操作は面倒なので次に回します。割り算や大小比較はもっと面倒なのでしばらくはやりません。