<< Home | About Forth | About TurboForth | Download | Language Reference | Resources | Tutorials | YouTube >>

A Brainfuck Compiler in Forth

Why do people climb mountains? Because they're there. Why do people write Brainf**k programs? I have absolutely no idea!

People say Forth is hard. I suppose it is hard at the beginning, but it gets easier, just like learning any other language, such as French or German, or English. It takes time. BrainFuck is just plain evil. Like Cantonese.

It has only eight commands, they are:

That's it. No variables. No subroutines. No way to load constants. Purely evil. Yet people write programs with it, presumably, for the same reasons as people climb mountains.

The Brainf**k Virtual Machine

The BF system works on a byte-based memory array. A single pointer points to a byte. The pointer is moved left and right with < and >. The contents of a byte within the array may be incremented and decremented with + and - respectively. The instruction . (dot) reads the current array element and outputs it as an ASCII character. The instruction , (comma) waits for a single key press, and places its ASCII value in the current array position. For looping, the [ command will continue if the current array position >0, otherwise, it jumps over it to the associated ].

That's it. You just learned Brainf**k.

Awful, isn't it?

The Brainf**k Compiler

I knocked together a simple compiler for BF programs in Forth in about 20 minutes. It was quite cool I suppose. It was quite slow, though, and one of the C.L.F regulars suggested ways in which the BF leant itself to optimisation. Well, I just had to, didn't I? And the following monster was born.

Source Code

Here's the source code:

Using the Compiler

The easiest way is to use the Classic99 emulator, which comes with TurboForth built in, ready to run. Start TurboForth from the cartridge menu, and hold down ENTER as it starts, to bypass auto-booting from DSK1.BLOCKS.

When the cursor appears, copy the above source code direct from the web page (click the mouse in the text box, then press CTRL A to select all text, then copy it (CTRL C on most systems)). Now paste the code directly into classic99, using the Edit menu in classic99. The source code will be pasted in and compiled, as if it was being entered from the keyboard.

Now you can run the programs below. The BF compiler reads text files and converts the BF code it finds in the files to Forth. So, paste these demo's into text files (one file for each program) and save them in DSK1 folder of classic99. For example, if you saved a text file in the DSK1 folder with the name BF-DEMO.TXT then you need to type the following at the TurboForth cursor:


The compiler will then read in and compile the file. When it's done, just type RUN and press enter. When the program finishes, type ERASE-BF to remove the compiled Brainf**k program from memory. You can then compile another Brainf**k program.

The Optimisation

The coolness comes in the form of the optimisations that are made as the code is compiled. They are quite simple to implement, but result in much faster code:

The last optimisation is worthy of further elucidation: The sequence [-] is used to decrement the value at the pointer to 0. It's the only way to do it. Obviously, this can be quite slow, since it's done in a loop, so if the byte in question has the value 255 then the loop has to execute 255 times, just to set a byte to zero! Clearly this is very slow, the compiler looks for this sequence, and upon seeing it replaces the code just generated into a call to the Forth word BF~ which zeros the cell with no loop necessary.

The other optimisations above are achieved by the compiler 'remembering' the type of instruction that it is currently compiling, and maintaining a counter for the number of consecutive same instructions that it has seen. When it sees a different instruction come through, then it issues the previous instruction, and begins "remembering" (i.e. counting) the next one.



The compiler sees + and so issues (compiles) any outstanding instructions and sets it's counter to 1 (bfOpCount in the source code below). Then it sees another + so it simply increments the counter again. It sees a third + so increments the counter again. Same for the 4th +. Next, it sees < so it issues a LIT $ BF+ sequence, zero's the count, and begins counting the number of < instructions. As soon as a different instruction arrives, it issues the code. Simple.

Limitations/Deviations from the "Standard"

The main deviation from the standard is that Brainf**k programs are supposed to have a 30,000 byte array to work in. That's too big for the TI-99/4A. The 4A only has 32K of RAM! Consequently, the entire 8K low region of the 32K memory expansion (>2000 to >4000) is used for the array, and the 24K (>A000 to >FFFF) is used for the compiler itself, and hosting the compiled the Brainf**k program.

Example BrainF**k Programs

Just paste these files into the editor in Editor/Assembler (using the Classic99 emulator) and save them in DV80 format. The BrainF**k compiler will then load and compile them for you, and you can just type RUN to execute them.

Hello World!

A programming language is not a programming language without a Hello World! program. Here's one for BrainF**k (source xxxx)

Fibonacci Sequence

The following program generates a Fibonacci sequence up to 100. Source: http://esoteric.sange.fi/brainfuck/bf-source/prog/fibonacci.txt

99 Bottles of Beer...

You know how the song goes! Source: http://esoteric.sange.fi/brainfuck/bf-source/prog/99botles.bf


This program counts from 9 down to 0:

Okay, I don't know about you, but my brain is most suitably f***ed! Enough BrainF***ing, and back to proper Forth programming!

6th May 2014

<< Home | About Forth | About TurboForth | Download | Language Reference | Resources | Tutorials | YouTube >>