Do you know how your programming language evaluate boolean expressions?

I know that some people would answer things like "boolean logic (of course)," but I want to explain here a mechanism present in the majority of the programming languages. Many people know how it works, but neither all know how to explain or why this happens.

I'm talking about the McCarthy evaluation, minimal evaluation, or (how it is more known in the Computer Science world) short-circuit evaluation.

The first time I saw that expression was in the book Programming Languages, written by Robert Sebesta. I thought he was going to do some parallel with an Electrical Engineering subject. When I reached the item, I noticed that I used it almost every day, even not knowing exactly what I was doing.

First contact

An expression's short-circuit evaluation is when the result of the expression is defined without the need to evaluate all operands and operators.

A simple example, consider the expression:

(25 * x) * (y % 14 + 21).

If the value of x is 0, no matter what, the result of the whole expression will be zero.

0 * (y % 14 + 21) = 0

Knowing the value of x, the need to evaluate the second expression (y % 14 + 21) or do the multiplication between the right and the left side may not exist.

Unfortunately, with arithmetic expressions, it is tough to detect when this shortcut can be used. However, the programming languages take advantage of this behavior to evaluate another type of expression.

Evaluating Boolean expressions

Consider the boolean expression: x < 1 && y > 2.

His final value is independent of the second expression if x >= 1 because FALSE && y > 2 will always be FALSE, no matter the value of y. We are sure about this because, following the boolean logic, both sides of && expressions need to be true to result in a true value.

Therefore, when x < 0, we don't need to evaluate y, the constant 2, the > operand, or even the && operation.

Unlike arithmetic expressions, it is much easier to know if we can take this shortcut during the runtime of our program on boolean expressions.

The majority of the programming languages use short-circuit evaluation, including Javascript, Ruby, and Python.

How can I use the short-circuit evaluation?

I will give an example of the use of short-circuit evaluation using a comparison between Javascript and Ruby.

You are writing a function that will accept one argument that can be anything unless null or false because receiving these values will raise an exception and stop your program.

I'm a Rubyist, so I would write something like:

def some_method(example_var)
 # some content that does not allow to receive an "example_var" nil or false 
end

example_var = nil
some_method(example_var) if example_var

Unfortunately, this syntax does not exist in Javascript, but we can do something similar with:

function someFunction(exampleVar) {
  // some content that does not allow to receive an "exampleVar" null or false  
}

var exampleVar = null;
exampleVar && someFunction(exampleVar); 

In this case, taking advantage of the short-circuit evaluation, the function someFunction would run only if exampleVar was not null, undefined, or false.

P.S.: The postconditional if in the Ruby example is just a sugar syntax and is not translated to a && something(a). I used that way to exemplify the usage of the short-circuit evaluation on the Javascript example.

Dual behavior

Some programming languages implement eager operators, alongside the short-circuit ones, that will run both sides of the expression. Ruby and Javascript are examples of languages that contain eager operators, but other famous languages like Python and Go don't include it.

You can use eager operators on Ruby and Javascript with: & and |. Besides that, you can use them as bitwise operators(Go and Python include those operators too, but just as bitwise, not eager).

To exemplify what I want to mean with that, I will provide a Ruby example using eager operators and short-circuit operators.

def some_method
  puts "I'm running."  
end

example_var = false

example_var && some_method # => false
example_var & some_method  # => I'm running; false

When you use the short-circuit operator, the method some_method is not executed because example_var was evaluated as false. The execution stopped, but when you run with the eager operator, both sides of the expression are evaluated (consequently, the method some_method will run).

What is the purpose of the short-circuit evaluation?

Probably, you are thinking about what the purpose of this short-circuit evaluation is, and I will explain with another example.

Suppose you are creating a loop to search the index of a value in an array using while in Java, and by mistake, you use the single & to evaluate your condition.

Java is one of the languages with dual behavior, and you can use & as the eager operator and && as the short-circuit operator just as we saw using Ruby.

A version of the code could be:

public class JavaExample {
    public static void main(String []args){
         int[] list = {1, 2, 3, 4, 5};
         int listen = list.length;
         int key = 6;
         int index = 0;

         while((index < listen) & (list[index] != key))
             index = index + 1;
    }
}

# $ javac JavaExample.java
# $ java -Xmx128M -Xms16M JavaExample
# Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6 at JavaExample.main(JavaExample.java:9)

Since the short-circuit evaluation is not being used, both sides of the & operation will be executed, no matter if the left side is true or false. If key is not present in the list, the program raises an exception indicating that the program is trying to access an index out of bound.

The same iteration that contains index == listlen will execute list[listlen], which causes the indexation error because the list is declared with the value listlen - 1 as the index upper limit.

But if you use the regular && that will not happen because Java uses short-circuit evaluation on boolean expressions.

If you try to reproduce this error on a language like Ruby, even with the eager operator & you will not see any exceptions because, by default, Ruby will check if the index is in the bounds of the array.

Life is not a bed of roses

Even the short-circuit evaluation looking good on the theory, we need to pay attention to some side effects that could happen.

Let's suppose we are using short-circuit evaluation in an expression, and a chunk of the expression that contains a side effect is not evaluated.

((x > y) || (y++) / 10)

On this expression, y is modified only when x <= y. If the programmer assumed that y would be changed each time the expression runs, that would result in a big mistake in the final result of the program.

Conclusion

If you want to go deeper, you can check the short-circuit logic formalization based on Hoare's conditional

That's it! I hope that you learned something about the short-circuit evaluation, and I wish that the acquired knowledge contributes to your programmer life.

Please leave a comment!