11

(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 at 0:14
  • 1
    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 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 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 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 at 10:13
10

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
8

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 at 12:29
0

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.