ファンタスティックなテール・コールとその実行方法
再帰はコンピュータ・サイエンスの基本的なプリミティブのひとつである。多くのアルゴリズムは、一般的な問題を再帰的な部分問題に単純化することによって生まれた。コードの観点からは、再帰は関数がそのロジックの一部として自分自身を呼び出すことを意味する。スタックは関数のインスタンスごとに消費されるため、過剰な再帰の深さはスタックオーバーフローとして知られる問題を引き起こす！
再帰呼び出しがたまたま末尾の位置（つまり関数が戻る直前）にある場合、この問題は末尾再帰を使うことで解決できる。この文脈では、呼び出し側のスタック・フレームを再利用してから呼び出し側にジャンプすることで、呼び出しを末尾呼び出しに変えることができる。これは、関数型プログラミング言語の一部で使用されているCPS（Continuation Passing Style）の重要なコンセプトであり、関数は戻り値を返さず、その結果に対してルーチンを呼び出し、スタックを使い切らないようにテールコールを使用する。
WebAssemblyは、ブラウザでネイティブかつ効率的に実行できる最新のバイトコードです。WebAssemblyは、関数型を含む他のほとんどのプログラミング言語に適したコンパイラ・ターゲットとして設計されている。速度と効率はWebAssemblyの設計の核心であり、テールコールが標準の拡張として提案されたのは当然のことである。
提案が完全に承認された標準になるには、2つの異なるブラウザ・エンジンで実装されるなど、いくつかのステップが必要だ。ChromeとEdgeで使用されているエンジンであるV8は、2020年にWebAssemblyのテールコールのサポートを追加した。これは正しい方向への一歩だったが、それ以来、提案の状況は停滞している。
AppleのWebkitはすでにECMAScript 6で適切なテールコールを実装している.,)ため、私たちはこの機能を実装し、提案の状況を前進させ、最終的には完全な標準化に向けて前進させる良い目標になると考えました。
この記事は、WebKitにどのようにこの機能を実装したかを読者に理解してもらいながら、WebAssemblyのテール・コールを解明することを目的としています。
記憶を呼び覚まそう...。
マシンレベルで関数の引数を表現するさまざまな方法があり、それらは「呼び出し規約」と呼ばれています。ここでは、SafariのJavaScriptエンジンであるJavaScriptCoreにおけるコールスタックの割り当て方法と引数の渡し方に焦点を当てます。同様の理由は他の環境にも当てはめることができます。
次のCコードは、数値の階乗を計算して表示するための末尾再帰的な解決策の典型的な例を示しています。
view rawprint_factorial.c hosted with ❤ by GitHub
最初の再帰呼び出しに注目してみよう。 factorial.
2つの定義が必要だ：
・呼び出し側: factorial 0、factorialの最初のインスタンス。
・呼び出し側: factorial 1、factorialの最初の末尾再帰呼び出し。
マシン・レベルで何が起こっているかを理解するためには、2つのプレーヤーを導入する必要がある。現在のフレームの最初のバイトを指すフレーム・ポインターと、スタックの先頭を表すスタック・ポインターである。フレーム・ポインターは現在のフレームの最初のバイトを指し、スタック・ポインターはスタックの先頭を表す。JavaScriptCoreでは、これにはスタック値、仮想レジスタ、ローカル変数、コールフレームヘッダーが含まれます。後者には、前のフレームポインタや呼び出し元の命令ポインタなど、「戻る」ために必要な状態が含まれる。
引数は、呼び出し元から呼び出し先に情報を伝えるために使用される。引数を渡す方法には、レジスタに格納する方法とスタックに格納する方法がある。レジスタで渡す方法が理想的である。というのも、利用可能なレジスタ数よりも多くの値がある可能性があり、その場合、それらはスタックに「こぼれる」ことになるからである。スタック・スペースの管理は、テール・コールを実装する上で重要な側面のひとつである。
factorial 0がfactorial 1を呼び出す場合、まずその呼び出し側のプロローグを確認する：
push $arg... | caller’s frame (factorial 0)
push $argN |
call $factorial /
push %rbp \
mov %rsp, %rbp | callee’s frame (factorial 1)
最初の命令はスタックポインタを前のフレームのアドレスにリセットする。pop命令はプロローグのpushに対応し、呼び出し元に入る前のスタックフレームに戻し、呼び出し元が再びローカルデータにアクセスできるようにする。retは、最後の呼び出し命令によってスタックトップに格納されたアドレスを使用して制御フローをリダイレクトし、呼び出し元のフレームに戻ることを可能にする。
引数に1を指定してfactorialを呼び出すと、factorial 1で再帰が終了し、2つのエピローグを経ることになる：
push $arg0 \
push $arg... | caller’s frame (factorial 0)
push $argN |
call fib /
push %rbp \
mov %rsp, %rbp |
... | callee’s frame (factorial 1)
mov %rbp, %rsp |
pop %rbp |
ret /
mov %rbp, %rsp \
pop %rbp | caller’s frame (factorial 0)
ret /
これは無駄であり、最適化できる。ここに、テールコールの排除という概念がある。テールコールの排除とは、着呼側を着呼側の延長とみなすことである。
WebAssembly での実行方法： return_call
以下は、テールコールを有効にした、階乗の例に相当するWebAssemblyです。
print_factorial.wat hosted with ❤ by GitHub
JavaScriptCoreでは、まずWebAssemblyが解析され、検証された後、ネイティブ・コードが生成され、実行がマシンに委譲される。
テールコールは通常のコールの一種であるため、エンジン内の既存のインフラのほとんどを再利用することができた。新しいルーチンは、着呼側のプロローグに入る前にフレームを準備するために追加された。これらの修正は、WebAssemblyの静的型付けのおかげで、実行時に収集された情報を必要としない。
factorial 0が初めて自分自身を再帰的に呼び出すときである。簡単のため、print_factorial → factorial 0 → factorial 1の呼び出しの連鎖をA → B → Cに抽象化する。
図1. C（factorial 1）コールサイトのスタック。
Bはreturn_call命令を含むので、スタックの適合を担当しなければならない。テールコールを実行した後のフレームは必要ない。
したがって、Cにジャンプする前に、BとAをマージする。
図2. C（factorial 1）にテール・コールする前の、並べ替え後のスタック。
Bのデータで何が変わったかに注目してほしい。Aが最初にBを呼び出したときにスタックにプッシュされた値を保持することで、CがAに戻ることを確認した（図1）。後で、CPUが保存されたリターン・アドレスを上書きしないように、callではなくjmp命令でCを開始するようにします。
CはBの拡張であるとはいえ、Bが担当する情報に依存していることに変わりはない。そのため、Cの引数を格納するためにAのスタック空間を再利用した（図2）。これを実行するには、BとCがどれだけのスタック・スロットを必要とするかを知る必要があった。静的解析中に関数のシグネチャを推論することで、その情報を得ることができた。
幸いなことに、変数引数はWebAssemblyの設計に含まれていないため、心配する必要はありませんでした。そして、新しいスタックオフセットを計算し、必要なものをBからAにコピーすることができます。
興味深いことに、Aから見ると、AとBはマージされたと言えます。この時点で、Cにジャンプする準備ができた。
ここでは、factorialの深い再帰的呼び出しを、return_callを使った場合と使わなかった場合の両方で比較する。
図3. 深い再帰ルーチンにおけるスタックの比較。
return_callを使用すると、階乗とそのすべての潜在的な再帰に1つのフレームしか使用しないことがわかる。
引数 vs. 返り値
WebAssemblyは複数の戻り値もサポートしています。これは、引数によって使用されるスタックが、呼び出し側の戻り値を等しく格納することを意味する。AはBの戻り値のために十分なスペースを持っていると仮定できるので、これはテールコールとうまく機能します（図4）。また、テールコールの仕様は、Bが同じ数の値を返す関数のみをテールコールできることを保証する。しかし、この場合、スタック上のオフセットに関する懸念が生じる。
図4. Bコールのスタック。Bの戻り値のための予約領域
JavaScriptCoreが実装していた以前の規約では、図4のようにフレームを準備し、戻り値をスタックポインタの近くに配置していた。テールコールの場合、フレームが再利用される可能性があるため、引数の数が変化する呼び出しが連鎖した場合、スタックのサイズが変化する。このような状況では、Aは期待したオフセットで戻り値を見つけることができない（図5）。
図5. A -> B -> Cのテール・コール・チェーンの異なる段階でのスタック。Cの引数の数がAのスタック・サイズを変更した。たとえリターン・カウントがCのシグネチャで保持されていたとしても、CがリターンしたときにAは間違ったオフセットでリターン値を期待する。
これは、関数のコード解析時にスタック値のオフセットが静的に計算されるためである。解決策として、スタックの反対側、つまり呼び出し元のフレーム・ポインタに近い側で戻り値をエンコードするように規約を変更した。
図6. 図5と同じ描写で、Aが適切に戻り値を収集できるようにオフセットが設定されている。
AがBを呼び出したかのようにスタックポインタを復元すると、期待された場所で戻り値を見つけることができる。
したがって、WebAssemblyにおけるテール・コールの実行可能な実装を実証したことになる。この機能は概念的には簡単ですが、例えば例外処理など、スタックに関わる多くの可動部分を持つ複雑なコードベースの中で、その場所を見つけなければなりません。この実装は、執筆時点ではまだレビュー中であり、より技術的なフォローアップについてはプルリクエストを参照してほしい。
次のステップ
我々は、WebAssemblyのテールコールがJavaScriptCoreにまもなく登場することを期待している。そうなれば、提案は事実上次の段階に進み、完全な標準化への道が開かれるでしょう。
私たちがWebKit / Safariでテールコールを利用できるようにし、最終的にはWebAssembly標準でも利用できるようにする当初の動機は、ブラウザでx86バイナリを実行するように設計された私たちの仮想マシンであるCheerpXのパフォーマンスを向上させることでした。以前の記事で述べたように、WebAssemblyでテール・コールを可能にすることで、ライブラリ・コールを実装するためによく使われる間接ジャンプの場合に、JIT化されたコードのオーバーヘッドを減らすことができる。
大まかに言えば、この標準化は、LLVMが「musttail」マーカーを持つ呼び出しとして表現するC++20コルーチンのような最新のプログラミング言語の機能をサポートする上で、最新のブラウザに役立ちます。これは、WebAssemblyではテール・コールなしでは適切に表現できません。
この貢献を通じて、WebAssemblyのテールコールを実験的な状態から完全に標準化された機能へと移行させ、すべての主要なブラウザで誰もが利用できるようにすることを目指しています。
引用元：https://leaningtech.com/blog/2022/07/11/fantastic-tail-calls-and-how-to-implement-them/
Discussion