LoginSignup
0
0

More than 3 years have passed since last update.

@junjis0203

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

Last updated at Posted at 2020-06-14

今回のスコープ

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

ステップ5
比較演算と論理演算
ステップ6
if文
ステップ7
while文とfor文

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

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

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

比較演算

比較演算自体は特に難しくありません。
ところで==と===の挙動の違いを確認するために仕様を見てみる。ここであっと思ったのですが本筋ではないのであとがきで書きます。

論理演算

さて問題の論理演算です。||の方で言うと、

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

何度も書いていますがこれを実現するためには条件分岐が必要です。
というわけでVMに条件分岐命令を実装しました。

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

JUMPを返された側はoffsetの値で次に実行する命令を調整します。

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内で分岐するようにしました。

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な左側評価結果」もしくは「右側評価結果」が残っている

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

[
  { 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は値であり、グローバルオブジェクトのプロパティです。
JOKEは今のところ「グローバルオブジェクト」は用意していないのでグローバルスコープの変数として定義しておきました。4

ステップ6：if文

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

if文を「アセンブル」する処理は以下のようになっています。

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節の命令列

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

[
  { 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文

オフセットの計算がめんどくさくなってきますが難しいことはありません。

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

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

[
  // 条件評価先頭
  { 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文の仕様（正確にはIeration Statementsと言ってwhileもその一つです）を見て「おや？」と思ったのは以下の部分です。あっ、JOKEはvarとか知らない子なので省きます。

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

ちょっと不思議な感じです。2つ目が初期化での変数宣言を表しているのは雰囲気でわかるのですが;が足りなくないでしょうか。
答えは、LexicalDeclaration自体が;を含んでいるので書かれていないというオチでした。

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とかもいますがスタックを調整するために入れています。

[
  // ループ中のみで有効なスコープを作る
  { 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。「マジなもの作ります」の意味ですが、作る前から「実装マジめんどくさい」の略ではないかとも言われています。

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

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

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

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

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

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

  6. MAJIってライブラリ自体は他にあるみたいですが。 ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0