Node.jsでつくるNode.js - Step 12: returnでブートストラップ達成

# はじめに

「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/5d8d61cdbf54390d8709)はreturnによる関数脱出を諦め、ついにブートストラップを実現しました。それで終わりにしようかと思ったのですが、どうしてもreturn処理を実現したくてもうちょっとだけ頑張ってみます。

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

# return への対応

## returnでやりたいこと

 return文が登場したら、現在実行箇所の後続の処理をスキップし、いまの関数から脱出しなければなりません。もう少し細かく言うとこうなります。

* （ユーザ定義）関数の処理中に発生する ... func_call の中
* return 式; の式を評価した値を返す
* 複数行の処理がある塊で、後続の行をスキップ ... stmts に相当
    * if のブロックや、 while のブロックも該当
* 繰り返し処理中でも、条件に無関係に繰り返しを中断して、抜け出す

関数呼び出し (func_call)の処理が終わる箇所まで、一気に抜け出せる必要があります。

## フラグによる通知

実際の処理は evaluate() を再帰的に呼び出して行うので、return処理の開始と終了を伝えてあげる必要があります。そこで、まずは一番安易にグローバル変数でフラグを持つことにしました。
最低限の対処として、フラグの変更や参照は関数に閉じ込めます。

* _setReturingFromFunc() ... return処理中のフラグを立てる（セットする）
* _resetReturingFromFunc() ... return処理中のフラグをクリアする（リセットする）
* _isReturingFromFunc() ... return処理中のフラグの状態を調べる

```js

let _returnFlag = 0;

function _setReturingFromFunc() {
  _returnFlag = 1;
}

function _resetReturingFromFunc() {
  _returnFlag = 0;
}

function _isReturingFromFunc() {
  return _returnFlag;
}
```

## フラグを立てる場所、クリアする場所

return処理のフラグを立てる場所（return処理が始まる場所）は、'ret' の処理になります。逆にフラグをクリアするのは、関数呼び出し処理 'func_call' が終わるところ（関数から抜けるところ）になります。

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

  else if (tree[0] === 'ret') {
    // --- STEP 12: return処理を開始 ---
    let ret = evaluate(tree[1], genv, lenv);
    _setReturingFromFunc(); // set "returning from function" flag
    return ret;
  }


  else if (tree[0] === 'func_call') {
    const mhd = genv[tree[1]];

    // ... 省略 ...

    // ---- STEP 8 ----
    else if (mhd[0] === 'user_defined') {
      let newLenv = [];
      let params = mhd[1];
      i = 0;
      while (params[i]) {
        newLenv[params[i]] = args[i];
        i = i + 1;
      }

      // --- STEP 12 : return 処理を終了 ----
      let ret = evaluate(mhd[2], genv, newLenv);
      _resetReturingFromFunc(genv); // clear flag, because function is finish
      return ret;
    }

  }

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

フラグをみて処理を中断する場所は2箇所ありました。1つ目は複数行を順番に処理する 'stmts' の部分で、2つ目は繰り返し処理の 'while' の部分です。

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

  else if (tree[0] === 'stmts') {
    let i = 1;
    let last;
    while (tree[i]) {
      last = evaluate(tree[i], genv, lenv);

      // --- STEP 12: returnフラグが立っていたら抜ける ----
      if (_isReturingFromFunc(genv)) {
        return last;
      }

      i = i + 1;
    }
    return last;
  }

  // ... 省略 ....

  else if (tree[0] === 'while') {
    // --- STEP 12: returnフラグが立っていたら抜ける ----
    let last = null;
    while (evaluate(tree[1], genv, lenv)) {
      last = evaluate(tree[2], genv, lenv);
      if (_isReturingFromFunc(genv)) {
        return last;
      }
    }

    return last;
  }

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

## returnを使ったFizzBuzz

前回Step11で用意した、returnでの関数脱出処理を含んだfizzbuzzをもう一度動かします。

```js:fizzbuzz11.js
function fizzbuzz(n) {
  if (n % (3*5) === 0) {
    return 'FizzBuzz';
  }
  else if (n % 3 === 0) {
    return 'Fizz';
  }
  else if (n % 5 === 0) {
    return 'Buzz';
  }
  else {
    return n;
  }

  // --- Should not come here ---
  return 'zzz';
}

let i = 1;
let ret;
while (i <= 20) {
  ret = fizzbuzz(i)
  println(ret);
  i = i + 1;
}
```

結果はこちら。

```
$ node mininode_step12.js fizzbuzz11.js
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
```

関数の最後まで行かずに、正しく途中で抜けられるようになりました。

## ブートストラップでreturnを実行

次はブートストラップでreturn処理ありのfizzbuzzを実行します。（デバッグメッセージ出力を加えています）

```
$ node mininode_step12.js fizzbuzz11.js
---ERROR: varibable NOT declarated (ref)--:_returnFlag
```

なぜか今回用意したグローバル変数が見つけられていません。

# ミニNode.js (mininode)でのグローバルスコープの扱い

## グローバル変数は存在しない

ソースコードを見直すと、ミニNode.js/ミニRubyでの変数は、関数ごとに新しく作られるハッシュで実現されています。これは下位の（内側の）関数からは見ることができません。そして一番外側のスコープで宣言された変数も同様です。
つまり、グローバル変数というものはサポートしないという仕様でした。「RubyでつくるRuby」をやっていた時には気が付きませんでした。

## 関数はすべてグローバル

グローバルに相当するハッシュgenvがありますが、それはすべての関数定義の保持に使われています。ということは、関数の方はローカルスコープがなくて、すべてグローバル関数扱いになるということですね。試して見ましょう。

```js:test12.js
function outer() {
  function inner() {
    println('inner');
  }

  println('outer');
}

// --- main ---
outer();
inner();
```

というソースを用意して、mininodeで実行してみます。

```
$ node mininode_step12.js test12.js
outer
inner
```

確かに、outer()関数の中で定義しているinner()関数も呼び出せています。グローバルとローカルのスコープの扱いは、なかなか難しいです。

# 組み込み変数? を利用してブートストラップ

## genvを利用

return処理のフラグのために今回mininodeでグローバル変数をサポートするというのが一つの対策ですが、genvに乗っかることにしました。いわば組み込み変数でしょうか。先ほどの関数を変更し、genvの初期化を追加します。

```js
//let _returnFlag = 0;

function _setReturingFromFunc(env) {
  env['g_returningFromFunc'] = 1;
}

function _resetReturingFromFunc(env) {
  env['g_returningFromFunc'] = 0;
}

function _isReturingFromFunc(env) {
  return env['g_returningFromFunc'];
}

let genv = {
  // ... 省略 ...

  // --- STEP 12: returnフラグを追加 ---
 'g_returningFromFunc' : 0, // Global Flag for returning from function

};
let lenv = {};
```

フラグ管理の関数は直接 genv（これ自体がグーローバル変数)が見れないので、引数で受け取るようにしています。そのため呼び出し側も genv を渡すように変更です。

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

  else if (tree[0] === 'ret') {
    // --- STEP 12: return処理を開始 ---
    let ret = evaluate(tree[1], genv, lenv);
    _setReturingFromFunc(genv); // set "returning from function" flag
    return ret;
  }

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

## return処理を含んだ fizzbuzzを動かす

これであらためてブートストラップしてみると、return処理を含んだfizzbuzz11.js を動かすことがきました。

```
$ node mininode_step12.js mininode_step12.js fizzbuzz11.js
1
... 省略 ...
14
FizzBuzz
16
17
Fizz
19
Buzz
```

## 自分自身もreturn処理を使う

あともう少しです。もともと今回の evaluate()は、return文を多用していました。returnが動くようになった（ハズ）なので、else をやめて return による脱出に戻します。

```js:evaluate()の一部抜粋

/*
  // --- before ---
  else if (tree[0] === 'lit') {
    return tree[1];
  }
  else if (tree[0] === '+') {
    return evaluate(tree[1], genv, lenv) + evaluate(tree[2], genv, lenv);
  }
  else if (tree[0] === '-') {
    return evaluate(tree[1], genv, lenv) - evaluate(tree[2], genv, lenv);
  }
*/

  // --- after --
  if (tree[0] === 'lit') {
    return tree[1];
  }
  if (tree[0] === '+') {
    return evaluate(tree[1], genv, lenv) + evaluate(tree[2], genv, lenv);
  }
  if (tree[0] === '-') {
    return evaluate(tree[1], genv, lenv) - evaluate(tree[2], genv, lenv);
  }
```

これであらためて実行してみたら、無事動きました。

```
$ node mininode_step12.js mininode_step12.js fizzbuzz11.js
```

4段重ねも、めちゃくちゃ遅いですが動きました！ （5段重ねはさすがにスタックサイズの制限を超えてしまい動きませんでした）

```
$ node mininode_step12.js mininode_step12.js mininode_step12.js mininode_step12.js fizzbuzz11.js
```

ここまでで「Node.jsつくるNode.js」で目指していたことはすべて完了です。満足、満足。

# おわりに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」([ラムダノート](https://www.lambdanote.com/products/ruby-ruby), [Amazon](https://www.amazon.co.jp/dp/4908686017)) に感銘をうけて自分でもミニNode.jsを作って見ましたが、本を読んでいた時には気がつかなかったことが多々ありました。

* 「RubyでつくるRuby」のステップの分解の仕方がすばらしい。少しづつ理解しながら無理なく実装できるようになっている。今回もとても参考になりました
* 中間点となる構文木 Tree の構造をそのまま使わせていただいたので、simplify()もevaluate()も考えやすかった。この設計がキモになっていますね
* 仕様の割り切りがすばらしい。大胆でかつよく整合性が取れていると思いました。今回自分で変数宣言をいじったりreturn文をサポートしたりしたことが、ことごとく引っ掛かりました

素晴らしい書籍を作ってくださった作者の遠藤さんとラムダノートさんに改めて感謝します。ありがとうございました。

# ここまでのソース

* [mininode_step12.js](https://github.com/mganeko/mininode/blob/master/mininode_step12.js)
* [sample/test12.js](https://github.com/mganeko/mininode/blob/master/sample/test12.js)
* [sample/fizzbuzz11.js](https://github.com/mganeko/mininode/blob/master/sample/fizzbuzz11.js)