Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@massie_g(がねこ まさし)

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

Last updated at Posted at 2018-06-04

はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) と PythonでつくるPythonに影響を受けて、Node.jsでミニNode.js作りにチャンレンジ中です。

前回は変数の宣言、代入、参照を実装しました。今回は「RubyでつくるRuby」の第6章をならって、条件分岐と繰り返しを作って見ます。

条件分岐 if

if の AST

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

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 を付け加えて、こちらはブロックを作らずに書いてみます。

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 の中に含まれる複数の文に対応できます。

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 のコードをかけると、

if (1) {
  2;
}
else 0;

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

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

実行 evaluate() の拡張

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

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を見て見ましょう。こちらのソースを読み込ませます。

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 に対応させる

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

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

  // ... 省略 ...
}

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


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 で、次の内容です。

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が実行できました！ 感動です。

次回

ここまでのソース

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);
3
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
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?