#3990 Algol and APL

#3990 Tell me about Algol

ALGOL (short for ALGOrithmic Language) is one of the most influential programming languages in history. While it isn't used for modern application development today, its DNA is present in almost every "curly brace" language you use, from C and C++ to Java and Rust.

Created in the late 1950s by an international committee of European and American computer scientists, it was designed to be a universal, platform-independent language for describing scientific and mathematical algorithms.

1. The Core Versions

The language evolved through three primary iterations:

ALGOL 58: The first draft, originally called IAL (International Algebraic Language). It introduced the idea of a machine-independent language.
ALGOL 60: The "Gold Standard." This version defined what we now consider "structured programming." It became the standard for publishing algorithms in academic journals for over 30 years.
ALGOL 68: A much more complex and ambitious version. It introduced features like user-defined types, parallelism, and a highly formal (though difficult to read) specification language.

2. Technical Innovations

ALGOL introduced several concepts that we now take for granted:

Block Structure & Lexical Scope

Before ALGOL, languages like FORTRAN were largely flat. ALGOL introduced the begin and end keywords (the ancestors of { and }), allowing programmers to group statements into blocks. This enabled lexical scoping, where variables declared inside a block were invisible outside of it.

Backus-Naur Form (BNF)

To describe the syntax of ALGOL 60, John Backus and Peter Naur created a formal notation called BNF. This became the industry standard for defining the grammar of almost every programming language that followed.

Recursion

ALGOL 60 was the first major imperative language to support recursion. This was a radical and controversial addition at the time, famously advocated for by John McCarthy (the creator of Lisp).

3. Notable Quirks & Challenges

Despite its brilliance, ALGOL had some "ivory tower" characteristics that limited its commercial success:

No Standard I/O: The original ALGOL 60 specification had no built-in commands for reading from a keyboard or writing to a screen. Each compiler writer had to invent their own, making programs surprisingly unportable in practice.
Call-by-Name: Unlike modern "call-by-value" or "call-by-reference," ALGOL 60 used a mechanism called call-by-name. This meant an argument was re-evaluated every time it was used in a function. This led to Jensen's Device, a clever (but confusing) trick for passing expressions to procedures.
Stropping: Because many early computers lacked a wide range of characters, keywords were often distinguished by "stropping"—writing them in bold or surrounding them with single quotes (e.g., 'BEGIN').

4. The Legacy: "ALGOL-like" Languages

Even if you never write a line of ALGOL, you are likely writing in an ALGOL-like language. Its direct descendants include:

Language	Relationship to ALGOL
Pascal	Created by Niklaus Wirth as a simplified, "clean" version of ALGOL concepts.
Simula	The first object-oriented language; it was built as an extension of ALGOL 60.
C	Derived from BCPL and B, which were simplified adaptations of ALGOL-style structures.
Ada	A heavily structured language (common in defense/NASA) that draws deeply from ALGOL 68.

The "Man or Boy" Test:
To see if a compiler truly handled ALGOL's recursion and scoping correctly, Donald Knuth devised the "Man or Boy Test." It was a snippet of code so complex that it would break any compiler that didn't perfectly implement the language's specifications.

Given your background with NASA and software safety, would you like to explore how Ada (an ALGOL descendant) evolved to handle Safety and Mission Assurance (S&MA) requirements?

Provide 5 simple examples of Algol used to do something useful

Since the ALGOL 60 standard famously lacked built-in Input/Output (I/O) to keep the language "pure" and machine-independent, these examples focus on the logic and structure of the code. In practice, programmers would use site-specific procedures like print or read.

Here are five examples of ALGOL 60 being used for practical algorithmic tasks.

1. Calculating a Fibonacci Sequence (Recursion)

ALGOL 60 was the first major language to implement recursion in a way that influenced modern computer science.

integer procedure Fibonacci(n);
value n; integer n;
begin
    if n <= 1 then
        Fibonacci := n
    else
        Fibonacci := Fibonacci(n-1) + Fibonacci(n-2)
end;

Significance: This looks remarkably similar to modern C-style languages. It established the standard way we write recursive functions today.

2. Finding the Maximum Value in an Array

This example demonstrates how ALGOL handled arrays and iterative loops using the for statement.

procedure FindMax(A, n, max);
real array A; integer n; real max;
begin
    integer i;
    max := A[1];
    for i := 2 step 1 until n do
        if A[i] > max then
            max := A[i]
end;

Significance: The step X until Y syntax was a very readable way to handle loops, providing more clarity than the assembly-like jumps found in earlier languages.

3. Computing the Sum of an Array (Iterative)

A bread-and-butter task for scientific computing. ALGOL was designed specifically for this kind of mathematical "heavy lifting."

begin
    real array Data[1:100];
    real Total;
    integer i;
    
    Total := 0;
    for i := 1 step 1 until 100 do
        Total := Total + Data[i];
    
    outreal(1, Total);  comment Example of a typical I/O call;
end

Significance: Note the 1:100 array bounds. ALGOL allowed you to define the lower bound of an array, a feature that many modern languages (which force 0-indexing) have actually lost.

4. Jensen’s Device (Summation of a Series)

This is a "useful" trick unique to ALGOL’s Call-by-Name evaluation. It allows you to pass an expression (like $i \times i$ ) into a procedure and have it evaluated repeatedly as the index changes.

real procedure Sum(k, lower, upper, expr);
integer k, lower, upper;
real expr;
begin
    real s;
    s := 0;
    for k := lower step 1 until upper do
        s := s + expr;
    Sum := s
end;

comment Usage to sum i-squared from 1 to 10;
Result := Sum(i, 1, 10, i * i);

Significance: In most languages, i * i would be calculated once before being passed. In ALGOL, the procedure "re-runs" that math for every step of the loop.

5. Quadratic Formula Solver

Because ALGOL was built for mathematicians, it handled complex branching logic for equations very cleanly.

procedure SolveQuadratic(a, b, c);
real a, b, c;
begin
    real disc, x1, x2;
    disc := b*b - 4*a*c;
    
    if disc > 0 then
    begin
        x1 := (-b + sqrt(disc)) / (2*a);
        x2 := (-b - sqrt(disc)) / (2*a);
    end
    else if disc = 0 then
        x1 := -b / (2*a)
    else
        comment No real roots;
end;

Significance: The use of begin and end blocks allowed for clear nested logic, preventing the "spaghetti code" common in languages that relied heavily on GOTO statements.

How ALGOL Lives On

While you likely won't see a .alg file in a modern NASA repo, you’ll see its ghost in Ada. Ada took the strict structure and mathematical "correctness" of ALGOL and hardened it for the Safety and Mission Assurance (S&MA) world.

Would you like to see a comparison of how one of these logic blocks looks in ALGOL versus how it’s implemented in Ada for high-reliability systems?

Did Algol utilize a specialized keyboard?

The answer is a classic "yes and no." While ALGOL didn't have a single, universal specialized keyboard like its contemporary APL (which famously required a dedicated keyboard with Greek and mathematical symbols), its design created a significant "Hardware Gap" that required clever workarounds on the standard keyboards of the 1960s.

Here is how the "ALGOL keyboard problem" was actually solved.

1. The Three Levels of Syntax¹

The creators of ALGOL 60 knew that keyboards in 1960 were limited (mostly upper-case only, few symbols). To solve this, they defined the language in three distinct "syntaxes":²

Publication Syntax: Used in academic papers.³ It featured subscripts, Greek letters ( $\pi$ ), and bold mathematical symbols ( $\leq, \neq, \equiv, \vee, \wedge$ ).
Reference Syntax: The "idealized" version used in the official language report.⁴ It used underlining to mark keywords (e.g., <u>begin</u>).
Hardware (Implementation) Syntax: This was the "real world" version. Since a standard Teletype couldn't do bold or underline, programmers had to adapt the code to whatever their local keyboard allowed.

2. "Stropping": The Keyboard Workaround

Since keyboards couldn't produce the bold or underlined words required for keywords like begin, if, or procedure, programmers used a technique called stropping. Depending on your machine, you would "strop" keywords so the compiler could distinguish them from variables:

Style	Example Code	Common On
Quote Stropping	'BEGIN' X := 1; 'END'	Standard Teletypes
Point Stropping	.BEGIN X := 1; .END	6-bit systems
Upper Stropping	BEGIN x := 1; END	7-bit systems (keywords in caps)

3. Specialized Hardware (The Exceptions)

While most people used standard equipment, there were specific cases where specialized hardware was built for ALGOL:

The Soviet Solution: In the USSR, ALGOL was extremely popular. They developed the GOST 10859 character set, which included almost all the special ALGOL symbols.⁵ They even built specialized card punchers and electric typewriters (like the Consul-260) that featured the specific mathematical symbols from the ALGOL report.⁶
The Burroughs B5000: This was a "native ALGOL" machine.⁷ While it used a relatively standard keyboard, its entire architecture and character set were optimized to handle ALGOL structures directly in hardware.
IBM 2741 Typeballs: Some users of IBM terminals used interchangeable "typeballs" (the "golf balls" from Selectric typewriters). You could swap in a typeball that had mathematical and logical symbols specifically to make ALGOL or APL code look "correct" on the page.

Summary

If you were a programmer in 1965, you likely used a standard ASR-33 Teletype or a punch card machine. You didn't have a specialized keyboard; instead, you spent your time typing single quotes around every keyword ('IF', 'THEN', 'ELSE') and using multi-character substitutions like GE for $\geq$ or NE for $\neq$ .

Would you like to see how these "hardware limitations" led to the creation of ASCII characters like the backslash (\) specifically to support ALGOL?

Tell me about APL

If ALGOL was the "Latin" of programming—structured, formal, and the foundation of modern syntax—then APL (short for A Programming Language) was its "Ancient Greek": beautiful, highly symbolic, and requiring a completely different mindset to read.

Created by Kenneth E. Iverson in the late 1950s, APL didn't start as a computer language at all. It was originally a mathematical notation designed for blackboards to describe data processing algorithms more clearly than standard math.

1. The Keyboard (The "Yes" this time)

In our previous look at ALGOL, we saw how programmers used "stropping" to fake special characters. APL took the opposite approach: it demanded the symbols.

To use APL effectively, you essentially needed a specialized machine. The most famous implementation was on the IBM Selectric terminal. IBM produced a specific typeball (the "golf ball") that replaced standard letters with Greek characters and mathematical symbols like:

⍴ (rho): For the shape or dimensions of an array.
⍳ (iota): For generating a sequence of numbers.
⌽ (phi): For reversing an array.
⍉ (transpose): For flipping a matrix.

Because there were more symbols than keys, programmers used overstriking—typing a character, backspacing, and typing another on top of it. For example, typing a quote ' over a decimal point . created the symbol for "logarithm."

2. "Notation as a Tool of Thought"

Iverson’s philosophy was that a concise notation allows the mind to "chunk" complex operations into single thoughts. In APL, you don't write loops. You describe what you want the entire array to do.

Key Rules:

Everything is an Array: Whether it’s a single number (scalar), a list (vector), or a table (matrix), everything is treated as a multi-dimensional object.
Right-to-Left Evaluation: Unlike standard math (PEMDAS), APL evaluates everything strictly from right to left.
No Precedence: + is not more important than ×. Everything is equal.

3. The "One-Liner" Culture

APL is famous for its "one-liners"—entire programs that fit on a single line that would take 50–100 lines in ALGOL or C.

Example: Generating Prime Numbers up to R

(~R \in R \circ.\times R) / R \leftarrow 1 \downarrow \imath R

\imath R: Generates a list of numbers from 1 to $R$ .
1 \downarrow: Drops the first number (the 1).
R \leftarrow: Saves this list as $R$ .
R \circ.\times R: Creates a multiplication table of all numbers in $R$ .
\in: Checks which numbers in the original $R$ are found in that multiplication table.
\sim: Negates it (finding the ones not in the table—the primes).
/: Filters the list to show only those primes.

4. Why Use It?

While it looks like "line noise" to the uninitiated, APL was incredibly popular in finance, insurance, and scientific research during the 60s and 70s.

High Density: You can see the entire logic of a complex system on one screen.
Speed of Thought: Domain experts (mathematicians and actuaries) could write their own code without needing a "translator" (programmer) to turn their math into nested loops.
Interactive: It was one of the first truly interactive REPL environments.

5. The Modern Legacy

APL didn't die; it evolved. If you use any of the following today, you are using the "grand-children" of APL:

NumPy / Pandas: The vectorized operations in Python are essentially APL concepts translated into readable English.
The J Language: A successor to APL (also by Iverson) that uses standard ASCII characters instead of symbols.
K / Q: Used almost exclusively in high-frequency trading for processing millions of data points per second.

Comparison at a Glance

Feature	ALGOL	APL
Primary Unit	The Statement	The Array
Logic	Loops and If-Then	Transformation of data
Readability	High (English-like)	Low (Symbolic/Hieroglyphic)
Hardware	Standard Keyboard	Custom Typeball/Keyboard

Would you like to see how a specific task—like a weighted moving average for simulation data—looks when written in APL versus a modern language like Python?

From <https://gemini.google.com/app/> Google Gemini 3.0 Pro (Thinking)

Search This Blog

Learning from ChatGPT