I like weird machines. Bonus points if they are small, or fast, or extra weird.

The next post walks through the actual turing machine I make out of this insane little sum function, so if you want less backstory and more code, skip over to that page.

The origin of this (mis)adventure in turing machine silliness stems from messing around with assignment statements. Namely, C has some interesting behavior regarding the return values of assignment statements:

int i = 0
printf("%s", (i = 2))

This prints 2. Why? Well, in C, the result of an assignment statement is the state of the left-hand operand after the assignment. Now, naturally, my first idea was that I could use this in a for loop to make some cool behavior:

for(int i = (printf("init ")*0); i<(printf("cond ")*0)+5; i += (printf("inc\n")*0)+1);

This not only compiles, but it prints the following:

init cond inc
cond inc
cond inc
cond inc
cond inc
cond

What’s going on here? One step at a time:

The loop init part multiplies the return value of printf (an int), with zero, assigning zero to i while still calling printf each time.

int i = (printf("init ")*0);

The loop condition section prints cond, multiplies that by zero, and adds five. This resolves to i<5 as the loop condition, but still calls printf("cond ") every time it checks.

i<(printf("cond ")*0)+5;

The loop increment block does the same thing, this time using += to increase the counter i by one after running the printf("inc\n").

i += (printf("inc\n")*0)+1

Needless to say, once you understand how return behavior works, this example is trivial. But we can do some fun stuff with this.

Let’s try a simple function that sums all the items in an array of integers, but in two lines of body (I’ve separated each part of the loop for ease of reading):

int sum(int a[], int len) {
    for(
        a[0] = ((a[1] += a[0])*0)+1;
        ++a[0] < len;
        a[1] += a[a[0]]
    );
    return a[1];
}

This routine is flawed, however. In order to make use of a counter and iterate over the array, we need to clear a[0] and use it. We add its previous value to a[1] beforehand, so the sum is still valid, but we run into a problem:

int main()
{
    int a[] = {1, 2, 3, 4, 5};
    const int a_len = 5;

    printf("Sum Result: %d\n", sum(a, a_len));
    printf("After Sum: %d\n", a[1]);

    return 0;
}

This outputs the following:

Sum Result: 15
After Sum: 15

As you can see, this is not optimal. Since C passes the address of the array, and not a copy of it, we actually modify the source array. Our original data is not intact! There are a few ways of combatting this. The first thing that came to mind is to do some algebra with the values in a[0] and a[1], but that’d be too easy of a solution. Besides, I want to take this up to eleven. Let’s make our own memory space to work using malloc instead:

for(
    int *m = (int *)malloc(sizeof(int)*2);
    ++m[0] < len;
    m[1] += a[m[0]]
);

People familiar with malloc() will already see a major problem: We have no way to zero out m at the beginning, and we have no way of getting m out of the loop. This is just one of the two lines I’m allowing myself to use (we could do more shenanagins in the return statement), but there’s already some severe problems. To remedy the first problem, we can (fortunately) just switch to calloc():

for(
    int *m = (int *)calloc(2, sizeof(int));
    m[0] <= len;
    m[1] += a[m[0]++]
);

calloc() is far less efficient than malloc(), but it zeroes out the memory it hands to us, so it fits our use case. Now, our method works (mostly), but we’ve still got problems. Let’s tackle the easier one first: getting the value out of the loop. By adding a lazy OR to our conditional, we can easily add a “cleanup” block in our loop that runs only once our main loop condition ends.

For simplicity of typing and reading, let’s also add some #defines to our header file.

/* main.h */
#define u8 uint8_t
#define u16 uint16_t
#define u32 uint32_t
#define usize uintptr_t

/* main.c */
usize sum(usize a[], usize len) {
    for(
        isize *m = calloc(2, sizeof(isize));
        m[0] < len || (len = m[1])*0;
        m[1] += a[m[0]++]
    );
    return len;
}

Yes, size_t would normally be a better alternative to uintptr_t to store the length argument. However, we need to be able to smuggle a pointer through it if we need to, thus it is a better choice in this case to simply have len always be as wide as a pointer.

Here, we use the argument len to smuggle a value out of scope, where normally we would need to spend an extra line declaring it outside of the loop in order to extract it. All we add is a lazy OR that only runs when the loop condition is false - this effectively gives us a cleanup block. We then use this block to assign our sum, contained in m[1], to our variable len, which is in the scope immediately outside ours. This lets us smuggle one value from memory into the return block, without having to disturb any outside values.

Now comes the hard part. We need to figure out how to free the memory used by m. Since free() returns void, our trick of using it in an arithmetic statement, then multiplying by zero won’t work. It may be possible to manually implement free in our cleanup statement, but that’s a bit outside the scope of this project. Thus, in the interest of brevity and functionality over a manual implementation of free, we’re just going to cheat again and call free before the return:

isize sum(isize a[], isize len) {
    for(
        isize *m = calloc(2, sizeof(isize));
        m[0] < len || (len = m[1])*0;
        m[1] += a[m[0]++]
    );
    free(m);
    return len;
}

This won’t compile, though, since m is out of scope at the point we call free().

isize sum(isize a[], isize len) {
    for(
        isize *m = calloc(2, sizeof(isize));
        m[0] < len || (len = m)*0;
        m[1] += a[m[0]++]
    );
    isize r = ((isize*)len)[1];
    free(len);
    return r;
}

This is breaking our constraints a bit more, but it’s necessary to be able to free m. All I did here was pack m into len, instead of just m[1]. Then, I unpack it when it’s in the scope we want, and call free.

In the interest of bringing it down from five to four lines, let’s move the memory declaration out of the loop, so we don’t have to pack and unpack it from len:

isize sum(isize a[], isize len) {
    isize *m = calloc(2, sizeof(isize));
    for(
        ;
        m[0] < len || (len = m[1])*0;
        m[1] += a[m[0]++]
    );
    free(m);
    return len;
}

It’s important to note that even though we stopped using it immediately after I explained it, the previous method of smuggling values out of the scope of the loop will come in handy later when we want to extract crash dumps and error codes.

Anyone with a working POC that frees memory inside the loop, shoot me an email at monty[at]kernelstack[dot]net.

The next post is going to begin to turn this concept into a turing machine, capable of executing 3BINS instructions.