Node.jsでつくるNode.js - Step 6: 条件分岐と繰り返し

# はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」([ラムダノート](https://www.lambdanote.com/products/ruby-ruby), [Amazon](https://www.amazon.co.jp/dp/4908686017)) と [PythonでつくるPython](http://akimacho.hatenablog.com/entry/2018/05/22/220109)に影響を受けて、Node.jsでミニNode.js作りにチャンレンジ中です。

[前回](https://qiita.com/massie_g/items/1e5bf8b3cca0ae08fd1c)は変数の宣言、代入、参照を実装しました。今回は「RubyでつくるRuby」の第6章をならって、条件分岐と繰り返しを作って見ます。

* [もくじ](https://qiita.com/massie_g/items/3ee11c105b4458686bc1)

# 条件分岐 if

## if の AST

まずはesprimaが作るASTをみてみましょう。こちらのソースを読み込ませます。

```js
if (1) {
  2;
}
```

ASTはこちら。

```
Script {
  type: 'Program',
  body:
   [ IfStatement {
       type: 'IfStatement',
       test: Literal { type: 'Literal', value: 1, raw: '1' },
       consequent:
        BlockStatement {
          type: 'BlockStatement',
          body:
           [ ExpressionStatement {
               type: 'ExpressionStatement',
               expression: Literal { type: 'Literal', value: 2, raw: '2' } } ] },
       alternate: null } ],
  sourceType: 'script' }
```

if は IfStatement になり、条件式を test に、成立時に実行する内容が consequent に記述されるようです。
が、ここで新しく BlockStatement という構造が出現しました。これは body の中に、さらに複数のStatementを持てるようです。Blockというからには、ブロックを作った場合に出現するのでしょう。

比較のため else を付け加えて、こちらはブロックを作らずに書いてみます。

```js
if (1) {
  2;
}
else 0;
```

得られたASTはこちら。

```
Script {
  type: 'Program',
  body:
   [ IfStatement {
       type: 'IfStatement',
       test: Literal { type: 'Literal', value: 1, raw: '1' },
       consequent:
        BlockStatement {
          type: 'BlockStatement',
          body:
           [ ExpressionStatement {
               type: 'ExpressionStatement',
               expression: Literal { type: 'Literal', value: 2, raw: '2' } } ] },
       alternate:
        ExpressionStatement {
          type: 'ExpressionStatement',
          expression: Literal { type: 'Literal', value: 0, raw: '0' } } } ],
  sourceType: 'script' }
```

else の内容は alternate に記述され、ブロックを作らなかったのでそのまま ExpressionStatement になっています。

しばし考えて、今回のミニNode.jsは次の方針にすることにしました。

* if だけ、 if - else の両方に対応
* ブロックあり、なしの両方をに対応

## 単純化 simplify() の拡張

elseのあり/なしで、返す配列の要素の個数を変えるようにしてみました。
またブロックの場合はmakeTree()を呼び出すことで、body の中に含まれる複数の文に対応できます。

```js
function simplify(exp) {
  // ... 省略 ...

  if (exp.type === 'IfStatement') {
    const condition = simplify(exp.test);
    const positive = simplify(exp.consequent);
    if (exp.alternate) {
      // -- with else --
      const negative = simplify(exp.alternate);
      return ['if', condition, positive, negative];
    }

    return  ['if', condision, positive];
  }
  if (exp.type === 'BlockStatement') {
    return makeTree(exp);
  }

  // ... 省略 ...
}
```

拡張したsimplify()にこちらの if - else のコードをかけると、

```js
if (1) {
  2;
}
else 0;
```

次のようなtreeが得られます。

```
[ 'if', [ 'lit', 1 ], [ 'lit', 2 ], [ 'lit', 0 ] ]
```


## 実行 evaluate() の拡張

実行側も if / if - else に対応できるように拡張します。

```js
function evaluate(tree, env) {
  // ... 省略 ...

  if (tree[0] === 'if') {
    if (evaluate(tree[1], env)) {
      return evaluate(tree[2], env);
    }
    else {
      if (tree[3]) {
        return evaluate(tree[3], env);
      }
    }

    return null;
  }

  // ... 省略 ...
}
```

# 繰り返し while

繰り返しには色々な種類がありますが、今回は while だけ対応します。

## while の AST

いつものようにASTを見て見ましょう。こちらのソースを読み込ませます。

```js
let i = 3;
while (i) 
  i = i - 1;
```

得られたASTはこちら。

```
Script {
  type: 'Program',
  body:
   [ VariableDeclaration {
       type: 'VariableDeclaration',
       declarations:
        [ VariableDeclarator {
            type: 'VariableDeclarator',
            id: Identifier { type: 'Identifier', name: 'i' },
            init: Literal { type: 'Literal', value: 3, raw: '3' } } ],
       kind: 'let' },
     WhileStatement {
       type: 'WhileStatement',
       test: Identifier { type: 'Identifier', name: 'i' },
       body:
        ExpressionStatement {
          type: 'ExpressionStatement',
          expression:
           AssignmentExpression {
             type: 'AssignmentExpression',
             operator: '=',
             left: Identifier { type: 'Identifier', name: 'i' },
             right:
              BinaryExpression {
                type: 'BinaryExpression',
                operator: '-',
                left: Identifier { type: 'Identifier', name: 'i' },
                right: Literal { type: 'Literal', value: 1, raw: '1' } } } } } ],
  sourceType: 'script' }
```

この結果、次のことが読み取れます。

* whileは、WhileStatement になる
* 条件は test に記述される
* 条件成立時の実行内容は body に記述される

## 単純化 simplify() を while に対応させる

```js
function simplify(exp) {
  // ... 省略 ...

  if (exp.type === 'WhileStatement') {
    const condition = simplify(exp.test);
    const body = simplify(exp.body);
    return ['while', condition, body];
  }

  // ... 省略 ...
}
```

## 実行 evaluate() を while に対応させる

```js

function evaluate(tree, env) {
  // ... 省略 ...

  if (tree[0] === 'while') {
    while (evaluate(tree[1], env)) {
      evaluate(tree[2], env);
    }

    return null;
  }

  // ... 省略 ...
}

```

# ついに FizzBuzz に到達

Step 4 の最後で %演算子に対応、前回のStep 5の最後でデバッグ用の関数 println の呼び出しに対応しているので、FizzBuzz に必要な機能が揃いました。早速試して見ましょう

ここまでのミニNode.jsのソースを mininode_step6.js とします。
また実行する FizzBuzz のソースは fizzbuzz6.js で、次の内容です。

```js:fizzbuzz6.js
let i = 1;
while (i <= 20) {
  if (i % (3*5) === 0) {
    println('FizzBuzz');
  }
  else if (i % 3 === 0) {
    println('Fizz');
  }
  else if (i % 5 === 0) {
    println('Buzz');
  }
  else {
    println(i);
  }

  i = i + 1;
}
```

さて実行して見ましょう。
```
$ node mininode_step6.js fizzbuzz6.js
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
```

ついにFizzBuzzが実行できました！ 感動です。

# 次回

* [Step 7: 組み込み関数を呼び出す](https://qiita.com/massie_g/items/22506a9dabbd13cee13f)

# ここまでのソース

```js:mininode_step6.js
// -------------------------
// mininode.js - Node.js by Node.js
// Step6:
// - OK: if / if-else
//   - OK: simplify
//   - OK: evaluate 
// - OK: while
//   - OK: simplify
//   - OK: evaluate 
// -------------------------

const esprima = require("esprima");
const fs = require('fs');

// --- parser ----
function loadAndParseSrc() {
  const filename = process.argv[2];
  //println('Loading src file:' + filename);

  const src = loadSrcFile(filename);
  const ast =  parseSrc(src);
  //println('-- AST ---');
  //printObj(ast);

  const tree = makeTree(ast);
  //println('-- tree ---');
  //printObj(tree);

  return tree;
}

function loadSrcFile(filename) {
  const src = fs.readFileSync(filename, 'utf-8');
  return src;
}

function parseSrc(src) {
  const ast = esprima.parseScript(src);
  return ast;
}

function makeTree(ast) {
  // --- handle multi lines ---
  let i = 0;
  let exps = [];
  while (ast.body[i]) {
    /* -- only ExpressionStatement --
    const line = ast.body[i].expression;
    const exp = simplify(line);
    exps[i] = exp;
    ---*/

    // --- for VariableDeclaration, ExpressionStatement --
    const line = ast.body[i];
    const exp = simplify(line);
    exps[i] = exp;

    i = i + 1;
  }

  // --- single line ---
  if (exps.length === 1) {
    return exps[0];
  }

  // --- multi lines ---
  const stmts = ['stmts'].concat(exps); // <-- can bootstrup ?
  return stmts;
}

function simplify(exp) {
  if (exp === null) {
    return null;
  }

  // --- STEP 6 ---
  if (exp.type === 'WhileStatement') {
    const condition = simplify(exp.test);
    const body = simplify(exp.body);
    return ['while', condition, body];
  }
  if (exp.type === 'IfStatement') {
    const condition = simplify(exp.test);
    const positive = simplify(exp.consequent);
    if (exp.alternate) {
      // -- with else --
      const negative = simplify(exp.alternate);
      return ['if', condition, positive, negative];
    }

    return  ['if', condition, positive];
  }
  if (exp.type === 'BlockStatement') {
    return makeTree(exp);
  }

  // --- STEP 5 ---
  if (exp.type === 'CallExpression') {
    const name = exp.callee.name;
    const args = exp.arguments;

    // --- only 1 arg --
    const arg = simplify(args[0]);
    return ['func_call', name, arg];
  }
  if (exp.type === 'ExpressionStatement') {
    return simplify(exp.expression);
  }
  if (exp.type === 'VariableDeclaration') {
    if (exp.kind === 'let') {
      const name = exp.declarations[0].id.name;
      const val = simplify(exp.declarations[0].init);
      return ['var_decl', name, val];
    }

    println('-- ERROR: unknown kind of decralation in simplify()) ---');
    printObj(exp);
    abort();
  }
  if (exp.type === 'AssignmentExpression') {
    const name = exp.left.name;
    const val = simplify(exp.right);
    return ['var_assign', name, val];
  }
  if (exp.type === 'Identifier') {
    return ['var_ref', exp.name]
  }

  if (exp.type === 'Literal') {
    return ['lit', exp.value];
  }
  if (exp.type === 'BinaryExpression') {
    return [exp.operator, simplify(exp.left), simplify(exp.right)];
  }

  println('-- ERROR: unknown type in simplify() ---');
  printObj(exp);
  abort();
}

// --- common ----
function printObj(obj) {
  console.dir(obj, {depth: 10});
  return null;
}

function println(str) {
  console.log(str);
  return null;
}

function abort() {
  process.exit(1);
}

// --- evaluator ---
function evaluate(tree, env) {
  if (tree === null) {
    return null;
  }

  if (tree[0] === 'stmts') {
    let i = 1;
    let last;
    while (tree[i]) {
      last = evaluate(tree[i], env);
      //println(last);
      i = i + 1;
    }
    return last;
  }

  // ---- STEP 6 ---
  if (tree[0] === 'while') {
    while (evaluate(tree[1], env)) {
      evaluate(tree[2], env);
    }

    return null;
  }
  if (tree[0] === 'if') {
    if (evaluate(tree[1], env)) {
      return evaluate(tree[2], env);
    }
    else {
      if (tree[3]) {
        return evaluate(tree[3], env);
      }
    }

    return null;
  }

  // ---- STEP 5 ---
  if (tree[0] === 'func_call') {
    const name = tree[1];
    return println(evaluate(tree[2], env));
  }
  if (tree[0] === 'var_decl') {
    // -- check NOT exist --
    const name = tree[1];
    if (name in env) {
      println('---ERROR: varibable ALREADY exist --');
      abort();
    }

    env[name] = evaluate(tree[2], env);
    return null;
  }
  if (tree[0] === 'var_assign') {
    // -- check EXIST --
    const name = tree[1];
    //if (env[name]) {
    if (name in env) {
      env[name] = evaluate(tree[2], env);
      return env[name];
    }

    println('---ERROR: varibable NOT declarated --');
    abort();
  }
  if (tree[0] === 'var_ref') {
    // -- check EXIST --
    const name = tree[1];
    if (name in env) {
      return env[name];
    }

    println('---ERROR: varibable NOT declarated --');
    abort();
  }

  if (tree[0] === 'lit') {
    return tree[1];
  }
  if (tree[0] === '+') {
    return evaluate(tree[1], env) + evaluate(tree[2], env);
  }
  if (tree[0] === '-') {
    return evaluate(tree[1], env) - evaluate(tree[2], env);
  }
  if (tree[0] === '*') {
    return evaluate(tree[1], env) * evaluate(tree[2], env);
  }
  if (tree[0] === '/') {
    return evaluate(tree[1], env) / evaluate(tree[2], env);
  }
  if (tree[0] === '%') {
    return evaluate(tree[1], env) % evaluate(tree[2], env);
  }
  /*
  if (tree[0] === '**') {
    return evaluate(tree[1], env) ** evaluate(tree[2], env);
  }
  */

  if (tree[0] === '===') {
    return evaluate(tree[1], env) === evaluate(tree[2], env);
  }
  if (tree[0] === '<') {
    return evaluate(tree[1], env) < evaluate(tree[2], env);
  }
  if (tree[0] === '>') {
    return evaluate(tree[1], env) > evaluate(tree[2], env);
  }
  if (tree[0] === '<=') {
    return evaluate(tree[1], env) <= evaluate(tree[2], env);
  }
  if (tree[0] === '>=') {
    return evaluate(tree[1], env) >= evaluate(tree[2], env);
  }

  println('-- ERROR: unknown node in evluate() ---');
  printObj(tree);
  abort();
}

// --------

let env = {};

const tree = loadAndParseSrc();
//println('--- tree ---');
//printObj(tree);

//println('--- start evaluate ---');
const answer = evaluate(tree, env);
//println('--- answer ---');
//println(answer);
```