Images #1
Comments
|
|
|
|
|
|
|
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
{{ message }}
Hi, I'm Eric Fischer, and I'm here to talk about what seems like
a fairly absurd idea: the idea that if-then-else had to be invented.
If-then-else is how we talk about conditions in programming languages:
if something is true, then do a thing, else do a different thing.
That's just English, right? Except that it isn't. I am a native speaker
of English, and I can't use "else" as a conjunction in normal speech,
only in computer programs.
So where did this
elsecome from? No one seems to have written about it.It's too microscopic a detail to have made it
into any books on the history of programming languages.
To understand why programmers talk about conditions the way they do,
I thought it might help to look at how conditional processes were
described before there were computers.
It is actually hard to find good examples of these.
About as close as you can come are surveys and legal procedures
that require you to answer certain questions only if you answered
yes to a different question. But for the alternative cases,
they say "if yes" or "if no," not "else."
And there are mathematical algorithms, like taking a cube root, that
involve some guesswork, and require repeating a step if you guessed wrong.
But algorithms were mostly described in terms of repetition,
not in terms of making decisions, and I haven't found any examples
of "else" being used when they do talk about decisions.
The first computer to be able to automatically perform a different set of instructions
based on the result of a previous calculation seems to have been the Eniac.
In 1946, Haskell Curry and Willa Wyatt wrote a report describing how to
use the Eniac to invert a function and interpolate values.
They used the name "discrimination" for the facility of making a decision
based on which of two numbers was larger.
The Eniac was programmed by connecting wires on plugboards, so
they did not have an instruction called
discriminate.They hadphysical wires connecting the control panel for one instruction
to the control panels of the alternative instructions that could follow it.
Very soon, though, computer programs began to be stored in memory
rather than wired together. In memory, instructions are normally
performed in numeric sequence, one after the other. A few special
instructions can change this sequence by jumping forward or back
to a different point in the sequence, either unconditionally or
only in some particular circumstance.
Here, for example, is the conditional jump instruction from the BINAC, one of
the first commercially produced computers. It checked whether the machine's
accumulator contained a negative number. If it did, it diverted the flow of
control to some specified instruction; otherwise, it let control continue
normally to the next instruction.
This instruction was designed to support a specific usage pattern:
if you wanted to do a thing several times, at the end of each iteration
you subtracted the total number of iterations you wanted to make from
the number of the current iteration. If the
result was negative, that meant you weren't done yet, so you jumped back to do
another round of calculation.
This same idea was carried forward into the first higher-level
programming languages, like Halcombe Laning and Neal Zierler's
language at MIT for Whirlwind. It followed exactly the same paradigm,
except that the numbered steps of the program were evaluations of
algebraic expressions, not single machine instructions.
The first widely used programming language was Fortran, from IBM,
and it generalized this paradigm a little bit. Instead of checking
whether the result of a calculation was negative, its "if" statement
checked whether an expression was negative, zero, or positive, and
jumped to one of three different locations in the program depending
on which it was.
This should theoretically have been more powerful than just checking
for a negative, but was probably actually just more confusing,
because it meant you always had to think about discontinuities in the flow of
control instead of being able to make a clean distinction between the
normal condition in which you continue on to the next step, and the
unusual condition in which case you have to do something different.
One way of making these three-way comparisons a little easier to think
about came from Flow-Matic, a programming language from Remington Rand
for business applications. It was Grace Murray Hopper's project before
COBOL, and many of its concepts were carried forward into COBOL.
In Flow-Matic, instead of looking at the sign of a number, you
said to compare two numbers, and then said where you wanted to jump
if the first number was less than, equal to, or greater than the
second. You still had to think about all of these as jumps in the
flow of control, but the jumps were based on comparisons, not on
arithmetic signs, so they were one step closer to talking about
conditions in a natural way.
That same year, two different national organizations began projects
to develop programming languages that were not tied to one particular
machine from one particular manufacturer. This machine independence
also meant they could try to think about what would be the most
natural way to talk about a process rather than what was the most
straightforward to implement on some particular machine.
The German authors of the "Proposal for a universal language for
the description of computing processes" made two big conceptual leaps
in how their "if" statement was formulated.
First, instead of giving special privilege to the three-way
less-than/equal/greater-than comparison form, their "if" statement
accepted arbitrary boolean expressions. You could calculate and
compare with as much complexity as you needed, including ands and ors,
as long as the final result ended up with a true or false value.
The second big leap was that instead of causing the flow of control
to jump around, their "if" statement caused only a temporary diversion,
just enough to let a series of statements subsidiary to
the condition to be executed. Afterward, whether the expression had
evaluated to true or to false, you would always end up at the
"always" statement at the end of the block, and the only difference
would be whether or not the subsidiary statements had been performed.
This looks almost like "if" as we now know it, including the idea
that there could be multiple ifs in a single block for different
conditions. But it is important to realize that they expected
all of the "ifs" to be evaluated, even if the first one had already
been determined to be true. So if the statements controlled by
the first if changed a variable that the second comparison depended upon,
both blocks of statements might execute.
Their proposal also included another entirely different conditional
form, called "case." It is unrelated to what "case" now means in
programming languages, and instead was another way to write boolean
expressions, with the expressions set apart in a separate section from the statements
they controlled. It appears that the reason to have both forms was
that you could put ifs inside cases, for nested comparisons.
In addition to the boolean expressions they also included a case
called "else," which seems to be the first use of the word in
programming languages. It denoted the case where none of the other
cases were true: the remainder, as they referred to it.
Why did they call it "else?" They don't say.
The best explanation for the word choice may be this note.
We are looking at a document that was originally written in German
and was hastily translated into English by someone whose native language
was not English. A carefully-chosen German word
was probably translated as an archaic English word and then never revisited.
Unfortunately we do not have the original German text to consult.
The other proposal for a machine-neutral programming language
came from the Association for Computing Machinery in the United States.
It took the the idea of controlling statements by boolean expressions a step further:
there wasn't even an "if" keyword; if an expression was followed
by an arrow, then the expression controlled the statements that
followed the arrow.
This form also gets very close to if-then-else as we now know it.
In particular, if you had a series of expressions and the statements
that they controlled on the same line, and one expression had
evaluated to true, all the rest of the expressions on the line
would be short-circuited and skipped. This was just like "else if"
as we use it now, but there was nothing corresponding to "else"
without another if.
The US and German organizations held a joint meeting at a conference
in Switzerland and merged their proposals into a single document
that they called the International Algebraic Language, and would
be subsequently renamed to Algol.
The "if" statement in the combined document came out looking
mostly like the German proposal that had gone in, except that
they eliminated the "always" terminator. This was possible because
they also introduced "begin" and "end" keywords to group statements
into blocks, so if there were multiple statements to be controlled
by an "if," you could put them together into a block instead of
needing the "always" to indicate where the block of controlled
statements ended.
The Algol "if" construction didn't have anything like "else."
Instead, they had a second conditional form called "if either,"
that did have its own "end" statement at the end of a block of
ifs, and used "or if" for what we would now call "else if." Like
the American proposal that had gone in, the "if either" form still
didn't have the idea of an "else" that was not followed by another if.
The next year, the story gets very muddy. There were several papers
presented about Algol at another conference in Paris in 1959, and
one of them is the famous paper where John Backus, who had previously
led the Fortran project, introduced the idea of formal grammars for
programming languages.
As described in his paper, Algol does not have the "if either"
conditional form. Instead, it has another keyword called "converge,"
which causes the top-level ifs within the block to behave like "else
ifs." Was this a proposal for a better "if either," or was it
an earlier draft of what had already become "if either," published
after it was already obsolete? There is no documentation to say
which it was.
In either case, "if either" would not last for much longer.
In 1957, John McCarthy at MIT had written a grant proposal
for a project that eventually became LISP, one of the other
extremely old programming languages that still survives today.
The language he proposed looks nothing like what LISP soon
became, but introduced the idea of the conditional expression,
as opposed to the conditional statement. The important
distinction here is that an expression must always have a value,
no matter what happens, as opposed to a statement which can
simply not happen if the condition that controls it is not true.
So McCarthy's "if function" always contains a clause called "otherwise."
"Otherwise" gives the final value of the expression when none of the
other conditions in the if function have evaluated to true.
This model of conditions inspired Klaus Samelson to clean up
and unify Algol's two separate conditional models at the end
of 1959. He eliminated the entire "if either" form, leaving
only the plain if, but added a clause called "else" that would
be performed when the expression controlling the corresponding "if"
had been false.
You could chain conditions together with "else if," just like
the previous "if either" had allowed with "or if," but you could
also use "else" by itself for a final set of statements that
would run if none of the conditions had been true.
This was the single conditional form that appeared in the Algol 60
report the next year, and is the form that almost all subsequent
programming languages have followed. If-then-else was apparently
not easy for people in 1960 to think about, because the Algol
report spends a page and a half explaining how it works, including
this arrow diagram and the
explation that "else" by itself is equivalent to "else if true then."
As I said at the start, this use of "else" as a conjunction
sounds strange to English speakers, and it did not take
long before some objections to it were raised. One was from
Christopher Strachey, designing the CPL programming language.
CPL was the grandparent of C and therefore the ancestor of
most programming languages in use today. He called "else"
"ignorantly incorrect English" and "egregiously incorrect,"
and wanted to use "test … then … or" instead. But that doesn't
sound very natural either, and it didn't catch on.
The MAD programming language from the University of Michigan
also went its own way. MAD was known
for its extremely long keywords, and in addition to using
"whenever" instead of "if," it used "otherwise" instead of "else"
and "or whenever" instead of "else if."
It is worth nothing the indentation in the MAD manual's example
of how to use "or whenever" and "otherwise." It was years before
most other programming languages adopted this style of indenting
the statements controlled by conditions, even though it now
seems unimaginable to do it any other way.
But even while CPL and MAD shunned the word "else," they kept
the form and only changed the vocabulary. Language designers still search
for the perfect way to write a
forloop, but the quest forthe perfect conditional form seems to have ended in 1959.
Thank you Klaus Samelson, for giving us a tool to think with
and a word to puzzle over.
The text was updated successfully, but these errors were encountered: