Algol – Breaking the sequential flow

Algol was the first real “algorithmic” language, more so than Fortran because the latter contained a lot of structures that we couldn’t consider pleasant, and most of them had to do with what is considered breaking the sequential flow. In early Fortran there were a lot of “jump” statements, either explicitly goto, or thinly veiled as goto (see arithmetic if). In early languages goto (or go to) was often used in place of repetitive statements, either because the programmer was use to jumps (from assembler), mistrusted loops, or just didn’t consider them. Algol used the go to statement and associated labels to break the sequential flow.

Consider the arithmetic sequence, S+1/n/n where S=0 initially, and n takes on a sequence of values 1,…,∞. This can be expressed as:

Of course ∞ makes for a lot of work, so it is easier to stop the process at some point, let’s say 1.6449 (π²/6). Here is an Algol program to perform the task:

This piece of code has two jumps. The first one, which uses the label L1 mimics a loop, repetitively processing the next value of n, until such time as S is greater-than-or-equal-to 1.6449, then the second jump is invoked to label L2, effectively exiting the loop.

Why Algol bested Fortran (for a bit)

Fortran was the first “real” language out of the gate (sorry Lisp), but Algol was hot on its heals, and although Fortran has survived to modern times, for a while there Algol60 provided some good competition for Fortran. Why? The main reason might be that from an algorithmic viewpoint, Algol60 provided better structural features. In the mid 1960s, Fortran66 was the latest version of Fortran. Consider the following piece of code:

   IF (A .LT. B) GO TO 20
   X = Y
   GO TO 30
20 X = 1
   Y = 2
30 A = A + 1

This code still made use of a lot of GO TO statements to mimic the “else” response to a conditional. With Algol60 this evolved into a true if-else conditional.

if A < B then begin
                 X := 1;
                 Y := 2;
              end
         else X := Y;
A := A + 1;

As interest in Algol60 waned (possibly due to IBMs dominance of the language market), its structural concepts were adopted by other languages: Algol68, Pascal, and C. Eventually, even Fortran adopted it in Fortran 77, throwing free the confines of the jump statement.

IF (A .LT. B) THEN
   X = 1
   Y = 2
ELSE
   X = Y
END IF
A = A + 1

A simple programming language

In “The Humble Programmer”, written by Dijkstra in 1972 he made the following statement:

Another lesson we should have learned from the recent past is that development of ‘richer’ or ‘more powerful’ programming languages was a mistake in the sense that these baroque monstrosities, these conglomerations of idiosyncrasies, are really unmanageable both mechanically and mentally.”

And to be honest, he was probably right… but that wasn’t even the worst of it. If he thought Algol 68 was a monster, C++ and Ada would balloon to gargantuan proportions. Have we lost the ability to create simple programming languages? I don’t necessarily mean for the purpose of creating commercial applications – the nature of interaction with hardware, networking etc, makes languages with large scale structure necessary. But along the way we have used these commercial languages to teach novices to program – and it hasn’t really worked.

One of the reasons why students become disengaged with introductory programming courses may be the vast amounts of language knowledge required, on top of learning problem solving skills, and algorithm design. It may be too much for people not use to thinking in a “programming” mode. Learning about language-specific syntax, and memory management, design, testing, blah, blah, blah – it may be overwhelming. Which is surprising, but then those of us who learned programming in the 1980s  learned to program in Pascal, or maybe Fortran. Before languages added things like OO, became “functional”, and masters of everything that a language could be, they were simple – no really they were.

There were languages created specifically for teaching programming. Pascal was one. S-Algol was another (it appeared after Pascal).

Here is a program in S-Algol which performs a Bubble sort:

let n = readi
let x = vector 1::n of 0.0
for i = 1 to n do x(i) := readr
for i = 1 to n-1 do
   for j = 1 to n-i do
      if x(j) > x(j+1) do
      begin
         let temp = x(j)
         x(j) := x(j+1)
         x(j+1) := temp
      end
write "The sorted numbers are 'n'"
for i = 1 to n do write x(i), "'n"?

The structure of this language was very simple. It was from a pre-OO time when the programming world was simpler, happier.

 

Ghosts in the machine: Algol 60

When Algol 60 first appeared, it heralded a new era for programming languages, one which encompassed the idea of “blocks” of code, amongst other things. So why did such a promising language fail? There are likely a number of reasons.

Firstly, Algol 60 had no I/O in the specification. This meant that when Algol was implemented on a particular machine I/O was added, and so the specifications for I/O differed among implementations. Secondly, the 1960s were awash with new programming languages – everyone wanted theirs to be the next “big thing”. It is harder to compete in this sort of an environment. There was also very little time between the release of Algol 60 and beginning work on its successor Algol 68. Algol may have been more successful if effort had been spent on improving Algol 60, rather than creating a whole new language.

Thirdly, and likely the biggest issue was IBM. Algol 60 made some headway in Europe, but never really established itself in North America. Why? IBM’s US domestic installed market share for computer systems was around 71.4% in the 1960s. Its main competitors, Honeywell and Univac held 8.1% and 9.6% of the market respectively [1]. Algol60 was suppose to take over some of Fortran’s territory, but due to IBM’s dominance, this never happened. In fact Fortran so dominated the industry, that even IBM’s other language PL/I (1964) failed to make any headway. On the business side, IBM adopted Cobol in 1962 as its primary development language.

By the time the tide started to turn against Fortran (in the late 1960s), effected by the surge of interest in structured programming, Algol60 had been usurped by Algol68. Algol68 was too complex a language, and other players in the guise of Pascal (and later C) would take over. Pascal was block-oriented, and structured, and would lead the way for programming in the 1970s. By the time S-algol appeared in the late 1970s, it was over for Algol. Which is a pity, because S-algol showed real promise. Here’s a bubblesort in S-algol.

[1] Arnst, C., “Charts show IBM outran others in ’60s”,  Computerworld, Nov.7, p.57 (1977)

The recursive factorial began life as Algorithm 33

When did the first recursive Factorial program appear? As a non-descript piece of code flagged as Algorithm 33 in Communications of the ACM, Volume 4 Issue 2, Feb. 1961. The code is written in Algol 60, as Algol was the first procedural language to allow recursion (i.e. Lisp allowed recursion, but was not a procedural language).

Strangely enough, the algorithm is so overlooked, searching for “Algorithm 33”  in the ACM digital library does not find it… you have to search manually through the issues online.

Evolution of if (iv): Ada and beyond

By 1977, Fortran had likely its greatest metamorphosis from an unstructured, to a quasi-structured language. At the eleventh hour the revision for the F77 standard was modified to reduce the impact of goto statements to match other languages, where its influence was minimal, or even non-existent. The changes made Fortran 77 vastly different from its predecessor, Fortran 66.

Of major importance, was the inclusion of a “block IF“, which took the following form:

IF (E) THEN
...
END IF

The use of THEN as a new keyword allowed a block of statements to be incorporated until the terminating keyword ENDIF was reached. This also solved the dangling else problem. This was augmented by the addition of the keyword ELSE, which allowed for a group of statements to be actioned if the preceding IF is not satisfied.

IF (E) THEN
    ...
ELSE
    ...
ENDIF

By the mid-70s, Fortran was likely coerced into making these changes due to the competition from C and Pascal, both of which offered these conditionals. These new F77 constructs allowed for improved program readability, especially through eliminating the need for statement labels, and goto statements. Here is an example:

IF (K.GT.0) THEN
    POSNUM = POSNUM + 1
ELSE IF (K.LT.0) THEN
    NEGNUM = NEGNUM + 1
ELSE
    ZEROS = ZEROS + 1
ENDIF

The emergence of Ada did nothing to evolve the if statement. Like Pascal and F77, it used a then keyword, borrowed the else-if idea from Algol68, renaming it elsif, and used the same structure terminator endif, as F77. By this stage, if statements had likely evolved as far as they would, and new languages were just selecting appropriate concepts from existing languages.

if C1 then 
    S1 
elsif C2 then 
    S2
elsif Cn then 
    Sn
else 
    S(n+1)
endif;

Fortran 90 would go on to finally make  the arithmetic if  obsolescent. Python would alter very little, adopting the elif of Algol68, and the lack of parentheses.

if x == 0:
    zeroes = zeroes + 1
elif x < 0:
    negnum = negnum + 1
else:
    posnum = posnum + 1

Julia as well uses an amalgam of structural pieces.

if x < 0
    negnum = negnum + 1
elseif x > 0
    posnum = posnum + 1
else
    zeroes = zeroes + 1
end

We are now in the age of mix-and-match, and it is unlikely the if statement will evolve to any great extent.

The evolution of if (iii): Algol68, Pascal and C

The design of the if statement in Algol 60 was likely the pinnacle of its evolution. From here on in every language tweaked its syntax, but there were no major changes. Languages like Algol 68, C, and Pascal all had conditional statements. Algol 68, although having the same name as “Algol” moniker, was a different language altogether.

Whereas Algol 60 required the use of explicit compound statements within an if statement if more than one statement was being controlled, Algol 68 incorporated the use of control structure terminators. For the if statement this meant the use of the reversed keyword fi. Algol 68 still lacked the parentheses of Fortran, but also had no requirements for compound statements, as each section was self-delineated. It had the following general form:

if C then
    ...
else
    ...
fi

This had the added effect of eliminating the dangling-else problem of Algol 60. Algol 68 also added the keyword elif, a short-hand to allow for a series of else-if statements:

if C1 then
    ...
elif C2 then
    ...
elif C3 then
    ...
else
    ...
fi

Here is an example:

if x>0 then
    posNum := posNum + 1;
elif x<0 then
    negNum := negNum + 1;
else
    zeros := zeros + 1;
fi

The if statement of C simplified that of Algol 60, deleting the then clause, and adding parentheses to enclose the conditional statement.  It had the following general form:

if (C) 
    statement1; 
else 
    statement2;

However, similar to Algol 60, groups of statements require the use of compound statements delineated by { }, and C also suffers from the dangling-else problem of Algol 60. Here is an example:

if (x>0)
    posNum := posNum + 1;
else if (x<0)
    negNum := negNum + 1;
else
    zeros := zeros + 1;

Pascal, which arrived at a similar time to C, has a syntax similar to that of C – except its logical expression was bracket-less, and it used the then keyword, like Algol 60. Like Algol 60, it also suffered from the dangling-else problem, and required the use of begin-end delineators for a compound statement.

if C then
    S
else
    S2;

 

The evolution of if (ii): Fortran IV and 66

Fortran did not make any inroads into modifying the if statement until later. Likely spurned on by Algol 60, Fortran IV introduced the logical if statement in 1965. It had the following form:

IF (E) STATEMENT

Where E was a logical expression, using operators of the form .EQ. for =, and .LE. for ≤. The statement was any statement except a DO statement or another logical IF. However unlike Algol 60, there were no compound statements, and no keyword corresponding to else. Both these had to be achieved by means of goto statements. In this sense it almost mimicked an if-else statement. Consider the example below:

    IF (A .LE. 0) GOTO 15
    W = X ** A
    GOTO 20
15  W = 0
20  ...

In this case, if the value of A is less than of equal to zero, the program jumps to statement 15, setting W to 0. Otherwise it calculates W=X**A, and jumps to statement 20. Notice that the Fortran conditional “operators” are stropped by the use of periods, e.g. .EQ.. This was done to avoid potential ambiguity. The expression A LE 0 could also have been interpreted as the variable ALE0. Fortran 66, the first industry standard made no changes to the if statement.

There were a number of differences between Fortran (IV) and Algol (60):

  1. Fortran used mnemonics to represent conditional operator, e.g. .LE., versus Algol’s ≤ (in some implementations <= was used due to the non-availability of ≤)
  2. Fortran uses parentheses, ( ),  to separate the logical expression from the statement, whereas Algol uses the additional keyword then.
  3. Fortran (66) required that each arithmetic statement on either side of a conditional be of the same datatype. This is because A.GT.B was often translated to A-B.GT.0.(This disappeared in F77).

By all accounts, Fortran IV, and 66 were extremely deficient with respect to conditional statements. The next major changes were not to appear until Fortran 77.

Consider code that looked like this in Algol 60:

if k>0 then posNum := posNum + 1
       else if k<0 then negNum := negNum + 1
                   else zeros := zeros + 1

The equivalent in Fortran 66 would be:

    IF (K.GT.0) GOTO 30
    IF (K.LT.0) GOTO 31
    ZEROS = ZEROS + 1
    GOTO 47
30  POSNUM = POSNUM + 1
    GOTO 47
31  NEGNUM = NEGNUM + 1
75  ...

How did if evolve in other languages? Algol 68, C, Pascal?

 

The evolution of if (i): pre-Fortran to Algol 60

Arguably one of the most important control structures to evolve is “if“. Without it, programs couldn’t make any sort of decisions.

Few algorithmic languages, apart from Plankalkül (1948), contained conditional statements. Plankalkül formed conditional statements with the help of a symbol which was an arrow with a period above it, which was used in the following manner:

The left side of the statement, B, signifies the condition (Bedingung) and is an expression with a boolean value, and the right side, a, is an arbitrary statement. If B evaluates to 0 (nein), then the statement ends here, otherwise if B is 1 (ja), then the statement continues with a. There is no “else” statement. Heinz Rutishauser’s Superplan (1949-1951), did not have a decision statement.

Decision statements in programming languages are intrinsically linked to branch instructions in assembler. The first language to use something akin to the modern form of the if statement was likely Fortran I which used an if statement as a form of three-way goto statement.

IF (E) L1, L2, L3

The expression, E is evaluated and one of the alternative paths of L1, L2, and L3 is chosen based on whether  E is negative, zero or positive. This became known as the arithmetic if. This could be used to derive a three-way decision statement of the form:

    IF (X-Y) 10, 10, 30
10  MAXNUM = Y
    GO TO 20
30  MAXNUM = X
20  ...

This says that if X-Y is less than or equal to zero, then the maximum is Y, otherwise the maximum is X. This made sense in the context of unstructured jumps using go to. This allowed for a very limited decision structure, where the expression always had to be expressed in terms of some numeric output.

In 1957-58 John McCarthy, developer of Lisp,  was writing a series of routines for legal chess moves in Fortran which prompted him to invent conditional expressions. He found the arithmetic if construct from Fortran I and II “awkward to use” [McCarthy81], and found it more natural to invent a Fortran function XIF(M,N1,N2) whose value was N1 or N2 based on whether M was zero or not (it was written in machine language). The function was likely not that efficient, as it required all three arguments to be evaluated before XIF() was entered. In Lisp, the conditional took the form of the cond function:

(cond (condition1 result1)
      (condition2 result2)
      ...
      (T resultN))

Later a more “traditional” like conditional operator was included into the specifications for Lisp, and appeared as follows:

X = IF (N .EQ. 0, ICAR(Y), ICDR(Y))

McCarthy suggested the use of this concept in Algol 58 when he was a member of the Algol committee. In the Algol 58 preliminary report the if statement took the form:

if (a>0); c:=a↑2↓×b↑2↓
if (a<0); c:=a↑2↓+b↑2↓
if (a=0); go to bed

Algol 58 did not really progress much, and was superseded by Algol 60. Algol 60 added the keyword then, to separate the logical expression from the statement to be executed. many considered this if-then combination to make the statement more readable. The Algol statement was also extended to include an “else” part. Here is an example of an if-then-else in Algol 60.

if x > 0 then pos := pos + 1 else negzero := negzero + 1

This lead to the ambiguity we know today as the “dangling-else”.  Whereas a statement such as:

if x=0 then if y=0 then m:=m+1

is not ambiguous, the following statement could be:

if x=0 then if y=0 then m:=m+1 else n:=n-1

Is 1 to be subtracted from n when x is non-zero, whatever the value of y, OR when x is zero but y is not? A conundrum.

To further add to the structural space, these if statements were constrained to the control of a single statement, which limited their usefulness. Algol 60 dealt with this through the use of the compound statement it had introduced using the keywords begin and end. For example, a piece of code to swap two numbers if x < y:

if x<y then begin dummy:=x; x:=y; y:=dummy end

Or, written in a more readable manner (many early languages crammed as much as they could on one line – blame punch-cards):

if x<y then 
begin 
    dummy:=x; 
    x:=y; 
    y:=dummy 
end

This structure could also be used to reduce the dangling-else problem:

if x=0 then 
begin
    if y=0 then m:=m+1 else n:=n-1
end

REF(S):

[McCarthy81] McCarthy, J., “LISP Session”, History of Programming Languages, pp.173-197, ACM (1981)

A brief look at the utter madness of Algol 68

People complain about old languages, usually before they even take a deeper look at them. Sure, some are “interesting”, to say the least. Go and read one of the language definitions from the 1960s, they are real eye-openers. Some of the language is quite interesting. Take Algol 68 for instance. Here’s a simple piece of code to calculate Fibonacci numbers:

COMMENT
Algol 68 program to calculate the Sieve of Eratosthenes
for some upper limit N
COMMENT

PROC eratosthenes = (INT n) []INT:
(
    [n]INT sieve;

    FOR i TO UPB sieve DO
        sieve[i] := i
    OD;
    INT k = ENTIER sqrt(n);
    sieve[1] := 0;
    FOR i FROM 2 TO k DO
        IF sieve[i] NE 0 THEN
            FOR j FROM i*i BY i TO n DO
                sieve[j] := 0
            OD
        FI
    OD;
    sieve
);

INT n;
print("Upper limit to calculate sieve? ");
read(n);
print((eratosthenes(n), newline))

If you are only use to looking at C-like code, this might look somewhat obscure, and it does get worse. But to programmers of the time, it probably seemed quite fine. Maybe we have become too complacent.