What was the first programming language, other than Lisp, to have “short-circuiting” Boolean expressions?

Question

(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) then … fi

is equivalent to the previous form.

Answer 1

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.

Answer 2

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.

Answer 3

Atlas Autocode - not an Algol by name, but a very Algol-like language created as a response to the 1958 IAL proposal - had short-circuit evaluation of conditional statements. Although this was a feature of the language from the start, the earliest I can find it mentioned explicitly is in Atlas Autocode Compiler for KDF9 on page 6-1-0 (pdf page 34) where b) iii) states "The conditions are tested from left to right, stopping as soon as sufficient information is obtained to give the overall verdict true or false". According to Tony Brooker and the Atlas Compiler-Compiler, the first AA compiler was written between 1962 and 1963. ("From mid-1962 to mid-1963 Jeff Rohl implemented AA using the Compiler Compiler.") (It is unknown to me if the earlier Manchester Autocodes of the 1950's implemented the same conditional logic.)

Answer 4

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”.

Answer 5

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.