Warning: These ideas don’t fit in the head along side those of “normal computer science”. Understanding them may damage you ability to converse with other computer scientists. I speak both languages but not in the same short span of time.

Understanding that the above warning is likely to have the opposite effect from that ostensibly intended — I proceed.

I describe this in concrete terms since the original abstract description led some to conclude that the language could not be implemented. (It has been.) Every type has a textual name in the form of a string which may appear in programs and in this note in bold. All values are of just one type. If <zot> is the name of some type then REF <zot> is the name of another type. A value of type REF <zot> is either NIL or an area of RAM just big enough to hold one value of type <zot>. Values, the name of whose type begins with REF are mutable, unless they are NIL. No other values are mutable. The assignment statement “x := y” is actually an infix operator with a side effect. Assignment is the only source of mutation in Algol 68. The expression x must evaluate to a non NIL value of type REF <zot> and then the expression y must evaluate to a value that may be coerced to type <zot>. The side effect is to make the reference x hold the value y.

When a routine is called and the caller wishes to share with the routine access to a reference which the caller can name, then the compiled code delivers the address of that reference to the compiled routine.

typedef struct(float f, int i) ST;
void xx(ST * w){printf("%e\n", w->f);}
ST st = {3, 4}; //an instance of type ST
Algol 68
PROC xx = (REF ST w)VOID: print((f OF w, newline));
ST st := (3, 4);
In C jargon we say that a pointer or reference was passed to the routine. In the Algol 68 case we say that the address of the reference was passed. The machine code, and thus the semantics are the same.

This is more than quibbling. In Algol 68 the types [10]INT, [10]REF INT, REF[10]INT, REF[10]REF INT are all distinct types and all useful. They closely correspond to the types declared by these C declarations:

typedef const int i[10];
typedef const int *ir[10];
typedef int const *ri[10];
typedef int const *rir[10];

I quote a few brief aphorisms from the Algol 68 Report which defines the language. To avoid headaches and mirth I replace “name” by “cell” and “mode” by “type”.

Every type has a textual name in the form of a string which may appear in programs and in this note in bold. Modes: Each value has an attribute, termed its “type”, which defines how that value relates to other values and which actions may be applied to it.
All values are of just one type. Names: A “cell” is a value which can be “made to refer to” some other value, or which can be “nil” {and then refers to no value}; moreover, for each type beginning with ‘reference to’, there is exactly one nil cell of that type.

While this seems a strange way of speaking, let me argue by analogy that it is standard English, if not standard computer science English. If I see a travel poster containing “Turkey” I may say that the poster refers to Turkey. Note that the poster is immutable—an immutable reference! If I see a black-board with the matrix {{0, 1}, {−1, 0}} I may say that the board refers to one of the Pauli matrices. If I overwrite that with another matrix the board then refers to that other matrix.

The report does not use “reference” to refer to something like a machine address. Instead it uses “cell” to refer to that mutable memory located by the address that others would call a “reference”. {The strings that identify types in the report begin with reference when values of those types are cells. The strings in the programs that name such types begin “REF ”,}

There is a game where pieces of paper are hidden each with a written clue to the whereabouts of the next piece. While you may correctly say that each piece refers to the next it is necessary to say as well that it locates it. The English word “reference” is not normally up to the use that computer science has put it to but I think “pointer” does nicely.

When an assignment statement is executed a cell has been identified by pointer which is the value of the left side expression in the statement, and that cell has thereby been made to refer to the new value from the right side of the statement. It is a bit confusing that the type of a pointer is spelled “REF ...”.

A particular cell is restricted to just one type or set of types established as it is created at run time.


What is a reference to an array of 10 integers (written REF [10]INT in the program)?
It is a cell that can hold (refer to) a sequence of 10 32 bit integers. (32 bit for most current machines; like C, A68 does not commit.) The only thing that it can refer to is such a sequence. You can only assign other such sequences to it. A special hack allows for reification of a sub-cell within, which refers to an integer so that an assignment can be made to an element of the sequence without disturbing the rest. Ditto for fields of a cell referring to a structure. Access to the sub-cell can be included in the arguments to a routine.

What is an array Z of 10 references to integers? (written [10] REF INT in the program)?
It is not 10 consecutive cells in RAM each referring to an integer. It is a general property of arrays that the first and last member is the same as in the array [3, 5, 6, 3]. Our array Z must be able to do this too; to wit Z[0] = Z[3] in which case Z[0] and Z[3] refer to the same cell in which case
Z[0] := 42; print(Z[3]);
must print 42!
This is in the spirit as the C program:

#include <stdio.h>
#include <stdlib.h>
int main(){
int*  Z[4];
{int j=4; while(j--) Z[j] = malloc(4);}
Z[3] = Z[0];
*Z[0] = 42;
printf("%d\n", *Z[3]);
return 0;}
or the Algol 68 program
[]REF INT z = (li, LOC INT, LOC INT, li);
z[1] := 42;
Both programs print 42. In the 2nd program “LOC INT” creates a new cell on the stack for an integer.

From the Algol 68 perspective there is a natural sequence to the types, INT, REF INT, REF REF INT, ...
The corresponding constructs in C are irregular.
ConstrctAlgol 68C
INTIn A68 “INT j = 5” ensures that j will be 5 for the scope of the identifier. #define j 5
const int j = 5;
is short for
int j;
initialized REF INT INT j := 6 which is short for
REF INT j = LOC INT := 6”
int j = 6;

This creates a cell for an integer and makes that cell refer to 7; then creates a cell for a REF INT makes that cell refer to the first cell.
int * j = malloc(sizeof(int));
* j = 4;

A program may commonly have definitions such as “INT j := 5;” and “INT k = 6;”. The type of j will be REF INT due to the ‘:=’, while k’s type will be INT. A simple compiler will put both 5 and 6 on the stack. The 5 will live as long as the stack while the 6 might be replaced by 7 by a statement such as “j := 7”. “k := 7” is rejected by the compiler since the type of the left hand side must begin REF.

In A68 the immutable is basic and the mutable type is a concept derived therefrom. In C the immutable type is derived from the basic concept of the mutable type. Early versions of C lacked the immutable concept.