BAL - Designed for hardware

Minor profanity warning! This article frequently mentions the programming language brainf**ck. Reader discretion is advised.

Brainfuck is one of the most popular esolangs and my personal favorite by far, but it was not designed with hardware implementation in mind. Its compilers can get as small as a couple hundred bytes, but it's highly ineffective to implement on modern chips. Let's see how to fix that.

Why?

For fun!

The goal for this series is to create a custom BPU (Brainfuck Processing Unit) microchip designed from scratch. In order to do this I need a version of brainfuck to serve as machine language for it. I hope to learn chip (and language) design in a fun and weird way.

Why not pure brainfuck?

It's already perfect after all...

At first glance brainfuck with its minimalism and a round number of commands (eight) seems easy to implement on hardware, but there are two major difficulties: jumps and command storage, which make it a nightmare to design a chip running pure brainfuck.

The problem with jumps is finding matching brackets to jump to. Saving addresses of jump targets makes it impossible to let the code modify itself (which I am a great fan of), and seeking the matching brackets every jump takes additional clock cycles wasting a lot of time on long jumps and potentially falling into an endless loop when the program is invalid (brackets don't match).

The problem with command storage is that each command takes at least 3 bits (8 different values) and there are a lot of them in each program. Using only 3 bits of each machine word wastes more than half of the word when using 8-bit words and gets worse when using bigger architectures leading to a lot of storage space wasted on just code.

Solving the storage problem

Two bad ideas and a good one

My first idea was to put two 3-bit brainfuck commands in each byte, thus wasting only a quarter of all bits. Sounds reasonable at first glance, after all it doubles the memory efficiency. This silution still wastes every fourth bit though and requires designing hardware that can split the read byte in two and evaluate the halves separately. That would be too much of a hassle for my fun-oriented brain.

Another approach would be to store each command as a one-hot byte, meaning only one bit would be 1 and the others would be 0. The main advantage of such approach is how easy it is to design a microprocessor that uses one-hot commands - you just hook each behaviour to each bit and call it a day, but it is very bad in terms of memory efficiency - it uses 8 bits to distinguish between 8 values. There is no room for clever optimisations that usually accompany one-hot encoding like running two commands in parallel.

What I settled for in the end required modifying the base brainfuck by letting each command take an argument. When compiling the command would take up top three bits of the machine word (whatever size it would be) leaving the rest for the argument. This approach is infinitely scalable, uses the memory (almost) optimally, fixes the jump problem and because of the way it uses the arguments it allows to merge several commands into one with a bigger argument making programs take up less space!

What do arguments do?

Wait, that's no brainfuck!

Arguments are pretty obvious with half of brainfuck's commands. +, -, > and < are usually repeated many times in a row, so the argument compresses a number of commands into one. For example:

• ++++++ in pure brainfuck is +6 in BAL
• --------- in pure brainfuck is -9 in BAL
• >> in pure brainfuck is >2 in BAL
• <<<<< in pure brainfuck would be <5 in BAL

You can already see how smaller will the BAL code be compared to vanilla brainfuck.

Jump commands are a little less straightforward as they can't just be repeated, instead the argument specifies how far should the program pointer jump when the condition is met, for example:

• [14 - if the cell is 0 jump forward 14 commands
• ]9 - if the cell is not 0 jump back 9 commands

It is a big change from brainfuck where brackets had to be matched and would only allow jumps to a matching bracket. BAL not only lets you use unmatched brackets but also allows jumping over brackets which opens a world of possibilities regarding control structures.

Arguments for input/output commands , and . were the hardest to give meaning to, so I sort of didn't. My imagined BPU would use the commands to interact with other devices such as a keyboard or a GPU, so their arguments can be used to specify which device to interact with and what the sent data means, it would be broadcasted for the other devices to interpret. Which codes correspond with what behaviour of which devices is left for the person implementing the BPU.

How to compile BAL?

It's supposed to be machine code

As mentioned earlier each full BAL command consists of two parts: a 3-bit brainfuck command and an argument. Brainfuck commands are compiled using this table:

You can see that pairs of similar commands like + and - or [ and ] only differ by the least significant bit. This will simplify the design of the final BPU.

The rest of the machine word is supposed to be filled with the command's argument, but there is room for one more optimisation. Note that +0, -0, >0 and <0 do nothing, and [0 and ]0 can cause an infinite loop. To get rid of these and gain a bit more power I decided that the rest of the machine word is supposed to be filled with the argument minus one except for . and , commands. For example when compiling for an 8-bit BPU:

• +6 compiles to 000 00101
• <20 compiles to 011 10011
• [31 compiles to 100 11110
• . compiles to 111 00000 (an implicit argument of 0)
• + compiles to 000 00000 (an implicit argument of 1)

Additionally any literal number not connected to a command should be compiled to itself to allow for easy data initialisation.

Conclusion

That's all, folks!

And so we have a complete brainfuck based machine language, just initialise you program and data pointers to 0 and you're good to go. If you didn't get something or you want more details head to the BAL esolangs.org page. The only implementation of BAL that I know of is my BAL fantasy console written in PICO-8.