JavaScript
Node.js

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


はじめに

「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);