今年も残りわずかとなりました。M.Hiroi's Home Page を開設してから 15 年が過ぎましたが、ここまで続けることができるとは M.Hiroi も思っていませんでした。これもひとえに M.Hiroi's Home Page に来てくださる皆様のおかげです。本当にありがとうございました。来年の事を言えば鬼が笑うといいますが、これからも M.Hiroi's Home Page の更新を続けることができればいいなあ、と思っております。
それでは、きたるべき年も皆様にとってよいお年でありますように。
M.Hiroi's Home Page を開設してから 15 年になりました。15 年間も続けることができたのは、M.Hiroi's Home Page に来てくださる皆様のおかげです。厚くお礼申しあげます。
これを期に、Web ページの記述を HTML4 + shift_jis から HTML5 + utf-8 に変更しました。何か不具合があればメールにてご連絡いただけると助かります。
これからもがんばりますので、今後ともよろしくお願い申しあげます。
JavaScript のお話です。古川さんの記事 で紹介されているトランスパイラ babel で「末尾再帰最適化」を試してみたかったので、Node.js をインストールしました。
Node.js は JavaScript で Web アプリケーションを作成するためのプラットフォームです。JavaScript エンジンは Google Chrome の V8 が使われています。Node.js を使って Web サーバーを構築し、そこでアプリケーションを動作させます。Apache など従来のサーバーに比べて、大量のリクエストを高速にさばくことができるそうです。
M.Hiroi は Node.js の機能をほとんど理解していませんが、REPL (Read-Eval-Print-Loop) が用意されているので、コマンドラインで高速に動作する JavaScript 処理系として使ってみるのも面白そうです。Node.js は次のページからダウンロードすることができます。
Windows 用のインストーラーが用意されているので、簡単にインストールすることができます。
Node.js をインストールすると、npm というパッケージマネージャもいっしょにインストールされます。Node.js で使用するモジュールやコマンドは npm を使って簡単にインストールやアンインストールすることができます。babel は次のコマンドでインストールすることができます。
C>npm install -g babel
babel の使い方ですが、コマンド babel で ECMAScript2015 (今後 ES6 と略記) で書かれた JavaScript ファイルを ES5 に変換します。すぐに実行したい場合はコマンド babel-node を使ってください。
それでは簡単な例題として、1 から n までの和を求める関数 sum_rec を末尾再帰でプログラムしてみましょう。
リスト : 1 から n までの和を求める function sum_rec(n, a) { if (n == 0) return a; return sum_rec(n - 1, a + n); } console.log(sum_rec(100000, 0));
このプログラムを node で実行するとスタックオーバーフローします。
C>node test.js C>test.js:1 n (exports, require, module, __filename, __dirname) { function sum_rec(n, a) { ^ RangeError: Maximum call stack size exceeded at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:1:79) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10) at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
babel-node で実行すると末尾再帰最適化により、答えを求めることができます。
C>babel-node test.js 5000050000
プログラムは babel により次のように変換されます。
リスト : 変換結果 "use strict"; function sum_rec(_x, _x2) { var _again = true; _function: while (_again) { var n = _x, a = _x2; _again = false; if (n == 0) return a; _x = n - 1; _x2 = a + n; _again = true; continue _function; } } console.log(sum_rec(100000, 0));
末尾再帰が繰り返し (while ループ) に変換されていることがわかります。
ただし、次のような相互再帰は最適化されないようです。
リスト : 相互再帰 function odd(n) { if (n == 0) return false; else return even(n - 1); } function even(n) { if (n == 0) return true; else return odd(n - 1); }
また、末尾再帰最適化された場合でも、実行速度が速くなるとは限りません。たらいまわし関数を node と babel で試してみました。
リスト : たらいまわし関数 (tak.js) function tak(x, y, z) { if(x <= y) return z; return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y)); } function test(x, y, z) { var s = new Date().getTime(); console.log(tak(x, y, z)); var e = new Date().getTime(); console.log(e - s); }
C>node tak.js 11 3525 C>babel-node tarai.js 11 3615
babel-node のほうが少し遅くなるようです。トランスパイラで末尾再帰最適化を効率的に実装するのは難しいのかもしれませんね。興味のある方はいろいろ試してみてください。また、今後は JavaScript エンジンに末尾再帰最適化が実装されていくでしょうが、どのくらい速くなるのか楽しみにしたいと思います。