なぜ右辺を評価しないことが遅延なのか

Question

javascriptの論理演算子&&は、左辺が偽であれば右辺を評価せず、||は、左辺が真であれば右辺を評価しません。
これを遅延評価と呼ぶそうですが、遅延という単語で思い浮かぶのは、「遅れる」こと「長引かせる」ことです。
全くつながりが見出せませんが、何が遅延しているから右辺を評価しないのでしょうか。

Answer 1

プログラミングの世界には評価戦略という概念があります。&&や||で言われている「遅延」と言う言葉は評価戦略での遅延評価のことを言っています。ただし、&&や||は遅延評価の中でも特殊なパターンと位置づけて、短絡評価と言う場合の方が多いです。

遅延評価の反対は正格評価です。評価戦略はこの二つの何れかにわかれます。そう、正格評価に対して、何かが遅れる(遅延する)から遅延評価と呼ばれるのです。ですので、まずは正格評価とは何かと言うことを理解する必要があります。

与えられた引数を単純に足すplus関数があるとして、次のような式を考えます。

var plus = function(a, b) { return a + b; };
plus(1 + 2, 3 * 4);

ほとんどのプログラミング言語では、0個以上の式を引数として、関数を呼び出し、一つの式になります。さて、この式について、関数を評価する前に、引数として割り当てられている各式を評価する必要はありますでしょうか？上の例では、plusを評価する前に1 + 2や3 * 4を評価し、その結果を求める必要があるかどうかと言うことです。普通はあると答えることでしょう。何を当たり前な事を…と思ったかも知れませんが、一見、この当たり前な評価の仕方を正格評価といいます。つまり、正格評価とは、ある関数の式について、その引数にあたる式全てを評価した後に関数自体を評価することです。

実は、上のことは全てのプログラミング言語においてそうであるとは言えません。例えば、Haskellの場合、

plus a b = a + b
plus (1 + 2) (3 * 4)

上の式では、始めにplus自体が評価されて、+の演算であると解釈されます。1 + 2や3 * 4が評価されるのはその後です。何言っているの？と思っているかも知れません。例えば下記のような式では、

plus' _ _ = 1
plus' (1 + 2) (3 * 4)

これも同じくplus'が始めに評価されます。そして、そこで値は1と確定してしまいます。つまり、この式では1 + 2や3 * 4が評価されることはありません。このように、引数が遅れて評価される(場合によっては評価すらされない)ため、遅延評価と言われます。つまり、遅延評価とは、正格評価の反対で、その引数にあたる式の一部、または、全てを評価せずに関数自体を評価することです。

なんとなくわかってきました？さて、関数の話でしたが、演算子も一種の関数と引数の組み合わせと捉えることができます。

(+)(1 + 2, 3 * 4);

JavaScriptでは上のように書けませんが、Lispなどでは(+ (+ 1 2) (* 3 4))と書いたりします。そう、同じ事です。演算子であっても、左辺と右辺は二つの引数と考えられます。正格評価であれば、それらは演算子の評価の前に、それぞれの式は評価されます。実際に足し算が行われるのはその後です。

ですが、&&と||だけはその正格評価の規則に従いません。

(||)(1 + 2, 3 * 4);

引き続き架空の書き方ですが、本来の関数と考えれば、両方の式が評価された後に、||の処理があると考えるべきです。ですが、JavaScriptの&&と||は例外的に遅延評価の一種である短絡評価を採用しています。1番目の式(つまり左辺)を評価した後に、&&や||での処理を行い、その後に2番目の式(つまり右辺)が評価されます。しかも、1番目の式の結果次第では、&&や||での処理によって、2番目の式(つまり右辺)は評価されない場合があります。どうしても右辺の式は&&や||自体の処理(評価)よりも評価することが遅れるため、他にあるような正格評価と比べて評価するタイミングが遅延しているとなるのです。

JavaScirptで他に遅延評価になるのは三項条件演算子(?:)だけです。まとめると、**演算子自体の評価よりも、中にある式の評価が遅れる(場合によっては評価されない)**というころが遅延評価と言われるゆえんとなります。

※ 遅延評価に興味があれば、Haskellなど遅延評価のある言語を学ぶと良いでしょう。
※ &&や||、または、同様の意味を持つandやorが短絡評価であるかどうかは言語によります。これらが短絡評価ではない言語も存在します。

Comments

[think49]

勉強になります。相乗りで申し訳ありませんが、少し質問させてください。
短絡評価を遅延評価の一部として説明されていますが、Wikipediaでは遅延評価を「評価しなければならない値が存在するとき、実際の計算を値が必要になるまで行わないこと」と説明しています。
例えば、短絡評価である `A || B` は `A` を評価するまで `B` の評価を保留する性質は持っていますが、`A || B` の評価値はその場で算出しています。
つまり、`B` は遅延評価ですが、全体としてみれば `A || B` は先行評価(正格評価)と考えられるのですが、どのように考えるべきでしょうか。
https://ja.wikipedia.org/wiki/%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1

[raccy]

問題にすべきなのは`A || B`という全体ではなく、その中の`||`がどのような評価戦略を持っているかと言うことです。`||`がもつ二つの引数(左辺と右辺)の評価が、`||`自体の評価より先行するのか、遅延するのかです。正格評価の演算子は、その演算子が何であるかに関わらず、両辺を評価してしまいます。しかし`||`は、演算子が`||`なのかを確認してから(もしかしたら`&&`だったかも知れない！)しか、`B`を評価しません。

うーん、こんな感じの説明でどうでしょうか？

そうそう、遅延評価と言っても、実装上は、必要になったときにしか呼び出されない＝必ず遅延する、ということを常に保証しているわけではありません。その前に評価し終わったキャッシュを使ったり、最適化により先に評価したりする場合もありえます。遅延評価では、プログラマが制御できない評価順序の入れ替えや省略が容易に発生するため、プログラミング言語全体で採用するには、Haskellのように副作用がない言語でないと無理という事情があります。逆に、副作用がある普通の言語での`||`や`&&`の短絡評価のように、評価順序や条件を満たす場合は評価しないことを保証している場合もあります。

[think49]

つまり、こういう事でしょうか。

- オペランドの全てが事前に評価されれば該当演算子は正格評価(先行評価)に分類される(評価値は即座に評価される)
- オペランドの一部が遅延評価されれば該当演算子は非正格評価(遅延評価)に分類される(評価値は遅延評価でなくとも良い)

遅延評価に分類される演算子でも「評価値が遅延評価される演算子」と「評価値が遅延評価されない演算子」の2種類存在するのが問題を複雑化しているように思いました。
(aaaaaaaa さんが質問された発端もそこにあるのかもしれません…。)

> その前に評価し終わったキャッシュを使ったり、最適化により先に評価したりする場合もありえます。
ECMAScript 仕様としては遅延評価でも「実装の最適化」によって先行評価している実装がある、という意味でしょうか。

[raccy]

評価戦略では「式を評価した評価値がいつ使われるのか」ではなく「式がいつ評価がされるのか」を問題にしています。式の評価自体に副作用が含まれている場合に「式がいつ評価されるのか」が重要であり、評価した結果は捨てられようが、ずっと後から使われようが、それによって副作用はないため、どうだっていいという考えです。

> ECMAScript 仕様としては遅延評価
えと、ECMAScriptではなくてプログラミング言語全体での話です。ECMAScriptは関数も通常の演算子も正格評価を採用しており、`&&`と`||`と`?:`の演算子だけが例外です。また、評価順序や評価するかしないかは言語仕様によって定められているため、最適化によりそれが変更されることはありません。ただ、Haskellなどの他の言語での遅延評価が必ずしもそうではないというだけの話です。

[think49]

こういう事でしょうか。

- 遅延評価は「式(オペランド)単位」で決定するもの
- 演算子や関数等の評価タイミングが遅延評価しているように見えるものは「全ての式が遅延評価した結果、そう見えているだけ」

先の分類に基づくなら、

- オペランドの全てが事前に評価されれば該当演算子は正格評価(先行評価)に分類される(評価値は即座に評価される)
- オペランドの「一部」または「全て」が遅延評価されれば該当演算子は非正格評価(遅延評価)に分類される(全てのオペランドが遅延評価されれば演算子の評価タイミングも遅延する)

> ただ、Haskellなどの他の言語での遅延評価が必ずしもそうではないというだけの話です。
わかりました。

[raccy]

そうそう「式」単位です。あと気をつけて欲しいのでは、一つの評価中に別の評価が入るということです。`A || B`でAがfalseだったとき、`||`の評価が開始されてから、`B`が評価されますが、それは`||`の評価の全てが完了する前です(ただ、`||`の評価が途中まで進んで、その意味がすでに変わっています)。最終的に`||`の評価の全てが終わる、つまり`A || B`全体の評価が確定されるのは、`B`の評価が終わった後になります。

[think49]

ようやく、理解できた気がします。
個人的に引っかかっていたのが Haskell の下記コードでした。

plus a b = a + b
plus (1 + 2) (3 * 4)

私は初め、仮引数の評価処理は関数 plus の内部コードが実行される時まで評価を保留して待機状態になると考えていました。
しかし、仮引数の処理は演算前の値を渡している時点で終了しており、「仮引数の評価値は (1 + 2) (3 * 4) である」と考えると合点がいきます。
a b = a + b では仮引数の値を展開していますが、これは関数処理の一部であって仮引数で保留されていた評価が再開されているわけではない、と理解しました。
この考えに基づくと式単位での遅延評価は存在しても、その上位の全ての機構では常に演算前の評価値が「即座に算出される」ことになります。
この考えは正しいでしょうか。

[raccy]

そうです、その通りで「式」のままplus関数に渡されています。これをthunk(サンク)といい、その説明だけで(というか、ちゃんと説明できる自信は無いのですが)長くなるの割愛しますが、概ねその考えで間違ってはいないと思います。

もし、興味があれば、SICPやHaskellの入門書を読むとさらによくわかると思います(私のつたない説明より正確に！)。ぜひ、チャレンジしてみてください。

[think49]

ありがとうございます。thunk(サンク)というのですね。
JavaScript的に実装するなら new Function でしょうか。
- 浮動小数点演算を整数演算後に10の乗数を除算する演算に変更して誤差を0にする
- 再帰処理を遅延評価して再帰処理ではなくする
遅延評価系ではこの辺りが実装出来たら面白そうだと思いました。
調べてみたところ、「竹内関数(たらい回し関数)」というものがあるようですね。
http://qiita.com/alucky0707/items/b3f9ab63c63e9e6399e6

Answer 2

比較のために、JavaScriptで関数を呼び出してみましょう。

function and_and(cond1, cond2){
  return cond1 && cond2;
}

var x = func(1) && func(2);
var y = and_and(func(1), func(2));

ここで、yを計算するときの関数呼び出しでは、たとえ関数の中で使おうが使うまいが、引数はすべて評価してから関数を呼び出すことになります。

その一方で、xを計算する際には、

1. func(1)を評価する。
2. 1.の値が真なら、func(2)評価する

という流れになっています。つまり、必要かどうかがわかるまで、func(2)の評価は遅延されています。

Comments

[aaaaaaaa]

ご回答有難うございました。
関数というものを利用することで必要か不必要化どうかに限らずいったん、両辺が評価されてから返り値を返すのに対して、yは、&&の仕様で偽であれば右辺が評価されません。
左辺が真か偽かの判別がつくまでのことを「遅延」と呼んでいたのですね。

Answer 3

一般に「遅延評価」というのは、「必要になるまで評価するのを遅らせる（これが遅延）。最後まで必要が無ければ評価しない」という意味です。

一般の二項演算子は、左辺と右辺を評価してから演算を行います。
これと比べて、右辺を必要になるまで評価しないと言うことから、遅延評価と呼んだ人がいるのだと思います。

Answer 4

参考情報

• 遅延評価 http://dic.nicovideo.jp/a/%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1

...
通常、関数の引数は関数に渡されるときに計算されるが、遅延評価では関数に渡した後、実際に計算が必要になるまで評価されない。

無限リストがこの利点を説明するためによく引き合いに出される。無限リストを評価するということは、無限リストの「全ての」要素を計算するということであるが、これは当然無限個の処理が終わるはずはないのでエラーになる。しかし、遅延評価では、無限リストは定義されたり、関数に渡されたりした時にはエラーにならず、関数内で請求された要素の値を返して特に問題なく動作する。
...

• ECMAScript 6 でジェネレータを作ったり、遅延評価してみる https://blog.ymyzk.com/2015/04/ecmascript-6-generator-lazy/

Answer 5

||の本来の意味、論理ORに従うと
左辺右辺共に評価し、片方、もしくは両方が真である場合に真を返すべきです。
しかし、左辺が真になった時点で結果は間違いなく真になるので
右辺は計算する必要がありません。

その際に右辺を評価しないことが遅延でなく
左辺を評価し、右辺の評価が必要になるまで評価を留めるため、遅延ということになります。
偽になった際に右辺を評価しないというのはどちらかというと副作用のようなものです。
&&に関しても同様です。

Comments

[matobaa]

横からですが、教えてください。「どちらかというと副作用」という表現がひっかかったのですが、その根拠ってありますか?
マルチコアやメニーコアを使うような場合など、遅延させずに投機的に評価しちゃったほうが有利な場面があるものの、javascriptにおいては *あえて* 左から順に遅延評価するように (つまり、副作用ではなく、意識的に) 仕様を定めているんじゃないかと思ってます。
もしかしたら将来、「遅延評価せずに投機的に実行される論理OR」のようなオペレータが登場するかもしれない。

[damalnylpo]

どちらかというと副作用と表現したのは
元々プログラミング言語の論理演算には遅延実行してくれないものが多くあったからです。
今でもVBあたりは
単純な論理演算はAND,ORで、遅延実行するものはANDALSO,ORELSEとして別物として扱われているのではないでしょうか。

実際のところ結果が確定した状態で右辺まで実行するのはあまり使いどころもないので
前方互換性を持たせるためであって
最近のものは遅延実行つきに統合されてますが
それらが論理演算の本質であると考える根拠にはなると思います。
それに名前も「遅延実行」はあくまで文脈としては"実行"に掛かっていますが
「論理演算子」はそのまま"演算子"にかかってるのも理由の一つです。
遅延実行そのものは論理演算以外でも使われますからね。

なので「遅延評価せずに投機的に実行される論理OR」というのは将来というより
最適化が進んでいなかったころの過去の遺物と考える方が自然だと思います。

ただ副作用といっても別に遅延実行が思いもよらない仕様の裏という意味ではなく、
あくまで本来の目的は論理演算にあるという意味であって、
仕様の意図していないものであるという意味ではありません。

関係ありませんがあなたは私のアイコンと本名ともに似ているので表現しがたい気持ちになりました。

[matobaa]

なるほど、ちょっと難しかったですが、なんとなく理解しました。「仕様の意図していないものであるという意味ではない」ということなので認識ズレはなさそうです。ありがとうございました。

関係ありませんがアイコン似てますね! 今後ともよろしくお願いいたします ^^

Answer 6

たとえば

<script>
if(typeof myvar=="undefined" || myvar == 0){
  console.log("error");
}else{
  console.log("ok");
}
</script>

変数myvarが未設定（もしくは設定したけど削除された）かどうかわからない時
if(myvar==0)的な処理を行うとundefinedなものを評価することになるので
そこでプログラムが止まってしまいます。
myvarを評価する前に、typeofでmyvarがundefinedを評価し、未設定であれば
myvarを評価しない必要があります。