利用者:Penguinafy/Funarg問題

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

関数定義がネストしているとき、内側の関数の本体ではその関数の引数以外の変数を参照しうる。Funarg 問題が難しくなるのは、そのような変数が参照する値は関数呼び出し時の環境で定まるのではなく、関数定義時の環境で定まる状況においてのみである。そのような変数の参照を単に禁止するか、クロージャを生成することで問題を解決することが多い。

Funarg 問題は２つに分類できる。上への funarg 問題は関数を関数呼び出しの結果として返すことで生じ、下への funarg 問題は関数を他の関数の引数として渡すことから生じる。

上への funarg 問題

プログラム実行の中である関数が他の関数を呼び出すとき、呼び出す側の関数のローカルな状態（引数やローカル変数など）は、呼び出された関数から実行が戻ったあと、計算を再開するために保存する必要がある。ほとんどのコンパイルされたプログラムでは、ローカルな状態をコールスタック上のスタックフレーム（アクティベーションレコードとも呼ばれる）に保存する。スタックフレームは関数を呼び出す際にプッシュ（メモリ割り当て）され、関数が返る際にポップ（メモリ開放）される。このような関数呼び出しの実装手法をスタックベースの関数呼び出しパラダイムと呼ぶ。上への funcarg 問題は呼び出し側の関数が、関数呼び出しの結果として得た関数を通して、呼ばれた関数のローカルな状態を参照した場合に生じる。このような参照を有効にするためには、関数が返る際にローカルな状態を開放せずに保持する必要があり、スタックベースの関数呼び出しパラダイムを崩すことになる。

コールスタックを使わずに、アクティベーションレコードをヒープに割り付けることでこの問題は回避できる。この場合、不要になったメモリの開放をガベージコレクションや参照カウントで実現する。アクティベーションレコードをヒープに割り付ける手法はスタックを用いる手法よりも効率が悪く（部分的に否定されているが）、実装を大幅に複雑にするとみなされてきた。そのような実装に関連して生じるであろう潜在的なオーバーヘッドを回避するために、普通のプログラムでは、関数を上へのfunargを作らないように実装することが多い（関数型言語で書かれたプログラムではそうでもないが）。さらに、この解決手法はガベージコレクションをサポートしない言語では採用できない。

効率を意識したコンパイラの中には、ハイブリッド手法を取るものがある。静的なプログラム解析によって、関数が上へのfunargを作らないと保証できる場合には、その関数のアクティベーションレコードをスタックに割り付け、そうでなければヒープに割り付ける。

他の解決法として、クロージャを生成するタイミングで変数の値をクロージャにコピーする手法がある。複数のクロージャ間で変数が共有されないため、変数が可変であるときの振る舞いが変わる。しかし、変数が不変であることがあらかじめ分かっていれば、この手法は振る舞いを変えない。ML言語は変数がすべて不変なのでこの手法をとる。Javaは匿名クラスに関してはこの手法をとる。匿名クラスではfinalな変数しか参照できないようになっており、変数の不変性が担保されている。

２つの振る舞いのどちらをとるかを、プログラマが明示的に指定する言語がある。PHP 5.3の無名関数ではクロージャで外側の変数を使うためにuse()節で変数を指定する必要がある。そこで変数を参照として指定すると、もともとの変数への変数を参照し、参照として指定しないと値を渡す。AppleのBlocks無名関数は捕捉したローカル変数はデフォルトで値として捕捉される。クロージャ間やスコープの外で状態を共有したければ、その変数を__block修飾子をつけて宣言する必要がある。この場合、その変数はヒープに割り付けられる。

例

以下のHaskell風の擬似コードでは関数の合成を定義する:

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

λ は新しい関数を作り出すための演算子で、この例では引数xをとりgにxを適用し、その結果をfに適用して得られる値を返す関数を作る。この λ 関数は内部状態として関数fとg（あるいはそれらへのポインタ）をもつ。

上へのfunarg問題はcompose関数の引数f,gがスタックフレームに割り付けられた場合に生じる。composeの呼び出しから実行が戻った際にfとgを保持するスタックフレームが開放されるため、ラムダ関数があとから呼び出されたときにgが過去に存在した無効なメモ領域を参照しようとしてしまう。

下へのfunarg問題

下へのfunargは、上へのfunargと同様に現在実行しているわけではない関数のローカルな状態にアクセスしうる。しかし、そのような状態を保持するスタックフレームは、普通、スタックから開放されていないため、上へのfunarg問題で生じたような問題は起きない。しかしながら、下へのfunargによって、実行時にクロージャやスタックフレームの木構造が生じ、プログラムの状態を理解するのが、人にとっても木飽きにとっても難しくなる。

たとえば、下へのfunargがあることで、末尾呼び出しや継続渡し形式で書かれたプログラムの効率的なコンパイルが複雑になる。このような書き方のプログラムは、有限サイズのスタック領域で実行されることが期待The downwards funarg problem complicates the efficient compilation of tail calls and code written in continuation-passing style. In these special cases, the intent of the programmer is (usually) that the function run in limited stack space, so the "faster" behavior may actually be undesirable. [[Category:プログラミング言語の実装]] [[Category:コンパイラ構築]]