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

# 第0回 はじまり

## Brainfuck とは
脳が震える難解プログラミング言語です。

## 目的
「Brainfuck（以下 BF）はチューリング完全な言語であり、理論上はC言語などと同等の表現力を持つ」というのはよく聞きますが、「理論上」って言われてもピンと来ない……。ということで、C言語ほどではなくても、それなりに良さげな、BF に変換できる言語を作ってみようと思います。著者は言語の実装とか詳しくないし、完成するかは不明です。

## 難しい
最初はマクロみたいな感じで、単純な置き換えでした。

```js
let output = "";
let put = (c) => ">" + "+".repeat(c.chatCodeAt()) + ".";

put("H"); put("e"); put("l"); put("l"); put("o");
output;
```

```bf
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
```

もうすこしメモリを効率よく使えないかと思って考えたのが、BF のメモリをスタックとして使う方法です。LISPを参考にすべてを関数にすることで処理がすっきりしました。

```js
let $ = (v) => typeof v === "string" ? $(v.charCodeAt()) : ">" + "+".repeat(v);
let input = () => ">,";
let print = (a) => a + "." + pop();
let pop = () => "[-]<";
let progn = (...args) => args.reduce((a, b) => a + pop() + b);
let add = (a, b) => a + b + "[-<+>]<";
let sub = (a, b) => a + b + "[-<->]<";
let bool = (a) => ">" + a + "[[-]<+>]<";
let not = (a) => ">+" + a + "[[-]<->]<";
let eq = (a, b) => not(sub(a, b));
let ne = (a, b) => bool(sub(a, b));
let if_else = (a, b, c) => ">+" + a + "[[-]<->" + b + "<]<[->[-]" + c + "<<]>>[-<<+>>]<<";

if_else(eq(input(), $(42)),
  print($("Y")),
  print($("N")))
```

```bf
>+>+>,>++++++++++++++++++++++++++++++++++++++++++[-<->]<[[-]<->]<[[-]<->>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<]<[->[-]>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<<]>>[-<<+>>]<<
```

ただ、これもあくまでもマクロで、処理がすべて展開されてしまいます。どういうことかというと、例えば再帰関数が書けません。while とスタックだけでも再現できることにはできるけど、やっぱりハノイの塔とか再帰で書いてみたいじゃないですか。

関数を呼び出すには、今現在プログラムのどこを実行しているのかと、呼び出したい関数がプログラムのどこにあるのかを把握していなければいけません。BF のインタプリタを作ればわかりますが、確かに BF には今現在どこを実行しているのかを指すプログラムカウンタ（インストラクションポインタ）は存在します。しかし、BF 自身はそれを自由に動かすことは出来ず、自由に動かせるのはデータポインタだけです。これはつまり、「BF のメモリ自体に命令を用意し、それを BF 自身で動かす必要がある」ということです……。

## メモリ領域
調べていくと、これは C言語などのコンパイラ言語の、コンパイル後の構造とまさに一致していることが分かりました。BF ってポインタの勉強になるだけかと思ったら、こんなところでも勉強になるとは……。

C言語などのメモリの割り当ては、４種類に分かれるそうです。

1. プログラム領域
2. 静的領域
3. ヒープ領域
4. スタック領域

[メモリ領域について勉強し始めた - Qiita](http://qiita.com/To_BB/items/e5540b80f08fd13c51b2)

最初はなるべくシンプルで、メモリも少なめに実装したいので、1と4を再現する方向性で行きます。

## 既存？
とかなんとかやってたら、ELVM とかいう恐ろしいものを発見しました。恐ろしいですねこれ……。でもやっぱり自分で作ってみたいので、参考程度にしつつ、続けます。

---

# 第1回 メモリの使い方の決定・実行部分の作成

## BF 前提知識

- `[-]` で値をリセット
- `[->+<]` で値を足せる。相手先が0確定ならコピーと言えるが破壊的である。`[->>+<<]` や `[-<+>>+<]` など応用できる。
- メモリをもう一つ使えば非破壊コピーできる。

## メモリをどう使うか

とりあえず前回通りプログラム領域とスタック領域を並べますが、BF は

- 指定アドレスにアクセスする方法がない
- 計算が破壊的

といった理由で、データを単に並べるだけだと機能しません。ポインタ用や計算・コピー用の領域が必要になります。そこで、４つのメモリをひとまとまりとして考え、以下のように割り振ることにします。

- （p）ポインタ用の領域。0 か 1 をとる。
- （v1）値保持用の領域。計算時は v2 や v3 にコピーして使う。
- （v2）計算用の領域。初期値は必ず 0。
- （v3）計算用の領域。初期値は必ず 0。

上手くやれば２つまとまりでも可能ですが、ややこしくなるので４つにします。

つぎに、プログラム領域とスタック領域の配置を決めます。とりあえず、「実行する命令のある地点」を指すものをプログラムカウンタ（PC）、「次にスタックにプッシュするべき地点」を指すものスタックポインタ（SP）と名付けます。以下は p の値をもとにした各領域の配置です。

```
|---------program---------||----stack----|
[0][0]...[0][0][1]...[1][1][1][1]...[1][1][0][0]...
             ^                             ^
            PC                            SP
```

こうすることで、PC、SP 間の移動が `<<<<[<<<<]` や `>>>>[>>>>]` で行えます。また、プログラムは右から左に並べます。PC を進めるには `+<<<<`、SP を進めるには `+>>>>` となります。

## 実行部分

BF プログラムの大まかな流れとしては、

1. プログラム（機械語）をメモリに配置
2. 命令を１つ読み取り、値によって処理する。終了命令なら終了
3. PC を左に進める
4. 2. に戻る

となります。与えられた機械語を BF に変換する時、1. は生成側でできますが、結局 2. ～ 4. は BF で書く必要があります。

現在 PC にいるとして、機械語は v1 に格納されているので、v2 に非破壊コピーします。「もし v2 が hoge なら～」という処理をしたいので、v2 から hoge を引いて、「v2 が 0 なら～」に変えます。残念なことに、BF のループは「x が 0 でなければ～」なので、v3 をフラグとして使うことにします。（中略）そうしていろいろやった結果が以下になります。例として hoge = 1 としています。また、BF では「今自分がどこにいるのか」を意識しないとわけがわからなくなるので、各行ごとに p に戻っています。

```bf
>[->+>+<<]<       move v1 to v2 and v3
>>>[-<<+>>]<<<    move v3 to v1
>>-<<             sub 1 from v2
>>>+<<<           turn v3 on
>>[<<             while v2 {
  >>[-]<<           clear v2
  >>>-<<<           turn v3 off
>>]<<             }
>>>[<<<           while v3 {
  >>>-<<<           turn v3 off
                    do something
>>>]<<<           }
```

これを命令の種類数に応じて繰り返します。終了命令を 0 とすることで、v1 がある間繰り返せば良くなります。

```bf

>[<                 while v1 {

  >[->+>+<<]<         move v1 to v2 and v3
  >>>[-<<+>>]<<<      move v3 to v1
  >>-<<               sub 1 from v2
  >>>+<<<             turn v3 on
  >>[<<               while v2 {
    >>[-]<<             clear v2
    >>>-<<<             turn v3 off
  >>]<<               }
  >>>[<<<             while v3 {
    >>>-<<<             turn v3 off
                        do something
    +<<<<               inc PC
  >>>]<<<             }

  >[->+>+<<]<         move v1 to v2 and v3
  >>>[-<<+>>]<<<      move v3 to v1
  >>--<<              sub 2 from v2
  >>>+<<<             turn v3 on
  >>[<<               while v2 {
    >>[-]<<             clear v2
    >>>-<<<             turn v3 off
  >>]<<               }
  >>>[<<<             while v3 {
    >>>-<<<             turn v3 off
                        do something
    +<<<<               inc PC
  >>>]<<<             }

  :
  :

>]<                 }
```

## 命令セット

実行部分ができたので、次に機械語の具体的な仕様、命令セットを決めていきます。ここは既存の命令セットを参考にするのが良さそうです。スタックを扱うコンピュータはレジスタマシンと区別してスタックマシンを呼ぶらしいと知ったので、それ的なものを中心に調べて一番参考になりそうだったのが……

「Whitespace」

Whitespace も難解プログラミング言語じゃねーか！

ですが、いい感じに命令がまとまっているのでこれを使うことにします。ヒープアクセスやサブルーチンなど色々改変する必要がありますが、その辺は次回やります。

続く

---

# 第2回 関数を呼ぶために

## 関数を呼ぶとはどういうことか

そもそも関数を呼ぶにはどうすればいいのでしょうか？　まず、引数なし、返り値なしの場合（サブルーチン）を考えてみると、内部での動作は以下のようになっています。

関数 $f$（caller）が関数 $g$（callee）を呼び出すとする。

>
1. $f$ の呼び出し地点の次を指すアドレスを覚えておく
2. $g$ の始まりに移動
3. $g$ の処理をする
4. 1. で覚えたアドレスに飛ぶ

では、$f$ が　$g$ を呼び出し、さらに $g$ が $h$ を呼び出すとき、アドレスはどのように覚えておけば良いのでしょうか？　これには、スタックを使います。

>
1. $f$ の呼び出し地点の次を指すアドレスをスタックにプッシュ
2. $g$ の始まりに移動
3. $g$ の処理を途中までする
4. $g$ の呼び出し地点の次を指すアドレスをスタックにプッシュ
5. $h$ の始まりに移動
6. $h$ の処理をする
7. スタックからポップした 4. のアドレスに飛ぶ
8. $g$ の残りの処理をする
8. スタックからポップした 1. のアドレスに飛ぶ

これで関数を再帰的に呼び出すことが可能です。

つぎに、返り値がある場合を考えてみます。

>
1. $g$ の返り値用の領域をスタックにプッシュ
2. $f$ の呼び出し地点の次を指すアドレスをスタックにプッシュ
3. $g$ の始まりに移動
4. $g$ の処理をする
5. 1. の領域に $g$ の返り値を代入
6. スタックからポップした 1. のアドレスに飛ぶ

さらに、引数もある場合を考えてみます。

>
1. $g$ の返り値用の領域をスタックにプッシュ
2. $f$ の呼び出し地点の次を指すアドレスをスタックにプッシュ
3. $g$ に渡す引数をスタックにプッシュ
3. $g$ の始まりに移動
4. $g$ の処理をする（引数を利用するにはスタックを参照する）
5. 1. の領域に $g$ の返り値を代入
6. 3. でプッシュした引数をすべてポップし捨てる
7. スタックからポップした 1. のアドレスに飛ぶ

最後にローカル変数を使う場合も考えてみたいのですが、一旦情報を整理します。これらを実現するには何が必要なのでしょうか。まず、スタックのプッシュとポップ操作は最低限必要です。そしてアドレスの受け渡しですが、これは機械語を生成するときに可能です。残るは、スタックを奥まで探る操作ですが、実は「取り出したい値がスタックのどこにあるか」というのは固定ではありません。以下の擬似コードの例を見てみます。

```
def f():
  return 1 + g(2)

def g(a):
  return 3 + a

f()
```

`g` において `a` を参照したいとき、どうすればいいのか？　まず、スタックを下から探るのは無理です。`g` は自分がいつ呼ばれるのか事前に知り得ないため、`g` が呼ばれた時点でのスタックの大きさを知ることは出来ないからです。では上から探る場合どうでしょう。スタックで全てを行うからには、`g` では「`3` をプッシュ」→「`a` を読み込んでプッシュ」→「上２つをポップして和をプッシュ」という操作になります。ここで `a` を読み込むときに、`3` が邪魔になります。とはいえ、引数読み込み時に `3` がプッシュされていることは機械語生成時にわかることです。よって、変数読み込み時のスタックトップと引数のある領域との差（オフセット）を計算しておけば対応できます。

アドレス|値
---|---
7|（`a` をここに読み込みたい）
6|`3`
5|引数 `a`(=`2`)
4|リターンアドレス
3|`g` の返り値
2|`1`
1|リターンアドレス
0|`f` の返り値

機械語において `push 3` という動作があるとき、offset を 1 増やせば、引数の領域との距離がわかります。逆に、`add` などの動作があるとき、スタックの大きさは減るので offset を 1 減らします。

では本題のローカル変数の操作について考えます（このあたりで悩んでしまい相当時間がかかった）。その関数内で定義された変数は、引数と同じように考えられます。では外側で定義された変数にはどうやってアクセスするのでしょうか？　以下の例を考えてみます。

```
a = 1
def f():
  b = 1
  def g():
    c = 1
    f()
  g()
f()
```

これは無限に関数呼び出しが起こるし、定義された変数を使ってないのでアホな例ですが、簡単のためです。まず呼び出しの順序を考えると、`main` → `f` → `g` → `f` → `g` → … となっています（プログラム全体は関数ではないが、一般化して `main` 関数と考えた方が楽）。n 回目に呼び出される `f`、`g` を `fn`、`gn` とし、それぞれの関数がアクセスできる変数、すなわち保持している「環境」を考えます。

関数|持っている環境
---|---
`main`|`main`
`f1`|`main` `f1`
`g1`|`main` `f1` `g1`
`f2`|`main` `f2`
`g2`|`main` `f2` `g2`
`f3`|`main` `f3`
...|...

これを踏まえて一般に言えることは、

- 外側の $f$ が内側の $g$ を呼ぶとき、$f$ の環境に $g$ の引数や変数を追加して $g$ に渡す
- 内側の $f$ が外側の $g$ を呼ぶとき、$g$ が必要な環境だけ（つまり、$f$ が保持するうち、$g$ より外側の環境）に $g$ の引数や変数を追加して渡す
- $f$ が自分を呼ぶとき、$f$ より外側の環境に新たな $f$ の引数や変数を追加して渡す

となります（つらい）。

「環境を渡す」方法ですが、いくつかあるそうです。現代の大体のコンピュータで使われているのは、関数呼び出しごとにスタックトップのアドレスを保持し、それをどんどん探っていく方法です（「スタティックリンク」というらしい。詳細不明）。しかし、前に述べたように `BF` はアドレスを扱うのがあまり得意じゃないので、関数呼び出しごとに環境をまるまるコピーする方法をとります（「ラムダリフティング」というらしい。詳細不明）。これを使うデメリットは関数呼び出しのオーバーヘッドが（時間的にも空間的にも）大きいこと、メリットは管理が楽なことと変数操作そのものは速くなることです。

この環境を渡すのも、スタックトップからのオフセットを指定すればできます。ということで命令セットに必要な命令は、

- スタック操作系
  - プッシュとポップ
  - オフセットを指定しての読み書き
- 演算系
  - 四則演算とか
- フロー操作系
  - 必ずジャンプ
  - 条件によってジャンプ
- 入出力
- 終了命令

となります。

以上、結構雑な解説になってしまいました。次回、BF で機械語の処理系を書きます。

---

[第3回 実行部分の続き（前編）](http://qiita.com/liburari/items/1d25de5f5caac3f63585#%E7%AC%AC3%E5%9B%9E-%E5%AE%9F%E8%A1%8C%E9%83%A8%E5%88%86%E3%81%AE%E7%B6%9A%E3%81%8D%E5%89%8D%E7%B7%A8)