評価戦略

評価戦略とは

評価戦略とは、プログラミング言語やラムダ計算などの計算モデルにおいて、式をどのように評価して値を得るかを定める規則群です。これは、サブルーチン呼び出しや演算子式の評価において、引数をいつ、どのような順序で評価するか、仮引数を実引数にどう置き換えるか、といった点を規定します。

概要

プログラミング言語では、評価戦略は言語仕様や実装によって定義され、サブルーチン呼び出しや演算子式の評価に影響を与えます。ラムダ計算のようなモデルでは、「式のどの部分から簡約するか」、「関数適用のどの部分を先に簡約するか」といった選択肢があります。これらは、プログラミング言語における正格評価と非正格評価に対応し、同じ用語が使われることもありますが、モデルの議論と実装の議論は区別されるべきです。

評価戦略は、関数の引数をどのように扱うかによって、大きく2つに分類されます。

正格評価 (strict evaluation): 関数の引数を、関数に渡す前に必ず評価する戦略です。
非正格評価 (non-strict evaluation): 関数の引数を、関数本体で実際に使われるまで評価しない戦略です。

プログラミング言語によっては、複数の評価戦略を選択できるものもあります。例えば、C++は基本的に値呼びですが、参照呼びも選択できます。

制御構造（if文など）や短絡評価される演算子は、正格評価の言語において、一種の非正格評価を実現すると見なせます。

正格な評価

正格評価では、関数の引数は関数に渡される前に完全に評価されます。これは、「先行評価」とも呼ばれ、多くのプログラミング言語が採用しています。

作用的順序

作用的順序の評価は、まずすべての引数を評価してから、関数を適用する評価方法です。これは計算モデルでよく使われる用語で、正規順序評価と対比されます。プログラミング言語における値呼びと同じとされることが多いですが、厳密には異なります。

値呼び

値呼びは、多くの言語で採用されている一般的な評価戦略です。関数呼び出しの際、実引数を評価し、その値を関数の仮引数に束縛します。関数内で仮引数に値を代入しても、それは局所的なコピーへの代入であり、呼び出し側の変数には影響しません。

手続き型言語では、演算子の評価順序（左から右か右から左か）が結果に影響することがありますが、これは言語仕様で定められている場合とそうでない場合があります。

参照呼び

参照呼びでは、仮引数は実引数そのもの、つまりエイリアスとなります。実引数は左辺値を持つ必要があります。関数内で仮引数を変更すると、呼び出し元の実引数も変更されます。

参照の値渡し

参照の値渡しは、オブジェクトへの参照を値として渡す評価戦略です。Python、Java、Ruby、JavaScriptなどで使われています。この評価戦略では、関数内でオブジェクトが変更されると、呼び出し元にもその変更が反映されます。ただし、新しいオブジェクトを代入しても、呼び出し元の変数が参照しているオブジェクトは変更されません。この点で、値渡しとは動作が異なります。

Call by copy-restore

Call by copy-restoreは、値呼びのように実引数の値をコピーしますが、関数から戻る際に仮引数の値を実引数に書き戻します。複数の引数に同じ変数を渡した場合、参照呼びとは異なり、それぞれが異なるコピーであるため、他の引数の内容は更新されません。

部分評価

部分評価は評価戦略というよりも最適化手法です。関数内で、束縛されていない変数を含まない部分式を評価したり、既知の引数を持つ関数適用を簡約したりします。副作用があると予期しない結果になる可能性があるため、純粋な式にのみ適用されることが多いです。

正格でない評価

正格でない評価では、関数の引数は関数本体で実際に使われるまで評価されません。これは「遅延評価」とも呼ばれます。ブール式の短絡評価や条件式も、一種の遅延評価です。

正規順序

正規順序評価は、最も外側の簡約可能な式から簡約する評価戦略で、関数の引数を評価する前に関数を適用します。これは、プログラミング言語における名前呼びと関連付けられますが、関数本体内までは評価しない点で名前呼びとは異なります。

名前呼び

名前呼びでは、関数の引数は評価されず、関数本体に直接置換されます。引数が複数回使われる場合、その度に再評価されます。値呼びとは異なり、引数が全く使われない場合は評価されません。

必要呼び

必要呼びは、名前呼びをメモ化したもので、一度評価された引数の値を保存し、以降の利用で再評価を避けます。副作用がない場合、名前呼びと同じ結果になり、引数が何度も使われる場合に性能が向上します。遅延評価の引数評価戦略として、必要呼びが使われます。

マクロ展開呼び

マクロ展開呼びは名前呼びに似ていますが、テキスト置換を使うため、意図しない結果になる可能性があります。健全なマクロは、変数の捕捉を避けるべきです。

非決定性の戦略

完全β簡約や未来呼びなどの評価戦略もあります。

部分適用

部分適用は、複数の引数を取る関数の一部だけを適用して、新しい関数を得る手法です。モジュール性を高める効果があります。

完全β-簡約

完全β-簡約は、任意の時点で任意の関数適用を簡約する戦略です。適用されない関数の本体内でも簡約が行われます。

未来呼び

未来呼びは、必要呼びに似ていますが、引数は関数本体とは並行して評価されます。引数が使われない場合は評価が中断されます。

楽観的評価

楽観的評価は、必要呼びの一種で、引数をある回数だけ部分評価します。必要呼びの性能低下を防ぎつつ、停止属性を保持します。

注

評価戦略は、プログラミング言語の動作を理解する上で非常に重要な概念です。それぞれの評価戦略には、長所と短所があり、適切な戦略を選択することが重要です。

参考文献

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

もう一度検索