JavaScript ES2015の「末尾再帰」最適化
JavaScriptの勉強で、ES2015の「アロー関数」を使う必要が出ました。
Visual Stuidio Code+Node.jsでES2015のJavaScriptコードを動かしていますが、ブラウザーでES2015はもうちゃんと動くのでしょうか?
- Google Chromeなど、ブラウザーのES2015対応状況を調べてみました。
- 最新のモダンブラウザーは、ほぼES2015に対応してましたが、「末尾再帰の最適化」という機能だけ未対応のブラウザーが多かったです。(2017年8月現在)
ECMAScript6(ES6、ES2015)のブラウザー対応一覧表
各ブラウザーのES2015対応状況が一覧表になってました。
ECMAScript 6 compatibility table
「proper tail calls (tail call optimisation)」という機能だけ、ほとんど赤で、未対応のブラウザーが多かったです。
これは、「末尾再帰」という機能でした。
- Safariは対応していました!(Apple頑張ってるね^^)
- 自分がメインで使っているGoogle Chromeは、未対応でした。(涙)
…まあ、でも「末尾再帰」という機能は、普段使ってないから問題ないかな?
こうしてみると、2017年8月現在は、ES2015のほとんどの機能がモダンブラウザーで対応済のようでした。
→ Babel等のトランスパイラーを使って、ES2015のJavaScriptコードをES5のJavaScriptのコードにダウンコンパイルしなくても大丈夫そうですね?
(「ユーザー=ほぼ自分」というプロダクトならES2015をそのまま投入しても平気?w)
(参考)
全てのブラウザで対応しているわけではないため、Babel等のトランスパイラを利用してES2015で書いたコードを各ブラウザで動くコードであるES5のコードにトランスパイル(変換)する必要がある。
末尾再帰とは?
ところで、この「末尾再帰」とは、いったい何なのでしょうか?
万一、使う必要が出てきた場合、エラーになると困るので知っておきたいところです。
末尾再帰(まつびさいき)とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。
再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し (Tail call)という。
呼び出しではなく、戻り先を保存しないジャンプに最適化できるという特徴がある。
末尾呼出し最適化(まつびよびだしさいてきか、tail call optimization)とは、末尾呼出しのコードを、戻り先を保存しないジャンプに変換することによって、スタックの累積を無くし、効率の向上などを図る手法である。
末尾呼出しの除去(tail call elimination)などとも言う。
末尾再帰の最適化
末尾再帰の最適化は、「tail call optimization」を略して「TCO」とも呼ばれます。
関数の再帰(自分で自分を呼び出す操作)を大量に繰り返すと、メモリー不足(スタックオーバーフロー)を引き起こして、途中で止まってしまいます。
スタックオーバーフローを防ぐには、スタック(呼び出し元の記録の積み重ね)を減らす工夫をすればOK!
→それが、TCOってわけですね?
(参考)
コールスタック
通常のプログラムの実行モデルでは、関数を呼び出すと、関数自身のローカル変数(引数や局所変数)や戻り先情報を保持するスタックフレーム(アクティベーションレコード)が生成されてコールスタックと呼ばれるスタックにpushされます。
関数はスタックフレームに計算途中の値を保持しつつ処理を続けます。
関数の実行が終わると対応するスタックフレームがpopされて呼び出し元のスタックフレームに復帰し、呼び出し元関数の実行が再開されます。
対応状況
ES2015は仕様であり、実際にそれを使えるかどうかはブラウザ等の実装に依存する。
そして、末尾呼び出し最適化を実装している環境は、かなり少ない。
Safari Node.js Chrome Firefox Babel 対応状況 ◯ △ × × × 確認したバージョン 10.0.2 6.9.2 55.0.2883.95 50.1.0 6.18.0 備考 - harmony
のみ- - v6で削除された
ES2015で特定の形で関数呼び出しがされている場合に末尾呼び出し最適化が行われるよう定められたが、パフォーマンスや、デバッグなどの実装上の問題が浮上したため、それを解決するための新たな構文がV8で実装された。
(※提案初期段階の仕様のため、この先廃止になったり仕様が大きく変わる可能性が大いにあります)
「 return continue fn() 」という形での呼び出しについて最適化が有効になる。
上記のJavaScriptコードを、Visual Studio Code+Node.js v6.11.2で実行してみたら、エラーになりました。
Node.js v6.11.2では、「continue」の使い方が文法エラーになってしまうようです。
末尾再帰の解説記事
その他、Google検索したときに出てきた解説記事をメモしときます。
ECMAScript 2015 Language Specification – ECMA-262 6th Edition
14.6 Tail Position Calls
All About Recursion, PTC, TCO and STC in JavaScript
Tail call optimization is a technique used by the compiler to transform your recursive calls into a loop using jumps.
(末尾再帰の最適化は、末尾呼び出しをジャンプを使ったループへ変換するために、コンパイラによって使われる手法です。)
Tail call optimization in ECMAScript 6
Tail call optimization can only be made in strict mode
(末尾再帰の最適化は、厳密モードでのみ行うことができます)
内容が込み入っており、しかも英語なので、何言ってるかよく分かりませんねwww
(もうちょっと勉強してから、また後で見てみよう…。)
関数型プログラミング
ちょうど今、関数型プログラミングの本を読んでいたので、JavaScriptの再帰呼び出しについて、少し勉強になりました。
(p.175)
正格評価が標準のJavaScriptにおいて、Haskellのような遅延評価を実装することは可能でしょうか?
評価のタイミングをずらすことで、それは可能です。
JavaScriptで関数型プログラミングを行う方法は、まだ勉強不足なのでよく分かっていません。
「末尾再帰」の最適化は、コンパイラに頼らなくても、自分でできるものなのかな?
ここら辺の話は、今後の宿題にしておきたいと思います。
まとめ
- JavaScriptのES2015は、モダンブラウザーのほとんどが対応している。
- ES2015の「末尾再帰」最適化に対応していたブラウザーは、Safariだけ。
- 末尾再帰の最適化が行われないと、スタックオーバーフローが起きる場合がある。
- スタックオーバーフローする可能性がある場合は、とりあえず「再帰」を普通の「ループ」(whileなど)に置き換えてみる。
JavaScriptの練習をするだけなら、ES2015をそのままChromeで動かしてもOK!