The Cell

I have had an itch to write this for at least 20 years and I can no longer resist. I have little hope of changing how people describe language semantics but I think that it bears on why this remains difficult for many readers.

When I began to study Algol68 their distinction between an integer and a place to store an integer was not immediately clear. When I understood there was no going back and the description of every other language became awkward to me and remains so today. I know of no other language that incorporates this distinction so thoroughly. Algol68 has a conventional type theory for values but to that they add for every type X, REF X which was the type of a place to store a value of type X. This is in contrast to C’s afterthought const. (I may need to show that that is not as powerful.) Instead of C’s lvalues Algol68 required that an assignment have an expression of type REF X on the left of := and of type X on its right.

REF INT” was the Algol68’s syntax for the type of a cell for an integer, or integer cell. Otherwise I will not recount Algol68’s terminology for that may have been part of the reason that few know of the ideas today. C supports *x = 3 as well as x = 3 and must explain them separately . The type REF INT serves as the type of a pointer to an integer.

Algol68 supported the idea of an array of cells for integers as distinct from a cell for an array of integers. Which notion should supply the function of the Fortran integer array? For various reasons the cell holding an array of constant integers was necessary. That sounds immutable except that the definition includes “cell” which means mutable. Algol68 allowed the syntax x[4] where x was a cell with an immutable array of ints and the expression yield a reference to an integer, assignment to which magically replaced the immutable array of ints with a different immutable array of ints. Compilers had to understand and implement this magic efficiently. I could pass x[4] as an argument to a function needing a cell, into which to store. This conceptual hack made this plan feasible. OCaml comes close to following this path except they failed to understand the Algol68 magic, or thought that their users would be unable to. OCaml has immutable integers but lacks immutable arrays of integers.

Syntactic sugar allows most Algol68 program text to look like conventional Algol. If “x” is a reference to a cell with an integer and “x” appears in a context that needs an integer then the compiler will comply and fetch the integer from the cell. The compiled code was quite conventional.

The problem, I think, is that conventional semantics for almost all languages start with a variable version of the value and then sporadically note that here and there you cannot modify that variable. Variable values come first and the constant version is parasitic and explained later. In Algol68 the constant values come first and then the cell is introduced as a place to store different constants at different times. You cannot modify 3. Early Fortrans allowed that and it was a famous bug.

Bliss was a precursor to Algol68 and got some or all of this right.