Funarg問題

計算機科学において、Funarg問題（関数引数問題）とは、プログラミング言語の実装において、第一級関数（第一級オブジェクトとしての関数）をスタックベースのメモリ割り当てで実装することの難しさを指す。

入れ子になった関数の本体が、関数が定義されている環境では定義されているが、関数呼び出しの環境では定義されていない識別子を直接（つまり、引数の受け渡しによってではなく）参照する場合に問題が生じる。この標準的な解決方法は、このような参照を禁止するか、クロージャを作成することである。

Funarg問題には微妙に異なる2つのバージョンがある。上向きFunarg問題は、関数呼び出しから関数を返す（あるいは 「上方へ 」送信する）場合に発生する。下向きFunarg問題は、関数を別の関数呼び出しのパラメータとして渡すことで発生する。

上向きFunarg問題

一般的なプログラムの実行中に、ある関数が別の関数を呼び出す場合、呼び出し側のローカル状態（パラメータやローカル変数を含む）は、呼び出し側が戻った後に実行を続行するために保持されなければならない。ほとんどのコンパイル済みプログラムでは、このローカルステートは、スタックフレームまたはアクティベーションレコードと呼ばれるデータ構造内の呼び出しスタックに格納される。このスタックフレームは、他の関数を呼び出す前にプッシュ（アロケート、割当）され、他の関数が呼び出しを行った関数に戻るときにポップ（デアロケート、開放）される。呼び出し関数が、呼び出された/呼び出された関数が戻った後に、呼び出された/呼び出された関数の状態を参照する場合、上向きFunarg問題が発生する。そのため、呼び出された関数の状態変数を含むスタックフレームは、関数が戻ったときに開放してはならず、スタックベースの関数呼び出しのパラダイムに違反する。

上向きのFunarg問題に対する一つの解決策は、スタックの代わりにヒープからすべてのアクティベーショ ンレコードを単純にアロケートし、不要になったときにそれらをデアロケートするために、ガベージコレクションや参照カウントのある形式に依存することである。ヒープ上でアクティベーションレコードを管理することは、歴史的にスタック上よりも効率が悪いと認識されており（これは部分的に矛盾しているが）、実装に大きな複雑さを課すと認識されてきた。一般的なプログラム（関数型プログラミング言語のプログラムではそうでもない）のほとんどの関数は、上向きのFunargを生成しないため、実装に関連する潜在的なオーバーヘッドに対する懸念が高まる。さらに、ガベージコレクションをサポートしない言語では、このアプローチは本当に難しい。

効率を重視するコンパイラの中には、静的コード解析によって、その関数が上向きのFunargsを生成しないことをコンパイラが推測できた場合、その関数の活性化レコードをスタックから割り当てるというハイブリッド・アプローチを採用するものがある。そうでない場合は、アクティベーションレコードはヒープから割り当てられる。

もうひとつの解決策は、クロージャの作成時に変数の値を単純にクロージャにコピーすることだ。この場合、クロージャ間で状態が共有されなくなるため、ミュータブル変数の場合は異なる動作になる。しかし，変数が定数であることが分かっていれば，この方法は等価である。ML言語では、変数は値に束縛されるため、このアプローチをとる。Javaもまた、無名クラス（とJava 8以降のラムダ）に関してこのアプローチをとっている。Javaでは、スコープで囲まれている変数のうち、実質的にfinal（つまり定数）であるものしか参照できない。

言語によっては、プログラマがこの2つの動作を明示的に選択できるものもある。PHP 5.3 の無名関数では、どの変数をクロージャに含めるかを use () 節で指定する必要がある。変数が参照で指定されている場合は、元の変数への参照が含まれる。また、アップルのブロックの無名関数では、キャプチャされたローカル変数は、デフォルトで値によってキャプチャされる。クロージャ間、またはクロージャと外部スコープ間で状態を共有したい場合は、__block修飾子を使って変数を宣言する必要がある。

例

以下のHaskellライクな擬似コードは、関数合成を定義している：

compose f g = λx → f (g x)

λは新しい関数を構築するための演算子で、この場合、引数はxの1つで、まずxにgを適用し、次にそれにfを適用した結果を返す。このλ関数は、関数fとg（またはそれらへのポインタ）を内部状態として保持する。

この場合に問題となるのは、compose 関数がパラメータ変数 f と g をスタック上に確保する場合である。compose 関数が戻ると、f と g を含むスタック・フレームは破棄される。内部関数 λx が g にアクセスしようとすると、破棄されたメモリ領域にアクセスすることになる。

下向きFunarg問題

下向きFunargは、関数が実際に実行されていないときの関数の状態を指すこともあるが、定義上、下向きFunargの存在はそれを生成した関数の実行に含まれるため、その関数のスタックフレームは通常スタックに格納されたままである。それにもかかわらず、下向きFunargの存在は、クロージャとスタックフレームのツリー構造を意味し、プログラムの状態に関する人間や機械の推論を複雑にする可能性がある。