評価戦略
評価戦略︵英: Evaluation strategy︶とは、プログラミング言語における式の評価を決定する︵通常決定的な︶規則群を意味する。特に関数や演算子の評価に重点を置き、関数の引数をいつ、どういう順序で評価するか、関数呼び出しや演算子がどの時点で関数に置換されるのか、その置換はどういう形態をとるかを定義する。関数の研究に使われる形式体系であるラムダ計算は、しばしば評価戦略のモデルとして使われる。評価戦略は、関数の引数をどう扱うかによって、正格(strict)な評価戦略と正格でない(non-strict)評価戦略に大きく分類される。プログラミング言語はいくつかの評価戦略を組み合わせていることもある。例えばC++は、値渡しと参照渡しを組み合わせている。主に正格な評価戦略を用いる言語でも、ブーリアン型の式やif文には正格でない評価戦略を用いることが多い。
正格な評価
正格な評価とは、関数の引数が常にその関数に引き渡される前に完全に評価されることを意味する。 チャーチ符号化においては、演算子の先行評価は関数の正格な評価に写像される。そのため、正格な評価は﹁先行評価﹂とも呼ばれる。多くのプログラミング言語は、関数については正格な評価をする。適用順序
適用順序︵Applicative Order︶評価とは、関数の引数を左から右に後順に走査して簡約可能な式を簡約していく評価戦略である。値渡しとは異なり、適用順序評価は関数を実際に適用する以前に可能な限り関数本体内の項数を減らそうとする。値渡し
値渡し︵Call-by-Value︶評価は、C言語からSchemeまで多くの言語で採用されている典型的な評価戦略である。値渡しでは、引数の式を評価し、結果として得られた値で関数内の対応する変数を束縛する︵通常、捕獲回避置換か新たなメモリ領域への値のコピーをする︶。その関数が引数となっている変数に値を代入しても、それは局所的なコピーへの代入であり、呼び出した側から見れば、その関数に渡したものは何も変化していない。 値渡しは一種類ではなく、関数に渡す前に引数を評価する戦略全般を指す。多くの言語︵Eiffel や Java︶は値渡しの際に引数と左から右の順序で評価するが、中には右から左の順序で評価する場合もあり、言語によっては︵Scheme、OCaml、C︶順序を明示していない。参照渡し
参照渡し︵Call-by-Reference︶評価とは、関数に対して引数の値そのものではなく、引数の参照を暗黙のうちに渡すことをいう。その関数が引数を変更すると、呼び出し側からもその変化が観測できる。引数の式が左辺値であれば、そのアドレスが使われる。そうでない場合、呼び出し側で一時的オブジェクトを構築し、そのオブジェクトへの参照が渡される。そのオブジェクトは関数から復帰した際に捨てられる。 言語によっては、参照を第一級オブジェクトとしている。例えば、MLには "ref" コンストラクタがある。C++でも参照は明示的に生成できる。これらの言語では、関数の引数として値への参照を渡すことを参照渡しと呼ぶこともある。 C言語のようにポインタを持つ言語では、参照渡しではなく﹁アドレス渡し︵Call-by-Address︶﹂と呼ぶこともある。コピー/復帰渡し
コピー/復帰渡し︵Call-by-Copy-Result︶とは、参照渡しの特殊ケースであり、呼び出し側から見て引数で渡した参照は一意となる。ソース上関数呼び出しに指定された引数が他のスレッドからもアクセス可能な参照であった場合、その内容を他からアクセスできない新たな参照にコピーする。関数から復帰したとき、その新たな参照について更新された内容を元の参照に書き戻してやる。 これが参照渡しと異なる意味を持つのは、ある関数呼び出しの複数の引数に同じ参照を渡した場合である。参照渡しでは、引数の1つを更新すると他の引数の内容も更新されるが、コピー/復帰渡しでは、それぞれが異なるコピーであるため、他の引数の内容が更新されない。ただし、呼び出し側に戻ったときにどうなるかは未定義である︵複数のコピーをどう書き戻すかという実装に依存する︶。 初期化されていない参照を渡す場合、この評価戦略を﹁結果渡し︵Call-by-Result︶﹂と呼ぶこともある。部分評価
詳細は「部分評価」を参照
部分評価では、適用されていない関数の本体内で評価が継続される。束縛されていない変数を含まない部分式は評価され、引数が既知の関数適用は簡約される。副作用があると、部分評価は予期しない結果を引き起こす可能性がある。このため、部分評価は関数内の副作用を持たない純粋な式についてのみ実施されることが多い。
正格でない評価
正格でない評価では、関数の引数は関数本体の評価で実際に使われるまで評価されない。 チャーチ符号化においては、演算子の遅延評価は関数の正格でない評価に写像される。そのため、正格でない評価は﹁遅延評価﹂とも呼ばれる。ブーリアン型の式は多くの言語で遅延評価されるが、この場合は短絡評価と呼ぶことが多い。条件式でも違う理由で遅延評価が使われることが多い。正規順序
正規順序︵Normal Order︶評価とは、最も外側の簡約可能な式を簡約する評価戦略であり、関数の引数を評価する前に関数を適用する。名前渡しでは適用されない関数の本体内までは評価しない点が異なる。名前渡し
名前渡し︵Call-by-Name︶評価では、関数の引数は全く評価されず、捕獲回避置換︵Capture-Avoiding Substitution︶を使って関数本体内に直接置換される。引数がその関数の評価で使われていない場合、その引数は全く評価されない。引数が複数回使われている場合、その度に再評価される。 値渡しはその引数が全く使われていなくとも必ず評価するため、名前渡しの方が好ましいとする考え方もある。しかし、引数が使われている場合は名前渡しの方が性能が悪いという批判もある。 名前渡しはそのまま実装されることは滅多に無いが、プログラムやプログラミング言語の理論的特性を検討する際にはよく使われる。実際の言語では、名前渡しの意味論は次の必要渡し評価の実装となっていることが多い。ALGOL 60 ではデフォルトの評価戦略が名前渡しである。必要渡し
必要渡し︵Call-by-Need︶とは名前渡しをメモ化したもので、関数の引数が評価されると、その値がそれ以降の利用のために代替として格納される。副作用がない場合、これは名前渡しと同じ結果となる。引数が何度も使われている場合、必要渡しの方が性能がよい。 必要渡しを使っている言語では、モナドなどを使う場合以外では計算の副作用をサポートしない。これによって、遅延評価以前に変数の値が変更されることによる予期しない振る舞いを防ぐ。 これは一種の遅延評価である。 必要渡しを使っている言語としてはHaskellが有名である。マクロ展開渡し
マクロ展開渡し︵Call-by-Macro-Expansion︶は名前渡しと似ているが、捕獲回避置換ではなくテキスト置換を使う。マクロ展開渡しであることを意識せずに使っていると、予期しない結果になることがある。Hygienicマクロはそのような問題を防ぐようになっている。非決定性の戦略
完全β-簡約
完全β-簡約︵full β-reduction︶においては、任意の時点で任意の関数適用が簡約される︵関数の引数を捕獲回避置換を使った関数に置換する︶。これは、適用されない関数の本体内でも行われる。未来渡し
未来渡し︵Call-by-Future︶あるいは並列名前渡し︵Parallel Call-by-Name︶は必要渡しに似ているが、関数の引数は︵必要に応じてではなく︶関数本体と並行して︵別スレッドで︶評価される。関数本体で引数を使用するときにスレッドの同期が行われる。引数が全く使われない場合、引数の評価をしているスレッドは中断され捨てられる。楽観的評価
楽観的評価︵Optimistic Eveluation︶は必要渡しの変形の1つであり、関数の引数はある回数だけ部分評価される︵回数は実行時に調整される︶。そして、評価は中断され、必要渡しで関数が適用される。この方法では必要渡しの性能低下を防ぎつつ、停止属性を保持する。関連項目
参考文献
- Harold Abelson and Gerald Jay Sussman. Structure and Interpretation of Computer Programs, Second Edition. MIT Press, 1996. ISBN 0-262-01153-0.
- Henry G. Baker, Jr. "The Incremental Garbage Collection of Processes", with Carl Hewitt, ACM Sigplan Notices 12. August 8, 1977. Pages 55-59.
- Clem Baker-Finch, Clem, David King, Jon Hall, and Phil Trinder. "An Operational Semantics for Parallel Call-by-Need", Research report 99/1. Faculty of Mathematics & Computing, The Open University, 1999.
- Robert Ennals and Simon Peyton Jones. "Optimistic Evaluation: a fast evaluation strategy for non-strict programs", in ICFP'03. ACM Press, 2003.
- Jocelyn Frechot. "Partial Evaluation", documentation for the Compose project. Online, Sept. 25, 2003.
- Bertram Ludäscher. CSE 130 lecture notes. January 24, 2001.
- Benjamin C. Pierce. Types and Programming Languages. MIT Press, 2002. ISBN 0-262-16209-1.
- P. Sestoft. "Demonstrating Lambda Calculus Reduction", in T. Mogensen, D. Schmidt, I. H. Sudburough (editors): The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones. Lecture Notes in Computer Science 2566. Springer-Verlag, 2002. Pages 420-435. ISBN 3-540-00326-6
