bfi.py - a Brainf*ck Interpreter in Python

* NOTE: It finally works correctly XD more to come!

* NOTE: As of April 2021 this project is only a partial implementation. The [ and ] commands are partially implemented, but cannot be nested.

Brain...What?

"Brainf*ck is an esoteric programming language created in 1993 by Urban Müller." (Wikipedia)

"An esoteric programming language ... is a computer programming language designed to experiment with weird ideas, to be hard to program in, or as a joke, rather than for practical use." (esolangs.org)

A valid brainf*ck program must entirely consist of the following 8 characters: > < + - . , [ ]

Here's an example "hello world" program found on One Step! Code:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

As you might have already guessed, there's no scenario in which brainf*ck is the best solution to any real-world technical problem. Brainf*ck developer positions are somewhat rare on Indeed. The language is intentionally obtuce.

...Why?

Brainf*ck is a sort of brain-teaser - something cocky developers can use to test their elite coding skills, or to flex on their luser friends with so called "better things to do".

However... there can be practical value in hacking on the brainf*ck language. It can actually be useful in the pursuit of understanding some of the fundamental concepts of computer science. Most notably, brainf*ck is designed as a minimalist representation of a Turing Machine. It can potentially be a fun way to help conceptualize Turing Completeness, and Alan Turing's revolutionary Nazi-defeating idea for a general-purpose computing device.

So in the quest for enlightenment (and hopefully to earn some programming street cred), I decided to try my hand at writing this brainf*ck interpreter in Python.

The brainf*ck Language

As a model of a Turing Machine, standard rules apply:

The machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there. Then, as per the symbol and the machine's own present state in a "finite table" of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head), then (iii) (as determined by the observed symbol and the machine's own state in the table) either proceeds to a subsequent instruction or halts the computation. Wikipedia

In the interest of extreme minimalism, the entire brainf*ck language is expressed in only 8 ASCII characters. Each symbol performs some operation on a (theoretically) infinite 'tape' of memory divided into 1-byte cells. There is also a read/write data pointer that can be moved to any cell on the tape. A diverse range of the standard loops and if/else constructs can even be produced with various different patterns of the conditional [ and ] commands.

Commands:

 >  Moves the data pointer one cell to the right.

 <  Moves the data pointer one cell to the left.

 +  Increments a byte at the current data cell by one.

 -  Decrements a byte at the current data cell by one.

 .  Reads the byte at the current data cell to an output device.

 ,  Reads one byte from an input device and writes it to the current data cell.

 [  Reads the byte at the current data cell...
      If (byte == 0x00):
        Move the instruction pointer to the matching instance of "]"
      Else:
        Proceed to the next instruction.

 ]  Reads the byte at the current data cell...
      If (byte != 0x00):
        Move the instruction pointer *back* to one position *after* the matching "["
      Else:
        Proceed to the next instruction.

The result is a fully Turing Complete language.

Implementation

• This interpreter stores data as a Python list. Each item in the list represents one data cell in the tape. The tape begins at position 0 in the list, and extends infinitely in the positive direction (within the limits of your Python interpreter's implementation of the list data-type).

• There is an instruction pointer to keep track of the next command to be executed.

• There is also a data pointer to keep track of the cell-position of the "read/write" head of the virtual Turing Machine.

• The following commands are fully functional: > < + - . ,

• The [ and ] commands are partially functional. They should operate as expected as a single pair, but cannot currently be nested.

Roadmap:

I'm pleased with the progress I've made so far, even in its incomplete state. However I'd certainly love to pick this back up again some time, finish the logic and polish up the interface...

In the meantime, I even wrote a "hello world" brainf*ck program that does not rely on the square-bracket operators, so it will execute correctly on any bf implementation, including this one in its current form:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++<<<<<<<<<<.>.>.>.>.>.>.>.>.>.>.>.

Try it on the brainfuck Visualizer by Fatih Erikli

I vaguely remember scrapping the for-loop structure for a while-loop, which now seems like an obvious step in the right direction. I also added a nest_level variable to keep track of how many [ ] pairs deep we are in the conditional structure. With these changes it seems like the rest should practically have written itself, although that wasn't the case for me the first time around. Hopefully next time my fresh eyes will shed some new light on the problem.

License Information:

This file is part of bfi.py.

bfi.py is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

bfi.py is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with bfi.py. If not, see https://www.gnu.org/licenses/.

Additional Links:

• brainf*ck Visualizer - a fantastic brainf*ck interpreter/debugger web-app by Fatih Erikli
• EsoLang.org - BrainF*ck
• BrainFuq - an implementation that enables the use of emoji characters
• Never Forget: Alan Turing's Posthumous Pardon...