Tag: Computing

In the beginning we had 16-bit integers. £327.67 was still a lot of money and the total amount in a single sale of your shop was unlikely to be more than that. Until it was and you got a negative amount on your sales slip. When the amount was represented in decimal, you still found yourself in for surprises when amounts started to exceed £999.99 or whatever you thought the maximum would be.

How computer systems handle integer overflow, depends very much on the programming language used. Integer BASIC versions usually aborted the program with an overflow error. That sucked, but at least you knew there was something wrong. Many compiled languages on the other hand, silently ignored the error and just wrapped the number around. Compiled C typically ignores the error. Most CPUs do have an overflow flag, so the machine has the possibility to check for overflow and throw an error in this case. But the designers of RISC-V, in all their wisdom, decided to leave out the overflow status flag because C was the only language worth dealing with and nobody ever checked for integer overflow. Of course you can still do it on RISC-V, but it takes multiple instructions.

In some cases, the wrap-around behaviour of integer overflow is actually desired, especially in hash functions or when emulating the behaviour of real hardware. This mostly applies to unsigned integers. The C standard specifies wrap-around behaviour for unsigned integers and (until recently) specified signed integer overflow as undefined behaviour.

Possible Handling

There are many ways to deal with integer overflow:

• Ignore it and wrap around, which is the default behaviour in C.
• Set an integer status bit, which could be checked after every addition and subtraction. Most CPUs, such as x86 and ARM have this.
• Trap the overflow in hardware. Some CPUs, like MIPS, can do this.
• Have a ‘sticky’ overflow status bit. It could be cleared before a computation and could be checked at the end of a computation. If any operation caused overflow, the bit would be set. This is what the exception flags in floating point hardware actually do.
• Use the maximum negative value 0x8000, 0x80000000 or 0x8000000000000000 as a special overflow value. If any of the inputs of an addition or subtraction have this value, or if an overflow occurs, the result is this value. It would be similar to the NaN value for floating point operations.
• Redo the operation with floating point (some versions of BASIC) or arbitrary size integers (Python).
• Throw an exception on integer overflow.
• Panic (abort the program) on integer overflow
• Saturate, i.e. let the result be either the maximum positive value (0x7ffffffff) or the maximum negative value (0x80000000). Some DSPs or SIMD instructions in some general purpose CPUs can do this.

Consequences

If you ignore integer overflow and just wrap around, integer addition retains its associative properties (a+b)+c is equal to a+(b+c). As soon as you start to saturate or trap the overflow condition, the associative property no longer holds. (MAXINT+1)-1 is not equal to MAXINT+(1-1). In the former case the result will be MAXINT-1 (in the case of saturation) or an error condition. In the latter case the result will be MAXINT. Therefore, in some cases, you are saved by not detecting overflow, but this is not something you should be relying on.

One early observation was that (A-B) < 0 is not a reliable way to check A < B. A-B could overflow and you would get the wrong result. For 16-bit signed integers, 30000 – -10000 overflows and gives a negative number, wile of course 30000 > -10000. Most CPUs have dedicated compare and conditional branch instructions that give you the correct result in all cases. The 8080 did not have an overflow flag at all and the 6502 and Z80 had an overflow flag, but no dedicated Branch-if-less-than instruction. You had to do multiple conditional branches to properly test for less-than of signed quantities. The 6809 on the other hand did have a BLT (Branch if less than) instruction, as did the 8086, 68000, ARM and anything more modern.

Computing the average of two integers can fail due to overflow, if done in a straightforward way. There are tricks to make it work under all circumstances. For unsigned integers we have the expression (a&b) + ((a^b)>>1)

Even if the computation itself does not overflow (as it is done in 32-bit on most modern machines), storing the result in a shorter variable (8 or 16 bits) could still overflow. Compilers may or may not add checks for this. For C they typically don’t,

In some cases you have to be very careful to cast the operands to a wider type before doing the operations. For example:

uint32_t a=1000000;
uint32_t b=2000000;
uint64_t c = (uint64_t)a * (uint64_t)b;

If we forget to cast, we do a 32×32 bit multiplication that overflows.

The Zig programming language is very picky about overflow checking. It even checks unsigned operations. If you do want wrap-around behaviour (for example for hash functions), you have to explicitly use operations that wrap around, like ‘+%’ and ‘-%’.

If a multiplication is part of the size computation for an allocation, we could allocate a way too small buffer if the multiplication overflows, which in turn could lead to memory corruption. It is therefore important to detect the overflow in this case. (but in the case of C, this is often not possible).

Avoiding Overflow

Integer overflow can often be avoided by choosing the data types for your computation sufficiently wide and to range-check your inputs.

For example, in a webshop (for consumers), it makes no sense to accept orders of more than 100 of the same item. If you allow the user to type any integer, even 1 billion, and do not check this is within reasonable limits, you could cause an overflow when multiplying it by the item price. If both the item price and the number of items are within a set range, you can prove that the multiplication cannot overflow.

With simple formulas, it is often feasible to assure that no overflow occurs whatever the input values, when the inputs are all within the acceptable range. If you also range-check intermediate values (like the running total of your order), you can prevent overflow from happening and possibly error out with a sensible message, such as “Orders above £10000 are not accepted”.

Dealing with Overflow

If you cannot avoid overflow (or stumble across it despite best efforts), you have to deal with it. It depends entirely on the situation what you should do. If your job is controlling an aircraft, it’s never acceptable to just abort and let the plane drop from the sky. It your job is computing this year’s tax statement, it might be good to abort, so somebody could recompile the program with larger integer types and redo the calculations. If your program contains lots of unsaved user data, you should at least try to save that data before aborting. A spreadsheet may convert the integer values to floating point values and redo the calculation that way.

Maybe the database format needs to be changed and all existing databases converted, because some fixed width fields are now too small to hold values that can occur after all. You should see these things coming in advance so you can plan the conversion ahead. For example the Unix timestamp overflow in 2038.

As with any error handling, there is never one good way that works in all cases.

Last time I talked about garbage collection, a feature that some programming languages have and other don’t. Garbage collection adds runtime overhead, but makes memory management safer. There is also a third way, used by Rust, in which the compiler makes checks at compile time and guarantees memory safety that way, but at the cost of very complex restrictions, hard to grasp by new programmers.

This time I will take about operator overloading. Some people like the feature, but others insist on it being left out of their favourite programming language because it adds unnecessary complexity to the language.

Infix operators

In the mid 1950s, FORTRAN introduced infix operators, complete with precedence rules ( in A+B*C the multiplication between B and C is performed first, before adding the result to A) and parentheses (In A*(B+C), the addition between B and C is performed first, before multiplying the result by A). This infix notation closely follows algebraic formulas used in mathematics for centuries.

Nearly all programming languages adopted infix expressions. Notable exceptions are FORTH (that uses Reverse Polish Notation, like B C + A *) or LISP (that puts the operator first and uses lots of parentheses, like (* A (+ B C))).

Infix expressions were a step up from assembly, where we used to write things like:

ADD T, B, C
MUL T, T, A

Operands in infix expressions can be variables, constants, array elements and function calls. Infix expressions are typically used on the right hand side of an assignment. An assignment statement in FORTRAN may look like:

A = A + COS(PHI) + 2*SIN(B(I))

Where B is an array (indexed by I), A and PHI are variables and COS and SIN are functions.

Operator Overloading

Languages like FORTRAN, BASIC, Pascal and C can use operators on a fixed number of data types, always including integers and real numbers. In Pascal we can use + and * operators for sets, in Basic we can use + to concatenate strings and in C we can use + to add to pointers. Nearly all languages have relational operations like < and > and also Boolean operators like AND and OR. But the types and semantics, as well as the data types that can be used, are hardcoded into the programming language. For example, it is not possible to define a COMPLEX number type and define new infix operators for them, equivalent to what the algebraic operators are for complex numbers in mathematics (some of these languages have COMPLEX data types, but these are then also hardcoded into the language).

Algol-68 was one of the first programming languages to have operator overloading. It could redefine existing operators for new types, it allowed you to add completely new infix operators and you could specify the priorities of any of these operators. This might have been too much flexibility and room for abuse.

Most large programming languages, like Python, C++, Ada and Rust do allow you to overload infix operators, but none of them allows to to add completely new infix operators or to redefine operator priorities.

Benefits

In mathematics, algebraic expressions are not just used with numbers, but for example also with vectors and matrices. Especially for those with knowledge of the problem domain, infix expressions are very readable. A single infix expression with vectors and matrices, can replace a rat’s nest of hard to read function calls. An expression with vectors and matrices is certainly more readable than a loop over the separate array values or two nested loops for matrix multiplication.

Types that are suitable for operator overloading:

• Vectors and matrices, with scalar multiplication, inner product, matrix multiplication and matrix-vector multiplication.
• New numeric types, like arbitrary size integers or complex numbers.
• Sets
• Lists and strings for concatenation (using + operator) and sometimes the * operator for replicating n times.
• Arbitrary algebraic types as mathematicians define them, as long as they can be represented in a computer and operations can be implemented.

Drawbacks

To an unsuspecting reader, an expression with infix operators may look like it’s just adding and multiplying integers (or maybe floating point numbers), while in reality it is doing arbitrarily complex operations on arbitrarily complex data structures.

Sometimes, operators are overloaded to do operations that are totally unrelated to their original meaning, for example the << operation in C++, that was originally “left shift”, but it is used to output something on an output stream.

In some languages, such as C++, you can also overload operations like assignment or array subscripting. This is all fine, as long as you do this to implement sane assignment or subscripting semantics for them, but it gets pretty ugly if you implement totally unrelated functionality for these operators.

In some languages, such as C++, you can also overload operations like assignment or array subscripting. This is all fine, as long as you do this to implement sane assignment or subscripting semantics for them, but it gets pretty ugly if you implement totally unrelated functionality for these operators.

Even in cases where it does make sense to overload, there are some drawbacks:

• It is not always clear what an overloaded operator will do. For example: is the ‘*’ operator between matrices doing matrix multiplication or component-wise multiplication instead?
• Overloaded operators and the function calls that the compiler invokes for these operations, may in many cases not be the optimal way to perform a task. Dedicated function calls for a specific task may run more efficiently.

What Some Languages Do

Three “small” languages that aim to replace C, chose different solutions:

• Zig does not have operator overloading. It has some infix operations on vectors though.
• Odin does not have operator overloading, but it has many operations on vectors, matrices, complex numbers and even quaternions. AFAIK, this is the only language that has quaternions as a built-in type.
• C3 does allow operator overloading. The documentation contains a plea to use it only in useful ways, but that might not help too much.

Many computer programs require more memory as the size of the data increases. For example, a spreadsheet uses more RAM if the sheet contains more columns and rows. If you delete a row or column of the spreadsheet, the RAM used by it should be freed, so it can be reused later if new rows or columns get added to it. If you delete parts of a spreadsheet and the RAM does not get freed, the program will keep using more and more RAM as you delete cells and later add new cells, even if the total size of the spreadsheet does not increase. This is called a memory leak. The longer you use the program, the more RAM it will use, until it requires more RAM than is available and the program crashes.

Many programs require the capability to dynamically allocate memory. Support in programming language varies. Most versions of BASIC do not allow you to allocate entirely new objects and arrays cannot be resized. However, strings can be of variable length, so you use way more memory if you have long strings in a string array, compared to the situation where all strings are null strings. In Python on the other hand, you can dynamically resize lists and even store new lists inside lists.

Allocation

Memory is allocated on what we mostly call the “heap”. A memory address range is reserved for the heap. When a program needs more RAM, it calls an operating system function to allocate a large chunk of memory in that address range. When that memory fills up and still more memory is needed, another system call is made to add more memory to the heap. Within that address range, the runtime library manages the blocks that are free and that are allocated. Free blocks are on a free list. When an allocation function is called, a free block is taken from the free list. When the free block was (much) larger than the amount of memory requested, the block is split. The used part is allocated and the unused part is put back on the free list. When an allocated block is freed, it is put on the free list again. If the freed block is next to another free block, these two blocks are usually merged into a single larger free block.

Even if we do everything right and free each block as soon as it is no longer in use, the heap may get fragmented. The total amount of free space may be large enough, but the free space may consist of many small blocks with allocated blocks in between.

Also an allocation may take much longer if a long free list must be traversed before a suitable block is found.

Some languages, like Zig allow you to specify which allocator you want to use in which situation, so you can have an allocator that is more suitable for a specific application.

Garbage Collection.

If you delete an object (for example a list) in Python, the Python interpreter itself takes care to free that memory. Take the following code fragment:

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b = a
a = None
b = None

The first line allocates memory for a list of 10 numbers. The variable a stores a reference to that list. The second line causes variable b to store a reference to the same list. The list is not copied: it’s the same list in the same memory. The third line causes the variable a to no longer refer to the list. But the list is still accessible through variable b, so it cannot be freed. The fourth line causes variable b to no longer refer to that list. Now it becomes unreferenced and it can be freed.

Earlier versions of Python used a reference count in each object. Line 1 would give the list reference count 1 (only one reference from variable a). Line 2 would increase the reference count to 2, line 3 would decrement it to 1 and line 4 would decrement it to 0, in which case it was time to free the memory. This is comparatively simple, but it would not work in case cyclic references exists. Lists can store references to other list (or even to the same list). Take for example the following Python fragment:

a = [1, 2, 3, 4, 5]
b = [10, a]
a[4] = b
a = None
b = None

The first three lines create a pair of lists that contain references to each other. List b has two elements: the number 10 and (a reference to) list a. List a has five elements: the numbers 1 through 4 and a reference to list b. Even when the variables are reassigned, the references inside the two lists remain valid and the reference counts will not decrease to 0. Both lists will be inaccessible though, as there are no other references from outside. Therefore, modern versions have a true garbage collector (in addition to the reference counting), to free up memory in situations like this.

A garbage collector performs the following job:

• It starts from all variables that contain references to objects. Those objects are marked.
• For all marked objects, check which other objects are referenced from them. If they are not already marked, mark them and repeat the operation for the newly marked objects.
• Free all allocated objects that are not marked.
• Remove the marking from the marked objects.

The job of a garbage collector is very complex. It uses much CPU power and while it is marking all dynamic objects that are still reachable, all operations of the program must be paused. This is unacceptable for hard real-time systems. If the program is supposed to react within 5 ms, we cannot accept that the program is frozen for 500 ms during garbage collection. In general you have no control when the garbage collector will kick in and when a large chunk of memory will actually be freed.

Languages like Python, Lisp, Java and Go have a garbage collector. Of all these, Go is a truly compiled language and its garbage collector is state of the art and aims to reduce the duration of any pauses in the program.

Manual Free

C is on the other extreme. See the following code snippet:

int *a = malloc(10 * sizeof(int));
int *b = a;
if (a == NULL) return -1;
...
free(a);

In the first line, we call the malloc function to allocate a chunk of memory for an array of 10 integers. We have to calculate the size manually: multiply 10 (the number of integers we want) by the size of one integer. Of course we have to check that the returned pointer is non-null.

The variable b points to the exact same array.

At the end of the program, we free the memory again. If we forget to free, we create a memory leak, if we free too soon, some pointers may still point to it, while the data in that memory range is no longer valid; the runtime system may have reused it for completely different purposes. If we call free(a), we may set a to the NULL pointer to prevent it from being used to access the array, but we may have forgotten about pointer b, which still points to the same memory.

Manual free leaves room for a lot of bugs that would be prevented by using garbage collection.

C,Pascal and Zig use manual free. C++ has this too, but it also has managed data types that take care of allocation and freeing internally.

Rust

And then of course we have Rust. Rust has no garbage collector, but it severely restricts how pointers (references) may be passed around. A dynamically allocated object always has one “owner”, which will be responsible for freeing it. References to objects can be “borrowed” by other functions, in which case they are temporarily unavailable to the owner. This is all checked by the compiler. The compiler knows when an object can be freed and it takes care to call free when appropriate, so you don’t have to do this explicitly.

Due to the restrictions that Rust puts on copying of pointers, it is not really possible to have data structures with cyclic references either.

The advantages of Rust:

• You don’t have a garbage collector with the runtime overhead and nondeterministic timing.
• You get memory safety with respect to freed dynamic memory. No use after free or double free and no memory leaks.
• Rust also makes sure that in a multithreaded environment, only one thread gets access to any given object at the same time (multiple readers are okay, but a writer needs truly exclusive access)..

Disadvantages of Rust:

• Some data structures, consisting of nodes linked by pointers, are impossible to create.
• Semantics of ownership and of the borrow checker are extremely complex. Getting a program compiled at all, can be a frustrating experience for beginners.

C was developed in 1972 by Brian Kernighan and Dennis Ritchie as a systems programming language to implement the Unix operating system. It was based on B, which was in turn based on BCPL, which was in tern based in CPL, a very full-featured programming language. B was the most minimalist of the series: it had only one data type, serving both as integer and as pointer (and as a sequence of characters) C added new data types to it, like separate char, short, int and long, plus pointers. Structures ware added very soon..C became very popular in the 1980s, eventually overtaking Pascal.

What’s Wrong

There are a lot of things wrong with C. They have been discussed at nauseam already, so I won’t go deep here. Here are a few of my favourites:

• Syntactic pitfalls, for example a stray semicolon after if or while, making the next statement separate from the conditional statement, even though it looks like it is controlled by it. There is also fall-trhough in switch statements and the dreaded single ‘=’ in a conditional where ‘==’ was intended. Even if you know to be careful with these, one in a thousand times your attention slips and a new bug is born.
• Null-terminated strings might have been a good idea in the 1970s, when every byte counted, nowadays they are a bug magnet. It is not easy to find the length of a string, therefore it is not easy to ensure that a string will fit the buffer allocated to it. For example, before uyou call a function like ‘strcat’, you need two calls to ‘strlen’ to determine the lengths of the two inputs. You need to add them and add one for the terminating null byte, before you can compare it to the size of the destination buffer.
• When an array is passed as a parameter to a function, no information about its length is automatically passed with it. From the point of view of the called function, it is just a pointer. We say that arrays decay into pointers. If you want to pass the array length to a function, it has to be done in a separate parameter. Both the caller and the called function have to do the right thing to make it work,
• Macros are very error-prone, in particular function-like macros. You always need to surround the parameters with parentheses and put the resulting expression in parentheses as well. The resulting expression has to look like a single (parenthesised) expression or as a do-while statement. C macros are not Turing-complete (which may be a good thing after all) as conditional evaluation cannot occur during expansion of a macro. There’s always m4 if you want this kind of flexibility.
• Header files are there only by convention, the language itself has no clear idea about module interfaces and modules. We end up using external tools to sort out the dependencies between object files and header files or editing Makefiles manually.

And we are lucky that in C89 (the first ANSI standard), the full parameter list is part of the function prototype (its declaration in the header). In earlier versions this was not the case. Your header only specified the name and the return type of a function. For example, a function that took one integer as a a parameter, could be called with two floats and a pointer as parameters instead. The compiler had no way of knowing that the function was called in the wrong way, as it only looked at one source file at a time. A separate program called ‘lint’ was there to find inconsistencies like that.

What’s Good

There are a lot of good things in C:

• C lets you do low level things, hat standard Pascal does not allow. C lets you cast any integer to a pointer and then access memory via that pointer. C lets you do pointer arithmetic. C lets you do bitwise ‘and’ and ‘or’, which is not standard in Pascal. C lets you implement a function like ‘malloc’ in C itself.
• C does not restrict you to use arrays of all the same size if you want to pass them as parameters to a function.
• As opposed to early standards of Pascal, C lets you compile parts of your program separately and it lets you reference functions in other parts via header files. It’s lower level than true modules, but it can be done.
• Any C function that you can use, can be implemented in the language itself. Compare that to Pascal, where you cannot implement functions like ‘read’ and ‘write’ as they take a variable number of parameters. On top of that, write has the special formatting syntax using the colon character. The C standard library is clearly separate from the language itself and it can be completely implemented in C.
• C is low level, so it does not require an extensive runtime library. C on an embedded system, only requires a small initialisation routine. You can run C programs (without most of the standard library functions) on a bare metal system with no operating system.
• C control structures are flexible, compared to Pascal. You can terminate functions early with ‘return’ and terminate loops early with ‘break’. This helps avoid excessive nesting, stupid additional Booleans and ‘goto’ statements.
• It is usually easy to inspect the machine code generated by the compiler and compare it with the C source code.
• A lot of libraries are written in C.
• C compilers are available for every platform under the sun.

C Alternatives

Many alternatives exist to C.

First the big languages:

• C++ is a superset of C. It has objects and inheritance, it has operator overloading and exceptions. Modern C++ adds smart pointers (that have a single owner at any given time, like in Rust) and it has convenient data types, defined by STL, that ‘just work’. It is a highly complex language. And because it is a superset of C, the dirty pitfalls are still there. You can still do manual allocation with ‘malloc’. Because of that, it can be harder to know what’s the right thing to do for any given data type. C++ does not have a garbage collector. If you leaned C++ in the 1990s, you will be amazed of what has been added to the language during the past decades.
• Go does have a garbage collector and it also has parallelism built-in. It was originally developed by Google. See https://go.dev, t is the ideal language for multi-threaded servers. Go aims to be a safe language, where simple mistakes cannot lead to memory corruption.
• Rust on the other hand avoids the garbage collector, but instead it uses an ownership model for each dynamically allocated object. At any given time, one piece of the program owns the object. References can be borrowed by other functions. Rust is not a truly object-oriented language with inheritance, but most of the benefits can be had with interfaces, that are called ‘traits’ in Rust. There are no exceptions, but the language helps you to handle error returns at each function call level. See https://rust-lang.org. Like Go, Rust aims to be a safe language.
• D. is an extremely feature-rich language (including an optional garbage collector). It has many high-level constructs, but as opposed to Python, it is still statically typed and still truly compiled. And it is mostly C-like syntax. See https://dlang.org

There are also smaller languages that want to stay closer to the true spirit of C. They want to fix some of the flaws of C, without introducing highly complex features like garbage collection, multiple inheritance, exceptions or parallel execution.. Some of these are single-developer projects, therefore they have no large communities around them. Some developers are very firm about features that will never be part of their languages, like inheritance, operator overloading, exceptions or macros. These languages do tend to have explicit allocation, a ‘defer’ statement (specify that something must be done whenever leaving a scope) and array slices. Some of these languages are:

• Zig has no macros, but it has compile-time execution instead. Learn one language and program the build system, generics and everything else. Memory allocators are explicit, error handling is explicit and integer overflow is checked by default. It can directly include C headers to call C functions. See https://ziglang.org
• Odin is another language at roughly the same level. Like in GO, there is no ‘while’ keyword and the ‘for’ loop allows you to just specify the terminating condition, so it behaves exactly like ‘while’ in C. Odin does not have any methods and a limited form of polymorphism. Map types (hash tables) are part of the language itself. See https:://odin-lang.org
• C3 has operator overloading and it has a macro system that closely matches the desired use cases. It has explicit error handling using an ‘Optional’ type. It supports contracts (assertion checking). C3 has a very C-like syntax, but it has capitalisation rules to distinguish type names, constant names and other names (this to simplify parsing). See https://c3lang.org

None of these smaller languages are going to displace C in the near future. Of the bigger languages mentioned, C++ is extremely widespread for large applications and Rust is taking over some of the code in the Linux kernel and system utilities, that were originally programmed in C.

When I started my study at the Eindhoven University of Technology, most computing was done on a Burroughs B7900 mainframe, that used Burroughs Extended Algol as its system programming language. We were taught Pascal though, but older students still wrote programs in Algol, that had fewer restrictions than Pascal and had a complex data type (complex numbers) too.

Algol-60

Algol started originally in 1958, mostly as a language to publish algorithms in (for example in scientific papers). Algol-60 became the version that was most popular and that everyone thinks of when you refer to Algol.

Algol had block structures for IF-THEN-ELSE and FOR-loops (but no simple while loop) and it had procedures with local variables and parameters. These procedures could be recursive, as opposed to the ones in FORTRAN.

Algol-60 had a few limitations though:

• In had only three data types: INTEGER, REAL and BOOLEAN, plus arrays of these. There was no character data type and there were no records or pointers. There was something as a string data type, but the only thing you could do was pass literal strings around to a function that would print them. There was no way to manipulate character strings.
• It defined no standard I/O functions, so this was not portable in any way.
• Like Pascal, it offered no modularity. A program was a standalone entity. But the order in which you declared variables and procedures was less rigid than that of Pascal.
• The set of control structures was very limited, keeping the evil GOTO statement necessary.
• But the biggest drawback was the call-by-name convention. In most languages, such as Pascal, you either pass parameters to a procedure by value (it is an input parameter to the procedure) or by reference (the procedure is allowed to modify whatever variable you pass to it). In Algol-60 you had the choice between pass by value and pass by name. Pass by name meant that the expression passed as an actual parameter, had to be re-evaluated each time it was used inside the procedure. For simple variables this made no difference, but for an array element, the expression that specified the index could depend on variables that were modified inside the called procedure. This was inefficient to implement, requiring mini-subroutines for each of the pass-by-name parameters. These had to be provided by the caller, so the called procedure could call them back. It was also very hard to analyse programs that used it in a nontriviial way. You could do really clever things with it though. Call by name was more of an unintended ramification of a definition than the desired behaviour of the language.

Burroughs Extended Algol was a full-fledged system programming language with all the data types you would want. The mainframe operating system was written in it and the language was very much extended compared to Algol-60. And as far as I know, they left out pass by name and implemented pass by reference instead.

Algol-68

Algol-68 was very much different from Algol-60. You cannot meaningfully consider these mere versions of the same language.

For one thing, it ditched call-by-name and replaced it with pass-by-reference. It added many more data types:

• Characters and strings.
• structs and unions. The keywords struct and union were carried over to the C language, along with the keyword void, meaning no value.
• References (which were pointers). There was dynamic allocation on the heap too.
• Complex numbers
• Flexible arrays.
• semaphores, to be used with parallel statements.

It had a very versatile slicing syntax for arrays and (unlike Python), it also supported multi-dimensional arrays.

It had versatile control structures, including one for parallel execution, an extensive standard I/O library and special syntax for formatted I/O. And you could also overload operators, define entirely new operators and specify the priority of each operator. C++, Ada and Python also have operator overloading, but none of them allows you to change operator priorities.

But Algol-68 still had no modules and separate compilation. A program was still a single source text.

The syntax and semantics of Algol-68 were complex and very few implementations existed at the time. Full implementations were even rarer. At the university we had books about the language, but no working compiler. We only got an open-source implementation for Linux in 2005 with Algol-68 Genie https://jmvdveer.home.xs4all.nl/en.algol-68-genie.html

Some features of the language were hard to implement. The language required garbage collection for objects allocated on the heap and parallel execution was its own can of worms.

The biggest stumbling block, however, was the grammar of the language. Other languages are specified by context-free grammars, in particular in the Backus-Naur Form (https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form). These grammars are easy to comprehend and there are tools to help create parsers for them.

The drawback of context-free grammars is that they do not accurately specify what programs are legal. The context-free grammar specifies fore example that an expression can contain an identifier (variable name) consisting of letters and digits, starting with a letter, but it does not specify that a variable with that name must be declared earlier in the program.

The grammar of Algol-68 on the other hand, does specify exactly which programs are legal. The grammar contains two levels: at one level you specify what production rules you can create and at another level you specify what programs you can create using those production rules you just created. A context-free grammar has just one static set of production rules to create a program. Algol-68 has a customised set of production rules for every set of variables and procedures you declare.

Algol-68 is not particularly hard to comprehend per se, nor is it particularly hard to parse (compared with other complex languages like C++ and Ada), but comprehending the specification and using the two-level grammar to base a parser on, that is very hard indeed.

That stupid octal dump program in Unix, that’s the reason why in Bourne shell, the “do” loops are terminated with “done” instead of “od”. The “if”-statements are terminated with “fi” and “case” statements with “esac”. those keywords come directly from the Algol-68 control structures. “od” terminates loops in Algol-68, but that would conflict with the name of the octal dump program, so it was not practical to use that as a keyword in the shell.