The FIFO is a change

One of my biggest sources of frustration in theoretical informatics.

Apr 04, 2025

Purveyors of C* probably know of its three fundamental primitive data types: bit, void, and fifo. Though the first two are self-explanatory, the third is quite odd, and the wiki’s current treatment does it little justice:

More generally, the bit is “something”, while void is “nothing”, and fifo is a secret third thing currently only valid in the context of transmogrification for the transient transit of data.

So we’re going to talk about what it actually is, what will soon come out of it God willing, and why that matters.

My *eureka* moment happened at D.H. Hill Library and was therefore etched out onto the eraser-friendly marble of the quiet rooms.

For a while I have been transfixed on a couple of ugly things about C*:

the lack of any theory to properly support pointers like the rest of the concrete type system
the sheer ridiculousness of the fifo datatype I had created for transmogrification in the spirit of GBA sound FIFOs

I had said in private a couple of months ago that “the FIFO definitely does not store any data”, and also that it is not a placeholder or representation for code either (ergo, it is a concrete data type). But those certainties were insufficient to make sense of it… until now. What I once called a ‘FIFO’ for lack of a better name is, in fact, a change.

In established programming language theory, there are two kinds of changes: static changes and dynamic changes. However, there is much more of a comprehensive continuum at work, and much of this continuum is expressible in C* thanks to the importation of some choice C keywords that acquire new meaning in the mechanicalist context. In order to effectively show this continuum at work however, we must learn a couple of concepts that arrive with the advent of C*.

Naked calls

C* introduces the notion of naked calls, which make for the same semantics as normal subroutine calls but with no implication about ABI compliance or calling convention. Observe:

/* implies the machine default or compiler-specified calling
 * convention */
void mysub( bit, bit );

/* no calling convention is specified at all! this will almost certainly
 * not compile as-is */
void mysub{ bit, bit };

The curly brace syntax there is actually a shorthand for the more complete (and useful) syntax:

void mysub{ bit, bit }{ };

The second set of curly braces are to contain attributes, a feature we have seen before in the context of structure member definitions. Attributes are, in any context, a curly-brace-enclosed list of string literals that the compiler knows the meaning of so that it may perform deeper semantic handling of the program than is possible imperatively using general-purpose language tools. With data types, this spells things like nontrivial number representations and even fully arbitrary encodings via transmogrification; with changes, this spells calling convention properties decomposed from conventions you have probably heard of before if you have ever written multi-platform C or C++ code.

So what is a pointer, really?

A pointer is a static change. Moreover, a pointer is also understood as a naked subroutine call with no arguments and an unspecified return type that may be specified via its underlying type. These two declarations are synonymous:

bit * mydata;
bit mydata{ void };

This may seem confusing, as it appears to commingle the semantics of data and code. It is not doing that! Rather, it is communicating that a name, mydata, has a bit at some unspecified address that will be resolved by the linker/desymboliser. In the end, mydata is reduced to an integral understood as a memory address, and the rest is detailing how one wishes to access what is behind that address.

Why would anyone want to have these semantics? Consider, for example, a hardware FIFO (I know, bear with me). The way one reads and writes to such a thing does not follow the convention of memory storage; writes may not be reflected upon later reads, ordering in general may be either arbitrarily defined or downright indeterminate, and reading or writing may be unsupported entirely. Also consider hardware registers: on many machines, writing a one clears a bit, which is very counterintuitive. It is in these circumstances that it may be more appropriate to use the naked call syntax. At the end of the day, this should be a carefully thought-out decision made by the system's ABI architect, once and forever.

ANSI C provides the volatile and register keywords as a shortcut to elucidate some of these odd properties of baremetal ABIs. However, they are not comprehensive, and in C* should only be used when they are the best fit for the symbol in question. If a special memory-mapped register is volatile but also has other behaviours besides being volatile, it should not simply be marked as volatile; instead, the symbol should be defined as a dynamic change using the naked call syntax, and then the appropriate attributes can be lobbed onto it detailing its nature precisely.

Enter code

A routine, or subroutine depending on the size of your call stack, or code depending on whether you have a machine at all, is a dynamic change. By the very nature of calling conventions, it rarely suits to have more than one, and therefore the parentheses used to invoke subroutine calls are understood to confer the default calling convention. That said, there may be times where other calling conventions are in use, and wouldn’t it be nice to not have to descend into the muck of assembly to deal with them? This is where the attributes of naked calls pull their heaviest duty.

But attributes can confer many kinds of properties upon symbols. They are mere declarations, after all. Whether or not the sequence of execution is influenced, what memories are modified and how so, what memories can be expected to be free to the callee vs. what memories must be saved and by whom, and what normalisations upon any parameters given or the parameters returned must be made – all of these things come together to define the ABI of a program, and are exposed declaratively to the programmer.

Why does this matter?

It massively bolsters C*’s expressive power for concrete computing systems even more so than it previously was (which, even then, already well outclassed all other known systems programming languages). It is approaching a canonical form for portable baremetal software that must interface with arbitrary hardware interfaces.

More importantly for the long term, it complete’s C*’s previously broken concrete type system. Until the advent of changes in C*, the nature of pointers and the separation of data and code were taken for granted in the language’s design. Like law & order and mechanicalism, the theory of changes will provide a steady stream of new features for C* as mere implications of its workings for quite some time.