評価戦略
 |
評価戦略︵ひょうかせんりゃく、英: evaluation strategy︶とは、プログラミング言語や、ラムダ計算のような式から成る計算模型において、如何なる手順で、評価すなわち式から値を得るか、という︵通常決定的な︶規則群である。
概要
プログラミング言語では、その意味のうち、サブルーチン呼び出しや演算子式の評価において引数をいつどういう順序で評価し、仮引数は実引数にどう置換されるのか、サブルーチン呼び出しや演算子式の値への置換はどうなのかといったことが、言語仕様によって、あるいは実装によって定義される︵あるいは未定義とされる︶。 ラムダ計算︵など︶における評価すなわち簡約︵reduction︶においては﹁(1)入れ子状になった式の最も外側から簡約するか、最も内側から簡約するか (2)関数適用の (X Y) という形の式において、XとYのどちらの簡約を先にするか﹂という選択肢がある。これは後述する、プログラミング言語における正格評価と非正格評価にほぼ対応し、同じ言葉が使われることもあるが、︵プログラミング言語の意味論の議論といった場合を別にして︶モデルについての議論と実装についての議論であり、混同するのが望ましくない場合もある。 評価戦略は、関数の引数をどう扱うかによって、正格 (strict) な評価戦略と非正格 (non-strict) な評価戦略に大きく分類される。 プログラミング言語によっては、複数の評価戦略を場合により選べるものもある。例えばC++は値呼びが基本だが、参照呼びを指定することもできる。 正格評価の手続き型言語ないし命令型言語における、if文のような制御の分岐をおこなう構造は、そういった言語の中で一種の非正格評価を実現するものとみなせる。また短絡評価される演算子も同様にみなせる。正格な評価
正格な評価とは、関数の引数が常にその関数に引き渡される前に完全に評価されることを意味する。 チャーチ符号化においては、演算子の先行評価は関数の正格な評価に写像される。そのため、正格な評価は﹁先行評価﹂とも呼ばれる。多くのプログラミング言語は、関数については正格な評価をする。作用的順序
作用的順序の評価[1]︵applicative-order evaluation︶は、もっぱらプログラミング言語よりは計算模型で使われる用語で、まず引数を全て評価し、それに関数をapply︵作用、ないし適用︶する、という方法である。正規順序の評価︵normal-order evaluation︶の逆として、対になっている。プログラミング言語における値呼びに同じとされることも多いが、英語版Wikipediaでは、関数の引数を左から右に後順に走査して簡約可能な式を簡約していく評価戦略で﹁値呼びとは異なり、関数を作用させる以前に可能な限り関数本体内の項数を減らそうとする﹂ものとしている。値呼び
値呼び︵call by value、値渡し: pass by value︶は、多くの言語で採用されている典型的な評価戦略である。値呼びでは、関数呼び出しにある実引数を評価し、関数の仮引数を新しい変数としてその値に束縛し、しかる後に関数本体を実行する。関数の中で仮引数である変数に値を代入しても、それは局所的なコピーへの代入であり、呼び出した側の変数には影響しない。 手続き型言語ないし命令型言語では、演算子の左辺と右辺や、複数個並んだ引数の評価順が左から右であるか右から左であるかは、結果に違いを齎すことがあるが、仕様で決めている言語もあれば、決めていない言語もある。参照呼び
参照呼び︵call by reference、参照渡し: pass by reference︶では、仮引数が実引数そのもの、すなわちエイリアス︵en:Aliasing (computing)︶になる。実引数は、左辺値を持たねばならない︵Pascalのように、実引数を変数に限定した言語もある︶か、左辺値を持たない式の場合は呼び出し側で一時的オブジェクトを構築する言語もある。Call by copy-restore
Call by copy-restore︵複製呼びの結果返し、などと意訳される︶は、参照呼びの特殊な実装とも見ることができる。実引数の値が値呼びと同様にコピーされるが、関数呼び出しから戻る時に仮引数の変数の値が、あたかも参照呼びされたかのように書き戻される。 参照呼びと異なるのは、ある call by copy-restore の関数呼び出しの複数の引数に同じ変数を渡した場合、参照呼びでは、引数の1つを更新すると他の引数の内容も更新されるが、こちらでは、それぞれが異なるコピーであるため、他の引数の内容が更新されない。呼び出し側に戻ったときにどうなるかはそれぞれの仕様ないし実装による。 他にも、再帰呼び出しを行ったり、マルチスレッド環境で他のスレッドから観察されたりした場合には結果が異なってくる場合がある。 遠隔手続き呼出し (RPC) などで、このようなふるまいが見られることがある。部分評価
詳細は「部分評価」を参照
部分評価は評価戦略というよりは最適化手法である。部分評価では、適用されていない関数の本体内で評価が継続される。束縛されていない変数を含まない部分式は評価され、引数が既知の関数適用は簡約される。副作用があると、部分評価は予期しない結果を引き起こす可能性がある。このため、部分評価は関数内の副作用を持たない純粋な式についてのみ実施されることが多い。
正格でない評価
正格でない評価では、関数の引数は関数本体の評価で実際に使われるまで評価されない。 チャーチ符号化においては、演算子の遅延評価は関数の正格でない評価に写像される。そのため、正格でない評価は﹁遅延評価﹂とも呼ばれる。ブーリアン型の式は多くの言語で遅延評価されるが、この場合は短絡評価と呼ぶことが多い。条件式でも違う理由で遅延評価が使われることが多い。正規順序
正規順序の評価[1]︵normal-order evaluation︶も、もっぱらプログラミング言語よりは計算模型で使われる用語で、最も外側の簡約可能な式を簡約する評価戦略であり、関数の引数を評価する前に関数を適用する。プログラミング言語における名前呼びに同じとされることも多いが、英語版Wikipediaでは、名前呼びでは適用されない関数の本体内までは評価しない点が異なるとしている。名前呼び
名前呼び︵call by name、名前渡し: pass by name︶では、関数の引数は全く評価されず、捕獲回避置換︵Capture-Avoiding Substitution︶を使って関数本体内に直接置換される。引数がその関数の評価で使われていない場合、その引数は全く評価されない。引数が複数回使われている場合、その度に再評価される。 値呼びはその引数が全く使われていなくとも必ず評価するため、名前呼びの方が好ましいとする考え方もある。しかし、引数が使われている場合は名前呼びの方が性能が悪いという批判もある。 名前呼びはそのまま実装されることは滅多に無い。実際の言語では、名前呼びの意味論は次の必要呼び評価の実装となっていることが多い。ALGOL 60 ではデフォルトの評価戦略が名前呼びである。 副作用のある言語における名前呼びには微妙なところがあり、en:Jensen's Device のような例が知られている。必要呼び
必要呼び︵call by need、必要渡し pass by need︶とは名前呼びをメモ化したようなもので、関数の引数が評価されると、その値がそれ以降の利用のために代替として格納される。副作用がない場合、これは名前呼びと同じ結果となる。引数が何度も使われている場合、︵更新に要するコストの合計が毎回計算するコストの合計より小さければ︶必要呼びの方が性能がよい。 遅延評価を引数の評価戦略として見た場合は必要呼びである、と言える。 必要呼びの言語としてはHaskellが有名である。マクロ展開呼び
マクロ展開呼び︵call by macro expansion︶は名前呼びと似ているが、捕獲回避置換ではなくテキスト置換を使う︵ため、捕獲が起き得る︶。マクロ展開呼びであることを意識せずに使っていると、予期しない結果になることがある。Hygienicマクロは、捕獲を回避するマクロである。非決定性の戦略
部分適用
部分適用はどちらかというとカリー化や第一級関数と関連する。複数の引数を取る関数において、一部の引数だけ適用された関数を得ることである。これに対して、すべての引数を適用することを完全適用と呼ぶ。 例として、Haskellのような関数型言語で、与えられた数値を2倍する関数を部分適用で作るとmultiply x y = x * y
twice x = multiply x 2
となる。部分適用されているのはtwiceを定義している'multiply x 2'の部分である。multiply関数は本来なら
multiply 2 3
のようにして使用するものであるが、これに2だけ適用して新たな関数twiceを得るのが部分適用である。
部分適用の重要性はモジュール性を高めることである。奇数・偶数の判定といった単純なものから、高階関数を駆使した複雑なものまで作り出すことができる。とくに遅延評価の言語で利用するとその効果は大きい。一方で、関数に副作用があると、思いもよらない結果をもたらすかもしれない。
完全β-簡約
完全β-簡約︵full β-reduction︶においては、任意の時点で任意の関数適用が簡約される︵関数の引数を捕獲回避置換を使った関数に置換する︶。これは、適用されない関数の本体内でも行われる。未来呼び
未来呼び︵call by future︶あるいは並列名前呼び︵parallel call by name︶は必要呼びに似ているが、関数の引数は︵必要に応じてではなく︶関数本体と並行して︵別スレッドで︶評価される。関数本体で引数を使用するときにスレッドの同期が行われる。引数が全く使われない場合、引数の評価をしているスレッドは中断され捨てられる。楽観的評価
楽観的評価︵Optimistic Evaluation︶は必要呼びの変形の1つであり、関数の引数はある回数だけ部分評価される︵回数は実行時に調整される︶。そして、評価は中断され、必要呼びで関数が適用される。この方法では必要呼びの性能低下を防ぎつつ、停止属性を保持する。注
- ^ a b 訳は、計算機プログラムの構造と解釈より
関連項目
参考文献
- 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
