Loading article…
コンピュータサイエンスにおいて、関数引数問題（funarg problem）とは、関数のスタックベースのメモリ割り当てを使用するように、プログラミング言語の実装において第一級関数（第一級オブジェクトとしての関数）を実装することの難しさを指します。
問題は、ネストされた関数の本体が、関数が定義されている環境で定義されているが、関数呼び出しの環境では定義されていない識別子を直接参照する場合（つまり、引数渡しではなく）にのみ発生します。[ 1 ]標準的な解決策は、そのような参照を禁止するか、クロージャを作成することです。[ 2 ]
関数引数問題には、微妙に異なる2つのバージョンがあります。上向き関数引数問題は、関数呼び出しから関数を返す（または何らかの方法で「上向きに」渡す）際に発生します。下向き関数引数問題は、関数を別の関数呼び出しの引数として渡す際に発生します。
一般的なプログラムの実行中に、ある関数Aが別の関数Bを呼び出す場合、Bのローカル状態（パラメータやローカル変数を含む）はどこかに保存されなければなりません。リーフ関数では、これはレジスタに保存できますが、Bがそれらのレジスタを使用する別の関数Cを呼び出す場合、Cが戻った後もBが処理を続行できるように、それらのレジスタはメモリ上のどこかに保持されなければなりません。
ほとんどのコンパイル済みプログラムでは、このローカル状態は、スタックフレームまたはアクティベーションレコードと呼ばれるデータ構造でコールスタックに格納されます。このスタックフレームは、B が C を呼び出す前にプッシュ（割り当て）され、B が戻る直前にポップ（解放）されます。上向き関数引数問題は、B の戻り値が、B が戻った後の B の状態（たとえば、ローカル変数 V）を参照する関数 F である場合に発生します。A は F を呼び出す可能性があり、F は V がまだ割り当てられている必要があります。したがって、B の状態変数を含むスタックフレームは、B が戻ったときに解放されてはならず、スタックベースの関数呼び出しパラダイムに違反します。
上向きの funarg 問題に対する解決策の 1 つは、スタックではなくヒープからすべてのアクティベーション レコードを割り当て、不要になったときに何らかのガベージ コレクションまたは参照カウントに頼ってそれらを解放することです。歴史的に、ヒープ上のアクティベーション レコードの管理はスタック上の管理よりも効率が悪いと認識されてきました (ただし、これは部分的に矛盾しています[ 3 ] )、実装の複雑さがかなり増すと認識されてきました。一般的なプログラムのほとんどの関数 (関数型プログラミング言語のプログラムではそれほどではありません) は上向きの funarg を作成しないため、その実装に関連する潜在的なオーバーヘッドに関する懸念が高まります。さらに、このアプローチは、ガベージ コレクションをサポートしていない言語では実際に困難です。
効率性を重視するコンパイラの中には、ハイブリッド方式を採用しているものがあり、静的プログラム解析によって、関数が上位引数を生成しないことがコンパイラによって推論できる場合は、関数のアクティベーションレコードをスタックから割り当てます。そうでない場合は、アクティベーションレコードをヒープから割り当てます。
別の解決策としては、クロージャ作成時に変数の値をクロージャにコピーする方法があります。可変変数の場合、クロージャ間で状態が共有されなくなるため、動作が異なります。しかし、変数が定数であることがわかっている場合は、この方法は同等です。ML言語では、変数は値にバインドされているため（つまり、変数は変更できないため）、この方法を採用しています。Javaも匿名クラス（およびJava 8以降のラムダ式）に関してこの方法を採用しており、実質的に定数である変数のみを囲むスコープ内で参照できますfinal。
一部の言語では、プログラマが2つの動作を明示的に選択できます。PHP 5.3の匿名関数では、句を使用してクロージャに含める変数を指定する必要がありますuse ()。変数が参照でリストされている場合は、元の変数への参照が含まれます。そうでない場合は、値が渡されます。AppleのBlocks匿名関数では、キャプチャされたローカル変数はデフォルトで値でキャプチャされます。クロージャ間、またはクロージャと外部スコープ間で状態を共有したい場合は、変数を修飾子付きで宣言する必要があります__block。この場合、その変数はヒープに割り当てられます。
以下のHaskell風の擬似コードは、関数合成を定義しています。
f g = λx → f ( g x )を合成するλは新しい関数を構築するための演算子で、この場合は引数 を 1 つ取り、に を適用し、次に に を適用したx結果を返します。この λ 関数は、関数および（またはそれらへのポインタ）を内部状態として保持します。gxffg
この場合の問題は、compose 関数がパラメータ変数fとをgスタック上に割り当てる場合に発生します。関数が戻ると、とcomposeを含むスタックフレームは破棄されます。内部関数がにアクセスしようとすると、破棄されたメモリ領域にアクセスすることになります。fgλxg
下方引数は、関数が実際に実行されていないときの関数の状態を指す場合もあります。ただし、定義上、下方引数の存在はそれを生成する関数の実行中に含まれるため、関数のスタックフレームは通常スタック上に保持されます。とはいえ、下方引数の存在はクロージャとスタックフレームのツリー構造を意味し、プログラムの状態に関する人間と機械の推論を複雑にする可能性があります。
下向きの関数引数は、上向きの関数引数の実装とも互換性がある必要があります。たとえば、関数Aが関数Bを呼び出し、Bのローカル変数Vを参照する関数値Fを計算する場合を考えてみましょう。BはFを関数Cの引数として渡し、CはFを呼び出し（下向きの関数引数）、その後戻ります。Bはローカル変数Vを使用し、最後にFをAに返します。AもまたFを呼び出します（上向きの関数引数）。BとFへの2つの呼び出しは、すべて同じローカル変数Vを共有する必要があります。
下方引数問題は、末尾呼び出しの効率的なコンパイルを複雑にします。通常、B が A に戻る前の最後のアクションが関数 C を呼び出すこと (そして C の戻り値を A に未変更で返すこと) である場合、B はC を呼び出す前にスタック フレームを解放することができ、スタックは A が C を直接呼び出した場合と同じ状態になります。一部の言語では、固定された限られた量のスタック領域で再帰的な末尾呼び出しを無制限に実行できることが保証されています。しかし、B が関数 F を C に渡し、F が B のローカル変数 V を参照する場合、C が戻るまで B のスタック フレーム (または少なくとも変数 V) は保持されなければなりません。
同様の問題は、関数が戻り値を返さずに、戻り値を（戻り値を返さない）継続関数に渡して終了する継続渡しスタイルのコードでも発生します。このような呼び出しは、無制限のメモリリークを防ぐために末尾呼び出しとして実装する必要があります。これにより、上向きの引数（BがFを返す）が下向きの引数（BがFを継続関数に渡す）に変わり、Fが呼び出される可能性がある限り、Bのスタックフレームを保持する必要があります。
歴史的に見ると、上向きの funarg 問題はより困難であることがわかっています。たとえば、Pascal プログラミング言語では、関数を引数として渡すことはできますが、戻り値として返すことはできません。そのため、Pascal の実装では、下向きの funarg 問題に対処する必要がありますが、上向きの問題に対処する必要はありません。Modula -2およびOberonプログラミング言語 (Pascal の子孫) では、関数をパラメータと戻り値の両方として使用できますが、代入される関数はネストされた関数であってはなりません。Cプログラミング言語は、関数定義をネストできないようにすることで、歴史的に funarg 問題の主な困難を回避してきました。すべての関数の環境は同じで、静的に割り当てられたグローバル変数と関数のみを含むため、関数のコードへのポインタで関数を完全に記述できます。Appleは、必要に応じてスタックからヒープにクロージャを動的に移動することで上向きの funarg 問題を解決するC 用のクロージャ構文を提案し、実装しました。Javaプログラミング言語では、匿名の内部クラスとローカルクラスのネストされた関数で使用されるコンテキストを宣言し、ラムダ式で使用されるコンテキストを実質的に final にすることで、この問題に対処しています。C#とD言語には、関数ポインタと関連変数をカプセル化するラムダ式（クロージャ）があります。final
関数型言語では、関数はどこにでも渡せる第一級の値です。したがって、SchemeやStandard MLの実装では、上方向と下方向の両方のfunarg問題に対処する必要があります。これは通常、前述のように、関数値をヒープに割り当てられたクロージャとして表現することで実現されます。OCamlコンパイラは、効率を最大化するために、（静的プログラム解析に基づく）ハイブリッド手法を採用しています。