関数型プログラミング言語Haskell
■ このスレッドは過去ログ倉庫に格納されています
0867デフォルトの名無しさん
NGNG関数doubleがdouble(x) = x + xと定義されていて、double(1+2)を計算する時、
double(1+1)→double(2)→2+2→4といった具合に式の内側から計算していくのがinner-most reduction。
double(1+1)→(1+1)+(1+1)→2+(1+1)→2+2→4と、式の外側から計算していくのがouter-most reduction。
一方、関数ifがif(true, x, y) = x, if(false, x, y) = yと定義されていて
if(true, 1, 1+2+...+10)を計算する時には、
inner-most reductionではif(true,1,1+2+...+10)→...→if(true,1,55)→1
outer-most reductionではif(true,1,1+2+...+10)→1となり、余分な計算を避けることができる。
inner-most reductionはcall by valueに相当する。
outer-most reductionはcall by nameに相当する。
副作用およびnon-terminationおよび計算量を除けば両者は同じ値が求まる。
graph reduction
double(1+1)の例で見たように、outer-most reductionでは
引数で渡ってきた式を複数回計算してしまうことが多い。
graph reductionでは式をグラフ構造で表現し、double(1+1)は
double(* + *)
| |
+---->1 + 1 (実際はちょっと違うけど、まあわかりやすく)
というグラフ構造で表現される。
ここで1+1はx+xの中で2回出現しているが同一ノードに参照されているから
double(1+1)→(1+1)+(1+1)→2+2→4という具合に計算されていき、
1+1は1度きり計算されるのみである。
■ このスレッドは過去ログ倉庫に格納されています