Short-circuit evaluation

Not to be confused with Short-circuit test.
Evaluation strategies

Short-circuit evaluation, minimal evaluation, or McCarthy evaluation (after John McCarthy) is the semantics of some Boolean operators in some programming languages 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 AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true.

In programming languages with lazy evaluation (Lisp, Perl, Haskell), the usual Boolean operators short-circuit. In others (Ada, Java, 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 structures rather than simple arithmetic operators, as they are not strict. In imperative language terms (notably C and C++), where side effects are important, short-circuit operators introduce a sequence point: they completely evaluate the first argument, including any 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:

The conditional connectives — "cand" and "cor" for short — are ... less innocent than they might seem at first sight. For instance, cor does not distribute over cand: compare

(A cand B) cor C with (A cor C) cand (B cor 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.

— Edsger W. Dijkstra[1]

Definition

In any programming language that implements short-circuit evaluation, the expression x and y is equivalent to the conditional expression if x then y else x, and the expression x or y is equivalent to if x then x else y. In either case, x is only evaluated once.

The generalized definition above accommodates loosely typed languages that have more than the two truth-values True and False, 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 if x then y else false and if x then true else y respectively for the boolean case.

Precedence

Although AND takes precedence over 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.[2]: §2.9.3 

The following simple left-to-right evaluator enforces a precedence of AND over OR by a 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'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.[3]

Support in common programming and scripting languages

As you look at the table below, keep in mind that bitwise operators often do not behave exactly like logical operators, even if both arguments are of 0, 1 or Boolean type.

Examples:

  • In JavaScript, each of the following 3 expressions evaluates to false:
    (true & true) === (true && true),
    (false | false) === (false || false),
    (1 & 2) === (1 && 2).
  • In PHP, each of the following 3 expressions evaluates to false:
    (true & true) === (true && true),
    (0 | 0) === (0 || 0),
    (1 & 2) === (1 && 2).
Boolean operators in various languages
Language Eager operators Short-circuit operators Result type
Advanced Business Application Programming (ABAP) none and, or Boolean[a]
Ada and, or and then, or else Boolean
ALGOL 68 and, &, ∧ ; or, ∨ andf , orf (both user defined) Boolean
APL ∧, ∨, ⍲ (nand), ⍱ (nor), etc. :AndIf, :OrIf Boolean[a]
awk none &&, || Boolean
Bash none &&, || Boolean
C, Objective-C &, |[b] &&, ||, ?[5] int (&, |, &&,||), opnd-dependent (?)
C++[c] none &&, ||, ?[6] Boolean (&&,||), opnd-dependent (?)
C# &, | &&, ||, ?, ?? Boolean (&&,||), opnd-dependent (?, ??)
ColdFusion Markup Language (CFML) none AND, OR, &&, || Boolean
D[d] &, | &&, ||, ? Boolean (&&,||), opnd-dependent (?)
Eiffel and, or and then, or else Boolean
Erlang and, or andalso, orelse Boolean
Fortran[e] .and., .or. .and., .or. Boolean
Go, Haskell, OCaml none &&, || Boolean
Java, MATLAB, R, Swift &, | &&, || Boolean
JavaScript none &&, &&=, ||, ||= Last value
Julia none &&, || Last value
Lasso none and, or, &&, || Last value
Kotlin and, or &&, || Boolean
Lisp, Lua, Scheme none and, or Last value
MUMPS (M) &, ! none Numeric
Modula-2 none AND, OR Boolean
Oberon none &, OR Boolean
OCaml land, lor[7] &&, || Boolean
Pascal and, or[f][g] and_then, or_else[g] Boolean
Perl &, | &&, and, ||, or Last value
PHP none &&, and, ||, or Boolean
POSIX shell (command list) none &&, || Last value (exit)
PowerShell Scripting Language none -and, -or Boolean
Python &, | and, or Last value
Ruby &, | &&, and, ||, or[8] Last value
Rust &, | &&, ||[9] Boolean
Smalltalk &, | and:, or:[h] Boolean
Standard ML Un­known andalso, orelse Boolean
TTCN-3 none and, or[10] Boolean
Beckhoff TwinCAT® (IEC 61131-3)[i] AND, OR AND_THEN,[11] OR_ELSE[12] Boolean
Visual Basic .NET And, Or AndAlso, OrElse Boolean
Visual Basic, Visual Basic for Applications (VBA) And, Or Select Case[j] Numeric
Wolfram Language And @@ {...}, Or @@ {...} And, Or, &&, || Boolean
ZTT &, | none Boolean
  1. ^ a b ABAP and APL have no distinct boolean type.
  2. ^ The bitwise operators behave like boolean operators when both arguments are of type bool or take only the values 0 or 1.[4]
  3. ^ When overloaded, the operators && and || are eager and can return any type.
  4. ^ This only applies to runtime-evaluated expressions, static if and static assert. Expressions in static initializers or manifest constants use eager evaluation.
  5. ^ Fortran operators are neither short-circuit nor eager: the language specification allows the compiler to select the method for optimization.
  6. ^ ISO/IEC 10206:1990 Extended Pascal allows, but does not require, short-circuiting.
  7. ^ a b Delphi and Free Pascal default to short circuit evaluation. This may be changed by compiler options but does not seem to be used widely.
  8. ^ Smalltalk uses short-circuit semantics as long as the argument to and: is a block (e.g., false and: [Transcript show: 'Wont see me']).
  9. ^ The norm IEC 61131-3 doesn't actually define if AND and OR use short-circuit evaluation and it doesn't define the operators AND_THEN and OR_ELSE. The entries in the table show how it works for Beckhoff TwinCAT®.
  10. ^ BASIC languages that supported CASE statements did so by using the conditional evaluation system, rather than as jump tables limited to fixed labels.

Common use

Avoiding undesired side effects of the second argument

Usual example, using a C-based language: 

int denom = 0;
if (denom != 0 && num / denom)
{
    ... // ensures that calculating num/denom never results in divide-by-zero error   
}

Consider the following example: 

int a = 0;
if (a != 0 && myfunc(b))
{
    do_something();
}

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

  1. 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.
  2. 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: 

bool is_first_char_valid_alpha_unsafe(const char *p)
{
    return isalpha(p[0]); // SEGFAULT highly possible with p == NULL
}

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

Idiomatic conditional construct

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

Perl idioms: 

some_condition or die;    # Abort execution if some_condition is false
some_condition and die;   # Abort execution if some_condition is true

POSIX shell idioms:[13] 

modprobe -q some_module && echo "some_module installed" || echo "some_module not installed"

This idiom presumes that echo 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 

if (expressionA && myfunc(b)) {
    do_something();
}

if myfunc(b) is supposed to perform some required operation regardless of whether do_something() is executed, such as allocating system resources, and expressionA evaluates as false, then myfunc(b) will not execute, which could cause problems. Some programming languages, such as 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.[14]

Reduced efficiency due to constraining optimizations

Short-circuiting can lead to errors in branch prediction on modern central processing units (CPUs), and dramatically reduce performance. A notable example is highly optimized ray with axis aligned box intersection code in ray tracing.[clarification needed] Some compilers can detect such cases and emit faster code, but programming language semantics may constrain such optimizations.[citation needed]

An example of a compiler unable to optimize for such a case is Java's Hotspot virtual machine (VM) as of 2012.[15]

See also

References

  1. ^ Edsger W. Dijkstra "On a somewhat disappointing correspondence", EWD1009-0, 25 May 1987 full text
  2. ^ "Shell Command Language". pubs.opengroup.org.
  3. ^ Bergstra, Jan A.; Ponse, A.; Staudt, D.J.C. (2010). "Short-circuit logic". arXiv:1010.3674 [cs.LO].
  4. ^ ISO/IEC 9899 standard, sections 6.2.5, 6.3.1.2, 6.5 and 7.16.
  5. ^ ISO/IEC 9899 standard, section 6.5.13
  6. ^ ISO/IEC IS 14882 draft.
  7. ^ "OCaml - the OCaml language".
  8. ^ "operators - Documentation for Ruby 3.3". docs.ruby-lang.org. Retrieved 2024-04-02.
  9. ^ "std::ops - Rust". doc.rust-lang.org. Retrieved 2019-02-12.
  10. ^ ETSI ES 201 873-1 V4.10.1, section 7.1.4
  11. ^ "Beckhoff Information System - English". infosys.beckhoff.com. Retrieved 2021-08-16.
  12. ^ "Beckhoff Information System - English". infosys.beckhoff.com. Retrieved 2021-08-16.
  13. ^ "What does || mean in bash?". stackexchange.com. Retrieved 2019-01-09.
  14. ^ "Referential Transparency, Definiteness and Unfoldability" (PDF). Itu.dk. Retrieved 2013-08-24.
  15. ^ Wasserman, Louis (11 July 2012). "Java: What are the cases in which it is better to use unconditional AND (& instead of &&)". Stack Overflow.

Read other articles:

Bason Bridge railway station

Disused railway station in England Bason BridgeBason Bridge railway station in 1963General informationLocationnear East Huntspill, SedgemoorEnglandGrid referenceST345458Platforms1Other informationStatusDisusedHistoryPre-groupingSomerset Central RailwayPost-groupingSR and LMS Western Region of British RailwaysKey datesJuly 1856Opened10 June 1963Closed to goods traffic7 March 1966Closed to passengers2 October 1972Closed to milk traffic Bason Bridge railway station was a station on the Highbridg...

 

Calendar (Windows)

Application of Microsoft windows This article is about the built-in Windows application. For the now defunct free downloadable Microsoft mail and calendar client, see Windows Live Mail. CalendarCalendar running on Windows 10, using the light themeDeveloper(s)MicrosoftOperating systemMicrosoft WindowsPredecessorWindows Live MailTypeElectronic calendar Calendar is a personal calendar application made by Microsoft for Microsoft Windows. It offers synchronization of calendars using Microsoft Exch...

 

Florian Gazan

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article n’est pas rédigé dans un style encyclopédique (mai 2016). Vous pouvez améliorer sa rédaction ! Florian GazanBiographieNaissance 14 janvier 1968 (56 ans)Paris, FranceNom de naissance Florian SpieroNationalité françaiseActivité Animateur de radio, animateur de télévisionPère Jean-Pierre SpieroAutres informationsA travaillé pour RTLEurope 2NRJEurope 1Fun Radiomodifier - modifier l...

Strada statale 271 di Cassano

Strada statale 271di CassanoDenominazioni successive Strada provinciale 236 di Cassano Strada provinciale ex SS271 Matera-Santeramo LocalizzazioneStato Italia Regioni Puglia Basilicata DatiClassificazioneStrada statale InizioBari FineSS 7 presso Matera Lunghezza60,160[1] km Provvedimento di istituzioneD.M. 16/11/1959 - G.U. 41 del 18/02/1960[2] GestoreANAS (precedente gestore) Provincia di Bari Provincia di Matera (dal 2001) PercorsoStrade europee Manuale La ex ...

 

Spike Cohen

Spike CohenCohen berkampanye pada 2020LahirJeremy Cohen28 Juni 1982 (umur 41)Baltimore, Maryland, Amerika SerikatPartai politikLibertarianSuami/istriTasha Cohen ​(m. 2010)​Situs webSitus web kampanye Jeremy Spike Cohen (lahir 28 Juni 1982) adalah seorang aktivis politik, wirausahawan dan podcaster Amerika Serikat. Ia menjadi nominee Partai Libertarian untuk wakil presiden Amerika Serikat dalam pemilu 2020, menjabat sebagai rekan sepencalonan Jo Jorgensen. ...

 

Daging paus

Daging paus di Pasar ikan Tsukiji, Tokyo Daging paus di pasar ikan Bergen, Norwegia Daging paus adalah daging dari paus untuk konsumsi manusia dan hewan lain, dan mencakup organ tubuh, kulit, dan lapisan lemaknya. Daging paus dimasak dengan berbagai cara dan dalam sejarah telah dikonsumsi di berbagai tempat di penjuru dunia, termasuk Eropa dan Amerika Kolonial.[1] Konsumsinya tidak terbatas pada penduduk di sekitar pantai karena daging dan lapisan lemaknya dapat diawetkan. Praktik kon...

العلاقات البرتغالية اليونانية

العلاقات البرتغالية اليونانية البرتغال اليونان   البرتغال   اليونان تعديل مصدري - تعديل   العلاقات البرتغالية اليونانية هي العلاقات الثنائية التي تجمع بين البرتغال واليونان.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: �...

 

Motor kran

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Motor kran adalah jenis motor listrik yang digunakan pada kran. Arus listrik yang digunakan dapat arus searah maupun arus-bolak-balik. Pada daya listrik lebih besar dari 200 kW, digunakan motor kran berjenis motor arus searah. Sedangkan pada pemakaian ...

 

Tobirama Senju

Artikel ini kemungkinan ditulis dari sudut pandang penggemar dan bukan sudut pandang netral. Mohon rapikan untuk menghasilkan standar kualitas yang lebih tinggi dan untuk membuat pemakaian nada yang netral. (Maret 2022) (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Karakter dalam seri NarutoTobirama Senju千手扉間Penampilan perdanaMangaBab 118AnimeNaruto episode 69Tampil diAnime, manga, OVA, dan permainanPengisi suaraInggrisPeter LurieJepangKen'yū Horiuchi Informasi ...

Золотой век Грузии

История Грузииსაქართველოს ისტორია Доисторическая Грузия Шулавери-шомутепинская культураКуро-араксская культураТриалетская культураКолхидская культураКобанская культураДиаухиМушки Древняя история КолхидаАриан-КартлиИберийское царство ФарнавазидыГруз�...

 

Clive Owen

Clive Owen Clive Owen (lahir 3 Oktober 1962) adalah seorang pemeran pria berkebangsaan Inggris yang memenangkan nominasi Academy Award, Golden Globe, dan BAFTA. Dia berkarier di dunia film sejak tahun 1988. Filmografi Tahun Film Sebagai Catatan 1988 Vroom Jake 1989 Precious Bane Gideon Sarn TV movie 1990 Chancer Stephen Crane/Derek Love TV series Lorna Doone John Ridd TV movie 1991 Close My Eyes Richard 1993 Class of '61 Devin O'Neil TV movie Century Paul Reisner The Magician Det. Con. George...

 

Associazione Calcio Turris 1978-1979

Voce principale: Football Club Turris 1944. Associazione Calcio TurrisStagione 1978-1979Sport calcio Squadra Turris Allenatore Nicola Chiricallo, poi Giulio Lopez Presidente Salvatore Gaglione Serie C1 - Gir. B14º posto Coppa Italia SemiproFase eliminatoria a gironi Maggiori presenzeCampionato: Strino (34) Miglior marcatoreCampionato: Barone (10) 1977-1978 1979-1980 Si invita a seguire il modello di voce Turris 1978-79 Questa voce raccoglie le informazioni riguardanti l'Associazion...

The Rotary Foundation

International nonprofit organization This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: The Rotary Foundation – news · newspapers · books · scholar · JSTOR (June 2010) (Learn how and when to remove this template message) The Rotary Foundation is a non-profit corporation that supports the efforts of Rotary International to achieve world understanding and pe...

 

Port Dickson (town)

Not to be confused with Port Dickinson. For the district of Port Dickson, see Port Dickson District. For the federal constituency represented in the Dewan Rakyat, see Port Dickson (federal constituency). 2°31′N 101°48′E / 2.517°N 101.800°E / 2.517; 101.800 This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Port Dic...

 

Modèle:Palette Israël au Concours Eurovision de la chanson

v · m Israël au Concours Eurovision de la chanson Participation 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 Représentants Années 1970 1973 : Ilanit 1974 : Kaveret 1975 : Shlomo Artzi 1976 : Chocolate, Menta, Mastik 1977 : Ilanit 1978 : Izhar...

الدولة الصفارية

الدولة الصفارية السلالة الصفارية صفاريون   861 – 1003   الدولة الصفارية في أقصى اتساعها في عهد يعقوب بن الليث الصفار عاصمة زرنج، موجودة حاليًا في أفغانستان نظام الحكم ملكية الديانة أهل السنة والجماعة صفاريون يعقوب بن الليث الصفار 861–879 خلف ابن أحمد 963–1002 التاريخ ال...

 

Smith (play)

Comedy by the British writer W. Somerset Maugham Maugham in 1911 Smith is a comedy by the British writer W. Somerset Maugham, written when he was becoming a successful dramatist. The play was first seen in London in 1909. In the play, Thomas Freeman returns after years abroad to his sister Rose, and gets to know the fashionable social set who meet at her home; he eventually finds that the parlourmaid has the most merit of any in the household. History After the success of Lady Frederick, his ...

 

تمبلر

تمبلرالشعارلقطة شاشةمعلومات عامةموقع الويب tumblr.com (الإنجليزية) نوع الموقع  القائمة ... برنامج مدونة — موقع ويب — خدمة الشبكة الاجتماعية — شركة — مجتمع إنترنت البلد الأصلي  الولايات المتحدة التأسيس فبراير 2007 الجوانب التقنيةاللغة الإنجليزية ترتيب أليكسا 77[1](4 مايو...

List of Netflix original films (since 2024)

For Netflix original series and related specials, see List of Netflix original programming. For Netflix original stand-up comedy specials, see List of Netflix original stand-up comedy specials. For Netflix exclusive international distribution films, see Lists of Netflix exclusive international distribution programming. Netflix is an American global on-demand Internet streaming media provider, that has distributed a number of original programs, including original series, specials, miniseries,...

 

SMA Negeri 1 Klaten

SMA Negeri 1 KlatenSmansa Klaten, Padmawijaya, Kampus 13InformasiDidirikan5 November 1957JenisNegeriAkreditasiA[1]Nomor Statistik Sekolah301046002001Nomor Pokok Sekolah Nasional20309676MotoPadmawijayaMaskotChiku si burung hantuKetua KomiteDrs. Sumargana, M.SJumlah kelas30 Kelas Reguler,3 Kelas Unggulan OSN (total 33 kelas)Jurusan atau peminatanIlmu Pengetahuan Alam dan Ilmu Pengetahuan SosialRentang kelasX, XI IPA-IPS, XI IPA (OSN), XII IPA-IPS, XII IPA (OSN)KurikulumKurikul...