Monday, January 24, 2011

A bit of history

The computers of the 50s were very primitive machines. The IBM 704, for example, had 4096 words of ferrite core memory (later expandable up to 32768 words) with an access time of 17 milliseconds. The Central Processing Unit, which was not a monolithic silicon chip, but a cabinet full of vacuum tubes, could execute 40 thousand instructions per second (twenty-five microsecond basic execution cycle).

It cost \$50,000 a month just to rent one. (That's more than \$4 million a year in today's dollars). And this was one of the most advanced machines available at the time. These days, the level 1 cache control would put this kind of power to shame.

The computer languages at the time were bizarre to say the least. Of course no one at all had any experience programming, let alone designing languages to make programming easier. The conventional wisdom at the time was that ‘information processing’ required an approach that differed fundamentally from ‘numeric calculation,’ so people tried out all sorts of weird ideas. One idea was string processing. The COMIT language was one of the earliest string processing languages that was based around the idea of rewrite rules. It is sort of like `sed` on acid:
```(8             PROGRAM TO BRING IN A NUMBER OF CONSTITUENTS AND PRINT OUT-
ALL OF THE N FACTORIAL PERMUTATIONS OF THEM)

INPUT                                \$ = Q + 1 + N       //*RSA1              INPUT
*                                    N = QL + QR/.1                               *
NUMBER Q + \$ + \$1 +  QL +  \$ + QR  + N = 1 + 2 + 4 + 3 + 5 + 7/.*6 + 6/.I1   NUMBER
*              Q + QL + \$ + N + \$ + QR = 3 + 2 + 6/.1 + 4 + 5                     *
PRINT                          \$1 + QL = 2 + 1          //*WAB2               PRINT
*                 QL + \$ + \$1 + QR + N = 2 + Q + 3 + 1 + 5 + 4                    *
PERMUTE \$1 + Q + \$1 + \$ + QL + \$ + QR + N = 3 + 2 + 4 + 1 + 5 + 6 + 7 + 8/.D1     *
TEST               QL + \$ + QR + \$/.G0 = 1 + 3 + 2 + 4                       NUMBER
MOVE               \$1 + Q + \$ + QR + 1 = 2 + 1 + 3 + 5 + 4                  PERMUTE
```
Yngve, Victor H. 1958. “A programming language for mechanical translation.” Mechanical Translation 5 (1). 25-41

The information processing language, IPL, on the other hand is more like assembly code with linked list support:
```            COMMENTS                TYPE  NAME  PQ  SYMB   LINK

Type-9 card                          9
1
Type-2 cards define regions.         2     A                1
The B-Region consists of             2     B                1
one cell, named "B0" or just "B".   2     I                1
2     L                2
The R-region has 2 cells,            2     R                2
named "R0" and "R1".                2     v                1
2     (                1
2     )                1
Type-1 cards are for comments.       1
1
Type-5, Q=1 says "DATA FOLLOWS."     5           1

L1---(AI(A v B))                          LI        0
(
A
I
(
A
v
B
)
)        0

Type-5, Q=blank says "ROUTINES       5
FOLLOW."                            1
1
R1 prints the list L1.               1
1
Q=3 says "TRACE THIS ROUTINE."            R1     13 L1
J151    0

P or Q = 0 can be left blank.

Type-5, SYMB=R1 says execute R1      5              R1
```
Correspondence between Hugh S. Kelley and Chuck Baker.

These languages differ from INTERCAL in that their designers were serious.

A notable exception was the language ALGOL.
```begin integer i; real y; real array a[0:10];
real procedure f(t); real t; value t;
f := sqrt(abs(t)) + 5*t^3;
for i := 0 step 1 until 10 do read(a[i]);
for i := 10 step -1 until 0 do
begin y := f(a[i]);
if y > 400 then write(i, "TOO LARGE")
else write(i,y);
end
end```
(taken from Wikipedia article on the Trabb Pardo-Knuth algorithm)

ALGOL doesn't look unusual to the modern eye. That in itself is testimony to the fact that ALGOL was years ahead of its time. As you can imagine, though, it was well beyond the capability of most computers to compile and run an ALGOL program.

When McCarthy started the “Advice Taker” project, he proposed a new language LISP that would be based around the linked-list paradigm of IPL and the λ-calculus of Alonzo Church. One of the goals of the language was to deliberately move away from the Turing-inspired mechanistic model of computation (Turing machine) and towards a more mathematical way of programming based upon recursion. (Incidentally, ALGOL was designed to support recursion, but the very first ALGOL implementations punted because it was too complicated to support and users didn't know how to use it.)

John Cowan said...

As Dijkstra said, Algol 60 was a great improvement on most of its successors.

Ruben Berenguel said...

Is it just me or algol looks a little like C code with Pyton-style indentation?

Cheers,

Ruben

Anonymous said...

Algol 60 is a fantastic language. What a shame they create the ugly successor, Algol 68 :-(