****
 式
****

================
 演算子順位文法
================

プログラムの構造は、文法に基づいて構文解析をすれば分かる。文法はBNFで書くのが普通(:numref:`bnf`)だが、式に関する部分はBNFだと煩雑になるので、演算子順位文法(:index:`operator precedence grammar`)を使うことが多い。

演算子順位文法では、それぞれの演算子に対して優先度と結合性を決める。

* 優先度は、演算子の間の順序関係である。式の中に優先度の高い演算子と低い演算子が含まれている時は、優先度の高い演算子が先に結合する（構文木で言うと、部分木を作る）。
* 結合性は、左結合と右結合がある。同じ優先度の演算子が並んでいる時は、左結合であれば左の演算子から先に結合し、右結合であれば右の演算子から先に結合する。

.. note::

   下の説明では、いちいち構文木を書くのが面倒なので、先に結合する部分をカッコで囲んで表す。カッコも終端記号であるから、カッコを付け加えると構文木としては異なるものになってしまうが、どこが先に結合するかということを伝えるだけならば問題ない。

   構文木から、プログラムの実行に影響を与えない部分を取り除いたものを抽象構文木(abstract syntax tree)と呼ぶ。下の説明では、抽象構文木が同じになるようにカッコを付けている。

   * `抽象構文木 - Hatada's Home Page <http://shopping2.gmobb.jp/htdmnr/www08/c-tips/ast/ast01.html>`_

.. admonition:: 優先度

   多くの言語では、数学と同じ優先度を使うので、 ``a + b * c`` は ``a + ( b * c )`` と同じになる。

.. admonition:: 結合性

   多くの言語では、四則演算は左から結合するので、 ``a - b + c - d`` は ``(( a - b ) + c ) - d`` と同じになる。

.. admonition:: APLの場合

   APL では、全ての演算子は同じ優先度で右から結合するので、 ``A × B ＋ C`` は ``A × ( B ＋ C )`` と同じになる。

.. admonition:: 課題12
   :class: exercise

   演算子の優先度と結合方向が次の表のようであるときに、下の式の構造を括弧を使って表わせ。

   ======  ========  ========
   優先度  結合方向
   ======  ========  ========
   高      左        ``#``, ``$``
   低      右        ``!``, ``?``
   ======  ========  ========

   1. ``a # b $ c``
   2. ``a ! b ? c``
   3. ``a # b ! c $ d``
   4. ``a # b ! c ? d``
   5. ``a # b $ c ! d ? e``

   :ref:`【解答例】 <ex12-answer>`

============
 評価の順序
============

式の値を実際に計算することを評価(:index:`evaluation`)と言う。

演算子の優先順位や結合性は構文の話で、式の評価は意味の話なので、別の話である(:numref:`definition_of_language`)ことに注意。

式がいくつかの部分式から成り立っている場合、（原理的には）どんな順序で評価してもかまわない。しかし、式が副作用を持っている場合は、評価順序によって結果が変わる可能性がある。

.. admonition:: 関数呼び出しの副作用

   次の C のプログラムでは、(ア)の式の ``a`` を先に評価するか ``fun1()`` を先に評価するかで結果が違う。

   .. code-block:: c

      int a = 1;

      int fun1() {
	a = 2;
	return 3;
      }

      void fun2() {
	a = a + fun1();  /* (ア) */
      }

      void main() {
	fun2();
      }

この問題に対する対応策としては、次のようなものがある。

1. 何もしない。--- 副作用を含む式の結果は処理系依存になる。
2. 副作用を禁止する。--- 命令型言語では非常に不便。
3. 評価順序を定めておく。--- 最適化の妨げになる。

* Cは（少なくとも昔の言語仕様では）1番。
* C++では、副作用完了点(:index:`sequence point`)が定義されていて、この点の間ではどんな順序で評価されるかわからないが、この点を越えて順序が変わることはないので、1番と3番の折衷。
* Javaは3番で、必ず左から右へと評価（ただし代入の場合は右辺の評価が完了してから代入）される。
* MLやHaskellなどの純粋関数型言語ではそもそも副作用がないので、2番。

==========
 短絡評価
==========

被演算子を全て評価しなくても、演算の結果が分かってしまうとき、残りの被演算子を評価せずに済ませることを短絡評価(:index:`short-ciruit evaluation <pair: short-circuit; evaluation>`)と言う。

.. admonition:: 論理演算子の短絡評価

   変数 ``a`` の値が負の時、次の式は ``b < 10`` を評価しなくても ``false`` であることが分かる。

   .. code-block:: c

      ( a >= 0 ) && ( b < 10 )

.. admonition:: 課題13
   :class: exercise

   Javaでは論理積・論理和の演算子は二種類あり、 ``&&``, ``||`` は短絡評価を行い、 ``&``, ``|`` は行わない。なぜ両方の演算子が必要なのか説明せよ。

   :ref:`【解答例】 <ex13-answer>`

==========
 遅延評価
==========

短絡評価を一般化して、任意の式において結果に影響を与えない部分は計算しないという方式もある。どの部分が必要かはやってみないとわからないので、必要であることが判った時点で計算を始める。本当に必要になるまで計算を始めないので遅延評価(:index:`lazy evaluation <pair: lazy; evaluation>`)と呼ばれる。

.. admonition:: Python3.xの ``range``

   .. code-block:: python

      for i in range(10000):
	 if i > 10: break
	 print(i*2)

   Python2.x の ``range`` は先に全部の要素を作ったが、Python3.x の ``range`` は必要な要素だけ作る。

.. admonition:: Ruby の Enumerable#lazy

   .. code-block:: ruby
   
      x = (1..Float::INFINITY).lazy.map{|x| x*2}
      puts x.first(10)

   ``map`` を実行する時点では、どこまで必要かわからない点に注意。

.. admonition:: Haskell

   Haskellでは、すべての式の評価が遅延評価である。

.. note::

   短絡評価や遅延評価は、評価戦略と関係しているが、それについてはまた後で説明する。