The Curious Relation of Turing Machines and BrainFry

Let's make a useless language useful by creating an interpreter yourself.
By Apan Trikha at Sun Apr 11 2021

Let's discuss with a programming language that is useless and useful at the same time. No, we aren't talking about C noobs, it's darn useful, we're talking about BrainFry, the ameliorated name for BrainFuck as the name is too profane to share links on social media like LinkedIN or on my resume. However, I'll address the name as it is. It's my personal website, I can give myself the F-word pass. For all practical reasons, this language is useless as the whole language is based on eight tokens, who in the right mind is going to use it to write production grade code?!? No one, not even the creator, Urban Müller considers it for any practical use except adding some challenge to an otherwise basic tasks on any language.

This language is what I call a meme language joining the ranks with Ook and ModiScript, which aren't intended to be used to solve a programming issue but to have fun (and no, I don't think ModiScript is disrespecting our PM).

But the biggest reason why I think BrainFuck can be useful is to understand Turing Machines. I know weird but it's a thing for 2 main reasons:

Believe it or not, but those eight tokens are sufficient to create a programming language which was the challenge Urban took to make it. In this blog post, I'll walk you through the grammar, discuss how it relates with Turing machines and give you a guide to create one yourself. The example I'll use is made using C++, you can but check the repository out here, don't worry, you can apply this knowledge using other languages. In fact, you can challenge yourself by recreating one using a different language like Go, Python, Java, etc.

In typical PixelTrik fashion, this will be a long article but I've added more visualization of inner workings through GIFs to provide the gist, feel free to skim first and then go in depth.

What are Turing Machines?

If you don't have a computer science background, allow me to introduce to our lord and our saviour, Turing machines. It's a conceptual machine from Alan Turing (the one who cracked the Enigma Code during World War II) that can read/write on an infinitely long tape using a set of rules which depends on the current state. That's the simplest definition I can come up for a Turing Machine. I want to just touch on the topic right now as the details will reveal to itself as we move on and create our interpreter.

This machine has an indefinitely long tape read by a read head (or a tape head) that recognizes the symbol and acts as prescribed by the rule set called transition table. Any system is considered to be Turing Complete if the input string can be accepted by a Turing machine using the above parts. This isn't obvious when modern computing languages are considered as they have multiple tokens that are identified as variables, operators, etc. This is were the meme languages shine.

Tokens of BrainFuck

As mentioned several times, this language comprises of 8 tokens, this is the time to get introduced.

Token Instruction
> Move data pointer to the right by a step
< Move data pointer to the left by a step
+ Increase the value stored in the data block by 1
- Decrease the value stored in the data block by 1
, Take a character from the input and store it in the data block integer
. Print the output of character stored in the data block
[ Check the data block value, if it is 0, then skip the instruction pointer to the matching ']'
] Check the data block value, if it is not 0, then jump the instruction pointer to the matching ']'

In case of any confusion, data block is the block pointed by the data pointer.

And that's about it. Believe me, that's all this language has to offer which is why it's a meme language. No fancy if-else statements, even basic arithmetic can a be a challenge on this thing. In case you're wondering what is a data pointer and what is the instruction pointer, the next section will elucidate on the matter.

Let's simplify this for ourselves

This language is true to the name, it fries the brain or to be explicit (staying with the original name), fucks the brain up! So, to simplify it, let's consider each this language to have a keyboard containing all valid symbols. This will be useful for visualization as we'll learn about each symbol to know the design.

How Turing Machines are BrainFuck are even related?

As explained Turing Machines need

BrainFuck just extends the concepts, a bit further. You have 4 tapes that are indefinitely long

Tape Type Description Head Name Operations
Code Provides all the instructions for the code Code Pointer or Instruction Pointer Read Only
Data Stores all data values and used to determine state transition too Data Pointer Read / Write
Input Different from Code Tape as it is invoked by (,) operator to store value directly to data block Stream Pointer (built-in) Read Only
Output Prints output using the data present in the data block, invoked by (.) operator Stream Pointer (built-in) Write Only

The state transition happens based on the value of data block and the symbol encountered. It'll be a bit hard for me to create a concise state machine out of this, but just because one way is hard, it doesn't mean that there aren't better ways. So, I'll use the following functions that are specified in my BrainFry interpreter which I have written in C++ 11. I have split all instructions into individual functions to study it well and modify it with less problems.

Token Function in BrainFry
> incPtr()
< decPtr()
+ incVal()
- decVal()
, getVal(inStream)
. putVal(outStream)
[ openBrac(codeTape)
] closeBrac()

Let's create our BrainFuck (or BrainFry) interpreter

With the theoretical background out of the way, now we can go straight into the development. For further simplification, I have split these 8 instructions to 4 types

Also, here are some key rules to this language too.

Data Value Operators (+ and -)

The operators + and - are what I call Data Value operators as they directly manipulate the value in the data block by incrementing or decrementing the value by 1. This means 

+++++++

Means increase the value by 7 regardless of the value stored in the data block. And similarly

---

Means decrease the value by 3. In case you're getting confused, the above GIF can help you visualise how it works using the keyboard analogy.

To achieve that, you simply need to dereference the value and then perform increment or decrement operations. Which means in C++, this means

    void incVal() {
        *dataPtr = (*dataPtr == MAX) ? MAX : *dataPtr + 1;
    }

    void decVal() {
        *dataPtr = (*dataPtr == 0) ? 0 : *dataPtr - 1;
    }

In case you're wondering how, I got MAX in the code and how it's initialized. I used the header file in C++, defined as

    MAX = std::numeric_limits<uint8_t>::max();

Easy isn't it? It sounds hard at first but with perspective, the process becomes easy.

Data Pointer Operators (> and <)

Much like Value Operators, Data pointers aren't different to implement at all, you just need to move the pointer by one step. This is a straight forward regardless of your style, whether you use an index or a pointer, they'll do the same job, move the pointer to the left or to the right by a step. Refer the GIF in case you're getting confused.

According to popular sources, the data tape is an array of 30,000 elements! Damn son, that's a lot of memory to be used to create a theoretically endless tape. Luckily, if you use dynamically allocated data structures like vectors (in C++ and Rust) or hash maps (in Python and Lua) or other ways to improve dynamic allocation like in Go, you're good to go! All you need to have some checks and now can create an infinitely long tape that is generated on demand. But what about in case of data pointer being at the beginning but the < operator is called? In that case, it won't do anything.

    // C++ Implementation
    void incPtr() {
            dataPtr++;
            if (dataPtr == dataTape.end()) {
                    dataTape.push_back(0);
                    dataPtr = dataTape.end() - 1;
                }
        }

    void decPtr() {
            if (dataPtr != dataTape.begin())
                dataPtr--;
        }

Input / Output Operators (, and .)

How can a program language be complete without a set of Input / Output operations that is defined under Von-Neumann architecture? You know which is essentially the base of Computer Architecture? Von-Neumann is often attributed as a distant German uncle of Alan Turing from whom Turing machines got its name, to know more about it, you can check it out here. It's out of scope of this blog, so I'll waste no further time.

This one is easy to explain but tricky to visualise as I built a more generic system that can go to any stream. But I'll do my best for Input. And for output.

To get the input, we need to extract a character from the input stream and then convert it into an integer and store it into our data tape. 

    void getVal(istream &inStream) {
            char input;
            inStream >> input;

            // Implicit conversion
            *dataPtr = input;
        }

Similarly, to get the output, just convert the data value to it's character counter part.

    void putVal(ostream &outStream) {
            outStream << char(*dataPtr);
        }

If you notice the explicit conversion in the latter snippet that's because in C++, the numbers can be converted into its string representation. That means 

    cout << 65 << endl;

Will generate output 65 instead of A (which is represented as 65 in the ASCII table).

Control Flow Operators ([ and ])

I'm calling this as control flow and not loop operators as these operators perform

And if the code pointer encounters right bracket and the current data block has non zero value, then jump the code pointer to the matching left bracket (])

Which means to exit a loop, the only condition is that when the right bracket is encountered, the data value must be 0.

For an example, the loop to add two numbers will be

[-<+>]

The data pointer will go to one cell to the left, increment a value and then move a cell to the right. This process will happen until the value of the cell on the right goes down to zero and the final answer will be in the left cell.

Exercise

To understand it better, try imagining two numbers on two consecutive cells and perform the loop above using the rules of the language you've understood so far. Not only this will give you better insight on the language but you'll be involved in the process to see the first hand how the language works in theory.

Balancing the brackets

It is all fun and games until you confront the art of balancing the brackets. This is so simple yet jarring that this is frequently asked in interview questions, how do I know that? Every single competitive programming site has at least 2 variations of this questions. There you go with the third one, this time we'll make it mildly useful as by stacks we can track the position we need to jump if the data value isn't 0.

This is where I'll reveal the implementation too as I used stack to keep track of positions where the code pointer must jump to.

When the left bracket is encountered by the code pointer and the value in current data block is 0, then it'll skip by iterating to the code strip and performs the following

Bracket Operation on stack
[ Push the location in the code tape to the stack
] Take the top and pop from the stack, if the top location is same as the one before starting this traversal, then stop.

And when the right bracket is encountered by the code pointer, it'll move to the location stored as the top of the stack as it represents the inner most bracket that needs to be balanced first. If the value in the data block is zero, then just pop from the stack.

To simplify it further, you can imagine

Bracket Operation on the stack (Simplified)
[ Push
] Pop

Which means the implementation will be when code pointer encounters left bracket.

    void openBrac(const string &codeTape) {
        codeStack.push(codePtr);
        
        if (*dataPtr == 0) {
            auto startPtr = codePtr;
            while(++codePtr != codeTape.end()) {
                if (*codePtr == '[')
                    codeStack.push(codePtr);
                if (*codePtr == ']') {

                    if (codeStack.empty())
                        throw runtime_error("Found a ']' that did not have a matching '['!");
                    auto tmpPtr = codeStack.top();
                    codeStack.pop();

                    if (tmpPtr == startPtr)
                        break;
                }
            }
        }
    }

And when code pointer encounters right bracket.

    void closeBrac() {
        if (codeStack.empty())
            throw runtime_error("Found a ']' that did not have a matching '['!");
        if (*dataPtr != 0)
            codePtr = codeStack.top();
        else
            codeStack.pop();
    }

Conclusion

If you've made it this far, congratulations! You've gone through a long article I sometimes call a blog. In case you're one of my potential employers, keep in mind, the F-word is used exclusively to use the intended name of the language and not to hurl insults. In case you're a university student, take this as an inspiration and challenge yourself with it but study the theory of computation before you implement. That'll provide you a better insight on what has been discussed.

2022 (C) Apan Trikha | Games | YouTube | Social