作って理解JavaScript：JOKE開発記その5 - 条件分岐とループ

# 今回のスコープ

今までは一つの開発記で一つのステップについて説明していましたが今回は関連の深い以下のステップをまとめて説明します。[^1]

[^1]: そもそも開発記と開発ステップは一対一対応の予定でもなかったので。

<dl>
<dt>ステップ5</dt>
<dd>比較演算と論理演算</dd>
<dt>ステップ6</dt>
<dd>if文</dd>
<dt>ステップ7</dt>
<dd>while文とfor文</dd>
</dl>

# ステップ5：比較演算と論理演算

条件分岐のためには比較演算を実装しないといけない。
また条件分岐のためには必須ではないけど論理演算もあるとよい。
というわけでこれらを実装するわけですが問題として、`&&`と`||`（短絡評価）のためには条件分岐（を行う命令）が必要という鶏が先か卵が先かな状況・・・

まあ悩んでいても仕方がないので論理演算を先に実装しました。ステップ5時点でのコードは以下にあります。
https://github.com/junjis0203/joke/tree/step0005

## 比較演算

比較演算自体は特に難しくありません。
ところで`==`と`===`の挙動の違いを確認するために[仕様](http://www.ecma-international.org/ecma-262/6.0/#sec-abstract-equality-comparison)を見てみる。ここであっと思ったのですが本筋ではないのであとがきで書きます。

## 論理演算

さて問題の[論理演算](http://www.ecma-international.org/ecma-262/6.0/#sec-binary-logical-operators-runtime-semantics-evaluation)です。`||`の方で言うと、

1. `||`の左側の式を評価する
2. 左側が**truthyであれば**、それを式の値とする
3. 左側が**truthyでなければ**、右側を評価しそれを式の値とする

何度も書いていますがこれを実現するためには条件分岐が必要です。
というわけでVMに[条件分岐命令を実装](https://github.com/junjis0203/joke/blob/step0005/lib/vm.js#L195)しました。

```js:vm.js抜粋（ステップ5）
    case I.JUMP_IF:
        {
            const val = stack.pop();
            if (val) {
                return {type: 'JUMP', offset: insn.offset};
            }
        }
        break;
```

[`JUMP`を返された側](https://github.com/junjis0203/joke/blob/step0005/lib/vm.js#L230)は`offset`の値で次に実行する命令を調整します。

```js:vm.js抜粋（ステップ5）
            const ret = executeInsn(context, insn);
            if (ret) {
                if (ret.type == 'EXIT') {
                    break;
                } else if (ret.type == 'JUMP') {
                    ptr = ptr + ret.offset;
                }
            }
```

順序が逆ですが次にこの`JUMP_IF`を使って`&&`と`||`の動作を「実装」する`Assembler`の処理です。
`&&`と`||`はノードを分けようかなと思いましたが`BINARY_OPERATOR`には変わりがないので[`Assembler`内で分岐](https://github.com/junjis0203/joke/blob/step0005/lib/assembler.js#L41)するようにしました。

```js:assembler.js抜粋（ステップ5）
    case N.BINARY_OPERATOR:
        assembleNode(node.left, insns);
        // custom operations is need
        if (node.operator == '&&' || node.operator == '||') {
            // dup for operation result
            makeInstruction(I.DUP);
            const rightInsns = [];
            assembleNode(node.right, rightInsns);
            if (node.operator == '&&') {
                makeInstruction(I.UNI_OP, {operator: '!'});
            }
            makeInstruction(I.JUMP_IF, {offset: rightInsns.length+1});
            // dupped value is no need if false
            makeInstruction(I.POP);
            insns.splice(insns.length, 0, ...rightInsns); 
        } else {
            assembleNode(node.right, insns);
            makeInstruction(I.BIN_OP, {operator: node.operator});
        }
        break;
```

条件ジャンプのオフセットを得るために「右側」部分を一度別配列`rightInsns`を使って「アセンブル」しているのがポイントです。[^2]
やっていることとしては（`&&`はひと手間多いので`||`で説明します）、

1. 「左側」を評価する命令列を実行
2. 「左側評価結果」を`DUP`（理由は後で説明します）
3. 「左側評価結果」がtruthyなら（右側を評価する必要はないので）、右側を評価する命令列を飛ばす（`JUMP_IF`）
4. 「左側評価結果」がtruthyでないなら、スタックトップを`POP`した後で右側を評価する命令列を実行する
5. 最終的にスタックには「truthyな左側評価結果」もしくは「右側評価結果」が残っている

[^2]: CRubyとかCPythonは初めは「飛び先ラベル」を指定しておき、後から「命令とラベルの距離」を計算してオフセットに置き換えるということをしています。JOKEもそうしようと思ったのですが別配列に作っておくことでラベルを使わなくてもいいことに気づきました。

実際に、`1 || 2;`というプログラムを変換してみると以下の命令列になります。[^3]

[^3]: `offset: 2`というのは`JUMP_IF`を読み込んだ時点で命令ポインタは4番目の`POP`に移動しているのでそこから2進む（結果最後の`POP`に行く）という意味です。ややこしかったのでHEADでは「自分から見て3つ先」とするように変更しています。

```js
[
  { command: 'PUSH', operand: 1 },
  { command: 'DUP' },
  { command: 'JUMP_IF', offset: 2 },
  { command: 'POP' },
  { command: 'PUSH', operand: 2 },
  { command: 'POP' }
]
```

`DUP`をしているのは「左側評価結果」を条件ジャンプにも「式全体の結果」にも使うためです。また、ジャンプしない場合は「左側評価結果」が余計に積まれている状態なので`POP`を入れています。

## undefined

比較演算／論理演算とは関係ないのですが「未定義」を表す`undefined`は特殊ですね。
`true`、`false`、`null`はリテラルですが、`undefined`は値であり、[グローバルオブジェクトのプロパティ](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/undefined)です。
JOKEは今のところ「グローバルオブジェクト」は用意していないので[グローバルスコープの変数](https://github.com/junjis0203/joke/blob/step0005/lib/object.js#L39)として定義しておきました。[^4]

[^4]: 変数なので代入できてしまいます。そこを対応するのはそのうち。

# ステップ6：if文

if文はここまで作ってきたものを使えばできるので難しくありません。
あっ、「無条件ジャンプ」は追加していますね。
https://github.com/junjis0203/joke/tree/step0006

if文を[「アセンブル」する処理](https://github.com/junjis0203/joke/blob/step0006/lib/assembler.js#L124
)は以下のようになっています。

```js:assembler.js抜粋（ステップ6）
    case N.IF:
        {
            assembleNode(node.expr, insns);
            const thenInsns = [];
            assembleNode(node.thenStmt, thenInsns);
            const elseInsns = [];
            if (node.elseStmt) {
                assembleNode(node.elseStmt, elseInsns);
            }
            // jump to thenInsns
            makeInstruction(I.JUMP_IF, {offset: 1});
            // jump to elseInsns
            makeInstruction(I.JUMP, {offset: thenInsns.length+1});
            // embed thenInsns
            insns.splice(insns.length, 0, ...thenInsns); 
            // jump to last
            makeInstruction(I.JUMP, {offset: elseInsns.length});
            // embed elseInsns
            insns.splice(insns.length, 0, ...elseInsns);
        }
        break;
```

少し長いですがやっていることは論理演算のときとほぼ同じです。

1. 「条件」を評価する命令列
2. 「条件評価結果」がtruthyなら2つ先[^5]に飛ぶ。つまり次の無条件ジャンプを跳び越す
3. 条件が成り立たないので、then節（に当たる命令列）を跳び越してelse節（に当たる命令列）に無条件ジャンプ
4. then節の命令列
5. 最後（今後命令が追加されるところ）に無条件ジャンプ（else節を跳び越す）
6. else節の命令列

[^5]: `offset: 1`となっていますが脚注3でも述べたようにこの時点では「今の命令ポインタ値」に足される値をオフセットにしています。

例えば`if (1) 2; else 3;`は以下のように変換されます（出力を短くするためなので、プログラム自体の意味は無視してください）

```js
[
  { command: 'PUSH', operand: 1 },
  { command: 'JUMP_IF', offset: 1 },
  { command: 'JUMP', offset: 3 },
  { command: 'PUSH', operand: 2 },
  { command: 'POP' },
  { command: 'JUMP', offset: 2 },
  { command: 'PUSH', operand: 3 },
  { command: 'POP' }
]
```

# ステップ7：while文とfor文

条件ジャンプと無条件ジャンプができればwhile文とfor文もすぐに実装できます。
https://github.com/junjis0203/joke/tree/step0007

## while文

[オフセットの計算](https://github.com/junjis0203/joke/blob/master/lib/assembler.js#L145)がめんどくさくなってきますが難しいことはありません。

1. 「条件」を評価する命令列
2. 1.の値を`!`する（条件がfalsyのときにループを抜けるため）
3. 「条件の否定」がtrueならループの先に飛ぶ
4. ループ本体の命令列
5. 条件評価の命令列先頭に飛ぶ無条件ジャンプ

`while (i < 10) i++;`を変換すると以下のようになります。

```js
[
  // 条件評価先頭
  { command: 'PUSH', operand: 'i' },
  { command: 'LOOKUP' },
  { command: 'PUSH', operand: 10 },
  { command: 'BIN_OP', operator: '<' },
  // 評価結果を否定後、trueならループの先の飛ぶ
  { command: 'UNI_OP', operator: '!' },
  { command: 'JUMP_IF', offset: 11 },
  // ループ本体
  { command: 'PUSH', operand: 'i' },
  { command: 'LOOKUP' },
  { command: 'DUP' },
  { command: 'PUSH', operand: 1 },
  { command: 'BIN_OP', operator: '+' },
  { command: 'PUSH', operand: 'i' },
  { command: 'ASSIGN' },
  { command: 'POP' },
  { command: 'POP' },
  // 条件評価先頭に飛ぶ
  { command: 'JUMP', offset: -15 }
]
```

## for文

[for文の仕様](http://www.ecma-international.org/ecma-262/6.0/#sec-iteration-statements)（正確にはIeration Statementsと言ってwhileもその一つです）を見て「おや？」と思ったのは以下の部分です。あっ、JOKEは`var`とか知らない子なので省きます。

```
for ( Expression ; Expression ; Expression ) Statement
for ( LexicalDeclaration Expression ; Expression ) Statement
```

ちょっと不思議な感じです。2つ目が初期化での変数宣言を表しているのは雰囲気でわかるのですが`;`が足りなくないでしょうか。
答えは、[`LexicalDeclaration`](http://www.ecma-international.org/ecma-262/6.0/#sec-let-and-const-declarations)自体が`;`を含んでいるので書かれていないというオチでした。

```
LexicalDeclaration :
    LetOrConst BindingList ;
```

ともかくfor文についても同じ発想で実行コードにアセンブルが行えます。

1. forの1つ目（初期化）の命令列
2. forの2つ目（条件）の命令列
3. 条件を否定し、否定したものがtrueならループ末尾へ
4. ループ本体の命令列
5. forの3つ目（更新処理）の命令列
6. forの2つ目の先頭への無条件ジャンプ

`for (let i = 0; i < 10; i++) sum += i;`を変換すると以下のようになります。説明していない`POP`とかもいますがスタックを調整するために入れています。

```js
[
  // ループ中のみで有効なスコープを作る
  { command: 'PUSH_SCOPE' },
  // forの1つ目
  { command: 'DEFINE', operand1: 'i', operand2: 'let' },
  { command: 'PUSH', operand: 0 },
  { command: 'PUSH', operand: 'i' },
  { command: 'INITIALIZE' },
  // forの2つ目
  { command: 'PUSH', operand: 'i' },
  { command: 'LOOKUP' },
  { command: 'PUSH', operand: 10 },
  { command: 'BIN_OP', operator: '<' },
  // 評価結果を否定後、trueならPOP_SCOPEまで飛ぶ
  { command: 'UNI_OP', operator: '!' },
  { command: 'JUMP_IF', offset: 19 },
  // ループ本体
  { command: 'PUSH', operand: 'sum' },
  { command: 'LOOKUP' },
  { command: 'PUSH', operand: 'i' },
  { command: 'LOOKUP' },
  { command: 'BIN_OP', operator: '+' },
  { command: 'PUSH', operand: 'sum' },
  { command: 'ASSIGN' },
  { command: 'POP' },
  // forの3つ目
  { command: 'PUSH', operand: 'i' },
  { command: 'LOOKUP' },
  { command: 'DUP' },
  { command: 'PUSH', operand: 1 },
  { command: 'BIN_OP', operator: '+' },
  { command: 'PUSH', operand: 'i' },
  { command: 'ASSIGN' },
  { command: 'POP' },
  // 3つ目の式結果が余計に積まれているのでPOP（一つ上のPOPは別の理由で入る）
  { command: 'POP' },
  // forの2つ目先頭に飛ぶ
  { command: 'JUMP', offset: -23 },
  { command: 'POP_SCOPE' }
]
```

# あとがき

以上、今回は条件分岐のための命令を中心に論理演算、if文、while文、for文を実装しました。
ようやく条件分岐とループを実装したので九九やFizzBuzzプログラムを作ることも可能になりました！

ところで、ここまで読まれた方は「何か足りていない」ことに気づかれたでしょうか。
そう、「条件分岐」と言ったら普通紹介されるswitch文を実装していません。
というのもswitch文をまともに動かすためにはbreakが要りますが、breakは今回説明したような「事前に計算できるオフセット」でのジャンプでは実装できない（できたとしてもおそらく簡単にはできない）ためです。「こんな風にすればいいだろ」というアイデアはあるのですがVMの変更が結構必要そうなので先に「固定オフセット」で実装できるif/while/for文までを実装しました。

さてもう一つ、比較演算のところで伏線しておきましたが「演算子の仕様（処理手順）」を見ていてあることに気づきました。
**JOKEでは論理演算以外の演算子の動作をJOKE自身を動かしてるJavaScript処理系に丸投げしているのです。**
ジョークな処理系とは言えこれは手抜きし過ぎたと反省しました。今から直す気はありませんが:stuck_out_tongue:

ということで、前回「いやーGC自力で実装してたら死ぬほど大変だった」と発言した反省も含めて、「本気の（演算子の動作等も仕様に書かれている通りに実行する）」JavaScript処理系を作ろうと思いました。名前から決める人間なのでコードネームはもう決まっていて

MAJI: More Adventurous Javascript Interpreter

です。JOKEに対してMAJIですね[^6]。「マジなもの作ります」の意味ですが、作る前から「実装マジめんどくさい」の略ではないかとも言われています。

[^6]: MAJIってライブラリ自体は他にあるみたいですが。

あ、JOKEの開発はまだ当分、セルフホスティングを達成するまで続けます。次回はbreakとcontinueを実装した後、switch文も実装する予定です。