Search code examples
haskellprogramming-languageslazy-evaluationmultiple-languages

Swap logical operator arguments for faster evaluation?


Does any programming language implement swapping of arguments of logical operation (such as AND, OR) for faster evaluation?

Example (I think such method could be implemented in a lazy evaluation language like Haskell)

  1. Lets say we have defined two predicates A and B.
  2. During program execution, B was evaluated to "True" and A was not evaluated
  3. In the later execution we have condition IF A OR B
  4. Arguments of "OR" are swapped, and the condition becomes IF B OR A
  5. Condition is evaluated to "True" without evaluating A

Solution

  • Under lazy evaluation, AND and OR are not commutative.

    foo :: Int -> Bool
    foo n = False && foo (n+1)  -- evaluates to False
    
    bar :: Int -> Bool
    bar n = bar (n+1) && False  -- diverges
    

    Under eager evaluation (strict semantics), and absence of side effects, they are commutative. I am not aware of any usual optimization being done by some compiler here, though. (Constants folding aside.)

    If side effects are present, AND/OR are not commutative, of course. For instance, an Ocaml compiler can not swap the arguments unless it can prove that at least one of them is side effect-free.