document

HTML5 & JavaScript side
twitter: @y_imaya

asm.js を手書きする

はじめに

人間は誰しもパフォーマンスを求め、最終的には asm.js か WebAssembly を手書きするようになるので、人権を手に入れるためにいつでも asm.js を書ける環境をつくります。 WebAssembly はさすがに手書き厳しそうでした。

というのは冗談で、zlib.js の一部の処理を asm.js で高速化できないかと考え、ひとまず Adler-32 と CRC-32 を asm.js で書き直してみた際にいろいろ苦労したので忘れないようにこの記事を書いています。

なお、今回 asm.js で書いたコードは以下の通り gist で公開しています。 zlib.js での採用はまだ検証が必要なので未定ですが、採用するにしてももう少しきちんとした書き方になるでしょう。

asm.js 手書き環境の整備

JavaScript shell

asm.js は Mozilla が言い始めただけあって Firefox で実行するのが一番良いのですが、毎回 Firefox で実行するのは正直手間です。 そこで、ここでは Web ブラウザを使わずにコマンドラインだけで asm.js として正しいかチェックを行う環境を JavaScript shell を使って構築していきます。 JavaScript shell とは Mozilla の JavaScript エンジン SpiderMonkey のコマンドラインツールです。

概要:https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Introduction_to_the_JavaScript_shell

ダウンロードと準備

下記のURLから、最新版の jsshell をダウンロードしましょう。

https://archive.mozilla.org/pub/firefox/nightly/latest-mozilla-central/

あとは展開してパスを通し、

$ js -w -c hoge.js

のように js ファイルを指定して実行すると、asm.js のチェック(というか、実際にコンパイルを試みる)を行います。 なお、 -w オプションは warning を表示するオプションで、asm.js まわりのメッセージは warning として出力されるため必要となり、 -c オプションはコンパイルのみ行い、実行はしないというオプションです。asm.jsとしてただしいコードかどうかはコンパイルできるかどうかで判別できるので、実行する必要はありません。

watch

各々の好きなタスクランナーで asm.js のコードが変更されたら JavaScript shell でチェックを行うようにすると便利です。

一例として npm scripts で chokidar-cli を使って行う場合の手順を書いておきます。

ディレクトリ構成

src 以下に *.asm.js というファイル名で asm.js のコードを置き、vendor/jsshell に JavaScript shell を配置しています。

.
├── package.json
├── src
│   ├── adler32.asm.js
│   └── crc32.asm.js
└── vendor
    └── jsshell
        ├── js
        ├── libmozglue.dylib
        └── libnss3.dylib

chokidar-cli のインストール
$ npm i -D chokidar-cli
npm scripts の登録

package.json 内の scripts に以下のように watch を追加します。

  "scripts": {
    "watch": "chokidar src/**/*.asm.js -c \"vendor/jsshell/js -w -c {path}\""
  },
監視の開始
$ npm run watch

これで src/ 以下に *.asm.js となるファイルを作ったり更新したりすると、JavaScript shell によるチェックが行われるようになりました。

ひとまず、 asm.js を手書きで開発していく環境が整ったと言っても良いでしょう。

asm.js で詰まったポイント

仕様を軽く読んだだけでは覚えきれず、詰まったポイントが幾つかあったので詰まった現象と対処法を書いておきます。 型関係のエラーは大体言われてすぐ気がつくので省略します。

32bit整数同士の掛け算が * 演算子で行えない

具体的には

TypeError: asm.js type error: one arg to int multiply must be a small (-2 ^ 20, 2 ^ 20) int literal

というエラーの場合、asm.js の仕様 に書いてあるように Math.imul を使いましょう。

Uint8Array, Int8Array 以外のヒープのビューにアクセスするときにエラーが出る

具体的には

TypeError: asm.js type error: index expression isn't shifted; must be an Int8/Uint8 access

というエラーです。

asm.js の仕様 によると index が数値ではなく expression の時は右シフトしなくてはならないので、 array[index << 2 >> 2] のようにしましょう。 (この仕様は正直通常のJSで遅くなるのでツライ)

大きなヒープで何度も計算すると素のJSよりも遅くなる

asm.js では function の引数などに配列を使うことはできません。 では、どうするかというと最初に Heap (ArrayBuffer) を asm.js コードに渡してやり、その中で Uint8Array などでビューを作ってやり、自分でメモリの構造を決め、asm.js 内の各 function では index と length を使ってここからここまでは何々の配列として扱う、みたいなことをします。

CRC-32 の計算では事前計算テーブルとデータという2つの配列を扱わなくてはならないため、この2つの配列を結合するあたらしい ArrayBuffer を作り、それを heap として asm.js のコードを呼んでいました。 このときのヒープの構造は 0-1023 バイトまでは事前計算テーブル(32bit*256個)、1024 バイト以降は CRC-32 に渡すデータとして扱う、という形にしました。

なお、この際

var table = new stdlib.Uint32Array(heap, 0, 256);
var data = new stdlib.Uint8Array(heap, 1024);

のようにビューでわかりやすくすればいいのでは、と思ってやってみたところ asm.js では許されていませんでした。(コンストラクタの引数は heap のみの一つだけ、と言われます) TypedArray#subarray などのメソッドも使えないので素直に先頭からの index でアクセスしましょう。

こうして、配列の CRC-32 ハッシュ値を求めようとする際に、毎回テーブル+データのヒープを作ってasm.jsに渡す素直な実装が出来たわけですが、当然 ArrayBuffer の作成と(計算が行われた後は使わなくなるため)破棄が行われ、何度も実行していると GC が大量に発生することになり、asm.js 化する前より性能が落ちたりします。

function crc32_asm(data) {
  var table = new Uint32Array([
    // CRC-32 の事前計算テーブル
    ...
  ]);

  function asm(stdlib, foreign, heap) {
    "use asm";

    var heapUint32 = new stdlib.Uint32Array(heap);
    var heapUint8  = new stdlib.Uint8Array(heap);

    function calc(pos, length) {
      // CRC-32 の計算をして返す
    }


    return {
      calc: calc
    }
  }

  // 事前計算テーブルとCRC-32を求めたい配列の結合
  var tableUint8Array = new Uint8Array(table.buffer);
  var dataLength = tableUint8Array.length + data.length;
  var heapSize = 1 << 8;
  while (dataLength  > heapSize) {
    heapSize <<= 1;
  }
  var heap = new ArrayBuffer(heapSize);
  var heapUint8Array = new Uint8Array(heap);

  heapUint8Array.set(tableUint8Array);
  heapUint8Array.set(data, tableUint8Array.length);

  // asm.js にヒープを渡し、返ってきた calc 関数に引数を渡しそのまま実行 
  return asm(self, {}, heap).calc(0, data.length) >>> 0;
}

Web ブラウザの開発ツールでプロファイルを取ったところ、GC が支配的になっていることに気づいたので、ArrayBuffer の作成を最低限に抑えるようにしました。

具体的には、asm.js コード全体を呼び出すのは現在のヒープサイズでは足りない際に、ArrayBuffer を倍の長さで作り直した時だけで、それ以外は以前のヒープに TypedArray#set でデータを上書きし、 asm.js コードの実行によって得られた function によってハッシュ値を計算するようにしました。

function crc32_asm() {
  var table = new Uint32Array([
    // CRC-32 の事前計算テーブル
    ...
 ]);

  function asm(stdlib, foreign, heap) {
    "use asm";

    var heapUint32 = new stdlib.Uint32Array(heap);
    var heapUint8  = new stdlib.Uint8Array(heap);

    function calc(pos, length) {
      // CRC-32 の計算をして返す
      ...
    }

    return {
      calc: calc
    }
  }

  function calcBufferSize(data) {
    return 1024 + data.length;
  }

  var tableUint8Array = new Uint8Array(table.buffer);
  var heapSize = 1 << 16;
  var heap;
  var heapUint8Array;
  var asmFunctions;

  function init() {
    update(new Uint8Array(0));
  }

  // バッファの拡張と事前計算テーブルをセットして asm.js を実行し直す
  function update(data) {
    var requireBufferSize = calcBufferSize(data);

    while (requireBufferSize > heapSize) {
      heapSize <<= 1;
    }

    heap = new ArrayBuffer(heapSize);
    heapUint8Array = new Uint8Array(heap);

    heapUint8Array.set(tableUint8Array);
    asmFunctions = asm(self, {}, heap);
  }

  function calc(data) {
    // 現在のヒープサイズで足りないときだけ、asm.js を実行し直す
    if (calcBufferSize(data) > heapSize) {
      update(data);
    }

    // データを heap にセットする
    heapUint8Array.set(data, 1024);

    return asmFunctions.calc(0, data.length) >>> 0;
  }

  init();

  return {
    calc: calc
  };
}

複数の配列を扱いたいという場合はわりとよくあると思うので、このバッファの使い回しは asm.js では基本となると思います。

また、私見ですがこのバッファの使い回しをすすめていくと、Webアプリケーション全体をプロセスとみなし、このバッファがプロセス内のデータセグメントとスタックセグメントのようになるのではないかと思います。 どういうことかというと、Webアプリケーション内全体で一度に大きな ArrayBuffer を確保し、asm.js で使用する変数や配列などをこの ArrayBuffer の中で割り当てていくメモリ管理コードを持つようになるということです。 このとき、長く使いそうなものは上から、一時的なものは下から積み上げていく、つまりプロセスにおけるデータセグメント内のヒープ領域とスタックセグメントのような形が考えられます。 そして、ヒープ領域の拡張時に断片化の解消などを含むメモリ管理の仕組みを再実装していくことになるのではないかと思います。

実際、Emscripten における runtime.js がそのような仕組みになっています。これは Emscripten が他言語で書かれたアプリケーションを動かすのを目的としているので、既存のプロセスのメモリ管理に相当する実装があるのは当然かも知れません。

つまり、人の手による温かみのある asm.js とは最終的にはほぼ Emscripten と同じようなコードになり、 asm.js の手書きとは人間 Emscripten になることであり、人権が失われ機械として生きていくということです。

zlib.js 0.3.0 リリース

致命的なバグの修正

HLIT と HDIST のデコードに関するバグ修正

Inflate において、リテラルと長さ符号(HLIT)と距離符号(HDIST)の展開において不具合があったため、Inflate に失敗あるいは正しくないデータになってしまうことがありました。 これはどういうことかと言うと、HLIT と HDIST は連続して格納されていますが、その中で同じ符号が連続する場合は繰り返しを行う処理があります。 0.2.0 までの実装では、HLIT と HDIST をそれぞれ別の配列として扱っていたため、 HLIT と HDIST をまたぐような繰り返し符号が出現していた際、誤ったデータが展開されてしまっていました。

0.3.0 では HLIT と HDIST の展開を連続する配列として展開し、その後のハフマン符号テーブルを構築する際に HLIT と HDIST を分離して行うようにしています。

仕様でいうと RFC1951 の 3.2.7 にある以下の部分を誤って実装していたということです。

The code length repeat codes can cross from HLIT + 257 to the
HDIST + 1 code lengths.  In other words, all code lengths form
a single sequence of HLIT + HDIST + 258 values.

不正な Deflate データによる無限ループの修正

0.2.0 までは細工された Deflate データを伸長しようとすると、無限ループに陥る場合がありました。 ハフマン符号を使ってリテラル・長さ符号と距離符号を取得する際、ハフマン符号のコード長が不正になっており、無限に読み込もうとして無限ループに陥ってました。

0.3.0 ではコード長をチェックして明らかに不正な場合、例外を投げるように修正しました。

その他のバグ修正

PKZIP 作成時、余計な領域が後ろに残っているバグの修正

0.2.0 までは PKZIP の作成を行うと、後ろに余計な領域が残っており、厳密なアーカイバで展開しようとすると「データのペイロード後にデータが存在します」という警告が出ていました。 これは "End of central directory record" のサイズ計算が誤っていて、余分にバッファを確保してしまうせいです。

https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT の 4.3.16 にある通り、22 が正しいサイズです。

このバグと修正方法についてはzlib.js 0.2.0のzip.js/zip.min.jsのバグの修正[ZIPファイルの破損]によって報告されていました。 @TakeshiOkamoto さん、ありがとうございました。

ビルド・テスト環境の変更

Ant によるビルドと BusterJS によるテストから、 Grunt によるビルドと Karma + mocha + power-assert によるテストに変更しました。 Grunt にする作業自体はだいぶ前に行っていたのですが、すでに時代遅れになっている気もするのでさらに変更するかもしれません…。

難読化されたJavaScriptコードを読む

はじめに

何らかの事情で JavaScript のコードを読み、その挙動について調査しなくてはいけないということはよくあると思います。
そんなとき、難読化やMinifyなどによって複雑怪奇に見えるコードに遭遇したという経験をもつひとも多いのではないでしょうか。

この記事はそんなコードにぶつかった際に、どうすれば良いのかを自分なりにまとめてみました。

また、jjencode 作者のはせがわようすけさんのJavaScript難読化読経というスライドを見て、
作者がネタバレしてるんだからこの辺の知見について書いても大丈夫だろうという気持ちで書き始めたことも一応記しておきます。

ツールによって難読化されたコードの読み方

まずはコードリーディング出来る状態にするため、よく見る2つのツールによる難読化のデコード方法について書いておきます。

Javascript Obfuscator

Javascript Obfuscatoreval(function(p,a,c,k,e,d){... から始まる特徴的なコードにエンコードするツールです。
このエンコードされた JavaScript コードは、先頭の evalconsole.log にするだけでデコードすることが可能です。
パッと見でのコードリーディングを防ぎたいというくらいの効果しかありません。

jjencode, aaencode, etc.

コードを読もうとしたとき、記号プログラミングの手法によって読みにくくなっていることがあります。
そうした場合は、開発ツールのコンソールを使ってデコードするところから始めます。
難読化ツールとしては jjencode が有名です。
これらの難読化ツールは基本的に number.constructor.constructor を使うことで Function を引き出し、Function(実行したいスクリプト本体文字列) とすることで任意のコードを実行しています。
booleanstring を使っても同様のことが出来るので、Number がハズレだったら StringBoolean を試すとよいでしょう)

蛇足かもしれませんが説明しておきますと、number.constructorNumber であり、Number.constructorFunction となります。

(0).constructor
=> Number() { [native code] }

(0).constructor.constructor
=> Function() { [native code] }

つまり、下記のように Number.constructorconsole.log にしてやることで、実行しようとしているコードを確認することができます。

Number.constructor = console.log.bind(console);

また、コードが何らかの悪意を持っている可能性がある場合は、下記のように debugger 文を使って実行を中断しましょう。(あるいは、例外を投げて失敗させても良いでしょう)

Number.constructor = function() {
    console.log(arguments);
    debugger;
};

記号プログラミングによる難読化手法は、より詳細な説明をはせがわようすけさんが資料を公開しているのでそちらを参照してください。

このように、jjencode などのエンコーダによる難読化は簡単にデコードできるため、解読を防ぐ用途での効果は期待しない方がよいでしょう。
実際、jjencodeには下記のように注意書きがされています。

Be aware

Using jjencode for actual attack isn't good idea.
- Decode easily. jjencode is not utilitarian obfuscation, just an encoder.
- Too characteristic. Detected easily.
- Browser depended. The code can't run on some kind of browsers.

Minify/Compile/Transpile されたコードの読み方

ここから、本来のコードリーディングの作業に入っていきます。
Minify/Compile/Transpile(以下、まとめてMinifyと表記します) されたコードをどのように追っていくかという話題です。
当然、SourceMap は提供されてないことを前提とします。

Pretty Print ツールによるソースコードの整形

まずは、ごちゃごちゃしているコードを Pretty Print (読みやすい形に変換)します。
Google Chrome などの開発者ツールについている Pretty Print でも良いのですが、後々のために Pretty Print した別のファイルにしておきます。

例えば、下記のようなコードを

function hello(a){alert("Hello, "+a)}hello("New user");

このようにきれいに整形してくれます。(例は Closure Compiler のオンラインサービス版の初期コード)

function hello(a) {
    alert('Hello, ' + a);
}
hello('New user');

Pritty Print する方法はいくつかありますが、自分は esprimaescodegen による Pretty Print スクリプトを愛用しています。

IDEによるリファクタリング

Pretty Print してしまえばあとは頑張ってコードを読んでいくだけなのですが、そのまま読んでいくのは人類には厳しいのでIDEのサポートを受けながらコードを読みやすい形に修正しながら読み進めていきます。
なぜIDEを使用するかというといくつかの理由がありますが、lintを使うなど他の環境でも同様のことができるなら問題ありません。
自分は WebStorm や Visual Studio を使っています。

unused variable の除去

未使用の変数は見つけ次第どんどん削除していきましょう。

dead code の除去

未使用の変数と同様に、到達しないコードもIDEが教えてくれるので削除していきます。

変数名/function名のリネーム

Minifyされたコードは変数やfunction名が a とか b といった短い名前に変更されています。
しかも、別のスコープでまた a とか b となっていくので、どれがどれだかややこしくなっています。
これをIDEのリファクタリング機能のリネームを活用することで分かりやすい名前にしていきます。
(どういう名前にするかは、コードをよく読んで推測するしかない)
単なる置換よりも、スコープなどを適切に判断してくれるIDEのリファクタリング機能の方が便利です。

変数の使いまわしの分離

Closure Compiler ではファイルサイズ優先の Minify を行うため、元々は別の変数だったものを同じ変数を再度利用することがあります。
(オプションで変更することは可能だが、オプションの変更を行うには自分でビルドしなおすか外部ツールを使用するしかありません)
そういった変数を見つけ出して、それぞれ別の変数に分離します。
簡単にですが見分けたい場合を書いておくと、数値をいれてる変数に文字列を入れるなど、別のものを同じ変数に入れていたら注意して読んだ方が良いでしょう。

6to5 に末尾呼び出し最適化が入ったと思ったら一瞬でなくなった

一昨日の記事を書いた後、末尾呼び出し最適化の実装にバグがあって速攻で消されたようです。

  • v3.5.0: 末尾呼び出し最適化の実装が入る
  • v3.5.1: 他のTailオブジェクトと混同して判定されてしまうため、Tail.prototype._isTailDescriptor というのを付けて対処
  • v3.5.2: _tailCall をつかった末尾呼び出し最適化がコメントアウト
  • v3.5.3: v3.5.0 以前の末尾再帰最適化の実装に戻す

少し見たところ、以下のようなケースでうまく動かないようです。

function foo() {
  return "foo";
}

function fooWrapper() {
  return foo();
}

function test() {
  var str = fooWrapper();
  if (str !== "foo") {
    throw new Error();
  }
}

function testWrapper() {
  return test();
}

testWrapper();

なぜこのケースでうまく動かないのか見ていきます。
このコードを 6to5(v3.5.1) で変換したものがこちらです。

"use strict";

var _tailCall = (function() {
    function Tail(func, args, context) {
        this.func = func;
        this.args = args;
        this.context = context;
    }
    Tail.prototype._isTailDescriptor = true;
    var isRunning = false;
    return function(func, args, context) {
        var result = new Tail(func, args, context);
        if (!isRunning) {
            isRunning = true;
            do {
                result = result.func.apply(result.context, result.args);
            } while (result instanceof Tail || result && result._isTailDescriptor);
            isRunning = false;
        }
        return result;
    };
})();

function foo() {
    return "foo";
}

function fooWrapper() {
    return _tailCall(foo);
}

function test() {
    var str = fooWrapper();
    if (str !== "foo") {
        throw new Error();
    }
}

function testWrapper() {
    return _tailCall(test);
}

testWrapper();

呼び出し順序は以下の順序です。

testWrapper
  _tailCall(test)
    test
      fooWrapper
        _tailCall(foo)

ここで問題となるのが _tailCall(foo) です。
これはもともと return foo(); なので "foo" が返るはずです。
しかし、この呼び出し順序では最初の _tailCall(test) が呼ばれた時に isRunnningtrue になるため、 _tailCall(foo) は Tail オブジェクトを返します。
var str = fooWrapper();str の値が Tail オブジェクトになってしまうため、変換前の結果と異なってしまいます。

今回のように他の末尾呼び出ししている function の戻り値を変数に代入するようなケースでもうまく動くような修正が入らなければ、再び末尾呼び出し最適化を有効にするのは難しそうな気配を感じます。
(現在はもともと入ってた末尾再帰最適化での高速化を行っているようです)
そのほかにもパフォーマンスの問題もあるので大変そうですが、はやく再び有効になると良いなあと思います。

6to5 に末尾呼び出し最適化が実装されたので調べてみた

@azu_re さんのツイートで知ったのですが、6to5 に末尾呼び出し最適化が追加されました。

ECMAScript 6 compatibility table によると ES6 transpiler では初めてテストを通った実装のようです。

6to5 ではどのような ECMA−262 5th のコードに変換して実現しているのか気になったので調査してみました。

末尾呼び出し最適化って何?

その前に「末尾呼び出し最適化って何?」って人のために簡単に説明しておきます。
通常、再帰するようなコードを書くとこんな感じになります。

function f(num) {
  var acc = arguments[1] || 0:
  return num <= 0 ? acc : f(num - 1, acc + num);
}

var result = f(5);
console.log(result);

この場合だと 5+4+3+2+1 を計算するコードですね。
f の呼び出しに注目すると、f(5) の中で f(4, 5) が呼ばれ、その中でさらに f(3, 9) が呼ばれ…という感じになっています。
この呼び出しをインデントで表すと以下のようになります。

result = f(5);
    return f(4, 5);
        return f(3, 9);
            return f(2, 12);
                return f(1, 14);
                    return f(0, 15);
                        return 15;

このように、再帰するたびにコールスタックが増えていきます。
コールスタックが増えるたびに f のスコープの変数なども保持していなくてはならないため、メモリをどんどん消費していきます。
(なお、ブラウザによりますがコールスタックがあまりに増えすぎると例外を投げて止まります)

それはよくないということで、return するときに function 呼び出している場合は現在のスコープを破棄して、呼び出している function の戻り値をそのまま呼び出し元に返すようにします。
これを末尾呼び出し最適化といいます。

あまり正確ではありませんが、前述の呼び出しに末尾呼び出し最適化を適用すると以下のようになります。
呼び出し自体は変わっていないのですが、呼び出し元がずっと同じイメージです。

result = f(5);
    return f(4, 5);
    return f(3, 9);
    return f(2, 12);
    return f(1, 14);
    return f(0, 15);
    return 15;

実際に変換してみる

元となるコードは下記の通り。

function f(num, acc=0) {
  return num <= 0 ? acc : f(num - 1, acc + num);
}

var result = f(5);
console.log(result);

これを 6to5 で変換したのがこちら。
_tailCall が一行になっていて読みにくいので Google Chrome の開発者ツールで整形しています。

"use strict";

var _tailCall = (function() {
    function Tail(func, args, context) {
        this.func = func;
        this.args = args;
        this.context = context;
    }
    var isRunning = false;
    return function(func, args, context) {
        var result = new Tail(func, args, context);
        if (!isRunning) {
            isRunning = true;
            do {
                result = result.func.apply(result.context, result.args);
            } while (result instanceof Tail);
            isRunning = false;
        }
        return result;
    };
})();

function f(num) {
    var acc = arguments[1] === undefined ? 0 : arguments[1];
    if (num <= 0) {
        return acc;
    } else {
        return _tailCall(f, [num - 1, acc + num]);
    }
}

var result = f(5);
console.log(result);

まず、return num <= 0 ? acc : f(num - 1, acc + num); の条件演算子が最適化され、retrun accreturn _tailCall(f, [num - 1, acc + num]); に分解されています。

ここからが末尾呼び出し最適化のキモで、_tailCall というメソッドが何を行っているのか見ていきます。

_tailCallfunc, args, context の3つの引数をとります。
func は元の function, args はその引数, context はおそらくレシーバを指しています。
これらは元となる function を function.prototype.apply で実行するのに不可欠だからです。
これらのコンテキストを Tail というオブジェクトにしています。

最初の呼び出しだけ do-while のループに入るようにして、次回以降はそのまま Tail オブジェクトを返すようにしています。
これは何をしているのでしょうか?
このコード例を元に条件文や変数を都度展開して追っていくと以下のようになります。

1. result = f(5);
    // f(5, 0)
    2. return _tailCall(f, [4, 5]);
        3. result = new Tail(f, [4, 5], undefined)
        4. result = result.func.apply(undefined, [4, 5])
            // f(4, 5);
            5. return _tailCall(f, [3, 9]);
                6. result = new Tail(f, [3, 9], undefined);
                7. return result; // Tail Object
        8. result = result.func.apply(undefined, [3, 9]);
            // f(3, 9);
            9. return _tailCall(f, [2, 12]);
                10. result = new Tail(f, [2, 12], undefined);
                11. return result; // Tail Object
        12. result = result.func.apply(undefined, [2, 12]);
            // f(2, 12);
            13. retrun _tailCall(f, [1, 14]);
                14. result = new Tail(f, [1, 14], undefined);
                15. return result; // Tail Object
        16. result = result.func.apply(undefined, [1, 14]);
            // f(1, 14);
            17. retrun _tailCall(f, [0, 15]);
                18. result = new Tail(f, [0, 15], undefined);
                19. return result; // Tail Object
        20. result = result.func.apply(undefined, [0, 15]);
            // f(0, 15);
            21. return 15; // not Tail Object
        22. return 15;

これを見るとわかるように、2回目以降の _tailCall 呼び出しはその場で function を呼び出すのではなく、Tail オブジェクトを返すようにすることでコールスタックが深くなっていくのを避けています。

追記(2015/02/10 13:00)

末尾呼び出し最適化の実装が不完全だったため v3.5.2 以降でこの実装は除外されました。
詳しくは別途記事を書いたのでそちらを見てください。

記事検索
最新コメント
最新トラックバック
カテゴリ別アーカイブ
タグクラウド
QRコード
QRコード
  • ライブドアブログ