Jump to content

BrainF*ck Interpreter and Language


WarFox
 Share

Recommended Posts

Introduction

BrainF*ck, for the rest of the article I will refer to as BF, is a language that came on the scene as an extremely complex esoteric language that was developed. It's syntax read as a series of symbols ([,],+,-,.,,) that comprised of the language. Most people who have seen the Hello World program written in BF were amazed at how odd it looked comparison to other languages and probably assumed it was extremely difficult to program in. However, I found it to be something different. BF is an extremely small language that can still be useful to a degree. It demonstrates a basic definition of what something means to be either a compiler or interpreter and how it does not have to have serve complexities. As I dive into the basic of the language, you will see why if you are already not familiar with it. Also, I have taken up during this winter break. a mild fascination with interpreters and compiler. I began working on my own esoteric language, SouthParkLang, that is posted about in another board on this forum. While starting my own, I looked at examples of languages and what it means to be an interpreter or a compiler and I found an excellent example with BF. Here is where I make a strong recommendation, if you are interested in how compilers and interpreters work, take some working with BF. In fact, craft your own compiler/interpreter for this language as it will give a basic outline of what a language must be able to handle.

Tool used (and my own implementation)

As a learning experience, I crafted my own interpreter implemented in Java. The source code can be found here. The advantaged of using my implementation of a BF interpreter is that it will output after each execution of an operation, also, I have condensed down the size of the array that the program is executed in. The "Standard" array size of a BF array is 30,000 integers, however I chopped it down to about 20 integers for this tutorial. By editing the MAX_SIZE variable in the ArrayField.java file, the size can be changed. I would also recommend commenting out line 36 in Interpreter.java if you choose to go with a larger array size so that the output is not printed.

Basics of the language

The language is a really simple language that only comprises of a few symbols. The program works within an array of integers, essentially think of it as the program memory. Each "function" or operation preforms an action on a index within the array.

Quote

+  [Increment value at index]

-  [Decrement value at index]

> [Shift index right]

< [Shift index left]

. [Output value at index]

, [Input value at index from user input]

[ [Start loop]

] [End loop if the current index in array has a value of zero]

These handful of symbol above compose the language. A few things to note, When outputing an inputing a value, there are conversions to and from ASCII value.

Here is a simple program and its output (remember, usually the whole array is not printed, but is in this article for demonstration of what is happening during execution):

Quote

>>   ++>++>++<-<-
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Starting at the 0 index, ad two, shift right, increment twice, shift right, increment twice, shift left, decrement once, shift left decrement once. End of program.

If you have taken a course in discrete math or have self studied any kind of number theory, this language can get pretty interesting. Before I saw how, I want to demonstrate input and output.

Spoiler

>> ,.
a
97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a
97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The command allows the user to input a value, here I input a (lowercase is significant). This stored the ASCII value of 97. By then executing a '.', 97 is converted from ASCII into its alpha-numerical representation of a.

Number theory and various topics in discrete math get interesting here. After all, if you wanted to write a program that stored 'a' without user input, prime factorization and reversing the division algorithm can come in handy with a loop. Or to produce a string, such as a "Hello World," nesting loops within loops to keep from incrementing each closes dozens and dozens of times by hand. This is an example of a loop to print 'a,' by using a single loop that is roughly 28 characters in length as opposed to increment one index 97 times.

Spoiler

>> ++++++++++++>+<[>++++++++<-]>.
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 35 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 38 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 39 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 43 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 44 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 46 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 47 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 48 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 52 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 53 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 54 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 55 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 56 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 58 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 59 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 61 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 62 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 66 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 71 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 72 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 73 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 74 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 76 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 77 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 78 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 79 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 81 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 82 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 83 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 84 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 85 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 86 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 87 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 88 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 89 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 89 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 89 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 89 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 89 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 91 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 92 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 93 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 94 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 95 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 96 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a
0 97 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Using a division algorithm, 97 can be divided by 8, 12 times and have a remainder of 1. So, set 12 for the amount of time to execute the loop, in the next index, increment once for the remainder. Then enter the loop, increment the 2nd index 8 times, 12 times.

Spoiler

97 = 8(12) + 1

Conclusion

BF is a really simple and elegant language, although it takes some time ton construct loops in order to something useful. It is an excellent language to learn for someone who wants to get into the mathematics of computation. Most of all, it is a great learning experience for all programmers to try to implement their own interpreter.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...