17

(This question is, of course, another thrilling installment of “The history of expression evaluation”; see the previous episodes here and here.)

In many programming languages, the Boolean operators ∧ and ∨, however they are spelled (and, &&, or, ||), evaluate their operands only as necessary. For example, if the first operand of ∧ is false, then no value of the second operand can make the result of the expression true. And if the first operand of ∨ is true, then the second operand need not be inspected at all, since the result is guaranteed to be true. This property is often referred to as “short-circuiting”.

It comes in handy in code like

if (x > 0) ∧ (a/x < 12) then

because the expression a/x is undefined if x = 0. It can also improve efficiency, if evaluating some of the operands would be computationally expensive.

The first language to support short-circuiting was the first language to have any notion of “Boolean expressions” at all: Lisp. (See page 22 of the LISP 1.5 Programmer's Manual.) What was the second language, not counting some dialect of Lisp?


Here are some notes on the subject. I'm putting them here in case they might be of use to anyone else interested in this sort of thing.

In Algol 60, Boolean operators were not short-circuiting, because…actually I don't know why. McCarthy was one of the language's designers, after all. I suppose you can get the same effect with something like

if if (x > 0) then (a/x < 12) else false then …,

but this is a little less elegant.

In Algol 68, Boolean operators are also not short-circuiting. One way to look at it is to consider that operators are not really different from procedures in Algol 68, and all arguments actual-parameters in procedure calls are always evaluated elaborated. Furthermore, if an exception were made for Boolean operations, then ∧ and ∨ could not be defined within the language using an operation-declaration.

There's a bit more to the story, however. When McCarthy was still a part of the committee designing the language, he wanted short-circuiting, even though it was at odds with the strict rules of evaluation elaboration that had been agreed upon. Instead of changing the fundamentals of the language, a new type of coercion, called “proceduring”, was introduced, which would essentially “thunkify” operands, allowing their evaluation elaboration to be delayed. An example from an early report was

op cand = (bool john, proc bool mccarthy) bool: if john then mccarthy else false fi;

Thus a bool as the second operand of cand would be “procedured” into a proc bool, which would be called only if the first operand is true. Eventually proceduring was dropped from the language, because “it complicated the syntax considerably (it is necessary to avoid cycles of proceduring and deproceduring) and it was a pain to implement”. (Source: section 2.3.3.6 in C. H. Lindsey, “A history of ALGOL 68”, History of programming languages—II.)

As in Algol 60, you can use a conditional expression conditional-clause; the if if example is also valid in Algol 68 (if you add a terminating fi). A convenient shorthand notation was introduced, so that

if (x > 0 | a/x < 12 | false) thenfi

is equivalent to the previous form.

11
  • 2
    cand didn't even work. If I recall it correctly, in if a cand (b; c) then ... fi, only c gets procedured. I probably got that from one of Lindsey's documents. What happened to thef though? (Not an operator, an actual part of the syntax) Jun 29, 2021 at 0:14
  • 2
    I assume you're excluding assembly languages? (Either with or without macros...) After all, the usual machine language sequence of instructions for conjunction (or disjunction) that one would naturally write in assembly is short-circuiting ...
    – davidbak
    Jun 29, 2021 at 1:14
  • 1
    @texdr.aft - I have now checked my (book) copy of the Lindsey paper in HOPL II. It's right after the part you quoted. "....pain to implement. Moreover it did not do the job it was intended to do, for in p cand (a:=b; q) it is only q that gets procedured, and a:=b is elaborated whether p is true or not". Jun 29, 2021 at 1:24
  • 1
    Not a candidate, but MDL went even further. It could evaluate both operands in parallel (timeshared) and cancel one if the other determined the outcome. Jun 29, 2021 at 9:43
  • 1
    Do you mean "short-circuiting" as a potential compiler optimization or "short-circuiting" as a required language feature, because those are two different things. Both FORTRAN II and COBOL compilers had the former even in the late 60's. Jun 29, 2021 at 10:13

4 Answers 4

13

My guess is Algol W (1966), from Wirth. Algol W has short-circuit AND and OR operators.

This is my best reference so far: link. I'll see if I can come up with an original description.

In this Stanford tech report - section 6.4.2.2 defines the operators with equivalent if-then-else expressions, explicitly showing that they short-circuit evaluation.

Algol Bulletin 27 - section 27.1.3 - contains an announcement of Algol W.

Wirth was, of course, one of those unhappy about the way things were going with "Algol X", the successor to Algol 60, so he resigned from the working group to follow his own muse. But being there at that time, he'd naturally have been exposed to McCarthy's views on the operators.

2
11

Simula has short-circuiting operators AND THEN and OR ELSE.  But I haven't been able to tell whether it was in Simula 1 (1962), or added in Simula 67.

1
  • Good find - I was thinking that Simula might have short-circuit operators, but had not yet found a reference. Jun 29, 2021 at 12:29
5

Another candidate is MAD, the “Michigan Algorithm Decoder”. According to a 1966 manual,

Object programs will skip the evaluation of the remaining terms of a disjunction (an “or” expression) as soon as one term has the value [true], and a similar statement holds for conjunctions (“and” expressions).

Documentation from 1962 does not mention this, but I find it likely that the behavior was always present, for two reasons:

  1. It's the simplest way to translate boolean expressions—extra work needs to be done if all terms are to be evaluated.
  2. A 1962 paper by the creators of MAD describes a translation scheme that short-circuits, stating that “The algorithm described here is now used in the MAD translator”.
6
  • 1
    I don't know about 'simplest'. Firstly, I assume that one wants p /\ q to be evaluated identically regardless of whether it's the right-hand side of an assignment or the condition in an if statement. Secondly, I assume that one wants p /\ q to be evaluated in the same manner as p x q, namely by evaluating both operands (rather than skipping q if p happens to be zero). So short-circuiting feels like adding special cases to the language. Jul 15 at 20:10
  • 1
    @another-dave Please note that evaluating Boolean expressions in RHS of an assignment follows the same short-circuiting rules, if a language requires short-circuiting. Using your assumptions (what are they informed by?), please write your analog of if p != nullptr && p->next != nullptr && p->next->val == 5 then ...
    – Leo B.
    Jul 16 at 8:25
  • My objection is that most languages expect evaluation of p /\ q to evaluate p and q, especially if p and q are procedure calls. I don't recall the IAL spec, which MAD claims to be related to, but I'm pretty sure Algol 60 would expect both procedures to be called. MAD may be consistent with respect to booleans, but to my eyes it is inconsistent with its other operators. Short-circuit elaboration is very useful, but (as in C) it ought to be distinct from the usual boolean operators. Given only one set of operators, my preference is for the usual ones.. Jul 16 at 13:49
  • FWIW, BLISS does (did?) not have short-circuit operators. One had to write IF P != 0 THEN IF P->NEXT != 0 THEN IF P->NEXT->VAL = 5 THEN ... which is ok until you think about ELSE, but the pain can be alleviated because BLISS is an expression language: write a 'top-level' IF-THEN-ELSE where the condition is itself a conditional expression starting with IF. Note, not real BLISS syntax above, I have forgotten too much. Jul 16 at 13:55
  • @another-dave How are C's short-circuit operators distinct from its "usual boolean operators"?
    – texdr.aft
    Jul 16 at 17:11
4

My recollection is that the Burroughs implementation of ALGOL-60 short-circuited, since it recast "and" and "or" as syntactic elements rather than as operators embedded inside expressions.

In view of the increasingly-hostile tone of SE I regret that I am not investing the time to plough through the manuals.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.