Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
************* Expressions ************* .. index:: pair: operator precedence; grammar ============================= Operator Precedence Grammar ============================= When given an expression, we can investigate its structure by making its parse tree. We have learned BNF(:numref:`bnf`) to write a grammar, but we prefer *operator precedence grammar* for expressions because it is much simpler. * Each operator has its precedence. The higher the precedence of a certain operator is, the smaller sub-tree it makes (in other words, it connects its arguments earlier than other operators). * Each binary operator is either left-associative or right-associative. When there are more than one operator of the same precedence in an expression, if they are left-associative, the leftmost operator connects its arguments first. If right-associative, the rightmost connects first. .. note:: Instead of drawing parse trees, we usually use parentheses to indicate which part is connected earlier than other parts. Preceisely speaking, parse trees of expressions with extra parentheses are different from original ones. Abstract syntax tree (AST) is a tree that can be made from a parse tree by removing non-essential nodes (e.g. parentheses). `Abstract syntax tree - Wikipedia `_ In the following explanation, we add parentheses to indicate precedences among operators, keeping the AST unchanged. .. admonition:: Precedences of arithmetic operators In most languages, arithmetic operators have the same precedences as mathematics. For example, ``a + b * c`` is equivalent to ``a + ( b * c )``. .. admonition:: Associativities of arithemtic operators In most languages, arithmetic operators are left-associative. For example, ``a - b + c - d`` is equivalent to ``(( a - b ) + c ) - d``. .. admonition:: Precedence and associativity in APL In APL, all operatos have the same precedence, and are right-associative. For example, ``A × B + C`` is equivalent to ``A × ( B + C )``. .. admonition:: Exercise 12 :class: exercise Suppose precedences and associativities of operators are given by the following table. Put parentheses at proper positions in expressions below so that their structures are explicit. =========== ================= ============ precedences associativities =========== ================= ============ high left-associative ``#``, ``$`` low right-associative ``!``, ``?`` =========== ================= ============ 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:`[Answer]` ===================== Order of evaluation ===================== *Evaluation* is the process to calculate values of expressions. Note that the order of evaluation is a different concept from precedence and associativity because evaluation is a semantic concept while precedence and associativity is a syntactic concept(:numref:`definition_of_language`). When an expression is composed of several sub-expressions, the result depends on the order of evaluation if some of sub-expressions have side-effects. .. admonition:: Side effect and evaluation order In the following C program, the result is different depending on that either variable ``a`` or function ``fun1()`` in the statement (1) is evaluated first. .. code-block:: c int a = 1; int fun1() { a = 2; return 3; } void fun2() { a = a + fun1(); /* (1) */ } void main() { fun2(); } As shown above, side-effect causes a problem if the order of evaluation is undefined. We may think of several solutions as follows: 1. Do nothing. --- The result is compiler dependent. 2. Prohibit side effect. --- It is not practical for imperative languages. 3. Define the order of evaluation. --- It obstructs optimization. * Old C language adopts (1). * Java adopts (3). It evaluates an expression from left to right (See `What are the rules for evaluation order in Java? `_ for detail). * C/C++ introduces a `sequence point `_, which is a mixture of (1) and (3). * Functional lanuages such as ML and Haskell adopts (2) with no problem because they have no side-effects. .. index:: pair: short-circuit; evaluation ========================== Short-circuit evaluation ========================== *Short-circuit evaluation* is an evaluation strategy where some sub-expressions may not be evaluated if the value of the entire expression can be determined without them. .. admonition:: Logical operators When the value of ``a`` is less than 0, the following expression can be evaluated to ``false`` without evaluating ``b < 10``. .. code-block:: c ( a >= 0 ) && ( b < 10 ) .. admonition:: Exercise 13 :class: exercise Java has two types of logical operators: ``&&`` and ``||`` are short-circuting and ``&`` and ``|`` are not. Explain why we need both types of operators. :ref:`[Answer] ` .. index:: pair: lazy; evaluation .. _lazyEvaluation: ================= Lazy evaluation ================= *Lazy evaluation* is an evaluation strategy where an expression is not evaluated until its value is necessary in another part later. Lazy evaluation implies short-circuit evaluation because sub-expressions are not required to be evaluated after the value of entire expression is calculated. .. admonition:: ``range`` in Python3 .. code-block:: python for i in range(10000): if i > 10: break print(i*2) In Python2, ``range(10000)`` generates a list of 10000 elements and returns them. In Python3, ``range(10000)`` returns a list whose elements have not been evaluated yet. The elements will be generated one by one when each time ``print(i*2)`` is executed. .. admonition:: Enumerable#lazy in Ruby .. code-block:: ruby x = (1..Float::INFINITY).lazy.map{|x| x*2} puts x.first(10) .. admonition:: Haskell Haskell uses lazy evaluation for every expression.