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:

Islam di Portugal

Islam menurut negara Afrika Aljazair Angola Benin Botswana Burkina Faso Burundi Kamerun Tanjung Verde Republik Afrika Tengah Chad Komoro Republik Demokratik Kongo Republik Kongo Djibouti Mesir Guinea Khatulistiwa Eritrea Eswatini Etiopia Gabon Gambia Ghana Guinea Guinea-Bissau Pantai Gading Kenya Lesotho Liberia Libya Madagaskar Malawi Mali Mauritania Mauritius Maroko Mozambik Namibia Niger Nigeria Rwanda Sao Tome dan Principe Senegal Seychelles Sierra Leone Somalia Somaliland Afrika Selatan ...

 

Maxillary artery

Artery supplying face structures in humans Maxillary arteryMaxillary artery and its branches. (Internal maxillary is horizontal at left center.)Plan of branches of maxillary artery.DetailsPrecursoraortic arch 1Sourceexternal carotid arteryBranches1st part: anterior tympanic - deep auricular - middle meningeal - superior tympanic artery - accessory meningeal - inferior alveolar2nd part: Posterior deep temporal artery - Pterygoid branches - masseteric - buccinator - Anterior deep temporal arter...

 

Indrian Koto

Indrian Koto (lahir 19 Februari 1983)[1] adalah seorang penyair Indonesia.[2] Sajak-sajak Indrian Koto telah dimuat di media cetak baik daerah maupun nasional, seperti di harian Kompas, koran Tempo, Media Indonesia, dan Riau Pos.[3] Indrian merupakan adik dari Raudal Tanjung Banua. Fadlillah Malin Sutan di Harian Haluan menyebut Indrian bersama E.S. Ito, Raudal Tanjung Banua, Dewi Sartika, Riki Dhamparan Putra, dan Damhuri Muhammad sebagai generasi sastrawan Indonesia ...

Van Buren County, Tennessee

County in Tennessee, United States County in TennesseeVan Buren CountyCountyVan Buren County Courthouse in Spencer FlagLocation within the U.S. state of TennesseeTennessee's location within the U.S.Coordinates: 35°41′N 85°28′W / 35.69°N 85.46°W / 35.69; -85.46Country United StatesState TennesseeFoundedJanuary 3, 1840Named forMartin Van Buren[1]SeatSpencerLargest townSpencerArea • Total275 sq mi (710 km2) •...

 

Geology of Suriname

Standing in the Marowijne River The geology of Suriname is predominantly formed by the Guyana Shield, which spans 90% of its land area. Coastal plains account for the remaining ten percent. Most rocks in Suriname date to the Precambrian. These crystalline basement rocks consists of granitoid and acid volcanic rocks with enclaves of predominantly low-grade metamorphic, geosynclinal rocks in the Marowijne area and of probably considerably older rocks in the Falawatra group of the Bakhuisgebirge...

 

Aéroport de Londres-Luton

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne s'appuie pas, ou pas assez, sur des sources secondaires ou tertiaires (novembre 2021). Pour améliorer la vérifiabilité de l'article ainsi que son intérêt encyclopédique, il est nécessaire, quand des sources primaires sont citées, de les associer à des analyses faites par des sources secondaires. Aéroport de Londres-LutonLondon Luton Airport Localisation Pays Royaume-Uni Ville Luton Coordo...

Without Warning (album)

This article is about the 21 Savage, Offset, and Metro Boomin album. For other albums, see Without Warning § Music. 2017 studio album by 21 Savage, Offset, and Metro BoominWithout WarningStudio album by 21 Savage, Offset, and Metro BoominReleasedOctober 31, 2017 (2017-10-31)Genre Hip hop trap Length33:22Label Slaughter Gang Epic Capitol Motown Quality Control Boominati Republic Producer Bijan Amir Cubeatz Dre Moon Metro Boomin Southside 21 Savage chronology Issa Album(...

 

Terminal City (Manhattan)

Commercial development in Manhattan, New York City Artist's depiction of Terminal City when complete; published 1913 Terminal City, also known as the Grand Central Zone, is an early 20th century commercial and office development in Midtown Manhattan, New York City. The space was developed atop the former Grand Central Station railyard, after the New York Central Railroad decided to rebuild the station into Grand Central Terminal, and reshape the railyard into a below-ground train shed, allowi...

 

Caprino Veronese

Caprino Veronesecomune Caprino Veronese – VedutaMonumento ai Caduti, in piazza a Caprino Veronese LocalizzazioneStato Italia Regione Veneto Provincia Verona AmministrazioneSindacoPaola Arduini (PdL - LN) dal 14-6-2014 TerritorioCoordinate45°36′N 10°48′E / 45.6°N 10.8°E45.6; 10.8 (Caprino Veronese)Coordinate: 45°36′N 10°48′E / 45.6°N 10.8°E45.6; 10.8 (Caprino Veronese) Altitudine254 m s.l.m. Superficie47...

Sergei Guriev

Russian economist In this name that follows Eastern Slavic naming customs, the patronymic is Maratovich and the family name is Guriev. Sergey GurievСергей ГуриевGuriev in 2021Born (1971-10-21) 21 October 1971 (age 52)Ordzhonikidze, North Ossetian ASSR, Russian SFSR, Soviet UnionNationalityOsseteCitizenshipSoviet Union, Russian FederationAlma materMoscow Institute of Physics and TechnologyKnown forHead Economist of the European Bank for Reconstruction and Develop...

 

By My Side Again

1999 filmBy My Side AgainTheatrical release posterSpanishCuando vuelvas a mi lado Directed byGracia QuerejetaScreenplay byGracia QuerejetaElías QuerejetaManuel Gutiérrez AragónProduced byElías QuerejetaStarringMercedes SampietroJulieta SerranoAdriana OzoresMarta BelausteguiRosa MariscalJorge PerugorríaCinematographyAlfredo MayoEdited byNacho Ruiz-CapillasMusic byÁngel IllarramendiProductioncompaniesSogetelElías Querejeta PCAlbares ProductionsBlue CinematograficaDistributed byWarner So...

 

Fort Leonard Wood

Lokasi Fort Leonard Wood, Missouri Fort Leonard Wood adalah census-designated place (CDP) di County Pulaski, Missouri, Amerika Serikat. Fort Leonard Wood memiliki populasi sebesar 13.666 jiwa pada tahun 2000. CDP ini dinamai dari Mayor Jendral Leonard Wood. Pranala luar Peta dan foto udara Koordinat: 37.738191° -92.117275° Peta jalan dari Google Maps, atau Yahoo! Maps, atau Windows Live Local Citra satelit dari Google Maps, Windows Live Local, WikiMapia Peta topografis dari TopoZone Gambar ...

The Woman Disputed

1928 film The Woman DisputedTheatrical posterDirected byHenry King, Sam TaylorWritten byC. Gardner SullivanProduced byJoseph M. Schenck ProductionsDistributed byUnited ArtistsRelease date September 1928 (1928-09) Running time108 minutesCountryUnited StatesLanguageSound film (Synchronized) The Woman Disputed is a 1928 American synchronized sound film. While the film has no audible dialog, it was released with a synchronized musical score with sound effects using both the sound-on-dis...

 

Básquet Coruña

Basketball team in A Coruña, SpainLeyma Básquet CoruñaLeaguesLEB OroFounded1996; 28 years ago (1996)ArenaPazo dos Deportes de RiazorCapacity4,425LocationA Coruña, SpainTeam colorsOrange and blue   PresidentRoberto CibeiraHead coachDiego EpifanioChampionships1 LEB Oro1 Copa GaliciaWebsitebasquetcoruna.com Home Away Club Básquet Coruña, more commonly referred by its sponsorship name of Leyma Básquet Coruña, is a professional basketball team based in A Coruña...

 

Animal culture

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: Animal culture – news · newspapers · books · scholar · JSTOR (May 2023) (Learn how and when to remove this message) Theory of cultural learning in non-human animals This article is about learning in non-human animals. For the place of animals in human culture, ...

Joe Morgan

American baseball player and analyst (1943–2020) This article is about the Baseball Hall of Famer. For the baseball player and manager, see Joe Morgan (manager). For other people named Joe Morgan, see Joe Morgan (disambiguation). Baseball player Joe MorganMorgan with the Cincinnati Reds in 1972Second basemanBorn: (1943-09-19)September 19, 1943Bonham, Texas, U.S.Died: October 11, 2020(2020-10-11) (aged 77)Danville, California, U.S.Batted: LeftThrew: RightMLB debutSeptember 21, 1963...

 

2008 NCAA Bowling Championship

Football tournament season 2008 NCAA Bowling ChampionshipTournament detailsDatesApril 2008Teams8Final positionsChampionsUMES (1st title)Runner-upArkansas State (1st title match)Tournament statisticsMatches played15Attendance467 (31 per match)Best playerJessica Worsley, UMES← 20072009 → The 2008 NCAA Bowling Championship was the fifth annual tournament to determine the national champion of women's NCAA collegiate ten-pin bowling. The tournament was played in Oma...

 

Niccolò Machiavelli

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Niccolò Machiavelli – berita · surat kabar · buku · cendekiawan · JSTOR (25 Juli 2020) Niccolò MachiavelliPotret Niccolò Machiavelli oleh Santi di TitoLahir(1469-05-03)3 Mei 1469Florence, Republic of Flore...

JS Pictures

South Korean production company 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: JS Pictures – news · newspapers · books · scholar · JSTOR (December 2017) (Learn how and when to remove this message) JS PicturesJS Pictures logoNative nameKorean nameHangul제이에스픽쳐스Revised RomanizationJeieseu Pikcheo...

 

USCGC Point Welcome

United States Coast Guard cutter USCGC Point Welcome (WPB-82329) USCGC Point Welcome on patrol in Vietnamese waters History United States NameUSCGC Point Welcome (WPB-82329) NamesakePoint Welcome, Aleutian Islands, Alaska, U.S. OwnerUnited States Coast Guard BuilderCoast Guard Yard, Curtis Bay, Maryland, U.S. Commissioned14 February 1962 Decommissioned29 April 1970 Honors andawards Navy Unit Commendation[2] Meritorious Unit Commendation (Navy)[3] Vietnam Service Medal with 2 s...