View source for Short-circuit evaluation

{{Short description|Programming language construct}}
{{Distinguish|Short-circuit test}}
{{More citations needed|date=August 2013}}
{{Evaluation strategy}}
'''Short-circuit evaluation''', '''minimal evaluation''', or '''McCarthy evaluation''' (after [[John McCarthy (computer scientist)|John McCarthy]]) is the semantics of some [[Logical connective|Boolean operators]] in some [[programming language]]s in which the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the <code>AND</code> function evaluates to <code>false</code>, the overall value must be <code>false</code>; and when the first argument of the <code>OR</code> function evaluates to <code>true</code>, the overall value must be <code>true</code>.

In programming languages with [[lazy evaluation]] ([[Lisp (programming language)|Lisp]], [[Perl]], [[Haskell]]), the usual [[Boolean expression|Boolean operators]] short-circuit. In others ([[Ada (programming language)|Ada]], [[Java (programming language)|Java]], [[Delphi (software)|Delphi]]), both short-circuit and standard Boolean operators are available. For some Boolean operations, like ''[[exclusive or]]'' (XOR), it is impossible to short-circuit, because both operands are always needed to determine a result.

Short-circuit operators are, in effect, [[control structure]]s rather than simple arithmetic operators, as they are not [[Strict function|strict]]. In [[imperative language]] terms (notably [[C (programming language)|C]] and [[C++]]), where side effects are important, short-circuit operators introduce a [[sequence point]]: they completely evaluate the first argument, including any [[Side effect (computer science)|side effects]], before (optionally) processing the second argument. [[ALGOL 68]] used ''proceduring'' to achieve ''user-defined'' short-circuit operators and procedures.

The use of short-circuit operators has been criticized as problematic:
{{Quote 
|text = The conditional connectives — "<u>cand</u>" and "<u>cor</u>" for short — are ... less innocent than they might seem at first sight. For instance, <u>cor</u> does not distribute over <u>cand</u>: compare
:(A <u>cand</u> B) <u>cor</u> C ''with'' (A <u>cor</u> C) <u>cand</u> (B <u>cor</u> C);
in the case ¬A ∧ C , the second expression requires B to be defined, the first one does not. Because the conditional connectives thus complicate the formal reasoning about programs, they are better avoided.
|author = [[Edsger W. Dijkstra]]<ref>[[Edsger W. Dijkstra]] "On a somewhat disappointing correspondence", EWD1009-0, 25 May 1987 [http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1009.PDF full text]</ref>}}

== Definition ==
In any programming language that implements short-circuit evaluation, the expression <code>''x'' and ''y''</code> is equivalent to the [[Conditional (programming)|conditional expression]] <code>if ''x'' then ''y'' else ''x''</code>, and the expression <code>''x'' or ''y''</code> is equivalent to <code>if ''x'' then ''x'' else ''y''</code>. In either case, ''x'' is only evaluated once.

The generalized definition above accommodates loosely typed languages that have more than the two [[truth-value]]s <code>True</code> and <code>False</code>, where short-circuit operators may return the last evaluated subexpression. This is called "last value" in the table below. For a strictly-typed language, the expression is simplified to <code>if ''x'' then ''y'' else '''false'''</code> and <code>if ''x'' then '''true''' else ''y''</code> respectively for the boolean case.

=== Precedence ===
Although {{code|AND}} takes [[operator precedence|precedence]] over {{code|OR}} in many languages, this is not a universal property of short-circuit evaluation. An example of the two operators taking the same precedence and being [[left-associative]] with each other is [[POSIX shell]]'s command-list syntax.<ref>{{cite web |title=Shell Command Language |url=https://pubs.opengroup.org/onlinepubs/009695399/utilities/xcu_chap02.html |website=pubs.opengroup.org}}</ref>{{rp|at=§2.9.3}}

The following simple left-to-right evaluator enforces a precedence of {{code|AND}} over {{code|OR}} by a {{code|continue}}:

 '''function''' short-circuit-eval (''operators'', ''values'')
     '''let''' ''result'' := True
     '''for each''' (''op'', ''val'') in (''operators'', ''values''):
         '''if''' ''op'' = "AND" && ''result'' = False
             '''continue'''
         '''else if''' ''op'' = "OR" && ''result'' = True
             '''return''' ''result''
         '''else'''
             ''result'' := ''val''
     '''return''' ''result''

=== Formalization ===
Short-circuit logic, with or without side-effects, have been formalized based on [[Hoare logic#Conditional rule|Hoare's conditional]]. A result is that non-short-circuiting operators can be defined out of short-circuit logic to have the same sequence of evaluation.<ref>{{cite arXiv |last1=Bergstra |first1=Jan A. |last2=Ponse |first2=A. |last3=Staudt |first3=D.J.C. |date=2010 |title=Short-circuit logic |eprint=1010.3674|class=cs.LO}}</ref>

=== Comparison with bitwise operators ===
<code>&</code> and <code>|</code> are [[Bitwise operation|bitwise operators]] that occur in many programming languages. The major difference is that bitwise operations operate on the individual bits of a binary numeral, whereas conditional operators operate on logical operations. Additionally, expressions either side of a bitwise operator are always evaluated.  In some languages, including [[Java (programming language)|Java]] and [[C sharp (programming language)|C#]], they can be used on boolean operands to force both sides to be evaluated.
<syntaxhighlight lang="java">
if (expression1 || expression2 || expression3)
</syntaxhighlight>If expression 1 is true, expressions 2 and 3 are not checked.
<syntaxhighlight lang="java">
if (expression1 | expression2 | expression3)
</syntaxhighlight>This checks expressions 2 and 3, even if expression 1 is true.

Short-circuit operators can thus reduce run times by avoiding unnecessary calculations. They can also avoid null exceptions when expression 1 checks whether an object is valid.

==Support in common programming and scripting languages==
The following table is restricted to common programming languages and the basic boolean operators for [[logical conjunction]] <code>AND</code> and [[logical disjunction]] <code>OR</code>. [[Bitwise operator]]s are shown only for languages that allow them to be used as eager boolean operators and have the same return type.

Note that there are more short-circuit operators, for example the [[ternary conditional operator]], which is <code>cond '''?''' e1 ''':''' e2</code> ([[C (programming language)|C]], [[C++]], [[Java (programming language)|Java]], [[PHP]]), <code>'''if''' cond '''then''' e1 '''else''' e2</code> ([[ALGOL]], [[Haskell (programming language)|Haskell]], [[Kotlin (programming language)|Kotlin]], [[Rust (programming language)|Rust]]), <code>e1 '''if''' cond '''else''' e2</code> ([[Python (programming language)|Python]]). Please take a look at [[ternary conditional operator#Usage]].

{| class="wikitable"
|+ Boolean operators in common languages
! Language !! [[Eager evaluation|Eager]] operators !! Short-circuit operators !! Result type
|-
| [[Ada (programming language)|Ada]]
| <code>and</code>, <code>or</code>
| <code>and then</code>, <code>or else</code>
| Boolean
|-
| [[ALGOL 68]]
| and, &, ∧ ; or, ∨
| {{depends|andf , orf ''(both user defined)''}}
| Boolean
|-
| [[APL (programming language)|APL]]
| <code>∧</code>, <code>∨</code>
| <code>:AndIf</code>, <code>:OrIf</code>
| Boolean
|-
| [[awk]]
| {{CNone|''none''}}
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Boolean
|-
| [[C (programming language)|C]], [[Objective-C]]
| <code>&</code>, <code><nowiki>|</nowiki></code>{{efn |name=bitwise_c |1=The bitwise operators behave like boolean operators when both arguments are of type <code>bool</code> or take only the values <code>0</code> or <code>1</code>.<ref>[http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf ISO/IEC 9899 standard, sections 6.2.5, 6.3.1.2, 6.5 and 7.16.]</ref>}}
| <code>&&</code>, <code><nowiki>||</nowiki></code><ref>[http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf ISO/IEC 9899 standard, section 6.5.13]</ref>
| int
|-
| [[C++]]{{efn |name=cpp |1=When [[operator overloading|overloaded]], the operators <code>&&</code> and <code><nowiki>||</nowiki></code> are eager and can return any type.}}
| {{CNone|''none''}}
| <code>&&</code>, <code><nowiki>||</nowiki></code><ref>[http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3092.pdf ISO/IEC IS 14882 draft.]</ref>
| Boolean
|-
| [[C Sharp (programming language)|C#]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Boolean
|-
| [[D (programming language)|D]]{{efn |name=d |1=This only applies to runtime-evaluated expressions, <code>static if</code> and <code>static assert</code>. Expressions in static initializers or manifest constants use eager evaluation.}}
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Boolean
|-
| [[Eiffel (programming language)|Eiffel]]
| <code>and</code>, <code>or</code>
| <code>and then</code>, <code>or else</code>
| Boolean
|-
| [[Erlang (programming language)|Erlang]]
| <code>and</code>, <code>or</code>
| <code>andalso</code>, <code>orelse</code>
| Boolean
|-
| [[Fortran]]{{efn |name=fortran |1=Fortran operators are neither short-circuit nor eager: the language specification allows the [[compiler]] to select the method for optimization.}}
| <code>.and.</code>, <code>.or.</code>
| <code>.and.</code>, <code>.or.</code>
| Boolean
|-
| [[Go (programming language)|Go]], [[Haskell (programming language)|Haskell]], [[OCaml]]{{efn |name=bitwise_without_bool |1=In lua and OCaml, bitwise operators <code>&</code>, <code><nowiki>|</nowiki></code> (OCaml <code>land</code>, <code>lor</code>) are restricted to integers and cannot be used with Booleans.}}
| {{CNone|''none''}}
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Boolean
|-
| [[Java (programming language)|Java]], [[R (programming language)|R]], [[Swift (programming language)|Swift]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&&</code>, <code><nowiki>||</nowiki></code>{{efn |1=In Java, these along with {{code|?…:}} are sometimes referred to as "conditional operators".<ref>{{Cite web|url=https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op2.html|title=Equality, Relational, and Conditional Operators (The Java™ Tutorials > Learning the Java Language > Language Basics)|website=docs.oracle.com|access-date=2019-04-29}}</ref>}}
| Boolean
|-
| [[JavaScript]]
| {{CNone|''none''}}
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Last value
|-
| [[Julia (programming language)|Julia]]
| {{CNone|''none''}}
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Last value
|-
| [[Kotlin (programming language)|Kotlin]]
| <code>and</code>, <code>or</code>
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Boolean
|-
| [[Lisp (programming language)|Lisp]], [[Lua (programming language)|Lua]]{{efn |name=bitwise_without_bool}}, [[Scheme (programming language)|Scheme]]
| {{CNone|''none''}}
| <code>and</code>, <code>or</code>
| Last value
|-
| [[MATLAB]]{{efn |name=matlab |1=The operator <code>&</code> behaves like a short-circuit operator when used in a statement following <code>if</code> or <code>while</code>.<ref>{{cite web |author=<!-- not stated --> |title=and, & |url=https://www.mathworks.com/help/matlab/ref/double.and.html |website=MathWorks Help Center |access-date=2025-02-02}}</ref>}}
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&</code>, <code><nowiki>|</nowiki></code>, <code>&&</code>, <code><nowiki>||</nowiki></code>
| Boolean
|-
| [[MUMPS]] (M)
| <code>&</code>, <code>!</code>
| {{CNone|''none''}}
| Numeric
|-
| [[Modula-2]]
| {{CNone|''none''}}
| <code>AND</code>, <code>OR</code>
| Boolean
|-
| [[Pascal (programming language)|Pascal]]
| <code>and</code>, <code>or</code>{{efn |name=pascal-1 |1=[[Pascal (programming language)#ISO/IEC 10206:1990 Extended Pascal|ISO/IEC 10206:1990 Extended Pascal]] allows, but does not require, short-circuiting.}}{{efn |name=delphi |1=[[Delphi (software)|Delphi]] and [[Free Pascal]] default to short circuit evaluation. This may be changed by [[compiler]] options but does not seem to be used widely.}}
| <code>and_then</code>, <code>or_else</code><!--{{refn |group=lower-alpha |name=pascal-2 |1=ISO/IEC 10206:1990 Extended Pascal supports <code>and_then</code> and <code>or_else</code>.<ref>{{cite web|url=http://www.gnu-pascal.de/gpc/and_005fthen.html#and_005fthen#GNU |title=and_then - The GNU Pascal Manual |publisher=Gnu-pascal.de |access-date=2013-08-24}}</ref>}}-->{{efn |name=delphi}}
| Boolean
|-
| [[Perl]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&&</code>, <code>and</code>, <code><nowiki>||</nowiki></code>, <code>or</code>
| Last value
|-
| [[PHP]]
| {{CNone|''none''}}
| <code>&&</code>, <code>and</code>, <code><nowiki>||</nowiki></code>, <code>or</code>
| Boolean
|-
| [[POSIX shell]], [[Bash (Unix shell)|Bash]]
| {{CNone|''none''}}
| <code>&&</code>, <code><nowiki>||</nowiki></code>
| Numeric (exit code)
|-
| [[PowerShell]] Scripting Language
| {{CNone|''none''}}
| <code>-and</code>, <code>-or</code>
| Boolean
|-
| [[Python (programming language)|Python]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>and</code>, <code>or</code>
| Last value
|-
| [[Ruby (programming language)|Ruby]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&&</code>, <code>and</code>, <code><nowiki>||</nowiki></code>, <code>or</code><ref>{{Cite web |title=operators - Documentation for Ruby 3.3 |url=https://docs.ruby-lang.org/en/3.3/syntax/operators_rdoc.html#label-Logical+Operators |access-date=2024-04-02 |website=docs.ruby-lang.org}}</ref>
| Last value
|-
| [[Rust (programming language)|Rust]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>&&</code>, <code><nowiki>||</nowiki></code><ref>{{Cite web|url=https://doc.rust-lang.org/std/ops/index.html|title=std::ops - Rust|website=doc.rust-lang.org|access-date=2019-02-12}}</ref>
| Boolean
|-
| [[Smalltalk]]
| <code>&</code>, <code><nowiki>|</nowiki></code>
| <code>and:</code>, <code>or:</code>{{efn |name=smalltalk |1=Smalltalk uses short-circuit semantics as long as the argument to <code>and:</code> is a block (e.g., {{code|false and: [Transcript show: 'Wont see me']|smalltalk}}).}}
| Boolean
|-
| [[Standard ML]]
| {{Unknown}}
| <code>andalso</code>, <code>orelse</code>
| Boolean
|-
| [[Visual Basic .NET]]
| <code>And</code>, <code>Or</code>
| <code>AndAlso</code>, <code>OrElse</code>
| Boolean
|-
| [[Visual Basic]], [[Visual Basic for Applications]] (VBA)
| <code>And</code>, <code>Or</code>
| {{CNone|''none''}}
| Numeric
|}
{{notelist}}

==Common use==
===Avoiding undesired side effects of the second argument===
Usual example, using a [[C (programming language)|C-based]] language:
<syntaxhighlight lang="c">
int denom = 0;
if (denom != 0 && num / denom) {
    ... // ensures that calculating num/denom never results in divide-by-zero error   
}
</syntaxhighlight>

Consider the following example:
<syntaxhighlight lang="c">
int a = 0;
if (a != 0 && myfunc(b)) {
    doSomething();
}
</syntaxhighlight>

In this example, short-circuit evaluation guarantees that <code>myfunc(b)</code> is never called. This is because <code>a != 0</code> evaluates to ''false''. This feature permits two useful programming constructs.

# If the first sub-expression checks whether an expensive computation is needed and the check evaluates to ''false'', one can eliminate expensive computation in the second argument. 
# It permits a construct where the first expression guarantees a condition without which the second expression may cause a [[run-time error]].

Both are illustrated in the following C snippet where minimal evaluation prevents both null pointer dereference and excess memory fetches:
<syntaxhighlight lang="c">
bool isFirstCharValidAlphaUnsafe(const char* p) {
    return isalpha(p[0]); // SEGFAULT highly possible with p == NULL
}

bool isFirstCharValidAlpha(const char* p) {
    return p != NULL && isalpha(p[0]); // 1) no unneeded isalpha() execution with p == NULL, 2) no SEGFAULT risk
}
</syntaxhighlight>

===Idiomatic conditional construct===
Since minimal evaluation is part of an operator's semantic definition and not an optional [[compiler optimization|optimization]], a number of coding idioms rely on it as a succinct conditional construct. Examples include:

[[Perl]] idioms:
<syntaxhighlight lang="perl">
some_condition or die;    # Abort execution if some_condition is false
some_condition and die;   # Abort execution if some_condition is true
</syntaxhighlight>

[[POSIX shell]] idioms:<ref>{{cite web |url=https://unix.stackexchange.com/questions/190543/what-does-mean-in-bash |title=What does {{!}}{{!}} mean in bash? |publisher=stackexchange.com |access-date=2019-01-09}}</ref>
<syntaxhighlight lang="bash">
modprobe -q some_module && echo "some_module installed" || echo "some_module not installed"
</syntaxhighlight>
This idiom presumes that <code>echo</code> cannot fail.

==Possible problems==
=== Untested second condition leads to unperformed side effect ===
Despite these benefits, minimal evaluation may cause problems for programmers who do not realize (or forget) it is happening. For example, in the code
<syntaxhighlight lang="c">
if (expressionA && myFunc(b)) {
    doSomething();
}
</syntaxhighlight>
if <code>myFunc(b)</code> is supposed to perform some required operation regardless of whether <code>doSomething()</code> is executed, such as allocating system resources, and <code>expressionA</code> evaluates as false, then <code>myFunc(b)</code> will not execute, which could cause problems. Some programming languages, such as [[Java (programming language)|Java]], have two operators, one that employs minimal evaluation and one that does not, to avoid this problem.

Problems with unperformed side effect statements can be easily solved with proper programming style, i.e., not using side effects in boolean statements, as using values with side effects in evaluations tends to generally make the code opaque and error-prone.<ref>{{cite web |url=http://www.itu.dk/people/sestoft/papers/SondergaardSestoft1990.pdf |title=Referential Transparency, Definiteness and Unfoldability |publisher=Itu.dk |access-date=2013-08-24}}</ref>

===Reduced efficiency due to constraining optimizations===
Short-circuiting can lead to errors in [[branch prediction]] on modern [[central processing unit]]s (CPUs), and dramatically reduce performance. A notable example is highly optimized ray with axis aligned box intersection code in [[Ray tracing (physics)|ray tracing]].{{clarify|date=November 2010}} Some compilers can detect such cases and emit faster code, but programming language semantics may constrain such optimizations.{{citation needed|date=October 2016}}

An example of a compiler unable to optimize for such a case is [[Java (programming language)|Java]]'s [[HotSpot (virtual machine)|Hotspot virtual machine]] (VM) as of 2012.<ref>{{cite web |last=Wasserman |first=Louis |date=11 July 2012 |title=Java: What are the cases in which it is better to use unconditional AND (& instead of &&) |url=https://stackoverflow.com/a/11412121 |website=Stack Overflow}}</ref>

==See also==
*[[Don't-care term]]
* [[Null coalescing operator]]
* [[Ternary conditional operator]]

==References==
{{Reflist}}

{{John McCarthy}}

[[Category:Articles with example C code]]
[[Category:Articles with example Perl code]]
[[Category:Compiler optimizations]]
[[Category:Conditional constructs]]
[[Category:Evaluation strategy]]
[[Category:Implementation of functional programming languages]]